首页 > 代码库 > [Leetcode] n queens n皇后问题

[Leetcode] n queens n皇后问题

The n-queens puzzle is the problem of placing n queens on an n×nchessboard 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.."]
]

 题意:返回皇后放置位置的所有解。

思路:采用回溯法,先试探的在第一行中的第一个位置放Q,然后去在二行中,在满足条件下,放第二个Q,一次类推,若是有一行没有地方放了,就放回上一行,改变此行Q的位置,依次类推,直到找到所有。

遇到问题一:如何记录某一行中Q的位置?我们可以用一个数组记录下某一行中Q所在的列数,这样,我们就可以先记下Q的位置,然后去试探下一行中Q的位置,若最后不能成为解,需要回溯,则state置为-1(为负数就行),然后试探该行中其他位置是否满足;

问题二:返回值中中间变量的定义形式?因为最后的结果是一个存放string类型的二维矩阵,所以定义中间变量时,可以用:vector<string> temp(n,string(n,‘.‘));

问题三:如何判断一个位置是否合适放Q?因为,我们试探下一个Q时,是在下一行中进行的,所以,同行就自然排除了;所以只需判断是否在同列,或者上一个Q的对角线上就行,对角线上的判断可以用,列差的绝对值和行差的绝对值是否相等来判断;

问题四:何时得出一种解?得出每行Q所在的列时,即row==n,数组中row应为仅能为n-1,若其等于n,说明已经找到该解中所有的Q位置。

代码如下:

 1 class Solution {
 2 public:
 3     vector<vector<string> > solveNQueens(int n) 
 4     {
 5         vector<vector<string>> res;
 6         vector<int> state(n,-1);
 7         helper(state,0,res);
 8         return res;
 9     }
10 
11     void helper(vector<int> &state,int row,vector<vector<string>> &res)
12     {
13         int n=state.size();
14         if(row==n)
15         {
16             vector<string> temp(n,string(n,.));
17             for(int i=0;i<n;++i)
18             {
19                 temp[i][state[i]]=Q;
20             }
21             res.push_back(temp);
22         }
23         else
24         {
25             for(int col=0;col<n;++col)
26             {
27                 if(isVaild(state,row,col))
28                 {
29                     state[row]=col;
30                     helper(state,row+1,res);
31                     state[row]=-1;
32                 }
33             }
34         }
35     }
36 
37     bool isVaild(vector<int> &state,int row,int col)
38     {
39         for(int i=0;i<row;++i)
40         {
41             if(state[i]==col||abs(row-i)==abs(col-state[i]))
42                 return false;
43         }
44         return true;
45     }
46 };

 

参考了JustDoIT的博客,其也给出了非递归的解法。

[Leetcode] n queens n皇后问题