6

所以我需要经典的 N-Queens 问题的帮助。

运行程序的命令将是： nqueens N k - 其中 N 是表的大小 (N x N)，k 是解决方案的数量

因此，例如，如果我通过键入nqueens 4 1来运行程序，则会打印出以下内容。

_ 问 _ _

_ _ _ 问

问_ _ _

_ _ 问 _

但是，我无法弄清楚如何处理超过 1 个解决方案？对于这个问题，我如何才能确定不止一种解决方案？

到目前为止我所拥有的如下：

#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <vector>


using namespace std;

class Board
{
private:
    bool** spaces;
    int size;

public:
    Board(int size)
    {
        this->size = size;
        spaces = new bool*[size];
        for (int i = 0; i < size; ++i)
        {
            spaces[i] = new bool[size];
        }
    }

    bool isSafe(int row, int column, vector<int>& state)
    {
       //check row conflict
       //no need to check for column conflicts
       //because the board is beimg filled column
       //by column
       for(int i = 0; i < column; ++i)
       {
          if(state[i] == row)
             return false;
       }

       //check for diagonal conflicts
       int columnDiff = 0;
       int rowDiff = 0;
       for(int i = 0; i < column; ++i)
       {
          columnDiff = abs(column - i);
          rowDiff = abs(row - state[i]);
          if(columnDiff == rowDiff)
             return false;
       }

       return true;

    }

    int getSize()
    {
        return size;
    }

    bool getSpace(int x, int y)
    {
        return spaces[y][x];
    }

    void setSpace(int x, int y, bool value)
    {
        spaces[y][x] = value;
    }

    Board(Board& other)
    {
        this->size = other.getSize();
        spaces = new bool*[size];
        for (int i = 0; i < size; ++i)
        {
            spaces[i] = new bool[size];
            for (int j = 0; j < size; ++j)
            {
                spaces[i][j] = other.getSpace(j, i);
            }
        }
    }

    void backtrack(vector<int>& state, int board_size)
  {
     int row = 0;
     int column = 0;
     bool backtrack = false;

     while(column < board_size)
     {
        while(row < board_size)
        {
           if(backtrack)
           {
              row = state[column] + 1;
              if(row == board_size)
              {
                 column--; //backtrack more
                 backtrack = true;
                 row = 0;
                 break;
              }

              backtrack = false;
           }

           if(isSafe(row, column, state))
           {
              state[column] = row;
              row = 0;
              column++; //advance
              backtrack = false;
              break;
           }

           else
           {
              if(row == (board_size - 1))
              {
                 column--; //backtrack
                 backtrack = true;
                 row = 0;
              }
              else
              {
                 row++;
              }
           }
        }
     }
  }
};

int print_solutions(Board *board, vector<int>& state, int board_size)
{
   for(int i=0; i < board_size; ++i)
   {
      for(int j=0; j < board_size; ++j)
      {
         if(state[i] == j)
            cout << 'Q' << " ";
         else
            cout << '_' << " ";
      }

      cout << endl;
   }
}   

int main(int argc, char* argv[])
{
    if (argc < 2)
    {
        cout << "Usage: nqueens [Board Size] [Number of Solutions]" << endl;
    return 1;
    }

    int board_size = atoi(argv[1]);
    //int solution_count = atoi(argv[2]);
    vector<int> state;
    state.resize(board_size);

    Board *my_board = new Board(board_size);
    my_board->backtrack(state, board_size);

    print_solutions(my_board, state, board_size);

    return 0;
}
4

4 回答 4

2

在这个解决方案中，我保留了大部分原始方法和代码：

#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <vector>
#include <iostream>

using namespace std;

class Board
{
private:
    bool** spaces;
    int size;

public:
    Board(int size)
    {
        this->size = size;
        spaces = new bool*[size];
        for (int i = 0; i < size; ++i)
        {
            spaces[i] = new bool[size];
        }
    }

    bool isSafe(int row, int column, vector<int>& state)
    {
       //check row conflict
       //no need to check for column conflicts
       //because the board is beimg filled column
       //by column
       for(int i = 0; i < column; ++i)
       {
          if(state[i] == row)
             return false;
       }

       //check for diagonal conflicts
       int columnDiff = 0;
       int rowDiff = 0;
       for(int i = 0; i < column; ++i)
       {
          columnDiff = abs(column - i);
          rowDiff = abs(row - state[i]);
          if(columnDiff == rowDiff)
             return false;
       }

       return true;

    }

    int getSize()
    {
        return size;
    }

    bool getSpace(int x, int y)
    {
        return spaces[y][x];
    }

    void setSpace(int x, int y, bool value)
    {
        spaces[y][x] = value;
    }

    Board(Board& other)
    {
        this->size = other.getSize();
        spaces = new bool*[size];
        for (int i = 0; i < size; ++i)
        {
            spaces[i] = new bool[size];
            for (int j = 0; j < size; ++j)
            {
                spaces[i][j] = other.getSpace(j, i);
            }
        }
    }

