N-Queens is a backtracking problem. Given a N x N chess board, our task is to arrange N queens in a way such that no two queens attack each other. Two queens are attacking each other if they are in same row, same column or diagonal. Minimum chess board size should be 4x4.
- Each row contains 1 queen
- For each row, keep track of the valid columns for queen placement. # (NOTE in a clever way)
- DFS, start from the first row, try each valid column and backtrack if necessary.
- Note that we can encode left/right diagonals as indexes in the following way: For any (r, c),
- its top-left to the bottom-right diagonal index is r – c, ∈ (-n, n)
- its bottom-left to the top-right diagonal index is r + c, ∈ [0, 2n)
- Each (r, c) takes the r-th row, c-th column, and the two diagonal indexes encoded above.
- Now we can use 4 sets to indicate whether those row/col/diagonal have been taken, if yes, a queen cannot be placed at (r, c).
- Moreover, if we search via dfs, proceeding row by row, we can avoid keeping # the row set, getting away with 3 sets only (column, and 2 diagonals).
- Each set indicates whether the column/diagonal with the specified index has been taken.
Given size of Chessboard: N=4
2 solutions exists. They are:
O(N!)