Backtracking - Question 1

Leetcode 51. N-Queens

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

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Constraints:

1 <= n <= 9

Analysis:

For each row, we can only put one queen, so we can make the trial row by row.

For each row, every position is possible to place the queen. Once the queen is set, the position should be recorded, since this information has limitations on new queen's position.

To simply the record and also the check, we can use a one dimensional array for this: the index is for the row, and its value for the column. Both information determines the position of the queen placed.

Once reached the last row, we can check how many queens have been placed. 

If it equals to n, it means that we find a valid solution; 

If not, we need to go back the trial step, reset the trial, and make a second trial, ... until make and finish all the trials.

See the code below:

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        m = n;
        ps.resize(m);
        fill(ps.begin(), ps.end(), -1);
        bt(0, 0);// row number, queen counts
        return res;
    }
private:
    int m;
    vector<vector<string>> res;
    vector<string> one;
    vector<int> ps;
    void bt(int x, int ct) {
        if(x==m) {
            if(ct==m) res.push_back(one);
            return;
        }
        string s(m, '.');
        for(int i=0; i<m; ++i) {
            // if(ps[x] != -1) continue;
            s[i] = 'Q';// make trial
            if(isValid(x, i)) {
                ps[x] = i;//record
                one.push_back(s);//save
                bt(x+1, ct+1);
                one.pop_back();//step back
                ps[x] = -1;//step back
            }
            s[i] = '.';// reset
        }
    }
    bool isValid(int x, int y) {
        for(int i=0; i<m; ++i) {
            if(i == x || ps[i] == -1) continue;
            if(y == ps[i] || abs(x-i) == abs(y-ps[i])) return false;
        }
        return true;
    }
};

 

Upper Layer