Bài toán này là tìm cách sắp xếp N quân hậu trên bàn cờ sao cho không quân hậu nào có thể tấn công bất kỳ quân hậu nào khác trên bàn cờ.
Các quân cờ có thể tấn công theo bất kỳ hướng nào như ngang, dọc, ngang và chéo.
Một ma trận nhị phân được sử dụng để hiển thị vị trí của N Nữ hoàng, nơi không có nữ hoàng nào có thể tấn công các nữ hoàng khác. Ở đây, chúng tôi giải quyết vấn đề 8 nữ hoàng.
Đầu vào
Kích thước của một bàn cờ vua. ở đây là 8 vì (8 x 8 là kích thước của một bàn cờ vua bình thường).
Đầu ra
Ma trận đại diện cho hàng và cột N có thể được đặt.
Nếu giải pháp không tồn tại, nó sẽ trả về 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
Trong đầu ra này, giá trị 1 cho biết vị trí chính xác cho các nữ hoàng.
Số 0 biểu thị các khoảng trống trên bàn cờ.
Thuật toán
isValid (board, row, col)
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
giải quyếtNQueen (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
Ví dụ
#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();
} Đầu ra
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