随笔-48  评论-259  文章-1  trackbacks-0

一、8皇后问题的分析   

 

8皇后问题实际上很容易一般化为n-皇后问题,即要求找出在一个n*n棋盘上放置n个皇后并使其不能互相攻击的所有方案。令(x1,x )表示一个解,其中x 是把第i个皇后放在第i行的列数。由于没有两个皇后可以放入同一列;因此这所有的xi将是截然不同的。那么应如何去测试两个皇后是否在同一条斜角钱上呢? 

    如果设想:棋盘的方格像二维数组a(1:n,1:n)的下标那样标记,那么可以看到,对于在同一条斜角线上的由左上方到右下方的每一个元素有相同的行一列值,同样,在同一条斜角线上的由右上方到左下方的每一个元素则有相同的+列值。假设有两个皇后被放置在(i,j)和(k,1)位置上,那么根据以上所述,仅当

        i-j=k-1或i+j=k+1

时,它们才在同一条斜角线上。将这两个等式分别变换成

       j-1=i-k 和 j-1=k-i

因此,当且仅当|j一1|=|ik|时,两个皇后在同一条斜角线上。

    过程Place(k)返回一个布尔值,当第k个皇后能放置于x(k)的当前值处时,这个返回值为真。这个过程测试两种情况,即x(k)是否不同于前面x(1),x(k-1)的值以及在同一条斜角线上是否根本就没有别的皇后。该过程的计算时间是

二、8皇后问题的算法  

 

[算法]: 可以放置一个新皇后吗?   [动画]

    procedure Place(k)

    //如果一个皇后能放在第k行和x(k)列,则返回.true;否则返回false。x是

    个全程数组,进入此过程时已置了k个值。abs(r)过程返回r的绝对值//

    global x(1:k);integer i;k

    iß1

    while i<k do

    if x(i)=x(k) //在同一列有两个皇后//

    or abs(x(i)-x(k))=abs(i-k) //在同一条斜角线上//

    then return(false)

    endif

    ißi+1

    repeat

    return(true)

    end Place

使用过程Place来改进以上算法给出的一般回溯方法,可得出下面求n皇后问题正确解的算法。

   [算法]: n皇后问题的所有解   [动画]

    procedure nqueens(n)

    //此过程使用回溯法求出在一个n*n棋盘上放置n个皇后,使其不能互相攻击

    的所有可能位置//

    integer k,n,x(1:n)

    x(1)ß0;kß1 //k是当前行;x(k)是当前列//

    whilek>0 do //对所有的行执行以下语句//

    x(k)ßx(k)+1 //移到下一列//

    while x(k)n and not Place(k) do //此处能放这个皇后吗/

    x(k)+x(k)+1

    repeat

    ifx(k)n //找到一个位置//

    then if k=n //是一个完整的解吗//

    thenprint(x) //是,打印这个数组//

                  elsek<--k+1;x(k)+0 //转向下一行//

    endif

    else kßk-1 "回溯"

    endif

    repeat

    end nqueens

    此时,读者可能对于过程nqueens怎么会优于硬性处理感奇怪。原因是这样的,如果硬

性要求一个8*8的棋盘安排出8块位置,就有 种可能的方式,即要检查将近4.4*10 个8元组。然而过程nqueens只允许把皇后放置在不同的行和列上,因此至多需要作81次检

查,即至多只检查40320个8元组。

可以用过程estimate来估算nqueens所生成的结点数。要指出的是,过程estimate所需要的假定也适用于nqueens,即,使用固定的限界函数且在检索进行时函数不改变。另外,在状态空间树的同一级的所有结点都有相同的度。图44.8显示了由过程estimate求结点估计数所用的五个8x8棋盘。如同所要求的那样,棋盘上每一个皇后的位置是随机选取的。对于每种选择方案,都记下了可以将一个皇后合法地放在各行中列的数目(即状态树的每一级没受限的结点数)。它们都列在每个棋盘下方的向量中。向量后面的数字表示过程estimate由这些量值所产生的值。这五次试验的平均值是1625。8皇后状态空间树的结点总数是

 因此不受限结点的估计数大约只是8皇后状态空间树的结点总数的2.34%。

[动画]

posted on 2007-06-21 22:21 星梦情缘 阅读(6215) 评论(5)  编辑 收藏 引用 所属分类: 算法分析

评论:
# re: 经典算法(5)---8—皇后问题 2007-06-22 23:25 | pass86
记得以前学习的时候用了回溯的算法。  回复  更多评论
  
# re: 经典算法(5)---8—皇后问题 2007-06-22 23:45 | 星梦情缘
我有回溯算法的,不过没发上来  回复  更多评论
  
# re: 经典算法(5)---8—皇后问题 2007-06-26 17:36 | 匿名
可以改进一下,用4个全局的数组分别存放8行、8列、两种斜线各15条上是否已经放了皇后。 每放置或取走一个皇后,都改一下这四个数组。这样判断是否能放,4个条件就够了,不用循环。  回复  更多评论
  
# re: 经典算法(5)---8—皇后问题 2007-12-13 15:28 | jenny
// 八皇后2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "iostream.h"
#include "math.h"
#define NUM 8 /*定义数组的大小*/
int x[NUM+1];
int place(int k)
{
int i=1;
while(i<k)
{
if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))
return 0;
i++;
}
return 1;
}
void nqueens(int n)
{
int k;
int t;
int d=1;
x[1]=0;k=1;
int tt=n/2;
while(k>0&&k<=n)
{
x[k]=x[k]+1;
{ while(x[k]<=n&&!place(k))
x[k]=x[k]+1;
if(x[k]<=n)
{
if((k==n)&&(n%2==0))
{ cout<<"输出皇后 {"<<d<<"} 队列"<<endl;
d++;
for(int i=1;i<NUM+1;i++)
printf("%5d",x[i]);
cout<<endl;
}
else {k++;x[k]=0;}
}
else k--;
}
}
}
int main(int argc, char* argv[])
{
nqueens(NUM);
return 0;
}
  回复  更多评论
  
# re: 经典算法(5)---8—皇后问题 2008-08-31 17:22 | LM
学习,谢谢  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理