科技行者

行者学院 转型私董会 科技行者专题报道 网红大战科技行者

知识库

知识库 安全导航

至顶网软件频道基础软件基于Delphi的“八皇后”问题动态实现

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

  • 扫一扫
    分享文章到微信

  • 扫一扫
    关注官方公众号
    至顶头条

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

作者:左才文 来源:计算机与信息技术 2007年10月31日

关键字: 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:开始、单幅、连续、退出按纽。


    • 评论
    • 分享微博
    • 分享邮件
    闂傚倸鍊风欢锟犲矗鎼淬劌绐楅柡鍥╁亹閺嬪酣鏌曡箛瀣仾濠殿垰銈搁弻鏇$疀鐎n亖鍋撻弽顓ㄧ稏闁跨噦鎷�

    婵犵數濮烽。浠嬪焵椤掆偓閸熷潡鍩€椤掆偓缂嶅﹪骞冨Ο璇茬窞闁归偊鍓涢悾娲⒑闂堟单鍫ュ疾濠婂嫭鍙忔繝濠傜墛閸嬨劍銇勯弽銊с€掗柟钘夊暣閺岀喖鎮滈埡鍌涚彋閻庤娲樺畝绋跨暦閸洖鐓涢柛灞剧矋濞堟悂姊绘担绛嬪殐闁搞劋鍗冲畷銏ゅ冀椤愩儱小闂佹寧绋戠€氼參宕伴崱妯镐簻闁靛牆鎳庢慨顒€鈹戦埥鍡椾簼婵犮垺锚铻炴俊銈呮噺閸嬪倹绻涢崱妯诲碍閻庢艾顦甸弻宥堫檨闁告挾鍠庨锝夘敆娓氬﹦鐭楁繛鎾村焹閸嬫捇鏌e☉娆愬磳闁哄本绋戦埞鎴﹀川椤曞懏鈻婄紓鍌欑劍椤ㄥ懘鎯岄崒鐐靛祦閹兼番鍔岄悞鍨亜閹烘垵顏╅悗姘槹閵囧嫰寮介妸褎鍣ョ紓浣筋嚙濡繈寮婚悢纰辨晣鐟滃秹鎮橀懠顒傜<閺夊牄鍔庣粻鐐烘煛鐏炶姤鍠橀柡浣瑰姍瀹曠喖顢橀悩铏钒闂備浇宕垫慨鎶芥⒔瀹ュ鍨傞柦妯猴級閿濆绀嬫い鏍ㄧ☉濞堟粓姊虹涵鍛【妞ゎ偅娲熼崺鈧い鎺嗗亾闁挎洩濡囧Σ鎰板籍閸繄顓洪梺缁樺姇瀵剙螖閸涱喚鍘搁梺鍓插亽閸嬪嫰鎮橀敃鍌涚厱閻庯綆鍋嗘晶顒傜磼閸屾稑绗ч柟鐟板閹煎湱鎲撮崟闈涙櫏闂傚倷绀侀幖顐も偓姘卞厴瀹曞綊鏌嗗鍛紱閻庡箍鍎遍ˇ浼村磿瀹ュ鐓曢柡鍥ュ妼婢ь垰霉閻樿秮顏堟箒闂佹寧绻傚Λ妤呭煝閺囥垺鐓冪憸婊堝礈濮樿泛钃熼柕濞у嫷鍋ㄩ梺缁樺姇椤曨參鍩㈤弴銏″€甸柨婵嗗€瑰▍鍥ㄣ亜韫囨稐鎲鹃柡灞炬礋瀹曢亶顢橀悢濂変紦

    重磅专题
    往期文章
    最新文章