이 문제는 체스판에서 N개의 퀸을 배열하여 어떤 퀸도 보드의 다른 퀸을 공격할 수 없도록 하는 것입니다.
체스 퀸은 가로, 세로, 가로, 대각선 어느 방향으로든 공격할 수 있습니다.
이진 행렬은 퀸이 다른 퀸을 공격할 수 없는 N 퀸의 위치를 표시하는 데 사용됩니다. 여기에서 8개의 퀸즈 문제를 풉니다.
입력
체스판 크기. (8 x 8은 일반 체스판 크기)와 같이 여기에서 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
solveNQueen(보드, 열)
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