N-Queens

Problem

The n-queens puzzle is the problem of placing n queens on an n x n chessboard so that no two queens can attack each other.

A queen in a chessboard can attack horizontally, vertically, and diagonally.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a unique board layout where the queen pieces are placed. 'Q' indicates a queen and '.' indicates an empty space.

You may return the answer in any order.

Examples

Example 1:

Input: n = 4

Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Example 2:

Input: n = 1

Output: [["Q"]]

Constraints

• 1 <= n <= 8

You should aim for a solution with O(n!) time and O(n^2) space, where n is the size of the given square board.

Solution

Run DFS backtracking, where the invariant is a valid board up to (c-1) columns. Each DFS call tries to add a queen to a column by scanning each row in that column.

class Solution {
    using Board = std::vector<std::vector<int>>;
 
    std::vector<std::string> make_empty_board_str(int n) {
        return std::vector<std::string>(n, std::string(n, '.'));  
    }
 
    void update_queen(Board &board, int r, int c, int n, int delta) {
        // column
        for (int rr = 0; rr < n; ++rr) {
            board[rr][c] += delta;
        }
        // row
        for (int cc = 0; cc < n; ++cc) {
            board[r][cc] += delta;
        }
        // diag (top-left to bottom-right)
        {
            int offset = std::min(r, c);
            int rr = r - offset;
            int cc = c - offset;
            while (rr < n && cc < n) {
                board[rr][cc] += delta;
                ++rr;
                ++cc;
            }
        }
 
        // anti-diag (top-right to bottom-left)
        {
            int offset = std::min(r, n - 1 -c);
            int rr = r - offset;
            int cc = c + offset;
            while (rr < n && cc >= 0) {
                board[rr][cc] += delta;
                ++rr;
                --cc;
            }
        }
    }
 
    void add_queen(Board &board, int r, int c, int n) {
        update_queen(board, r, c, n, +1);
    }
 
    void remove_queen(Board &board, int r, int c, int n) {
        update_queen(board, r, c, n, -1);
    }
 
public:
    vector<vector<string>> solveNQueens(int n) {
        // Bit board indicates what positions are open
        Board board(n, std::vector<int>(n, 0));
        std::vector<int> queen_row_for_col(n, -1);
        std::vector<std::vector<std::string>> result;
 
        // Invariant is that board is valid with queens placed up to col (c - 1)
        std::function<void(int)> dfs;
        dfs = [&](int c) {
            // If c == n, then we successfully placed N-Queens
            if (c == n) {
                auto sol = make_empty_board_str(n);
                for (int cc = 0; cc < n; ++cc) {
                    sol[queen_row_for_col[cc]][cc] = 'Q';
                }
                result.push_back(sol);
                return;
            }
            // Try to place a queen at each row
            for (int r = 0; r < n; ++r) {
                // Not a valid position to place a queen
                if (board[r][c] > 0) { continue; } 
                // Queen can be placed here, place it then try next
                else {
                    add_queen(board, r, c, n);
                    queen_row_for_col[c] = r;
                    dfs(c + 1);
                    remove_queen(board, r, c, n);
                    queen_row_for_col[c] = -1;
                }
            }
        };
 
        dfs(0);
        return result;
    }
};