N-Queens (LeetCode 51)
N-Queens is the classic backtracking problem. You get an n × n chessboard and have to place n queens on it so that no two queens attack each other. A queen attacks anything in its row, its column, or either of its diagonals. The goal is to return every board that works, with each row written as a string: 'Q' for a queen and '.' for an empty square.
For n = 4 there are exactly two boards that work:
. Q . . . . Q .
. . . Q Q . . .
Q . . . . . . Q
. . Q . . Q . .
For n = 8, the classic chessboard, there are 92.
The idea
Every row needs exactly one queen (two queens in the same row would attack each other), so I go row by row. In the current row, I try each column. If a queen there is safe from every queen I’ve already placed, I put it down and move on to the next row. If I get through all n rows, that’s a full board, and I save it.
The backtracking part is what happens after a recursive call comes back: I pick the queen back up and try the next column. Place, recurse, undo. That’s the whole pattern, and it’s how the search eventually tries every possibility without ever building a board that’s already broken.
The code
class Solution {
public List<List<String>> solveNQueens(int n) {
//int n dictates the number of columns and rows our board will contain
List<List<String>> result = new ArrayList<>();
List<String> partialBoard = new ArrayList<>();
queensHelper(n, 0, partialBoard, result);
return result;
}
public void queensHelper(int totalRequiredQueens, int currentNumQueens, List<String> partialBoard, List<List<String>> result) {
if (totalRequiredQueens == currentNumQueens) {
//add a copy, since partialBoard keeps changing as we backtrack
result.add(new ArrayList<>(partialBoard));
return;
}
for (int col = 0; col < totalRequiredQueens; col++) {
if (validQueenPosition(currentNumQueens, col, partialBoard, totalRequiredQueens)) {
String currentRow = fillInRow(col, totalRequiredQueens);
partialBoard.add(currentRow);
queensHelper(totalRequiredQueens, currentNumQueens + 1, partialBoard, result);
partialBoard.remove(partialBoard.size() - 1);
}
}
}
public String fillInRow(int col, int N) {
StringBuilder currentRow = new StringBuilder();
for (int c = 0; c < N; c++) {
if (c == col) {
currentRow.append('Q');
} else {
currentRow.append('.');
}
}
return currentRow.toString();
}
public boolean validQueenPosition(int currRow, int currCol, List<String> partialBoard, int totalRequiredQueens) {
//we will iterate through the elements above me, left-diagonal, and right-diagonals
//Check: the rows directly above me, keeping col constant
//not row <= currRow!! Because, i haven't added this row to my currBoard just yet! So we must exclude it!
for (int row = 0; row < currRow; row++) {
if (partialBoard.get(row).charAt(currCol) == 'Q') {
return false;
}
}
//Check: the left-diagonal row above me, and then keep in that direction
for (int col = currCol - 1, row = currRow - 1; col >= 0 && row >= 0; col--, row--) {
if (partialBoard.get(row).charAt(col) == 'Q') {
return false;
}
}
//Check: the right-diagonal row above me, and then keep in that direction
for (int col = currCol + 1, row = currRow - 1; col < totalRequiredQueens && row >= 0; col++, row--) {
if (partialBoard.get(row).charAt(col) == 'Q') {
return false;
}
}
//If i've reached this line, that means I can place a queen at [currRow][currCol] of the partialBoard
return true;
}
}
currentNumQueens pulls double duty here: it’s how many queens I’ve placed so far, and it’s also the row I’m working on, since I place exactly one queen per row.
Checking a square
Since I fill the board from the top down, every queen already on the board is above the square I’m checking. So validQueenPosition only ever looks up, in three directions:
- Straight up, the same column in every row above me.
- Up and to the left, one diagonal step at a time until I fall off the board.
- Up and to the right, same thing in the other direction.
I don’t have to check the row itself, because nothing has been placed in it yet. That’s what my comment on the first loop is about: it’s row < currRow, not row <= currRow, since the current row isn’t on partialBoard until after the check passes. And I never have to look down, because nothing is down there yet.
The undo step
partialBoard.add(currentRow);
queensHelper(totalRequiredQueens, currentNumQueens + 1, partialBoard, result);
partialBoard.remove(partialBoard.size() - 1);
These three lines are the heart of backtracking. Add the row, explore everything that can come after it, then remove it so the board is exactly how it was before. Then the loop moves on to the next column like nothing happened.
This is the opposite of what I do in Number of Islands, where a cell stays marked forever. There, a cell’s island never changes, so there’s nothing to undo. Here, a queen in row 2, column 1 is right for some boards and wrong for others, so every choice has to be taken back once I’m done exploring it.
One thing that tripped me up: when I hit a full board, I add new ArrayList<>(partialBoard), not partialBoard itself. My original comment on that line was:
//not sure how to append List<String> to a List<List<String>>....
The copy is the answer. partialBoard is the one list I keep adding to and removing from the whole time. If I saved it directly, every saved “board” would point at that same list, and by the end of the search it’s empty again. Copying freezes the board the way it looked at that moment.
Runtime
Row 0 has n columns to try. Since every queen takes up a column, row 1 has at most n - 1 columns left that could work, row 2 has at most n - 2, and so on. So the search places at most around partial boards. At each one, I try n columns, and each check walks up to squares, which gives a loose upper bound of . In practice the diagonal checks cut off way more branches than that, which is the whole point of backtracking: a broken board gets thrown out the moment it breaks, instead of after it’s filled in.
For space, the recursion goes n calls deep, and partialBoard holds up to n strings of length n, so that’s , not counting the boards I return.