力扣51. N 皇后（回溯法）

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4

输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1

输出：[["Q"]]

提示：

1 <= n <= 9

经典的回溯法问题，类似的需要回溯法的还有排列组合问题，一般是DFS+回溯来实现一个暴力搜索。

N皇后问题的有两个核心，一个是回溯，一个是对4个限定条件的判断（行、列、两条对角线）

1.回溯核心逻辑

void backtracking(element length,element end,element result,element set,int startIndex,...)

{

    if(终止条件==end){

        result.add(set);  //将当前集合加到结果集中

    for(i=startIndex;i<length;++i){

        更新当前集合set;

        backtracking(length,end,result,set,...);  //往下一层遍历

        还原当前集合set;

    }

}

2.由于棋盘每行每列都会有一个皇后，我们可以选择一行一行确定或者一列一列遍历，这边我选择一行一行遍历。如果一行一行遍历，那么我们在遍历的过程中只需要记录列的皇后放置信息（因为每行放置了皇后之后就会进入下一层遍历，不会在该层停留，即已经确保了同一行只有一个皇后）、主对角线、副对角线的信息。

(0,0)	(0,1)	(0,2)	(0,3)
(1,0)	(1,1)	(1,2)	(1,3)
(2,0)	(2,1)	(2,2)	(2,3)
(3,0)	(3,1)	(3,2)	(3,3)

在一个棋盘上，假设某点坐标为( i , j )我们可以明显看出同一主对角线上i - j的值相同（注意不是|i - j|相同），同一副对角线上的i + j相同，据此我们可以用三个数组来快速判断某个位置能不能放入皇后。

 1 class Solution {

 2 public:

 3     vector<int> column,ldiagonal,rdiagonal;

 4     vector<vector<string>> result;

 5     void backtracking(int n,vector<string> mmap,int row){

 6         if (row==n){  //棋盘内已有n个皇后

 7             result.push_back(mmap);

 8             return;

 9         }

10

11         for (int j=0;j<n;++j){

12             if (column[j]==0&&ldiagonal[row+j]==0&&rdiagonal[row-j+n-1]==0){

13                 // cout<<row<<" and "<<j<<endl;

14                 // cout<<row-j+n-1<<" "<<abs(row-j)<<endl;

15                 mmap[row][j]='Q';

16                 column[j]=1;

17                 ldiagonal[row+j]=1;

18                 rdiagonal[row-j+n-1]=1;

19                 backtracking(n,mmap,row+1);

20                 //回溯

21                 rdiagonal[row-j+n-1]=0;

22                 ldiagonal[row+j]=0;

23                 column[j]=0;

24                 mmap[row][j]='.';

25             }

26         }

27         return;

28     }

29     vector<vector<string>> solveNQueens(int n) {

30         //初始化

31         vector<string> initial;

32         for (int i=0;i<n;++i){

33             string temp;

34             for (int j=0;j<n;++j){

35                 temp.push_back('.');

36             }

37             initial.push_back(temp);

38         }

39         for (int i=0;i<25;++i){

40             column.push_back(0);

41             rdiagonal.push_back(0);

42             ldiagonal.push_back(0);

43         }

44

45         backtracking(n,initial,0);

46

47         return result;

48     }

49 };

巴特西

力扣51. N 皇后（回溯法）

最新文章

热门文章