c++ - C++ 中的 N Queens 使用 vector

Question

我无法理解回溯，我可以从概念上理解我们采取行动，然后如果找不到解决方案，我们会尝试下一个解决方案。

考虑到这一点，我正在尝试解决 N Queens 问题， 我正在找出所有可以放在下一行的可能候选者，然后一个一个地尝试它们，如果一个候选者没有产生解决方案，我将其弹出并继续下一个。

这是我想出的代码的核心:

void n_queens(int n)
{
  vector<int> queens = vector<int>();
  backtrack(queens,0,n);
}

void backtrack(vector<int>& queens, int current_row, int N)
{
  // check if the configuration is solved
  if(is_solution(queens, N))
  {
    print_solution(queens,N);
  }
  else
  {
    // construct a vector of valid candidates
    vector<int> candidates = vector<int>();
    if(construct_candidates(queens,current_row,N,candidates))
    {
      for(int i=0; i < candidates.size(); ++i)
      {
        // Push this in the partial solution and move further
        queens.push_back(candidates[i]);
        backtrack(queens,current_row + 1,N);
        // If no feasible solution was found then we ought to remove this and try the next one
        queens.pop_back();
      }
    }
  }
}

bool construct_candidates(const vector<int>& queens, int row, int N, vector<int>& candidates)
{
  // Returns false if there are no possible candidates, we must follow a different
  // branch if this so happens
  for(int i=0; i<N; ++i)
  {
    if(is_safe_square(queens,row,i,N))
    {
      // Add a valid candidate, this can be done since we pass candidates by reference
      candidates.push_back(i);
    }
  }
  return candidates.size() > 0;
}

它不会为我提供的任何输入打印任何内容。我尝试通过 gdb 运行它但没有成功，我认为这是因为我对回溯的基本理解有问题。

我已经阅读了几本书和一个在线教程中关于回溯的内容，但我仍然感到模糊，如果有人能给我一些想法来解决这个问题并帮助我理解这个有点不直观的概念，那就太好了。

完整的可编译源代码是:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// The method prototypes
void n_queens(int n);
void backtrack(vector<int>&, int current_row, int N);
bool construct_candidates(const vector<int>&, int row, int N, vector<int>&);
bool is_safe_square(const vector<int>&, int row, int col, int N);
bool is_solution(const vector<int>&, int N);
void print_solution(const vector<int>&, int N);

int main()
{
  int n;
  cin>>n;
  n_queens(n);
  return 0;
}

void n_queens(int n)
{
  vector<int> queens = vector<int>();
  backtrack(queens,0,n);
}

void backtrack(vector<int>& queens, int current_row, int N)
{
  // check if the configuration is solved
  if(is_solution(queens, N))
  {
    print_solution(queens,N);
  }
  else
  {
    // construct a vector of valid candidates
    vector<int> candidates = vector<int>();
    if(construct_candidates(queens,current_row,N,candidates))
    {
      for(int i=0; i < candidates.size(); ++i)
      {
        // Push this in the partial solution and move further
        queens.push_back(candidates[i]);
        backtrack(queens,current_row + 1,N);
        // If no feasible solution was found then we ought to remove this and try the next one
        queens.pop_back();
      }
    }
  }
}

bool construct_candidates(const vector<int>& queens, int row, int N, vector<int>& candidates)
{
  // Returns false if there are no possible candidates, we must follow a different
  // branch if this so happens
  for(int i=0; i<N; ++i)
  {
    if(is_safe_square(queens,row,i,N))
    {
      // Add a valid candidate, this can be done since we pass candidates by reference
      candidates.push_back(i);
    }
  }
  return candidates.size() > 0;
}

bool is_safe_square(const vector<int>& queens, int row, int col, int N)
{
  for(int i=0; i<queens.size(); ++i)
  {
    // case when the queens are already placed in the same row or column
    if(queens[i] == row || queens[i] == col) return false;
    // case when there is a diagonal threat
    // remember! y = mx + c for a diagonal m = 1 therefore |x2 - x1| = |y2 - y1|
    if(abs(i - row) == abs(queens[i] - col)) return false;
  }
  //Returns true when no unsafe square is found
  //handles the case when there are no queens on the board trivially
  return true;
}

bool is_solution(const vector<int>& queens, int N)
{
  return queens.size() == N;
}

void print_solution(const vector<int>& queens, int N)
{
  for(int i=0; i<N; ++i)
  {
    for(int j=0; j<N; ++j)
    {
      if(queens[i] == j){ cout<<'Q'; }
      else { cout<<'_'; }
    }
    cout<<endl;
  }
}

Answer 1

这不是基本问题，只是一个错误。

在is_safe_square中，改变

queens[i] == row

到

i == row