基于Delphi的“八皇后”问题动态实现[1]

摘要 对于八皇后问题的实现如果结合动态的图形演示则可以使算法的描述更形象更生动使教学能产生良好的效果

关键词 八皇后问题 沖突 数据结构 线程类

八皇后问题是一个古老而着名的问题是回溯算法的典型例题该问题是十九世纪着名的数学家高斯年提出在X格的国际象棋上摆放八个皇后使其不能互相攻击即任意两个皇后都不能处于同一行同一列或同一斜线上问有多少种摆法

下面用delphi实现的八皇后问题的动态图形程序能够演示全部的组解八皇后问题动态图形的实现主要应解决以下几个问题

沖突

包括行列两条对角线

（）列规定每一列放一个皇后不会造成列上的沖突

（）行当第i行被某个皇后占领后则同一行上的所有空格都不能再放皇后要把以i

为下标的标记置为被占领状态

（）对角线对角线有两个方向在同一对角线上的所有点（设下标为(ij)）要么(i+j)是常数要么(ij)是常数因此当第i个皇后占领了第j列后要同时把以(i+j)(ij)为下标的标记置为被占领状态

数据结构

为了对该问题的执行过程进行控制需将该问题中的主要数据及相应的操作定义成一个线程类方法在New菜单中单击Other选项在对话框中选Thread object在classs name中输线程类的类名具体定义如下

type

Tbhh = class(TThread)

private

a:array[]of integer;

tt:integer;

qc:Tbitmap;

procedure prt;

function pd(ij:integer):boolean;

procedure hsu(i:integer);

protected

procedure Execute; override;

public

constructor create(flag:boolean);

end;

var

dstep:boolean;

解决沖突的具体函数

function pd(ij:integer):boolean;

var ij:integer;

begin

pd:=true;

if i<>

then begin for i:= to i do for j:= to do

if a[ij]=

then begin if j=j then pd:=false else if abs(ii)=abs(jj)then pd:=false end

end

end;

棋盘与棋子的图片（需要用画图程序作出）生成装入及显示过程如下

procedure TFormPaintBoxClick(Sender: TObject);

var q:tbitmap;

begin

q:=tbitmapcreate;

qloadfromfile(e:\八皇后\backimgbmp);

paintboxcanvasDraw(q);

end;

end

[] []