八皇后问题
【题目描述】
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线(对角线)上，问有多少种摆法。
【输入描述】
无
【输出描述】
一共有多少种摆法
【样例输入】
无
【样例输出】
92
【题目分析】
(1)框架分析
放置第ｉ个(行)皇后的算法为：
int search(i)；
{
int j;
for (第i个皇后的位置j=1;j<=8;j++ ) //在本行的8列中去试
if (本行本列允许放置皇后)
{
放置第i个皇后；
对放置皇后的位置进行标记；
if (i==8) 输出 //已经放完个皇后
else search(i+1)； //放置第i+1个皇后
对放置皇后的位置释放标记，尝试下一个位置是否可行；
}
}(2)
主要解决几个问题： 冲突：包括行、列、两条对角线 行：规定每行放一个皇后，不会造成行上的冲突 列：当第col列被某个皇后占领后，则同一列上所有位置不在放皇后，要把 flag[col] 置为被占领状态。 对角线：对角线有两个方向。当第n行第col列皇后占领后，上下对角线标记 为被占领状态。
规律：左上到右下，我们叫主对角线，同一主对角线i-j是个常数。右上到左下，我们称为副对角线，同一副对角线i+j是个常数。所以,
左上到右下： i-j+7 （C++ 不支持负数）
右上到左上： i+j
(3)
1.初始化（清除棋盘） 2.循环8次 放置一个皇后； 检查是否满足条件，如满足，登记皇后位置； 如不满足，则退回，增加一步后在放皇后。 3. 知道放置最后一个皇后
【参考代码1】
用col表示列，L_diagonal表示主对角线(就是左上到右下),R_diagonal表示副对角线(就是右上到左下)
#include<iostream>
using namespace std;
int col[10],L_diagonal[10],R_diagonal[10]; //分别表示标记数组，列数组，主对角线数组，副对角线数组
int ans[10]; //结果数组
int sum;
int dfs(int i)//用i来表示皇后所处的行位置
{
int j; //用j表示皇后所处的列位置
for(j=1;j<=8;j++)
if((col[j]==0)&&(L_diagonal[i-j+7]==0)&& (R_diagonal[i+j]==0))// 列、主对角线、副对角线没有被占领过
{
ans[i]=j; //在当前(i,j)位置上摆放一个皇后
col[j]=1; //占领当前(i,j)所在的列
L_diagonal[i-j+7]=1; //占领当前(i,j)所在的主对角线
R_diagonal[i+j]=1; //占领当前(i,j)所在的副对角线
if(i==8)
{
//print(); //此题没有要求输出
sum++; //摆放种数加1
}
else
dfs(i+1);
col[j]=0; //回溯(i,j)所在的列
L_diagonal[i-j+7]=0; //回溯当前(i,j)所在的主对角线
R_diagonal[i+j]=0;//回溯当前(i,j)所在的副对角线
}
}
int main()
{
dfs(1);
cout<<sum<<endl;
return 0;
}
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。