算法 n皇后 求详细解答 n皇后问题回溯算法
高分求人工智能N皇后回溯算法vb程序,明早之前!
应该可以的，如果有空可以把“\”删掉，不影响大局
C++:用分支界限法解决n皇后问题(急)
#include<iostream.h>
#include<time.h>
#include<math.h>
long sum=0;
int count=0;
int place(int k,int*p)
{
for(int j=1;j<k;j++)
if((abs(k-j)==abs(p[j]-p[k]))||(p[j]==p[k])) return 0;
return 1;
}
void backtrack(int*p,int n)
{
p[1]=0;
int k=1;
while(k>0){
p[k]+=1;
while((p[k]<=n)&&!(place(k,p))){p[k]+=1;count++;}
if(p[k]<=n)
if(k==n) sum++;
else{
k++;
p[k]=0;
}
else k--;
}
}
void main()
{
int n,*p;
clock_t start,end;
cout<<"输入皇后的个数,n=";
cin>>n;
p=new int[n+1];
for(int i=0;i<=n;i++) p[i]=0;
start=time(0);
backtrack(p,n);
end=time(0);
cout<<"经过时间:"<<difftime(end,start)<<"秒"<<endl
<<"有"<<sum<<"种方案!"<<endl
<<"搜索结点次数为:"<<count<<endl;
}
谁有n皇后问题的答案？
八皇后问题程序及注解
www.mydrs. 2003-12-3 大榕树
大家一定见过这种办法吧 ,但是做为初学者理解起来特别困难 ,我就把我当时对它的理解简单说一下,不对的地方大家给个 建议!
program eightqueens;
var
x:array[1..8] of integer;
a,b,c:array[-7..16] of boolean;
i:integer;
procedure print;
var k:integer;
begin
for k:=1 to 8 do write(x[k]:4);
writeln;
end;
procedure try(i:integer);
var j:integer;
begin
for j:=1 to 8 do
if a[j] and b[i+j] and c[i-j]
then begin
x:=j;
a[j]:=false;
b[i+j]:=false;
c[i-j]:=false;
if i<8 then try(i+1)
else print;
a[j]:=true;
b[i+j]:=true;
c[i-j]:=true
end
end;
begin
for i:=-7 to 16 do
begin
a:=true;
b:=true;
c:=true
end;
try(1);
end. 现在循环从 i=1 ,j:=1 to 8 do 开始 此时 计算机检测到 i=1 j=1 简化为(1,1)为空,占用该位置并令该位置对应的斜线和水平方向的位置为 false ,然后程序就开始去执行try(2),注意此时计算机在i=1 这层仅仅走拉一个循环(j=1)就跳到拉i=2 这层里此时计算机从j:=1 to 8 do 又开始循环,排除 j=1,j=2 得到 (2,3)注意计算机在层里也只是走拉3(j=3)个循环然后又跳到拉i=3 这层依次类推得到(3,5),(4,2)(5,4)而在i=6 这层里计算机从j:= 1 to 8 do 都没有找到合适的位置,此时注意在i=6 这层里计算机计算机将返回到i=5 这层里,(因为用拉递归)并且释放(5,4)该位置,为什么要释放呢?因为原因很简单如果不释放的话 该位置对应的斜线和水平方向会对以后的几层造成影响,让计算机误认为为false.此时的在i=5这层里 j=4才是结束,然后计算机又会从j=5到 8 开始去找合适的位置 ,如果找不到又会返回到上一层依次类推直到计算机找到一组解 输出,假设在(8,3)这个位置是计算机找到的一组解,此时计算机又会从j=4到8 开始循环,如果找不到 计算机就会返回上一层的即i=7这层接着上一次的跳出位置走完以后的循环,依次类推不断的返回,跳出, 求解,(即令前几个位置不变,从第8个位置变换,没有空位置的.接会返回上一层)最后返回到i=1这层里,注意此时在这层里也只是走拉j=1个循环然后计算机就又开始从j= 2 去试着找....大家有没有算过求出所有的解要走过多少个循环?我想估计也不下1000个吧.其实整个过程就是一个重复的过程(即递归)倒着想在i=7 这层里的j=1 位置即(7,1) 计算机会去试从(8,1)到(8,8)这8 个位置,而在(7,2)也同样会去试这8 个位置 等等在(6,1)会试(7,1)到(7,8) 等. 这是正着考虑(1,1)这里计算机会试着从(2,1)到(2,8)这8个位置而在这8 个位置里并没有试完就有空位置 (2,3)此时计算机会在这个位置对下一层里开始试(3,1)..(3,8)依次类推,试不通的返回,接着走完上一层直到试完所有的位置!
PASCAL N皇后问题
n皇后问题（非递归）
top := 1; // 从第一个皇后开始尝试
while (top > 0) do // 当还有活动节点时循环
if (top > n) then // 是否n个皇后都放置在棋盘了
begin
inc(count); // 找到一组解，总数加一
dec(top); // 回到上一皇后继续
end
else // n个皇后还没有都放置好
begin
inc(x[top]); // 当前皇后到下一列
if (x[top] > n) then // 是否超出棋盘
dec(top) // 超出棋盘，回到上一个皇后继续
else // 没有超出棋盘
if check(top) then // 检查当前位置是否可以放皇后
begin
inc(top); // 可以放置，继续尝试下一个皇后
x[top] := 0; // 下一个皇后从第一列开始尝试
end;
end;
n皇后问题（边界判定）
function check(pos: integer): boolean;
var
i: integer;
begin
check := true;
for i := 1 to pos - 1 do
if (x[pos] = x[i]) or (abs(x[pos] - x[i]) = abs(pos - i)) then
begin
check := false;
break;
end;
end;
n皇后问题（递归）
procedure search(k: integer);
var
i: integer;
begin
if k > n then // 是否前n个皇后都已经放下
inc(count)
else // 还有皇后没放
for i := 1 to n do // 从第1列开始逐列尝试
begin
x[k] := i; // 把第k个皇后放在第i列
if check(k) then // 第k个皇后是否可以放在第i列
search(k + 1); // 可以放，继续处理第k+1个皇后
end;
end;