八皇后问题

灰太狼 2022-09-19 15:20 15阅读 0赞

**八皇后问题**

**作者：** **Ackarlix**

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯 1850 年提出：在 8X8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

高斯认为有 76 种方案。 1854 年在柏林的象棋杂志上不同的作者发表了 40 种不同的解，后来有人用图论的方法解出 92 种结果。

算法一：递归实现 n 皇后问题

算法分析：   
 数组 a 、 b 、 c 分别用来标记冲突， a 数组代表列冲突，从 a\[0\]~a\[7\] 代表第 0 列到第 7 列，如果某列上已经有皇后，则为 1 ，否则为 0 ；   
 数组 b 代表主对角线冲突，为 b\[i-j+7\] ，即从 b\[0\]~b\[14\] ，如果某条主对角线上已经有皇后，则为 1 ，否则为 0 ；   
 数组 c 代表从对角线冲突，为 c\[i+j\] ，即从 c\[0\]~c\[14\] ，如果某条从对角线上已经有皇后，则为 1 ，否则为 0 。

程序如下：

＃ i nclude <stdio.h>

static char Queen\[8\]\[8\];  
static int a\[8\];  
static int b\[15\];  
static int c\[15\];  
static int iQueenNum=0; // 记录总的棋盘状态数

void qu(int i); // 参数 i 代表行

int main()  
\{  
int iLine,iColumn;

// 棋盘初始化，空格为 \* ，放置皇后的地方为 @  
for(iLine=0;iLine<8;iLine++)  
\{  
a\[iLine\]=0; // 列标记初始化，表示无列冲突   
for(iColumn=0;iColumn<8;iColumn++)  
Queen\[iLine\]\[iColumn\]='\*';  
\}

// 主、从对角线标记初始化，表示没有冲突   
for(iLine=0;iLine<15;iLine++)  
b\[iLine\]=c\[iLine\]=0;

qu(0);  
return 0;  
\}

void qu(int i)  
\{  
int iColumn;

for(iColumn=0;iColumn<8;iColumn++)  
\{  
if(a\[iColumn\]==0&&b\[i-iColumn+7\]==0&&c\[i+iColumn\]==0) // 如果无冲突   
\{  
Queen\[i\]\[iColumn\]='@'; // 放皇后   
a\[iColumn\]=1; // 标记，下一次该列上不能放皇后   
b\[i-iColumn+7\]=1; // 标记，下一次该主对角线上不能放皇后   
c\[i+iColumn\]=1; // 标记，下一次该从对角线上不能放皇后   
if(i<7) qu(i+1); // 如果行还没有遍历完，进入下一行   
else // 否则输出   
\{  
// 输出棋盘状态   
int iLine,iColumn;  
printf(" 第 %d 种状态为： /n",++iQueenNum);  
for(iLine=0;iLine<8;iLine++)  
\{  
for(iColumn=0;iColumn<8;iColumn++)  
printf("%c ",Queen\[iLine\]\[iColumn\]);  
printf("/n");  
\}  
printf("/n/n");  
\}  
  
// 如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置   
Queen\[i\]\[iColumn\]='\*';  
a\[iColumn\]=0;  
b\[i-iColumn+7\]=0;  
c\[i+iColumn\]=0;  
\}  
\}  
\}

算法二：用栈实现的 n 皇后问题

＃ i nclude<iostream.h>  
 ＃ i nclude<fstream.h>  
/\*=== 定义栈与操作 ==------------------\*/  
struct Stack \{  
Stack \*top;  
int row;  
int col;  
\}\*Top;  
  
void Push(int row,int col);  
void Pop();  
/\*===== 栈的定义完毕 ==---------------\*/

\#define MAXQUEEN 8  
/\*======= 三个冲突数组确定是否能放置皇后   
\*\*///0 表示无冲突， 1 表示有冲突   
static int a\[MAXQUEEN\];// 列冲突   
static int b\[MAXQUEEN\*2-1\];// 主对角线冲突   
static int c\[MAXQUEEN\*2-1\];// 副对角线冲突   
static int d\[MAXQUEEN\];  
/\*======\*\*/  
  
void SetQueen(int row,int col);// 放置皇后后在该处设置冲突   
void DeSetQueen(int row,int col);  
bool NoConflict(int row,int col);// 判断该位置放置皇后   
// 是否与其他皇后冲突   
  
