[LeetCode] N-Queens I && II

N-Queens I

Problem Statement (link):

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

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement,
where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Analysis:
Eight queens puzzle is a classic problem in use of DFS backtracking algorithm, it can be generalized to a N-queens puzzle.

The high-level idea of the backtracking algorithm is to choose any location as a start, try all possible positions until no violation to the rule has found. If a violation is found, we immediately abandon current placement and move the next possible position, if all possibilities has been tried for current queen, we go back to the previous queen and move that queen to its next possible position.

As describe in the statement, the rule for this game is: only one queen is placed in each row and column. This rule is used to check whether a position is legal for placing a queen.

Thus, the pseudo code looks like this:

1. Place the first queen in the left upper corner of the table.
2. Save the attacked positions.
3. Move to the next queen (which can only be placed to the next line).
4. Search for a valid position. If there is one go to step 8.
5. There is not a valid position for the queen. Delete it (the x coordinate is 0).
6. Move to the previous queen.
7. Go to step 4.
8. Place it to the first valid position.
9. Save the attacked positions.
10. If the queen processed is the last stop otherwise go to step 3.

The time complexity is exponential, same as all other backtracking algorithms.

A space-saving trick is we use 1-D vector to store the queens' 2-D location, where A[i]=j indicates row i, col j has a queen.

Code:

class Solution {
public:
    vector<vector<string> > out;
    // main function
    vector<vector<string> > solveNQueens(int n) {
        if (n==0) return out;
        vector<int> A(n, -1);   // Stores state for current solution, A[i]=j indicates row i, col j has a queen
        placeQueen(A, 0, n);    // starts from row 0
        return out;
    }

    // iterate thru row
    void placeQueen(vector<int> A, int cur, int n){ // cur - current row #
        if (cur==n) printOut(A, n);
        else {
            for (int i=0; i<n; i++){    // traverse thru each row, i-col
                A[cur]=i;
                if (isValid(A,cur)) {
                    placeQueen(A, cur+1, n);
                }
            }
        }
    }

    // To check if the current position is valid to place a queue
    bool isValid(vector<int> A, int row){
        for (int k=0; k<row; k++) { // row iteration
            if (A[k]==A[row] || (abs(A[k]-A[row])==(row-k))) {
                return false;
            }
        }
        return true;
    }

    // Update out to include current solution
    void printOut(vector<int> A, int n) {
        vector<string> v;   // a solution
        for (int i=0; i<n; i++){
            string s(n,'.');    // for each row
            s[A[i]] = 'Q';
            v.push_back(s);
        }

        out.push_back(v);
    }
};

N-Queens II

Problem statement (link):

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

Analysis:
The algorithm is exactly the same as in N-Queens I. Only difference is that instead of populating the location of each queens when we find a solution, we only need to count the number of solutions.

Code:

class Solution {
public:
    vector<vector<string> > out;
    int num;
    // main function
    int totalNQueens(int n) {
        if (n==0) return 0;
        vector<int> A(n, -1);   // Stores state for current solution, A[i]=j indicates row i, col j has a queen
        num = 0;
        placeQueen(A, 0, n);    // starts from row 0
        return num;
    }

    // iterate thru row
    void placeQueen(vector<int> A, int cur, int n){ // cur - current row #
        if (cur==n) num++;
        else {
            for (int i=0; i<n; i++){    // traverse thru each row, i-col
                A[cur]=i;
                if (isValid(A,cur)) {
                    placeQueen(A, cur+1, n);
                }
            }
        }
    }

    // To check if the current position is valid to place a queue
    bool isValid(vector<int> A, int row){
        for (int k=0; k<row; k++) { // row iteration
            if (A[k]==A[row] || (abs(A[k]-A[row])==(row-k))) {
                return false;
            }
        }
        return true;
    }
};