/*八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。*/
//如果N个对象的列号,行号,正对角序号,逆对角序号都没有重复,则满足要求
#include<iostream>
#define N 8
using namespace std;
int u[N+1]={0},l[2*(N+1)]={0},r[2*(N+1)]={0},cnt=0;//前三个数组是判断该对象的行号,正对角序号,逆对角序号是否与之前对象有重复
class Queen
{
int x,y,m,n;//列号,行号,正对角序号,逆对角序号
public:
Queen():x(0),y(0),m(0),n(0){}
int judge()//判断该对象的行号,正对角序号,逆对角序号是否与之前对象有重复
{
return (!u[y]&&!l[m]&&!r[n]);
}
void goOne()//置1,表示被占用
{
u[y]=l[m]=r[n]=1;
}
void goZero()//置0,表示没被占用
{
u[y]=l[m]=r[n]=0;
}
void setxy(int a,int b)
{
x=a;y=b;m=a-b+N;n=a+b;
}
void print()
本内容试读结束,登录后可阅读更多
下载后可阅读完整内容,剩余2页未读,立即下载