資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時裝學
法律學C++ 程式，解決 N 後問題
這個問題是要在棋盤上找到 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(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
solveNQueen(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
更新於： 30-Jul-2019
11K+ 觀看次數
廣告