N-Queens Backtracking Java | Fresher Interview
Fast recall
Quick revision
Core answer
row - col and row + col.Whether you structure it row-by-row and check column + both diagonals efficiently
Checking only columns (missing diagonals), or doing O(n) scans per placement instead of O(1) sets
Use row-col and row+col to index diagonals and place one queen per row to cut the search space
Interview-ready guide
Interview answer
N-Queens is the canonical backtracking problem.
I have to place n queens on an n by n board so that no two attack each other, meaning no two share a row, a column, or a diagonal. The first simplification, which is really important, is that I place exactly one queen per row. That immediately removes all row conflicts and means that for each row I only have to choose a column, which dramatically cuts the search space.
So I go row by row. For the current row, I try each column, and a column is safe if no previously placed queen is in that same column or on either of the two diagonals through that square. The clever part is identifying the diagonals cheaply.
For one diagonal family, the value row minus column is constant along it, and for the other family, row plus column is constant. So I keep three boolean arrays: one for columns, one for the row-minus-column diagonals, and one for the row-plus-column diagonals. That lets me check whether a square is under attack in O of one instead of scanning the whole board each time.
When I find a safe column, I mark all three flags, that's the choose step, recurse to the next row to explore, and then when the recursion returns I clear those flags, the un-choose step. When I successfully place a queen in every row, I've found a valid arrangement. One small implementation detail: row minus column can be negative, so I offset it by n when indexing the array.
Checking only columns and forgetting the diagonals is the classic mistake here.
N-Queens Backtracking Java | Fresher Interview
Direct Answer
Place queens one row at a time. For each row, try each column; a column is valid if no queen shares its column or either diagonal. If valid, place the queen and recurse to the next row; on return, remove it (backtrack). Track attacked columns and diagonals with boolean sets for O(1) checks. Diagonals are identified by row - col and row + col.
Deep Dive & Architecture
Placing exactly one queen in each row removes row conflicts automatically. A recursive level therefore means “choose a safe column for this row.” Three lookup sets are enough to test the other attacks: column, row - column, and row + column.
Cells on the same descending diagonal share row - column; cells on the same ascending diagonal share row + column. Because row - column can be negative, an array implementation adds an offset such as n before using it as an index.
One 4 × 4 solution
The column choices [1, 3, 0, 2] mean queens at (0,1), (1,3), (2,0), and (3,2). Every column is different. Their row - column values are -1, -2, 2, 1, and their row + column values are 1, 4, 2, 5, so no diagonal id repeats.
If a later row has no safe column, remove the previous queen and clear its three markers before trying the next column. Reaching row n means one complete board has been found. The worst-case search is roughly O(n!), while the board path and conflict sets use O(n) additional state.
Code Example
int count = 0;
void solve(int r, int n, boolean[] col, boolean[] diag1, boolean[] diag2) {
if (r == n) { count++; return; } // all rows placed
for (int c = 0; c < n; c++) {
int d1 = r - c + n, d2 = r + c; // diagonal ids (offset)
if (col[c] || diag1[d1] || diag2[d2]) continue; // PRUNE conflicts
col[c] = diag1[d1] = diag2[d2] = true; // choose
solve(r + 1, n, col, diag1, diag2); // explore
col[c] = diag1[d1] = diag2[d2] = false; // un-choose
}
}
// One queen per row + O(1) checks; diagonals via r-c and r+c.
Common Mistakes & Pitfalls
- Only checking columns: you must also block both diagonals (
r-c,r+c). - O(n) safety scan: scanning the board each placement is slow; use boolean sets for O(1).
- Negative diagonal index:
r - ccan be negative - offset bynfor array indexing. - Forgetting to un-mark: clear the column/diagonal flags after recursion.
Check your understanding
Answer these without looking back at the article.
- What is backtracking and how does it differ from regular recursion?
- How do you generate all subsets of a set using backtracking?
- How do you find all combinations that sum to a target?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.