← Back to DSA Course | Chapter 8: Recursion & Backtracking | Lesson 5 of 7

N-Queens समस्या

N-Queens chess queens को एक board पर इस तरह रखने जैसा है कि उनमें से कोई भी एक-दूसरे को capture न कर सके, जब भी एक placement trouble का कारण बने वापस backing up करते हुए।

In this page:

  1. Problem Idea
  2. Safe Position
  3. Backtracking Search
  4. Board Representation
  5. Practice
Syntax
markup 
def solve(row):
    if row == n:
        record(board)
        return
    for col in range(n):
        if is_safe(row, col):
            board[row] = col
            solve(row + 1)
            board[row] = -1    # backtrack

Problem Idea

N-Queens आपसे n chess queens को एक n-by-n board पर इस तरह रखने को कहता है कि कोई दो queens एक-दूसरे को attack न कर सकें — मतलब कोई दो एक row, column, या diagonal share न करें। यह एक canonical backtracking problem है क्योंकि constraints ज़्यादातर placements को जल्दी fail करा देते हैं, जो बिल्कुल वहां है जहां pruning फायदा देता है।

उदाहरण: Problem Idea

#include <iostream>
using namespace std;
int main() {
	int n = 4;
	cout << "Place " << n << " queens on a " << n << "x" << n << " board, none attacking another";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int n = 4;
		System.out.println("Place " + n + " queens on a " + n + "x" + n + " board, none attacking another");
	}
}
n = 4
print("Place", n, "queens on a", n, "x", n, "board, none attacking another")
#include <stdio.h>
int main() {
	int n = 4;
	printf("Place %d queens on a %dx%d board, none attacking another", n, n, n);
	return 0;
}

Safe Position

एक position एक नई queen के लिए सिर्फ तब safe है जब कोई मौजूदा queen पहले से इसका column occupy न करे, और कोई मौजूदा queen उस square के through दोनों diagonals में से किसी पर न बैठी हो। इन तीन conditions को जांचना यह determine करता है कि एक placement आगे explore करने लायक भी है या नहीं।

उदाहरण: Safe Position

#include <iostream>
using namespace std;
bool isSafe(int cols[], int row, int col) {
	for (int r = 0; r < row; r++)
		if (cols[r] == col || abs(cols[r] - col) == row - r) return false;
	return true;
}
int main() {
	int cols[] = {1, 3};
	cout << (isSafe(cols, 2, 0) ? "Safe" : "Not safe");
	return 0;
}
public class Main {
	static boolean isSafe(int[] cols, int row, int col) {
		for (int r = 0; r < row; r++)
			if (cols[r] == col || Math.abs(cols[r] - col) == row - r) return false;
		return true;
	}
	public static void main(String[] args) {
		int[] cols = {1, 3};
		System.out.println(isSafe(cols, 2, 0) ? "Safe" : "Not safe");
	}
}
def is_safe(cols, row, col):
    for r in range(row):
        if cols[r] == col or abs(cols[r] - col) == row - r:
            return False
    return True

cols = [1, 3]
print("Safe" if is_safe(cols, 2, 0) else "Not safe")
#include <stdio.h>
#include <stdlib.h>
int isSafe(int cols[], int row, int col) {
	for (int r = 0; r < row; r++)
		if (cols[r] == col || abs(cols[r] - col) == row - r) return 0;
	return 1;
}
int main() {
	int cols[] = {1, 3};
	printf(isSafe(cols, 2, 0) ? "Safe" : "Not safe");
	return 0;
}

Backtracking Search

चूंकि कोई दो queens कभी एक row share नहीं कर सकतीं, आप per row बिल्कुल एक queen रख सकते हैं और सिर्फ तब अगली row पर move कर सकते हैं जब current placement safe हो। अगर किसी row में हर column एक dead end की ओर ले जाए, पिछली row पर backtrack करें और इसका अगला available column try करें।

उदाहरण: Backtracking Search

