递归算法之八皇后
八皇后问题核心:
1:同一行或者同一列不能放置皇后;
2:斜率为1/-1的对角线上不能有两个皇后。
如图:
实现原理:
#include<iostream>
#include<cstdio>
using std::cout;
using std::endl;
int count = 0;
int detection(int(*board)[8], int line, int row)//board:棋盘,line:行,row:列
{
int i;
int b1,b2;//y=kx+b
int flag1,flag2,flag3;
flag1 = flag2=flag3=0;//标志变量
//判断列
for (i = 0; i < 8; i++)
{
if (board[i][row] != 0)//判断第第row列每行元素是否为0
{
flag1 = 1;//设置标志位
break;//退出
}
}
//斜率为1/-1对角线判断
b1 = row - line;//y=kx+b
b2 = line + row;//y=-kx+b
for (int j = 0; j <line; j++)//遍历行
{
if (flag2 == 1)//如果找到不合理情况则没必要继续
break;//退出行
for (int k = 0; k < 8; k++)//遍历列
{
if (board[j][k] == 1)//检测j行k列中数据为1的元素
if (k - j - b1 == 0 || k + j - b2 == 0) // 如果该元素满足该点方程则本次放置不合理(双对角线同时检测)
{
flag2 = 1;//设置标志位
break;//退出本次列循环
}
}
}
if (flag1 || flag2 )
return 0;//只要有一种情况使得标志位flag为1那么久返回0;不满足
else
return 1;//满足返回1
}
int recursive(int(*board)[8], int line, int row)//board:棋盘,line:行,row:列 递归函数
{
int board2[8][8];//临时棋盘
int n;//临时列
for (int i = 0; i < 8;i++)//拷贝传入递归中的棋盘
for (int j = 0; j < 8; j++)
board2[i][j] = board[i][j];
if (line == 8)//递归结束条件,第七行放置完毕line=8;
{
count++;//方法总数
for (int i = 0; i < 8; i++)//打印每一种方法
{
for (int j = 0; j < 8; j++)
cout << board[i][j] << " ";
cout << endl;
}
cout << count << endl;
}
else//递归调用
{
for (n = 0; n < 8; n++)//n:临时列,一次穷举每一行中符合方案的每一列的放置
{
if (detection(board2, line, n) != 0)//检测是否可以放置
{
for (int k = 0; k < 8; k++)//将可以放的第line行其他元素清0,好处:不会存在当我们回退一级递归时不会出现
board2[line][k] = 0; //同一行中放置两个1,返回上一级递归时我们将前一次不满足的放置清0
board2[line][n] = 1; //放置元素
recursive(board2, line + 1, n);//不可用line++;line++会改变前一次的递归调用总的line这样当有错误方案时line无法后退
} //line+1:前一级的递归函数中的line没有被改变
}
}
return 0;
}
void main()
{
int board[8][8] = { 0 };
int line=0;//行
int row=0;//列
recursive(board, line, row);
system("pause");
}
转载请标明原贴出处:https://blog.****.net/zj490044512