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

[Leetcode] n queens n皇后问题

2024-10-19 11:56:03   211人阅读

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皇后问题


联系
我们