八皇后问题 1.问题描述 设在初始状态下在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第1 行，第2 行……第8 行上布放棋子。在每一行中共有8 个可选择的位置，但在任一时刻棋盘的合法布局都必须满足 3 个限制条件（1）任意两个棋子不得放在同一行（2）任意两个棋子不得放在同一列上（3）任意棋子不得放在同一正斜线和反斜线上。 2.基本要求 编写求解并输出此问题的一个合法布局的程序。 3、实现提示： 在第i 行布放棋子时，从第1 列到第8 列逐列考察。当在第i 行第j 列布放棋子时，需要考察布放棋子后在行方向、列方向、正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在第i+1 行布放棋子；若该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再试探在第i 行第j+1 列布放棋子。 4 程序代码 #inclu de #inclu de static char Qu een[8][8]; static int a[8]; static int b[15]; static int c[15]; static int Qu eenNu m=0; //记录总的棋盘状态数 v oid qu (int i); //参数 i 代表行 int main() { int Line,Column; //棋盘初始化，空格为*，放置皇后的地方为@ for(Line=0;Line<8;Line++) { a[Line]=0; //列标记初始化，表示无列冲突 for(Column=0;Column<8;Column++) Queen[Line][Column]='*'; } //主、从对角线标记初始化，表示没有冲突 for(Line=0;Line<15;Line++) b[Line]=c[Line]=0; qu(0); return 0; } void qu(int i) { int Column; for(Column=0;Column<8;Column++) { if(a[Column]==0&&b[i-Column+7]==0&&c[i+Column]==0) //如果无冲突 { Queen[i][Column]='Q'; //放皇后 a[Column]=1; //标记，下一次该列上不能放皇后 b[i-Column+7]=1; //标记，下一次该主对角线上不能放皇后 c[i+Column]=1; //标记，下一次该从对角线上不能放皇后 if(i<7) qu(i+1); //如果行还没有遍历完，进入下一行 else //否则输出 { //输出棋盘状态 int Line,Column; cout<<"第"<<++QueenNum<<"种状态为："<
VIP