    bool backtrack(vector<int>& state, int& column, int board_size)
  {
     int row = 0;
     bool backtrack = column == board_size;

     while(column < board_size || backtrack)
     {
        {
           if(backtrack)
           {
              if (column == 0)
                 return false;
              column--;
              row = state[column] + 1;
              if(row == board_size)
              {
                 backtrack = true;
                 continue;
              }

              backtrack = false;
           }

           if(isSafe(row, column, state))
           {
              state[column] = row;
              row = 0;
              column++; //advance
              backtrack = false;
              continue;
           }

           else
           {
              if(row == (board_size - 1))
              {
                 backtrack = true;
              }
              else
              {
                 row++;
              }
           }
        }
     }
     return true;
  }
};

void print_solutions(Board *board, vector<int>& state, int board_size)
{
   for(int i=0; i < board_size; ++i)
   {
      for(int j=0; j < board_size; ++j)
      {
         if(state[i] == j)
            cout << 'Q' << " ";
         else
            cout << '_' << " ";
      }

      cout << endl;
   }
    cout << endl;
}   

int main(int argc, char* argv[])
{
    if (argc < 3)
    {
        cout << "Usage: nqueens [Board Size] [Number of Solutions]" << endl;
    return 1;
    }

    int board_size = atoi(argv[1]);
    int solution_count = atoi(argv[2]);
    vector<int> state;
    state.resize(board_size);

    Board *my_board = new Board(board_size);
    int column = 0;
    while (solution_count-- > 0 && my_board->backtrack(state, column, board_size))
        print_solutions(my_board, state, board_size);

    return 0;
}
  • 修复：编译错误：cout 未知 -> #includeiostream
  • 添加：额外的换行符print_solutions以分隔多个解决方案
  • 固定：print_solutions打印转置表
  • 固定：编译错误：print_solutions不返回值->void
  • 固定：argc检查
  • 补充：solution_count通过移动column到呼叫站点的支持
  • 固定：回溯代码重复（column--，row = 0）
  • 固定：不必要的内循环（row < board_size）
  • 未修复：my_board已泄露
  • 不固定：整个Board类及其实例是不必要的
于 2013-11-17T02:08:51.223 回答
2

这是我的蛮力递归解决方案。它不是最优的（没有回溯），但对于最大 14 x 14 的棋盘来说效果很好。在递归方法queensSolution中，第一个参数是棋盘的大小。第二个参数编码皇后的实际位置。

例如，描述图片上位置的向量将是 {1, 3, 0, 2}。这意味着：在第一行（计数从 0 开始，因此它是向量的第一个元素），皇后位于位置 1（左起第二个样方），第二行（向量中的第二个元素）放置一个皇后在位置 3（该行的最后一个样方）等。

在此处输入图像描述

第三个参数包含将包含所有解决方案位置的向量（如上所述编码为向量）。help 方法intersect检查将放置在位置 {queens.size(), x} 上的新皇后之间是否存在碰撞。当新皇后与任何现有皇后在同一“列”（x 位置）上，或者新皇后与任何现有皇后的 x 位置和 y 位置之间的距离是否相等（对角线位置）时，就会发生碰撞。我们不必检查新皇后是否会被放置在已经放置了其他皇后的行 (y) 中，因为每次我们向queens向量中添加一个元素时，我们都会将其放入新行中。

#include<vector>
using namespace std;

bool intersect(const vector<int> &queens, int x) {
    int y = queens.size();
    for (int i = 0; i < y; i++) {
        if ((abs(queens[i] - x) == 0) || (abs(queens[i] - x) == y - i))
            return true;
    }
    return false;
}

void queensSolution(const int dim, vector<int> queens, vector<vector<int>> &res) {
    if (queens.size() >= dim) {
        res.push_back(queens);
        queens.clear();
        return;
    }
    for (int i = 0; i < dim; i++) {
        if (!intersect(queens, i)) {
            queens.push_back(i);
            queensSolution(dim, queens, res);
            queens.pop_back();
        }
    }
}

例如，要查找 4 x 4 棋盘的所有解决方案，请执行以下操作：

int main(){
  int dim = 4;
  vector<int>queens;
  vector<vector<int>> result;
  queensSolution(dim, queens, result);
}

返回后queensSolution，向量结果包含两个向量：{1, 3, 0, 2}和{2, 0, 3, 1}。

于 2018-10-02T14:16:20.550 回答
1

您可以使用递归方法来解决它。我写了一篇关于此的文章：递归教程：C 中的 N-queens。要获得所有解决方案，只需运行递归而不终止找到的第一个解决方案。

这里还有一个启发式解决方案：八皇后拼图。

于 2013-11-17T16:16:42.770 回答
0

Check this gist. It's a simple recursive function that returns all the solutions. It works by placing each time a queen a the next row. The method is_safechecks if it is safe to place a queen at column col in the next row. The solution are vector where the index i is the row and the value at that index is the column. Each time a queen is placed successfully, the vector grows by one element and is added to the set of candidate solutions which are returned back up in the recursive calls stack.

于 2014-03-02T01:02:58.237 回答