八皇后問題求解器：遞歸與非遞歸回溯動態演示

專案概述

Delphi 開發的教學軟體，以動態圖形演示八皇后問題求解全過程。支援遞歸回溯與非遞歸回溯兩種算法，多執行緒架構，可即時調整演示速度，提供 5 組前景/背景圖形風格。附完整原始碼與資源檔。

核心架構設計

多執行緒模型

• 主執行緒：UI 互動、參數設定、結果顯示。
• 工作執行緒 (TQueenThread)：執行求解算法，透過 Synchronize 回主執行緒繪圖，避免跨執行緒 UI 操作。
• 同步機制：自訂視窗訊息 (WM_SEEKFINISH, WM_SEEKSUSPEND) 替代訊號量，實現執行緒掛起/恢復/通知。

關鍵資料結構

Q: array[1..8] of integer; // Q[i] = 第 i 列皇后所在行 (1~8)
CellWidth = 50; CellHeight = 50; // 棋盤格尺寸

算法實作核心代碼

遞歸回溯 (QSeek)

function TQueenThread.QSeek(n: integer): boolean;
begin
  if n > 0 then
  begin
    // 示範模式：清除上一嘗試位置
    if FDemo then begin FQueen := n; Synchronize(ShowDelete); end;

    inc(Q[n]); // 嘗試下一行

    // 示範模式：顯示嘗試位置
    if FDemo then begin FSeekQueenIcon := FSeekIcon; Synchronize(ShowDraw); Sleep(FDelay); end;

    if Q[n] <= 8 then
      if QClash(n) then // 無衝突
      begin
        // 示範：閃爍衝突皇后
        if FDemo then ... Synchronize(ShowClashRestore) ...;
        result := QSeek(n + 1); // 遞歸處理下一列
      end
      else // 衝突：嘗試本列下一行
        result := QSeek(n)
    else // 本列無可用行：回溯
    begin
      Q[n] := 0;
      if QSeek(n - 1) then result := QSeek(n) else result := false;
    end;
  end
  else result := false; // n=0 表示回溯失敗
end;

非遞歸回溯 (QSeekNonrecursion)

function TQueenThread.QSeekNonrecursion(n: integer): boolean;
var flag: boolean; m: integer;
begin
  m := n; flag := false;
  repeat
    if FDemo then ... Synchronize(ShowDelete) ...;
    inc(Q[n]);
    if FDemo then ... Synchronize(ShowDraw) ... Sleep(FDelay) ...;

    if Q[n] > 8 then // 超出範圍：回溯
    begin Q[n] := 0; dec(n); end
    else if not QClash(n) then // 無衝突
    begin
      if FDemo then ... Synchronize(ShowClashRestore) ...;
      if m = n then flag := true else inc(n); // 找到解或進入下一列
    end
    else // 有衝突：閃爍提示後繼續嘗試本列下一行
      if FDemo then ... Synchronize(ShowClashRestore) ...;
  until flag or (n < 1);
  result := flag;
end;

衝突檢測 (QClash)

function TQueenThread.QClash(n: integer): boolean;
var i: integer; flag: boolean;
begin
  flag := false; i := 1;
  while (i < n) and not flag do
  begin
    // 同行 或 同對角線
    flag := (Q[n] = Q[i]) or (Abs(Q[n] - Q[i]) = (n - i));
    inc(i);
  end;
  result := flag; // true = 有衝突
end;

UI 互動流程

• 開始/暫停/繼續：按鈕切換執行緒 Suspend/Resume。
• 演示模式：勾選啟用動畫與延遲 (TrackBar 控制速度)。
• 算法切換：遞歸/非遞歸即時切換。
• 結果記錄：每找到一解，記錄至 ListBox，雙擊可重播該解擺放過程。
• 風格切換：5 組皇后/嘗試/衝突圖示 + 5 種棋盤背景，即時切換。

技術亮點總結

1. Win32 圖形程式設計：TCanvas、TBitmap、TIcon 運用，CopyRect 實現區域刷新。
2. 多執行緒同步：Synchronize 封送繪圖至主執行緒，自訂訊息實現協作式調度。
3. 算法可視化教學價值：直觀展示回溯法「試探-衝突-回溯」核心邏輯，非遞歸版本揭示狀態機本質。
4. 完整專案結構：兩個 Unit (Unit1 UI, Unit2