N-queen问题:无法弄清楚为什么我的解决方案不起作用

Question

我正在为即将到来的面试尝试标准的N-Queens问题。 我尝试试运行我的代码，它似乎工作正常。我无法发现代码中的错误。

我正在逐列遍历它，并使用回溯从不正确的路径重复返回。 谁能帮我为什么这没有给我所需的输出(详情如下(？

这是问题陈述

#include<bits/stdc++.h>
using namespace std;
void solve(vector<vector<int>> &ans, vector<int> &curr, int col, int n){
if(col==n){
ans.push_back(curr);
return;
}
bool flag=false;

for(int row=0; row<n; row++){
if(col==0){
curr.push_back(row);
solve(ans, curr, col+1, n);
curr.pop_back();
}
else{
for(int i=0; i<curr.size(); i++){
if((curr[i] == row) || (abs(row-curr[i]) == (col-i))){
flag=true;
break;
}
}
if(flag)
continue;
curr.push_back(row);
solve(ans, curr, col+1, n);
curr.pop_back();
}
}
}
int main()
{
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<vector<int>> ans;
vector<int> curr;
solve(ans, curr, 0, n);
for (int i = 0; i < ans.size(); i++) {
cout << "[";
for (int j = 0; j < ans[i].size(); j++) 
cout << ans[i][j]+1 << " "; 
cout << "]";
}
cout << endl;
}
return 0;
}

示例输入如下所示：

2
1
4

相应的输出将是：

[1 ]
[2 4 1 3 ] [3 1 4 2 ]

编译器给了我一个输出(对于我的代码(：

[1 ]

Answer 1

bool flag变量(用于检查将女王放在(row, col)是否会与curr中的任何现有女王相交(目前正在跨行重复使用。

因此，如果您将行bool flag=false;放在for(int i=0; i<curr.size(); i++){正上方，它应该为您的测试用例生成正确的输出。

其他注意事项：

1. 创建单独的函数bool does_intersect(const vector<int>& cur, int row, int col)检查 queen 交集条件可能更容易，这样就不需要bool flag变量了。
2. 可以删除if(col==0){条件，因为它不会执行else部件无法处理的任何操作。

Answer 2

该解决方案通过了 LeetCode 对 N Queens 问题的在线判断，并使用三个标志来解决问题：

#include <string>
#include <vector>
class Solution {
public:
std::vector<std::vector<std::string>> solveNQueens(int n) {
std::vector<std::vector<std::string>> possibilities;
std::vector<std::string> n_queens(n, std::string(n, '.'));
std::vector<int> flag_col(n, 1);
std::vector<int> flag_diag_a(2 * n - 1, 1);
std::vector<int> flag_diag_b(2 * n - 1, 1);
solveNQueens(possibilities, n_queens, flag_col, flag_diag_a, flag_diag_b, 0, n);
return possibilities;
}
private:
void solveNQueens(std::vector<std::vector<std::string>>& possibilities,
std::vector<std::string>& n_queens,
std::vector<int>& flag_col, std::vector<int>& flag_diag_a, std::vector<int>& flag_diag_b,
int row, int& n) {
if (row == n) {
possibilities.push_back(n_queens);
return;
}
for (int col = 0; col != n; col++) {
if (flag_col[col] && flag_diag_a[row + col] && flag_diag_b[n - 1 + col - row]) {
flag_col[col] = flag_diag_a[row + col] = flag_diag_b[n - 1 + col - row] = 0;
n_queens[row][col] = 'Q';
solveNQueens(possibilities, n_queens, flag_col, flag_diag_a, flag_diag_b, row + 1, n);
n_queens[row][col] = '.';
flag_col[col] = flag_diag_a[row + col] = flag_diag_b[n - 1 + col - row] = 1;
}
}
}
};

对于面试，您可能不应该使用：

#include<bits/stdc++.h>
using namespace std;

并确保编写干净的代码。

>N Queens 是一个低频面试问题。在面试中要问的问题要好得多(例如岛屿数量(，可能你不会得到N个皇后区。但是，练习是件好事。

Answer 3

这是使用回溯解决N-Queens问题的非常简单的方法：

#include <bits/stdc++.h>
using namespace std;
int m[20][20];
bool ended = false;
void print(int n){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cout<<(m[i][j] == -1? "O" : "-")<<" ";
}
cout<<endl;
}
}
void fill(int val, int row, int col, int n){
int d = 1;
for(int i = col + 1; i < n; i++, d++){
m[row][i] += val;
if(row - d >= 0) m[row - d][i] += val;
if(row + d < n)  m[row + d][i] += val;
}
}
void solve(int n, int col = 0){
if(ended) return;        
if(col == n){ print(n); ended = true; return; }

for(int i = 0; i < n; i++){
if(m[i][col] == 0){
m[i][col] = -1;
fill(1, i, col, n);
solve(n, col + 1);
m[i][col] = 0;
fill(-1, i, col, n);
}
}
}
int main(){
memset(m, 0, sizeof(m));
solve(8);                 //dimension of board    
return 0;
}

我们的想法是始终向前看。将女王放在矩阵中为 0 的插槽中。之后，在她可以移动到的所有插槽中添加 1。当您从回溯返回时，从刚刚添加的相同插槽中减去 1 并继续尝试。