[LeetCode] 51. N-Queens

Well-known back tracking problem.

class Solution {
public:
    vector<vector<bool>> board;
    vector<vector<string>> res;

    bool safe(int row, int col, const int n) {
        // Skip row-wise check and cells lower than current row.
        for(int r = 0; r < row; r++) { if(board[r][col]){ return false; } }
        for(int r = row-1, c = col-1; r >= 0 && c >= 0; r--, c--) {
            if(board[r][c]){ return false; }
        }
        for(int r = row-1, c = col+1; r >= 0 && c < n; r--, c++) {
            if(board[r][c]){ return false; }
        }
        return true;
    }

    int rcsv(int cur_row, const int n) {
        if (cur_row == n) {
            vector<string> ans(n, "");
            for(int i = 0; i < n; i++) { 
                for(bool cell: board[i]) { ans[i] += cell ? 'Q' : '.'; } }
            res.push_back(ans);
            return 1;
        }

        int ret = 0;

        for(int col = 0; col < n; col++) {
            if (!safe(cur_row, col, n)) { continue; }
            board[cur_row][col] = true;
            ret += rcsv(cur_row+1, n);
            board[cur_row][col] = false;
        }

        return ret;
    }

    vector<vector<string>> solveNQueens(int n) {
        board.assign(n, vector<bool>(n, false));
        res.clear();
        rcsv(0, n);
        return res;
    }
};

 

Without recursion:

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> board(n, string(n, '.'));

        vector<bool> col(n, false);
        vector<bool> diag1(2 * n - 1, false);
        vector<bool> diag2(2 * n - 1, false);

        vector<int> queen(n, -1);

        int row = 0;
        int c = 0;

        for(;;) {
            bool placed = false;

            for(; c < n; c++) {
                int d1 = row + c;
                int d2 = row - c + n - 1;

                if(col[c] || diag1[d1] || diag2[d2]) { continue; }

                board[row][c] = 'Q';
                queen[row] = c;
                col[c] = diag1[d1] = diag2[d2] = true;

                placed = true;
                break;
            }

            if(placed) {
                if(row == n-1) { res.push_back(board); }
                else { row++; c = 0; continue; }
            }
            else {
                if(--row < 0) { break; }
            }

            int old = queen[row];
            board[row][old] = '.';
            col[old] = diag1[row + old] = diag2[row - old + n - 1] = false;
            queen[row] = -1;

            c = old + 1;
        }

        return res;
    }
};