8皇后问题实现思路:用一个二维数组board[8][8]来表示棋盘、二维数组中的元素来表示方格,因此board[0][0]、board[0][1]、、、board[7][7]一共64个元素分别代表棋盘上64个方块。board[i][j]=1代表棋盘上第i行第j列的方格放置皇后了,board[i][j]=0代表棋盘上第i行第j列的方格没有皇后,其中0<=i<=7,0<=j<=7。
皇后的攻击范围见下图(5角星代表皇后):
程序实现见源代码:
#include"iostream" using namespace std; #include "stdlib.h" #define QUEUE_NUM 8 #define QUEUE 1 #define NO_QUEUE 0 void handle(void); int main(void) { handle(); return 0; } //判断当前位置所在的列、斜线上是否安全 安全返回true 不安全返回false bool is_safe(bool(*board)[QUEUE_NUM],int row,int col) { bool col_flag = false; bool diag_flag = false; //当前位置所在的列是否有皇后 for(int i=0;i<QUEUE_NUM;i++) { if(board[i][col] == QUEUE) { col_flag = true; break; } } //当前位置所在的斜线上是否有皇后 for(int i=0;i<QUEUE_NUM;i++) { for(int j=0;j<QUEUE_NUM;j++) { if(abs(j-col) == abs(i-row)) //在一条斜线上时斜率相等 { if(board[i][j] == QUEUE) { diag_flag = true; break; } } } } if(col_flag || diag_flag) { return false; } else { return true; } } /************************************************************************ (*board)[QUEUE_NUM]: 指向棋盘行的指针 row: 在第row行放置皇后 scheme_num: 摆放的方案数 /************************************************************************/ void queue(bool(*board)[QUEUE_NUM],int row,int& scheme_num) { //另开辟存储空间,存储当前方案。避免修改以前的方案 bool cur_board[QUEUE_NUM][QUEUE_NUM]; for(int i=0;i<QUEUE_NUM;i++) { for(int j=0;j<QUEUE_NUM;j++) { cur_board[i][j] =board[i][j]; } } if(QUEUE_NUM == row) { //皇后已经放置完,输出当前方案 scheme_num++; cout<<"第"<<scheme_num<<"种放置方案:"<<endl; for(int i=0;i<QUEUE_NUM;i++) { for(int j=0;j<QUEUE_NUM;j++) { cout<<cur_board[i][j]<<' '; } cout<<endl; } cout<<endl<<endl; } else { for(int col=0;col<QUEUE_NUM;col++) { //判断当前位置所在的列与斜线上是否危险 if(is_safe(cur_board, row, col)) { //保证当前位置所在的行没有皇后 for(int j=0;j<col;j++) { cur_board[row][j] = NO_QUEUE; } //在当前位置放置皇后 cur_board[row][col] = QUEUE; queue(cur_board,row+1,scheme_num); } } } } void handle(void) { //board是一个二维数组用来表示一个棋盘、元素为1表示该位置已经放置了皇后、为0表示该位置没有放置皇后 bool board[QUEUE_NUM][QUEUE_NUM]; for(int row=0;row<QUEUE_NUM;row++) { for(int col=0;col<QUEUE_NUM;col++) { board[row][col] =NO_QUEUE; } } int scheme_num = 0; queue( board, 0, scheme_num); }