N-Queens

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

tag: backtracking

经典问题，九皇后问题，利用回溯算法。

皇后的攻击范围是同一行，同一列，同一斜线。所以同一行只能有一个皇后，我们可以按行插入皇后。

每次插入新的皇后时，检测该皇后是否会攻击到现有的皇后。如果发生冲突，则尝试该行的下一列。如果所有的列都不行，则返回上一层–即上一行。

如果插入皇后时不发生冲突，则进入下一层–即下一行，继续搜索。

该算法还有优化的空间。我为了让算法直观，用了一个bool [][] board变量表示当前棋盘的状态。true表示该单元格被皇后占据，false表示空。

实际上，我们可以用一个一位数组int a[n]表示棋盘状态，下标n表示第n行，a[n]的值表示该行皇后所处的列，然后进行搜索。在下一题中： N-Queens II，我用了这个优化的算法。

class Solution {
public:
    //I try to fill the board row by row
    vector<vector<string> > solveNQueens(int n) {
        vector<vector<bool> > board(n, vector<bool>(n, false));//false means empty; true means occupied by a queen
        vector<vector<string>> re;
        if(n == 0){
            return re;
        }
        //fill the first row
        for(int j = 0; j < n; j++){
            board[0][j] = true;
            _solveQueens(1, board, re);
            board[0][j] = false;
        }
        return re;
    }
    void _solveQueens(int row, vector<vector<bool> > &board, vector<vector<string> > &re){
        int size = board.size();
        if(row == size){//finish
            re.push_back(generateResult(board));
            return;
        }
        
        //not finish
        for(int j = 0; j < size; j++){
            board[row][j] = true;
            if(checkBoard(board, row, j) == true){//leagal 
                _solveQueens(row + 1, board, re);
            }
            board[row][j] = false;
        }
    }
    
    vector<string> generateResult(vector<vector<bool> > &board){
        vector<string> strs;
        string s;
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board.size(); j++){
                char c = board[i][j] == true?'Q': '.';
                s.push_back(c);
            }
            strs.push_back(s);
            s.clear();
        }
        return strs;
    }
    bool checkBoard(vector<vector<bool> > &board, int row, int column){
        int size = board.size();
        for(int k = 0; k < size; k++){
            //check row
            if(board[row][k] == true && k != column){
                return false;
            }
            //check column
            if(board[k][column] == true && k != row){
                return false;
            }
            //check diagonal
            int r0 = row - k;
            int c0 = column - k;
            int c1 = column + k;
            bool flag = false;
            if(r0 >= 0 && c0 >= 0){
                flag |= board[r0][c0];
            }
            if(r0 >= 0 && c1 < size){
                flag |= board[r0][c1];
            }
            //no need to check below part of the board
            if(flag == true && k != 0){
                return false;
            }
        }
        return true;
    }
};