N-Queens Problem
In this page:
Problem Idea
N-Queens asks you to place n chess queens on an n-by-n board so that no two queens can attack each other — meaning no two share a row, column, or diagonal. It's a canonical backtracking problem because the constraints make most placements fail quickly, which is exactly where pruning pays off.
Example: 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;
}Login to try C/C++/Java code in the editor
Safe Position
A position is safe for a new queen only if no existing queen already occupies its column, and no existing queen sits on either diagonal through that square. Checking these three conditions is what determines whether a placement is even worth exploring further.
Example: 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;
}Login to try C/C++/Java code in the editor
Backtracking Search
Because no two queens can ever share a row, you can place exactly one queen per row and move to the next row only when the current placement is safe. If every column in a row leads to a dead end, backtrack to the previous row and try its next available column.
Example: 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;
}Login to try C/C++/Java code in the editor
Board Representation
A common way to represent the board is a simple array where the index is the row and the value is the column holding that row's queen — this avoids storing a full 2D grid and makes safety checks (column and diagonal comparisons) fast arithmetic instead of grid lookups.
Example: 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;
}Login to try C/C++/Java code in the editor
Practice
N-Queens is a favorite because it demonstrates the full backtracking pattern cleanly: constrained choices, an easy safety check, and enough failed branches that pruning visibly transforms an otherwise-exponential search into something tractable for reasonable board sizes.
Example: 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;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 7 topics to unlock
0/7 topics done
Complete these topics first: