c++ - 使用 vector 的 C++ 中的 N 个皇后

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

考虑到这一点，我正在尝试解决 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;
  }
}

最佳答案

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

在 is_safe_square 中，更改

queens[i] == row

至

i == row

关于c++ - 使用 vector 的 C++ 中的 N 个皇后，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11289770/