LeetCode 51 N Queens asks you to place n queens on an n x n chessboard so that no two queens attack each other. That means you cannot share a row, a column, or a diagonal. The output is every valid arrangement, formatted as rows of . and Q, so the work is not about finding one placement and stopping, it is about enumerating all placements that satisfy the constraints.
In Java, a good way to think about it is to place queens one row at a time and treat each placement as a decision point. Every time you pick a column for the current row, you want an immediate way to reject conflicts without scanning the board, then you want a clean way to undo the placement when you back up and try the next column. That naturally leads to backtracking with lightweight state, and Java’s strengths fit well because arrays and primitive values give fast checks, fast updates, and predictable memory behavior while you walk the search tree and build the final List<List<String>> output only when a full solution has been reached.
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.
Example 1:
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1
Output: [["Q"]]
Constraints:
1 <= n <= 9
Solution 1: Backtracking With Column and Diagonal Flags
This solution sticks to the most direct board model. Place one queen per row, try each column, and keep three fast lookup tables that tell you if a column or diagonal is already occupied. When a spot is safe, place the queen, recurse to the next row, then undo the placement on the way back.
Continue reading this post for free, courtesy of Alexander Obregon.
