Delphi 動態演示八皇后問題：回溯法與多執行緒可視化實作

問題背景

八皇后問題由高斯 1850 年提出：在 8×8 棋盤放置 8 個皇后，使任兩者不同行、不同列、不同對角線。共有 92 組解。結合動態圖形演示，能直觀展示回溯搜尋過程，教學效果顯著。

核心衝突檢測邏輯

• 列：每列固定放一后，天然無衝突。
• 行：以陣列 row[i] 標記第 i 行是否被佔用。
• 對角線：主對角線 i+j 為常數，副對角線 i-j 為常數。放置后時同步標記 diag1[i+j]、diag2[i-j+7]（偏移避免負索引）。

資料結構與執行緒類設計

封裝於 TThread 衍生類別 Tbhh，避免封鎖主 UI：

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;

衝突檢測函數

function Tbhh.pd(i, j: Integer): Boolean;
var i1, j1: Integer;
begin
  Result := True;
  if i <> 1 then
    for i1 := 1 to i-1 do
      for j1 := 1 to 8 do
        if a[i1, j1] = 1 then
          if (j1 = j) or (Abs(i1-i) = Abs(j1-j)) then
            Exit(False);
end;

回溯遞迴核心

procedure Tbhh.hsu(i: Integer);
var j: Integer;
begin
  if i > 8 then begin
    Inc(tt); 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;

繪圖與元件配置

• PaintBox1：繪圖面板，顯示當前合法佈局。
• Label1：顯示解序號（第 N 幅）。
• 四按鈕：開始、單步、連續、退出。
• 圖片資源：backimg.bmp（棋盤）、queen.bmp（皇后）。

繪圖同步程序

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 then Suspend else begin s:=10; for i:=1 to 100000 do s:=s*s/s end; // 連續模式延遲
end;

主表單控制邏輯

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 not dstep then begin bhh.Suspend; dstep := True end else bhh.Resume;
end;

procedure TForm1.Button3Click(Sender: TObject); // 連續
begin
  dstep := False; bhh.Resume;
end;

執行緒建構子初始化

constructor Tbhh.Create(flag: Boolean);
var i, j: Integer;
begin
  inherited Create(flag);
  q := TBitmap.Create; q.LoadFromFile('e:\八皇后\backimg.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;

教學價值總結

此實作展示：回溯法遞迴結構、衝突檢測數學建模、多執行緒與 Synchronize 安全更新 UI、動態可視化教學輔助。程式碼結構清晰，易於擴展至 N 皇后或其他約束滿足問題。