#include<iostream.h>
const int n = 15 ; //15皇后问题.改动n可变成N皇后问题
const int n_sub = n - 1 ;
int queen[n] ; //N个棋子.N对应每一列,如n=0的棋子只下在0列,1下1....类推
bool row[n] ; //棋局的每一行是否有棋,有则为1,无为0 ;
bool passive[2*n-1] ; //斜率为1的斜线方向上是不是有皇后
bool negative[2*n-1] ; //斜率为负1的斜线方向上是不是有皇后.
//之所以用全局变量,因全局数组元素值自动为0
int main()
{
int cur = 0 ;//游标,当前移动的棋子(哪一列的棋子)
bool flag = false ; //当前棋子位置是否合法
queen[0] = -1 ; //第0列棋子准备,因一开始移动的就是第0列棋子
int count = 0 ; //一共有多少种下法 ;
cout<<"============================Starting============================="<<endl ;
while(cur>=0)
{
while(cur>=0 && queen[cur]<n && !flag) //当还不确定当前位置是否可下
{
queen[cur]++ ;
// cout<<"第"<<cur<<"列棋子开始走在第"<<queen[cur]<<"行"<<endl ;
// cin.get() ;
if(queen[cur] >= n) { //如果当前列已经下完(找不到合法位置)
// cout<<"当前行是非法行,当前列棋子走完,没有合法位置,回溯上一列棋子"<<endl ;
// cin.get() ;
queen[cur] = -1 ; //当前列棋子置于准备状态
cur-- ; //回溯到上一列的棋子
if(cur>=0) {
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
//由于要移下一步,所以回溯棋子原位置所在行应该没有棋子啦.置row[]为false
//并且棋子对应的斜线的标志位passive[cur]和negative[cur]也应该要设为false ;
}
else {
//先判断棋子所在行没有棋子
if(row[queen[cur]] == false) { //当前行没有棋子
// cout<<"棋子"<<cur<<"所在行没有其他棋子,正在检查斜线"<<endl ;
flag = true ; // 暂设为true,或与之前棋子斜交,则再设为false ;
//以下检查当前棋子是否与之前的棋子斜线相交
if( passive[queen[cur] + cur] == true || negative[n_sub + cur - queen[cur]] == true) {
flag = false ;
// cout<<"出现斜线相交,该位置不合法"<<endl ;
}
else
flag = true ;
if(flag) { //没有斜交,位置合法
// cout<<"斜线也没有相交,该位置合法"<<endl ;
if(cur == n-1) //如果是最后一个棋子
{
// cout<<"棋子走完一轮,总走法加1"<<endl ;
count++ ; //总走法加一 ;
}
row[queen[cur]] = true ;// 当前行设为有棋子
passive[queen[cur] + cur] = true ;//当前行正斜率方向有棋子
negative[n_sub + cur - queen[cur]] = true ; //当前行负斜率方向上也有棋子
cur++ ;
if(cur >= n) {
cur-- ;
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;//原理同回溯
}
flag = false ;
}
}
}//else
}
}
cout<<n<<"皇后问题一共有"<<count<<"种解法"<<endl ;
return 0 ;
}
//计算15皇后用时1分钟15秒
//把n改成16,测16皇后用时大约8分钟
//以上测试在Barton 2000+,KingstonDDR400 256M下测试
/*
斜线判断如下:
正斜率对应数组passive[2*n-1] ;
0 1 2 3.... . n
1 2 3 4..... n+1
2 3 4 5.... .n+2
3 4 5 6..... n+3
....................
n-1 n n+1 n+2...2*n-1
利用行和列的坐标相加,即可得到其对应斜线对应的passive[i].再看一下passive[i]是否为1即可知道该斜线上是否有其他棋子.
负斜率判断如下
负余率对应数姐negative[2*n-1]
n-1 n n+1 n+2...2*n-1
..............................
3 4 5 6.... n+3
2 3 4 5.... .n+2
1 2 3 4..... n+1
0 1 2 3.... . n
用棋子所在位置的横坐标(cur)减去纵坐标(queen[cur]),再加上n-1,即可得到对应的
negative[i]数组,若为1,则该行有棋子.
*/