Short C++ solution representing board as vector<int>


  • 1
    C

    The basic idea is to represent the board as a vector of int, where each index is a column of the board, and each value is the row the queen is on. We can do this because all solutions have exactly one queen on every column. Then, for each column, we place a queen on each row and check if the board is valid. If it is, we recurse on the next column. Checking if the board is valid is straightforward - we just check the row and diagonals of the newest queen against the existing queens:

    class Solution {
    public:
        bool isValid(const vector<int>& columns, int col) {
            for (int c = 0; c < col; ++c) {
                if ((columns[c] == columns[col])
                    || (col - c == columns[col] - columns[c])
                    || (col - c == columns[c] - columns[col])) {
                    return false;
                }
            }
            return true;
        }
    
        int totalNQueens(vector<int>& columns, int col) {
            if (col == columns.size()) {
                return 1;
            }
            int total = 0;
            for (int row = 0; row < columns.size(); ++row) {
                columns[col] = row;
                if (isValid(columns, col)) {
                    total += totalNQueens(columns, col + 1);
                }
            }
            return total;
        }
    
        int totalNQueens(int n) {
            vector<int> columns(n, 0);
            return totalNQueens(columns, 0);
        }
    };

  • 0

    brilliant! using one 1 vector column and 1 variable col. @@


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.