//  
char ArrayQueen\[MAXQUEEN\]\[MAXQUEEN\];  
ofstream outQueen;// 定义一个输出文件流   
void DisplayAndSet();  
//  
bool Queen();  
//  
void main()  
\{  
  
Top = new Stack;  
Top->top=NULL;  
  
outQueen.open("queen.txt",ios::out,filebuf::openprot);  
for(int x=0;x<MAXQUEEN;x++)  
for(int y=0;y<MAXQUEEN;y++)  
ArrayQueen\[x\]\[y\]='\*';  
cout<<" 结果在 queen.txt 文件中 "<<endl;  
cout<<MAXQUEEN<<" 皇后问题是否有解有解？： "<<Queen()<<endl;  
outQueen.close();  
\}  
//  
bool Queen()  
\{  
int count = 0;// 计数器   
int col = 0;// 最初从 0 列开始   
int precolrow\[MAXQUEEN\] = \{0\};// 记录每一列上次的行数，全部初始化为 0  
while( col<MAXQUEEN )  
\{  
int row=precolrow\[col\];// 从该列上一次记录的行数开始循环   
while(row<MAXQUEEN)  
\{  
if(NoConflict(row,col))// 判断该位置是否发生冲突   
\{  
Push(row,col);// 将皇后位置压入栈   
SetQueen(row,col);// 设置该方位有冲突   
if(col==MAXQUEEN-1)// 判断是否找到   
\{  
count++;// 计数器   
outQueen<<" 第 "<<count<<" 种情况 :"<<endl;  
DisplayAndSet(); // 输出状态，还原空白棋盘   
DeSetQueen(row,col); // 将第八个皇后冲突数组置 0  
Pop(); // 开始寻找下一个状态   
precolrow\[col\]=row+1;col--; // 最后一列， row+1 行在重新开始寻找   
break;// 跳出行循环，重新开始列循环   
\}  
  
precolrow\[col\]=row;// 记录该列的行   
break;// 跳出，进行下一次列循环   
  
\}row++;// 如果发生冲突，继续行循环   
  
\}  
  
if(row<MAXQUEEN)// 继续下一列循环   
col++; // 如果 row 等于了 MAXQUEEN, 也就是说，该列无法放置皇后 ,  
else // 需弹出前一列的皇后，   
// 而且从前一列再开始循环，并从被弹出的皇后那一行的下一行开始行循环   
\{  
Pop();  
precolrow\[col\]=0;  
\--col;  
DeSetQueen(precolrow\[col\],col);  
precolrow\[col\]++;  
  
\}  
if(precolrow\[0\]==MAXQUEEN&&count>0)// 控制结束   
return true;  
if(precolrow\[0\]==MAXQUEEN)  
return false;  
  
\}  
return true;  
\}

void SetQueen(int row,int col)  
\{  
a\[col\]=1;  
b\[row+col\]=1;  
c\[row-col+MAXQUEEN-1\]=1;  
d\[row\]=1;  
\}

void DeSetQueen(int row,int col)  
\{  
a\[col\]=0;  
b\[row+col\]=0;  
c\[row-col+MAXQUEEN-1\]=0;  
d\[row\]=0;  
\}

bool NoConflict(int row,int col)  
\{  
if(a\[col\]!=1&&b\[row+col\]!=1&&c\[row-col+MAXQUEEN-1\]!=1&&d\[row\]!=1)  
return true;  
return false;  
\}

void DisplayAndSet()  
\{  
Stack \*temp=Top->top;  
for(int x=0;x<MAXQUEEN;x++,temp=temp->top)  
ArrayQueen\[temp->row\]\[temp->col\]='@';  
for( x=0;x<MAXQUEEN;x++)  
\{ for(int y=0;y<MAXQUEEN;y++)  
outQueen<<ArrayQueen\[x\]\[y\]<<' ';  
outQueen<<'/n';  
\}  
temp=Top->top;  
for(x=0;x<MAXQUEEN;x++,temp=temp->top)  
ArrayQueen\[temp->row\]\[temp->col\]='\*';  
\}

void Push(int row,int col)  
\{  
Stack \*s = new Stack;  
s->row = row;  
s->col = col;  
s->top = Top->top;  
Top->top = s;  
  
\}

void Pop()  
\{  
if(Top->top!=NULL)  
\{  
Stack \*temp=Top->top;  
Top->top = temp->top;  
delete temp;  
\}  
\}

输出结果有 92 种状态