N-Queens Problem in Java
Problem
The N-Queens problem asks how many ways n chess queens can be placed on an n by n board so that no two share a row, column, or diagonal — a placement that fails partway through has to be undone and retried, which is exactly what backtracking is for.
Given a board size n, count how many distinct arrangements place n queens so that none of them attack each other.
Java Program
public class NQueensProblem {
static int count = 0;
static boolean isSafe(int[] cols, int row, int col) {
for (int r = 0; r < row; r++) {
int c = cols[r];
if (c == col || Math.abs(c - col) == Math.abs(r - row)) return false;
}
return true;
}
static void solve(int[] cols, int row, int n) {
if (row == n) {
count++;
return;
}
for (int col = 0; col < n; col++) {
if (isSafe(cols, row, col)) {
cols[row] = col;
solve(cols, row + 1, n);
// no explicit unmark needed — cols[row] is overwritten before being read again
}
}
}
public static void main(String[] args) {
int n = 4;
solve(new int[n], 0, n);
System.out.println("Total solutions for 4-Queens: " + count);
}
}Output
Core Logic
Placing one queen per row, checking every earlier queen for a conflict before committing, and moving to the next column when a placement fails, explores every arrangement without ever revisiting a doomed board state twice.
- 1
cols[row]records which column the queen in that row was placed in — since exactly one queen goes in each row, this single array fully describes a partial board. - 2
isSafe(cols, row, col)checks every already-placed queen for a same-column conflict or a same-diagonal conflict (where the row and column distances match). - 3
solve(cols, row, n)tries every column in the current row; whenever one is safe, it commits that column and recurses into the next row. - 4Reaching
row == nmeans every row got a safe queen, so a full valid arrangement was found and the solution counter increments — there's no need to undocols[row]explicitly, since the next column tried in that row simply overwrites it.
Key Point: Checking isSafe before committing each queen is what prunes the search — a conflicting placement is rejected immediately rather than being allowed to recurse several rows deeper before failing.
Why: In the worst case the search tries close to n! column orderings before the constraint checks rule most of them out early, while the recursion depth — and the cols array — only ever holds n entries; the true number of checks performed is far smaller in practice since a conflict is caught long before a row is fully explored.