[LeetCode 51] N-Queens I

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.."]
]

算法1 这种棋盘类的题目一般是回溯法, 依次放置每行的皇后。在放置的时候，要保持当前的状态为合法，即当前放置位置的同一行、同一列、两条对角线上都不存在皇后。 class Solution { public: vector> solveNQueens(int n) { vector> result; vector sol(n, string(n, '.')); solver(0, sol, result); return result; } void solver(int row, vector &cur, vector> &res){ if(row == sol.size()){ res.push_back(sol); return; } for(int col = 0; col < sol.size(); col++){ if(isValid(row, col, sol)){ sol[row][col] = 'Q'; solver(row + 1, sol, res); sol[row][col] = '.'; } } }

//判断在cur[row][col]位置放一个皇后，是否是合法的状态
//已经保证了每行一个皇后，只需要判断列是否合法以及对角线是否合法。
bool isValid(int row, int col, vector<string> &sol){
    for(int i = 0; i < row; i++) // 列
        if(sol[i][col] == 'Q') return false;
    //右对角线(只需要判断对角线上半部分，因为后面的行还没有开始放置)
    for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--,j--)
        if(sol[i][j] == 'Q')return false;
    //左对角线(只需要判断对角线上半部分，因为后面的行还没有开始放置)
    for(int i = row - 1, j = col + 1; i >= 0 && j < sol.size(); i--, j++)
        if(sol[i][j] == 'Q')return false;
    return true;
}

};

算法2 上述判断状态是否合法的函数还是略复杂，其实只需要用一个一位数组来存放当前皇后的状态。 假设数组为int state[n], state[i]表示第 i 行皇后所在的列。那么在新的一行 k 放置一个皇后后: 判断列是否冲突，只需要看state数组中state[0…k-1] 是否有和state[k]相等； 判断对角线是否冲突：如果两个皇后在同一对角线，那么|row1 - row2| = |column1 - column2|，（row1，column1），（row2，column2）分别为冲突的两个皇后的位置

class Solution { public: vector > solveNQueens(int n) { vector state(n, -1); solver(state, 0); return res; } void solver(vector &state, int row){ //放置第row行的皇后 int n = state.size(); if(row == n){ vector sol(n, string(n, '.')); for(int i = 0; i < n; i++) sol[i][state[i]] = 'Q'; res.push_back(sol); return; } for(int col = 0; col < n; col++){ if(isValid(state, row, col)){ state[row] = col; solver(state, row + 1); state[row] = -1;; } } }

//判断在row行col列位置放一个皇后，是否是合法的状态
//已经保证了每行一个皇后，只需要判断列是否合法以及对角线是否合法。
bool isValid(vector<int> &state, int row, int col){
    for(int i = 0; i < row; i++)//只需要判断row前面的行，因为后面的行还没有放置
        if(state[i] == col || abs(row - i) == abs(col - state[i]))
            return false;
    return true;
}

private: vector> res; };

算法3：(算法2的非递归版） class Solution {

public: vector > solveNQueens(int n) { vector state(n, -1); for(int row = 0, col; ;){ for(col = state[row] + 1; col < n; col++){ //从上一次放置的位置后面开始放置 if(isValid(state, row, col)){ state[row] = col; if(row == n-1){ //找到了一个解,继续试探下一列 vectortmpres(n, string(n,'.')); for(int i = 0; i < n; i++) tmpres[i][state[i]] = 'Q'; res.push_back(tmpres); } else {row++; break;}//当前状态合法，去放置下一行的皇后 } } if(col == n){ //当前行的所有位置都尝试过，回溯到上一行 if(row == 0)break;//所有状态尝试完毕，退出 state[row] = -1;//回溯前清除当前行的状态 row--; } } return res; }

//判断在row行col列位置放一个皇后，是否是合法的状态
//已经保证了每行一个皇后，只需要判断列是否合法以及对角线是否合法。
bool isValid(vector<int> &state, int row, int col){
    for(int i = 0; i < row; i++)//只需要判断row前面的行，因为后面的行还没有放置
        if(state[i] == col || abs(row - i) == abs(col - state[i]))
            return false;
    return true;
}

private: vector > res; };

思路： 经典8皇后问题的推广版n皇后问题。两题其实是一回事，I的难度反而更大一些。因为能解I得到所有解， 必然能知道一共几个解从而能解II。同样也是类似DFS的backtracking问题。 难点在于如何判断当前某一位置是否可以放皇后，需要通过之前所有放置过的皇后位置来判断。 对已经放置的任意皇后，需要判断当前位置是否在同一行、列、对角线上这三个条件。

1. 逐行放置皇后：排除在同一行的可能。
2. 记录之前所放皇后的列坐标：col[i] = j表示第i行的皇后在第j列。这样在放置第i+1行时，只要保证col[i+1] != col[k], k=0...i 即可。
3. 对角线判断：对于任意(i1, col[i1]) 和 (i2, col[i2])，只有当abs(i1-i2) = abs(col[i1] - col[i2])时，两皇后才在同一对角线。

class Solution { public: vector > solveNQueens(int n) { vector> allSol; vector sol;

    vector<int> col;
    solveNQ(n, 0, col, sol, allSol);
    return allSol;
}

void solveNQ(int n, int irow, vector<int> &col, vector<string> &sol, vector<vector<string>> &allSol) {
    if(irow == n) {
        allSol.push_back(sol);
        return;
    }

    for(int icol = 0; icol < n; icol++) {
        if(validPos(col, irow, icol)) {
            string s(n,'.');
            s[icol] = 'Q';
            sol.push_back(s);
            col.push_back(icol);
            solveNQ(n, irow + 1, col, sol, allSol);
            sol.pop_back();
            col.pop_back();
        }
    }
}

bool validPos(vector<int> &col, int irow, int icol) {
    if(irow<col.size()) return false;
    for(int i = 0; i < col.size(); i++) { // 用irow替换col.size()
        if(icol == col[i] || abs(irow - i) == abs(icol - col[i]))
            return false;
    }
    return true;
}

};