人工智能中的N皇后问题?
做一个DEV的小程序,解决N皇后问题,要求是要求使用DFS /BFS /启发式搜索三种.
能做的可以跟我联系 qq:532196770,必有重谢.
[解决办法]
http://blog.csdn.net/alai04/archive/2006/05/06/711111.aspx
用STL实现先深搜索及先宽搜索
——N皇后问题例子
符合你的要求，自己看看完整算法吧
[解决办法]
#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 ;
}
