【lintcode】N皇后问题

落日映苍穹つ 2022-06-01 05:10 192阅读 0赞

n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击。
    给定一个整数n，返回所有不同的n皇后问题的解决方案。
    每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。
    
    样例
    对于4皇后问题存在两种解决的方案：
    [".Q..", // Solution 1
    
     "...Q",
    
     "Q...",
    
      "..Q."],
    
     ["..Q.", // Solution 2
    
     "Q...",
    
      "...Q",
    
       ".Q.."]

思路：

*  国际象棋中皇后可以攻击同行同列以及同一斜线上的棋子，所以要以此来判断在一个棋盘格上能否放置一个皇后。我们使用一个长度为n的一维数组**Queens**来存储每一行的皇后的位置(-1表示没有皇后)。对于位置(r, c),只需判断`Queens[i] >= 0 && (Queens[i] == c || abs(r-i) == abs(c-Queens[i]))` ，若为真表示有冲突，不可放置。
 *  求解过程使用回溯法，(r,c)表示当前位置 对于该位置有如下几种情况：  
    1.r == n-1  
    　**a**.　 c == n-1(即行尾), 如果有解，则记录这个解，然后回溯到上一行的皇后之后的位置（同时删去关于该皇后的记录）；否则直接回溯到上一行  
    　**b**.　未到行尾,如果有解，则记录这个解，然后清除该行的记录，最后将ｃ加１，移动到下一个位置；否则直接移动到下一个位置  
    　  
    2.r < n-1（即未到最后一行）  
    　**a**. c < n-1,即没有到行尾　如果可以放置皇后则记录相应的位置，然后令 r = r + 1, c = 0 ,移动到下一行； 否则将c加1，移动到下一个位置  
    　**b**.c == n-1,即到达行尾　如果可以放置皇后，则记录，然后移动到下一行；否则，则回溯到上一行的皇后所在位置的后一个位置
    
    3.在回溯的过程中可能会出现**c >= n**的情况，这时候如果 r == 0，则函数直接返回；否则回溯到上一行

代码

第一次写的题解中核心函数**solve**太过复杂，下面先提前给出一个简化过的**solve**函数。

void solve2(int r){
            if(r == n){
                for(int i = 0; i < n; i++)
                    result[i][Queens[i]] = 'Q';
                results.push_back(result);
    
                for(int i = 0; i < n; i++)
                    for(int j = 0; j < n; j++)
                        result[i][j] = '.';
            }
            else{
                for(int i = 0; i < n; i++){
                    for(int j = r; j < n; j++)
                        Queens[j] = -1;
                    if(check(r, i)){
                        Queens[r] = i;
                        solve2(r+1);
                    }
                }
            }
        }

完整题解如下

class Solution {
        vector<int> Queens;
        vector<vector<string> > results;
        vector<string> result;
        int n;
    public:
        /*
         * @param n: The number of queens
         * @return: All distinct solutions
         */
        vector<vector<string> > solveNQueens(int _n) {
            // write your code here
            n = _n;
            Queens.resize(n, -1);
            result.resize(n);
            for(int i = 0; i < n; i++)
                result[i].resize(n, '.');
    
            if(n == 1){
                result[0][0] = 'Q';
                results.push_back(result);
                return results;
            }
            else if(n < 4)
                return results;
    
            solve(0,0);
            return results;
        }
    
        void solve(int r, int c){
            if(c  >= n)
                if(r == 0)
                    return;
                else{
                    r--;
                    //删去回溯点的解
                    result[r][Queens[r]] = '.'; 
                    int t = Queens[r];
                    Queens[r] = -1;
                    solve(r, t+1); //回溯到上一行
                    return;
                }
            if(r == n-1){
                for( ; c < n; c++){
                    if(check(r,c)){
                        result[r][c] = 'Q';
                        results.push_back(result); //添加新解
                        result[r][c] = '.'; //删去本行的皇后
                    }
                    if(c == n-1){ 
                        //若已到行尾，则回溯
                        r--;
                        //删去回溯点的解
                        result[r][Queens[r]] = '.'; 
                        int t = Queens[r];
                        Queens[r] = -1;
                        solve(r, t+1); //回溯到上一行
                        return;
                    }
                }
            }
            else{
                for( ; c < n; c++){
                    if(check(r,c)){
                        result[r][c] = 'Q';
                        Queens[r] = c;
                        r++;
                        solve(r,0);
                        return;
                    }
                    if(c == n-1){
                        if(r == 0)
                            return; //如果已经回溯到了第一行，则返回
                        else{
                            r--;
                            //删去回溯点的解
                            result[r][Queens[r]] = '.'; 
                            int t = Queens[r];
                            Queens[r] = -1;
                            solve(r, t+1); //回溯到上一行
                            return;
                        }
                    }
                }
            }
        }
    
        int check(int r, int c){
            for(int i = 0; i < Queens.size(); i++)
                if(Queens[i] >= 0 && (Queens[i] == c || abs(r-i) == abs(c-Queens[i])) ) 
                    return 0;
            return 1;
        }
    };