时间戳

首页 > 解决方案 > 使用 C++ 的 N-Queens 算法

c++ - 使用 C++ 的 N-Queens 算法

问题描述

我正在尝试使用 C++ 解决 N-Queens 问题，但我没有得到正确的输出，也许我的is_attacked()函数有一些问题。请帮助我改进我的代码。

#include <bits/stdc++.h>
using namespace std;
int N;
int board[10][10] = {0};

//to check attacking position
bool is_attacked(int row, int col) {
for(int i=0;i<N;++i)
{
    if(board[row][i] == 1 || board[i][col] == 1)
        return true;
}
if(row >= 1)
    if(board[row-1][col-1] == 1 || board[row-1][col+1] == 1)
        return true;

return false;
}
//to print the values
void print()
{
  for(int i=0;i<N;++i)
  {
    for(int j=0;j<N;++j)
    {
        cout << board[i][j] << " ";
    }
    cout << "\n";
  }
}
//to solve the problem
bool solve(int n) 
{
   if(n == 0)
     return true;
   //main logic, i => row, j => columns
   for(int i=0; i < n; ++i)
   {
     for(int j=0; j<n; ++j)
     {

        if(is_attacked(i, j))
            continue;
        board[i][j] = 1;
        if(solve(n-1))
            return true;
        board[i][j] = 0;

      }
    }
  return false;
}

int main() {
 cin >> N;
 //let's add some basic_cases
  if(N == 2 || N == 3)
  {    cout << "Not possible";
       exit(0);
  }
  if(solve(N))
     print();
  else 
     cout << "Not Possible";
  return 0;
}

它应该显示

0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

但我得到

1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

请帮助我...提前谢谢...

标签： c++c++14

解决方案

is_attaced 中检查对角线的部分不起作用。它有两个基本问题，首先你不检查所有行的所有对角线 - 你只检查前一行。其次，当您位于第一列或最后一列时，您正在进行越界访问。

一种效率不高但易于理解的实现分别检查两个对角线

for( int i=min(col, row); i>0;i-- )
{
   if( board[row-i][col-i]==1 )
      return true;
}
for( int i=MAX_COL; i>row;i-- )
{
   if( board[row-i][col+i]==1 )
      return true;
}

一种更好的方法是在一个循环中完成这两项工作。

推荐阅读