N皇后问题
这个问题是在国际象棋棋盘上找到N个皇后的排列，以使没有一个皇后可以攻击棋盘上的任何其他皇后。
象棋皇后可以沿水平，垂直，水平和对角线的任何方向进攻。
二进制矩阵用于显示N个皇后的位置，其中没有皇后可以攻击其他皇后。
输入输出
Input: The size of a chess board. Generally, it is 8. as (8 x 8 is the size of a normal chess board.) Output: The matrix that represents in which row and column the N Queens can be placed. If the solution does not exist, it will return 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 In this output, the value 1 indicates the correct place for the queens. The 0 denotes the blank spaces on the chess board.
算法
isValid（板，行，列）
输入： 棋盘，棋盘的行和列。
输出- 将女王/王后排成一排并且放置位置是否有效时为True。
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
EndresolveNQueen(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 8
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