对于八皇后问题的实现,如果结合动态的图形演示,则可以使算法的描述更形象、更生动,使教学能产生良好的效果
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 下面用 delphi6 实现的 八皇后问题的动态图形 程序,能够演示全部的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:开始、单幅、连续、退出按纽。 ![](http://image50.360doc.com/DownloadImg/2012/03/1215/22245874_1.jpg)
对于八皇后问题的实现,如果结合动态的图形演示,则可以使算法的描述更形象、更生动,使教学能产生良好的效果
程序清单: (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. |
|