摘要 對於八皇後問題的實現，如果結合動態的圖形演示，則可以使算法的描述更形象、更生動，使教學能產生良好的效果。
關鍵詞 八皇後問題 沖突 數據結構 線程類
八皇後問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀著名的數學家高斯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：開始、單幅、連續、退出按紐。
程序清單：
（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.
