摘要 對於八皇後問題的實現
如果結合動態的圖形演示
則可以使算法的描述更形象
更生動
使教學能產生良好的效果
關鍵詞 八皇後問題 沖突 數據結構 線程類
八皇後問題是一個古老而著名的問題
是回溯算法的典型例題
該問題是十九世紀著名的數學家高斯
年提出
在
X
格的國際象棋上擺放八個皇後
使其不能互相攻擊
即任意兩個皇後都不能處於同一行
同一列或同一斜線上
問有多少種擺法
下面用delphi
實現的八皇後問題的動態圖形
程序能夠演示全部的
組解
八皇後問題動態圖形的實現
主要應解決以下幾個問題
沖突 包括行
列
兩條對角線
(
)列
規定每一列放一個皇後
不會造成列上的沖突
(
)行
當第i行被某個皇後占領後
則同一行上的所有空格都不能再放皇後
要把以i
為下標的標記置為被占領狀態
(
)對角線
對角線有兩個方向
在同一對角線上的所有點(設下標為(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[
]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 i
j
:integer;
begin
pd:=true;
if i<>
then begin for i
:=
to i
do for j
:=
to
do
if a[i
j
]=
then begin if j
=j then pd:=false else if abs(i
i)=abs(j
j)then pd:=false end
end
end;
棋盤與棋子的圖片(需要用畫圖程序作出)生成裝入及顯示過程如下
procedure TForm
PaintBox
Click(Sender: TObject);
var q:tbitmap;
begin
q:=tbitmap
create;
q
loadfromfile(
e:\八皇後\backimg
bmp
);
paintbox
canvas
Draw(
q);
end;
end
[] []
From:http://tw.wingwit.com/Article/program/Delphi/201311/8516.html