#include <iostream>
using namespace std;
int n = 4, count = 0;
int cols[10];
bool isSafe(int row, int col) {
	for (int r = 0; r < row; r++)
		if (cols[r] == col || abs(cols[r] - col) == row - r) return false;
	return true;
}
void solve(int row) {
	if (row == n) { count++; return; }
	for (int col = 0; col < n; col++)
		if (isSafe(row, col)) { cols[row] = col; solve(row + 1); }
}
int main() {
	solve(0);
	cout << "Solutions: " << count;
	return 0;
}
public class Main {
	static int n = 4, count = 0;
	static int[] cols = new int[10];
	static boolean isSafe(int row, int col) {
		for (int r = 0; r < row; r++)
			if (cols[r] == col || Math.abs(cols[r] - col) == row - r) return false;
		return true;
	}
	static void solve(int row) {
		if (row == n) { count++; return; }
		for (int col = 0; col < n; col++)
			if (isSafe(row, col)) { cols[row] = col; solve(row + 1); }
	}
	public static void main(String[] args) {
		solve(0);
		System.out.println("Solutions: " + count);
	}
}
n = 4
count = 0
cols = [0] * n
def is_safe(row, col):
    for r in range(row):
        if cols[r] == col or abs(cols[r] - col) == row - r:
            return False
    return True

def solve(row):
    global count
    if row == n:
        count += 1
        return
    for col in range(n):
        if is_safe(row, col):
            cols[row] = col
            solve(row + 1)

solve(0)
print("Solutions:", count)
#include <stdio.h>
#include <stdlib.h>
int n = 4, count = 0, cols[10];
int isSafe(int row, int col) {
	for (int r = 0; r < row; r++)
		if (cols[r] == col || abs(cols[r] - col) == row - r) return 0;
	return 1;
}
void solve(int row) {
	if (row == n) { count++; return; }
	for (int col = 0; col < n; col++)
		if (isSafe(row, col)) { cols[row] = col; solve(row + 1); }
}
int main() {
	solve(0);
	printf("Solutions: %d", count);
	return 0;
}

Board Representation

Board represent करने का एक आम तरीका एक simple array है जहां index row है और value इस row की queen रखने वाला column है — यह एक पूरी 2D grid store करने से बचता है और safety checks (column और diagonal comparisons) को grid lookups के बजाय fast arithmetic बनाता है।

उदाहरण: Board Representation

#include <iostream>
using namespace std;
int main() {
	int cols[4] = {1, 3, 0, 2};
	for (int row = 0; row < 4; row++) cout << "Row " << row << " -> Col " << cols[row] << endl;
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] cols = {1, 3, 0, 2};
		for (int row = 0; row < 4; row++) System.out.println("Row " + row + " -> Col " + cols[row]);
	}
}
cols = [1, 3, 0, 2]
for row in range(4):
    print("Row", row, "-> Col", cols[row])
#include <stdio.h>
int main() {
	int cols[4] = {1, 3, 0, 2};
	for (int row = 0; row < 4; row++) printf("Row %d -> Col %d\n", row, cols[row]);
	return 0;
}

Practice

N-Queens एक favorite है क्योंकि यह पूरे backtracking pattern को साफ़ तरीके से demonstrate करता है: constrained choices, एक easy safety check, और इतने failed branches कि pruning visibly एक अन्यथा-exponential search को reasonable board sizes के लिए tractable किसी चीज़ में बदल देती है।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	int solutions[] = {1, 0, 0, 2, 10};
	cout << "4-Queens has " << solutions[3] << " solutions";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] solutions = {1, 0, 0, 2, 10};
		System.out.println("4-Queens has " + solutions[3] + " solutions");
	}
}
solutions = [1, 0, 0, 2, 10]
print("4-Queens has", solutions[3], "solutions")
#include <stdio.h>
int main() {
	int solutions[] = {1, 0, 0, 2, 10};
	printf("4-Queens has %d solutions", solutions[3]);
	return 0;
}
Related Topics

Two Sum समस्या · Coin Change समस्या · Activity Selection समस्या · Backtracking परिचय

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. सिर्फ columns जांचना और diagonals भूल जाना, जहां दो queens एक diagonal share करती हैं अगर abs(r1 - r2) == abs(c1 - c2)।
  2. Backtracking करते समय queen position reset न करना, इसलिए पुरानी placements बाद वाली को प्रभावित करती हैं।
  3. हर queen के लिए per row एक queen के बजाय सभी rows try करना, जो कहीं ज़्यादा धीमा है।
🔒

Chapter Quiz — Complete all 7 topics to unlock

0/7 topics done

Complete these topics first:

← Previous Lesson Backtracking Introduction Next Lesson → Sudoku Solver

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.