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

下载本文示例代码
　　摘要 对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动，使教学能产生良好的效果。 　　关键词 八皇后问题 冲突 数据结构 线程类　　八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯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：开始、单幅、连续、退出按纽。共2页。 1 2 : 　　摘要 对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动，使教学能产生良好的效果。 　　关键词 八皇后问题 冲突 数据结构 线程类　　八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯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：开始、单幅、连续、退出按纽。共2页。 1 2 : 下载本文示例代码


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