51. N皇后

该题为著名的n皇后问题。

Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> mark;
        vector<string> queenposition;
        vector<vector<string> > map;
        //初始化。
        string a = "";
        for(int i = 0; i < n;i++){
            a = a + ".";
        }
        for(int i = 0; i < n; i++){
            queenposition.push_back(a);
            mark.push_back(a);
        }
        
        dfs(mark,queenposition,map,0,n);
        return map;
    }
    void putOneQueen(vector<string> &mark,int x,int y,int n){
        static const int dx[8] = {-1,-1,-1,0,0,1,1,1};
        static const int dy[8] = {-1,0,1,-1,1,-1,0,1};
        
        mark[x][y] = '1';

        for(int i = 0; i < 8; i++){
            int nx = x + dx[i],ny = y+dy[i]; 
            while(0 <= nx && nx < n && 0 <= ny && ny < n){
                mark[nx][ny] = '1';
                nx += dx[i];
                ny += dy[i];	
            }
        }
	}
    
    void dfs(vector<string> &mark,vector<string> &queenposition,vector<vector<string> > &map,int col,int n){
        //出口
        if(col == n){
            map.push_back(queenposition);
            return;
        }
        for(int i = 0; i < n;i++){
            if(mark[col][i] == '.'){//可以放皇后 
                vector<string> temp_mark = mark;//记录回溯前的镜像。
                //放皇后。 
                queenposition[col][i] = 'Q';
                putOneQueen(mark,col,i,n);
                //递归调用。 
                dfs(mark,queenposition,map,col+1,n);
                //回溯 
                mark = temp_mark;
                queenposition[col][i] = '.';
            }
        }
    }
};

该题考查对递归与回溯算法的掌握。

使用一个矩阵来存储是否可以放皇后的状态。
每当一行放置了一个皇后后，更新其状态，并在下一行中挑选合适的位置来放置该行的皇后。

直到每一行都放置了皇后，保存状态，返回上一个递归过程。

回溯主要针对矩阵的状态和皇后放置的位置，以便利于递归返回过程中的再次使用。