| |
摘要 对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动，使教学能产生良好的效果。
关键词 八皇后问题 冲突 数据结构 线程类
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
下面用 Delphi 6实现的八皇后问题的动态图形程序，能够演示全部的92组解。八皇后问题动态图形的实现，主要应解决以下几个问题。
冲突
包括行、列、两条对角线：
（1）列：规定每一列放一个皇后，不会造成列上的冲突；
（2）行：当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i
为下标的标记置为被占领状态；
（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第i个皇后占领了第j列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。
数据结构
为了对该问题的执行过程进行控制，需将该问题中的主要数据及相应的操作定义成一个线程类。方法：在New菜单中单击Other选项，在对话框中选Thread object，在classs name中输线程类的类名。具体定义如下：
type
Tbhh = class(TThread)
private
a:array[1..8,1..8]of integer;
tt:integer;
q,c:Tbitmap;
procedure prt;
function pd(i,j:integer):boolean;
procedure hsu(i:integer);
protected
procedure Execute; override;
public
constructor create(flag:boolean);
end;
var
dstep:boolean; |
解决冲突的具体函数
function pd(i,j:integer):boolean;
var i1,j1:integer;
begin
pd:=true;
if i<>1
then begin for i1:=1 to i-1 do for j1:=1 to 8 do
if a[i1,j1]=1
then begin if j1=j then pd:=false else if abs(i1-i)=abs(j1-j)then pd:=false end
end
end; |
棋盘与棋子的图片（需要用画图程序作出）、生成、装入及显示过程如下：
procedure TForm1.PaintBox1Click(Sender: TObject);
var q:tbitmap;
begin
q:=tbitmap.create;
q.loadfromfile('e:\八皇后\backimg.bmp');
paintbox1.canvas.Draw(0,0,q);
end;
end. |
组件设置
paintbox1：绘图板，显示当前的合法布局。
Label1：文字标签，显示当前合法布局的序号。
Button1,button2,button3,button4：开始、单幅、连续、退出按纽。
程序清单：
（1）代码单元unit1：
procedure TForm1.Button1Click(Sender: TObject);
begin
dstep:=true;
bhh:=tbhh.create(false);
button1.enabled:=false;
button2.enabled:=true;
button3.enabled:=true;
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
if dstep=false then begin bhh.suspend; dstep:=true end
else bhh.resume
end;
procedure TForm1.Button3Click(Sender: TObject);
begin
dstep:=false; bhh.resume;
end; |
（2）代码单元unit2：
uses unit1;
procedure Tbhh.Execute;
begin
hsu(1);
form1.button1.enabled:=true;
form1.button2.enabled:=false;
form1.button3.enabled:=false;
end;
procedure tbhh.prt;//显示
var i,j,ix,iy:integer;
s:real;iis:string[2];
begin
str(tt:2,iis);
form1.label1.caption:='第'+iis+'幅';
form1.paintbox1.canvas.draw(0,0,q);
for i:=1 to 8 do
for j:=1 to 8 do
if a[i,j]=1 then
begin
ix:=(i-1)*50+1;
iy:=(j-1)*50+1;
form1.paintbox1.canvas.draw(iy,ix,c);
end;
if dstep=true then suspend
else begin s:=10; for i:=1 to 100000 do s:=s*s/s end;
end;
procedure tbhh.hsu(i:integer);//回溯求解
var j:integer;
begin
if i>8 then begin tt:=tt+1; synchronize(prt)end
else for j:=1 to 8 do
begin a[i,j]:=1;if pd(i,j) then hsu(i+1);a[i,j]:=0;end
end;
constructor tbhh.create(flag:boolean);//创建该线程的一实例并对有关的变量进行初始化
var i,j:integer;
begin
inherited create(flag);
q:=tbitmap.create;q.loadfromfile('e:\八皇后\backing.bmp');
c:=tbitmap.create;c.loadfromfile('e:\八皇后\queen.bmp');
for i:=1 to 8 do
for j:=1 to 8 do
a[i,j]:=0; tt:=0;
end;
end. |
|
.JPG){kind=small}
中山比尔科技 / 中山华盛科技有限公司.JPG){kind=small}
.JPG)
.JPG){kind=small}
.JPG){kind=small}
