解决N皇后问题的C ++程序

这个问题是在国际象棋棋盘上找到N个皇后的排列，以使没有一个皇后可以攻击棋盘上的任何其他皇后。

象棋皇后可以沿水平，垂直，水平和对角线的任何方向进攻。

二进制矩阵用于显示N个皇后的位置，其中没有皇后可以攻击其他皇后。在这里，我们解决了8个皇后问题。

输入值

棋盘的大小。这里是8，因为（8 x 8是普通棋盘的大小）。

输出结果

代表可以放置N个皇后区的行和列的矩阵。

如果解决方案不存在，它将返回false。

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

在此输出中，值1表示皇后区的正确位置。

0表示国际象棋棋盘上的空格。

演算法

isValid（板，行，列）

Begin
   if there is a queen at the left of current col, then
      return false
   if there is a queen at the left upper diagonal, then
      return false
   if there is a queen at the left lower diagonal, then
      return false;
   return true //otherwise it is valid place
End

resolveNQueen(board,col)

Begin
   if all columns are filled, then
      return true
   for each row of the board, do
      if isValid(board, i, col), then
         set queen at place (i, col) in the board
         if solveNQueen(board, col+1) = true, then
            return true
         otherwise remove queen from place (i, col) from board.
      done
   return false
End

示例

#include<iostream>
using namespace std;
#define N 4
void printBoard(int board[N][N]) {
   for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++)
         cout << board[i][j] << " ";
         cout << endl;
   }
}
bool isValid(int board[N][N], int row, int col) {
   for (int i = 0; i < col; i++) //check whether there is queen in the left or not
      if (board[row][i])
         return false;
   for (int i=row, j=col; i>=0 && j>=0; i--, j--)
      if (board[i][j]) //check whether there is queen in the left upper diagonal or not
         return false;
   for (int i=row, j=col; j>=0 && i<N; i++, j--)
      if (board[i][j]) //check whether there is queen in the left lower diagonal or not
         return false;
   return true;
}
bool solveNQueen(int board[N][N], int col) {
   if (col >= N) //when N queens are placed successfully
      return true;
   for (int i = 0; i < N; i++) { //for each row, check placing of queen is possible or not
      if (isValid(board, i, col) ) {
         board[i][col] = 1; //if validate, place the queen at place (i, col)
         if ( solveNQueen(board, col + 1)) //Go for the other columns recursively
            return true;
         board[i][col] = 0; //When no place is vacant remove that queen
      }
   }
   return false; //when no possible order is found
}
bool checkSolution() {
   int board[N][N];
   for(int i = 0; i<N; i++)
   for(int j = 0; j<N; j++)
   board[i][j] = 0; //set all elements to 0
   if ( solveNQueen(board, 0) == false ) { //starting from 0th column
      cout << "Solution does not exist";
      return false;
   }
   printBoard(board);
   return true;
}
int main() {
   checkSolution();
}

输出结果

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