數獨 (Sudoku)，一個在 9×9 的方陣中填入數字的遊戲。由於規則簡單，卻又富含深奧的技巧而受到世人喜愛。解數獨對人類來說是一項不簡單的事情，即便是經過訓練，也無法在短時間內破解難度較高的數獨。那麼，我們是否可以寫一個程式來幫我們解數獨呢？
人類與電腦的差別
首先，對數獨有深入研究的朋友應該知道，人類要解數獨靠的是一些候選數字刪除的技巧，例如初學者也可以自行領悟的：摒除法 (Hidden Single)、唯餘法 (Naked Single)，或是較難以發現的高深技巧：區塊摒除法 (Intersection)、矩形排除法 (X-Wing)、數對刪減法 (Naked Pair)、隱數對刪減法 (Hidden Pair)……等等。數獨技巧種類繁多，其中也有許多耐人玩味，有興趣的讀者可以參考數獨技巧。
然而，對電腦而言，使用這些人類鑽研的技巧去解題反而是更吃力的。電腦善於數字計算，而不擅於軌跡追蹤、形狀判斷。因此，本文將介紹的數獨解題器與上述解題技巧無關，是純粹利用電腦的演算來解數獨。
解題思維
首先，我們先用 9×9 的 sudo 陣列代表數獨，裡面數字 1~9 即為填入之數字，而未填入之空格則以 0 表示，如圖 1 所示。
sudo 陣列表示數獨示意圖。接下來，我們要讓電腦建立一個候選數字表 (Candidates)，表中裝有陣列每一格可以填入的數字。由於我們需要以 9×9 陣列代表數獨的每一格，又要以長度為 9 的布林陣列表示數字 1~9 是否可以填入，因此我們會創建 9×9×9 的 candid 陣列來表示候選數字表，如圖 2 所示。
candid 陣列代表候選數字表示意圖。接下來，我們要告訴電腦如何透過給定的數獨 sudo 產生候選數表 candid。根據數獨的基本規則：「同一宮、行、列中的數字不得重複」。可以設定一開始所有格子中的候選數字都被 1~9 填滿，然後針對 sudo 中每個已填入數字刪除同宮、行、列的候選數字。舉例來說，圖 3 中 (2,3) 的數字 3 已經填入了，因此第 2 列、第 3 行、左上宮內的所有候選數字 3 都要被刪除。
概念很簡單，但現在有個小問題：如何取得同宮元素的座標？數獨中特有的九宮格不像行列一般可以直接透過索引值取得，我們需要定義一個小函式：輸入某格行列座標 (r,c)，輸出該格所在之宮格的行列座標 (rs,cs)。舉例來說：輸入 (2,3)，輸出 (2,3) 所在之宮格座標 (1:3, 1:3)。而這樣的小函式其實只要一行匿名函式 (Anonymous function) 就可以達成：
%% tri() example >> tri = @(x) 3*ceil(x/3-1) + (1:3); >> tri(1) ans = 1 2 3 >> tri(3) ans = 1 2 3 >> tri(4) ans = 4 5 6 >> tri(7) ans = 7 8 9
取得 (r,c) 所在之宮格座標只要使用 (tri(r),tri(c)) 即可。有了 tri，我們便可以設計函式 getCandid，依照給定的數獨 sudo 產生候選數表 candid
%% getCandid.m function candid = getCandid(sudo) candid = ones(9,9,9); tri = @(x) 3*ceil(x/3-1) + (1:3); [rs,cs] = find(sudo); for i = 1:numel(rs) r = rs(i); c = cs(i); n = sudo(r,c); candid(r,c,:) = 0; %cell del candid(r,:,n) = 0; %row del candid(:,c,n) = 0; %col del candid(tri(r),tri(c),n) = 0; %tri del end end
在 getCandid 中，一開始設定 9×9×9 的 candid 陣列元素全為 1，利用 find 找到 sudo 內已填入數字的座標，接著針對每一個已填入的數字，刪除同宮 (tri)、行 (col)、列 (row)、格 (cell) 的候選數字 (設為 0)。
有了候選數字之後，我們只需要利用解八皇后問題中用到的回溯法 (Backtracking)，不斷的猜測性地填入數字，每次猜完再重新建立新的候選數表，繼續猜測下一個數字。倘若猜錯了而解不出答案，就回到上一個分支，繼續猜另一個數字，直到猜對為止。
%% sudoBacktracker.m function sudo = sudoBacktracker(sudo) candid = getCandid(sudo); if all(sudo(:)) return end [r,c] = find(~sudo,1); for sol = find(candid(r,c,:))' sudoTmp = sudo; sudoTmp(r,c) = sol; sudoTmp = sudoBacktracker(sudoTmp); if all(sudoTmp(:)) sudo = sudoTmp; return end end end
很快的，我們只用了 30 行便寫出了一個基礎的數獨解答程式 sudoBacktracker。然而，這樣的解法需要大量的猜測，若是遇到難題容易花上相當多的時間。這裡我們以「世界上最難的數獨」來測試
%% sudoBacktracker Test >> sudo sudo = 8 0 0 0 0 0 0 0 0 0 0 3 6 0 0 0 0 0 0 7 0 0 9 0 2 0 0 0 5 0 0 0 7 0 0 0 0 0 0 0 4 5 7 0 0 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 0 6 8 0 0 8 5 0 0 0 1 0 0 9 0 0 0 0 4 0 0 >> tic; sudo = sudoBacktracker(sudo); toc Elapsed time is 891.924517 seconds. >> sudo sudo = 8 1 2 7 5 3 6 4 9 9 4 3 6 8 2 1 7 5 6 7 5 4 9 1 2 8 3 1 5 4 2 3 7 8 9 6 3 6 9 8 4 5 7 2 1 2 8 7 1 6 9 5 3 4 5 2 1 9 7 4 3 6 8 4 3 8 5 2 6 9 1 7 7 9 6 3 1 8 4 5 2
花費了約 892 秒 (將近 15 分鐘) 才解出來，可以說是相當的沒效率。與八皇后問題中的狀況雷同，我們需要預先排除不可能的狀況，以提高求解的效率。
加入有效率的判斷
雖然在本文開頭提及，人類解數獨的方法對電腦來說是沒效率的，但純粹的使用回溯法解數獨的效率卻更差勁。最快速的演算法都是結合了有效率的判斷，大量減少不必要的猜測，以加速求解。
首先，我們知道當數獨中某格的候選數字只剩下一個時，我們就可以直接填入該格的答案。當能夠直接填入答案時，就不需要猜測求解。所以接下來，我們要讓電腦知道如何填入答案。我們需要建立 newSudo 函式，去檢查 sudo 中的每個空格 (r,c) 所對應的 candid(r,c,:)，看看該格的候選數字的數量 numel(find(candid(r,c,:))) 是否為 1，若是則將該數字填入 sudo(r,c)。
%% newSudo.m function sudo = newSudo(sudo,candid) [rs,cs] = find(~sudo); for i = 1:numel(rs) r = rs(i); c = cs(i); candidTmp = find(candid(r,c,:)); if numel(candidTmp) == 1 sudo(r,c) = candidTmp; return end end end
有了 newSudo 後，我們就不需要每次都猜測答案了。這裡特別注意：每當填入一個新數字後就必須立即更新候選數字表，否則會有數字誤填的狀況 (這就是 newSudo 裡面會有個 return 的原因)。而更新完候選數表後，我們又可以再次使用 newSudo 填入一個新數字。直到 newSudo 無法填入數字時，我們才需要利用回溯法猜數字。因此，我們可以寫一個 sudoSolver 改進剛才的缺點：
%% sudoSolver.m function sudo = sudoSolver(sudo) sudoTmp = []; while ~isequal(sudoTmp,sudo) sudoTmp = sudo; candid = getCandid(sudo); sudo = newSudo(sudo,candid); end if all(sudo(:)) return end [r,c] = find(~sudo,1); for sol = find(candid(r,c,:))' sudoTmp = sudo; sudoTmp(r,c) = sol; sudoTmp = sudokuSolver(sudoTmp); if all(sudoTmp(:)) sudo = sudoTmp; return end end end
注意到 sudoSolver 只是加入了一個 while 迴圈來重複執行 getCandid, newSudo，此外利用 sudoTmp 來確認是否有新數字被填入而已。接下來，讓我們同樣用世界上最難的數獨來測試一下：
%% sudoSolver Test >> sudo sudo = 8 0 0 0 0 0 0 0 0 0 0 3 6 0 0 0 0 0 0 7 0 0 9 0 2 0 0 0 5 0 0 0 7 0 0 0 0 0 0 0 4 5 7 0 0 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 0 6 8 0 0 8 5 0 0 0 1 0 0 9 0 0 0 0 4 0 0 >> tic; sudo = sudoSolver(sudo); toc Elapsed time is 73.899803 seconds. >> sudo sudo = 8 1 2 7 5 3 6 4 9 9 4 3 6 8 2 1 7 5 6 7 5 4 9 1 2 8 3 1 5 4 2 3 7 8 9 6 3 6 9 8 4 5 7 2 1 2 8 7 1 6 9 5 3 4 5 2 1 9 7 4 3 6 8 4 3 8 5 2 6 9 1 7 7 9 6 3 1 8 4 5 2
結果耗時馬上就縮短到約 74 秒了。從原先的將近 15 分鐘縮短到約 1 分鐘，差 15 倍的效率就只是加入一個 newSudo 來填入數字而已，可見演算法的重要性。
事實上，我們還可以再加入一些基礎的填數規則：任一宮、行、列中，某數字的候選格只剩一格，便可以填入此答案。根據此想法，進一步修改 newSudo 如下：
%% newSudo.m function sudo = newSudo(sudo,candid) tri = @(x) 3*ceil(x/3-1) + (1:3); for n = 1:9 for r = 1:9 candidTmp = find(candid(r,:,n)); if numel(candidTmp) == 1 sudo(r,candidTmp) = n; candid = getCandid(sudo); end end for c = 1:9 candidTmp = find(candid(:,c,n)); if numel(candidTmp) == 1 sudo(candidTmp,c) = n; candid = getCandid(sudo); end end candidN = candid(:,:,n); for r = 3:3:9 for c = 3:3:9 candidTmp = find(candidN(tri(r),tri(c))); if numel(candidTmp) == 1 sudoTmp = sudo(tri(r),tri(c)); sudoTmp(candidTmp) = n; sudo(tri(r),tri(c)) = sudoTmp; candid = getCandid(sudo); end end end end [rs,cs] = find(~sudo); for i = 1:numel(rs) r = rs(i); c = cs(i); candidTmp = find(candid(r,c,:)); if numel(candidTmp) == 1 sudo(r,c) = candidTmp; candid = getCandid(sudo); end end end
測試結果變成
%% sudoSolver Test 2 >> sudo sudo = 8 0 0 0 0 0 0 0 0 0 0 3 6 0 0 0 0 0 0 7 0 0 9 0 2 0 0 0 5 0 0 0 7 0 0 0 0 0 0 0 4 5 7 0 0 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 0 6 8 0 0 8 5 0 0 0 1 0 0 9 0 0 0 0 4 0 0 >> tic; sudo = sudoSolver(sudo); toc Elapsed time is 6.011989 seconds. >> sudo sudo = 8 1 2 7 5 3 6 4 9 9 4 3 6 8 2 1 7 5 6 7 5 4 9 1 2 8 3 1 5 4 2 3 7 8 9 6 3 6 9 8 4 5 7 2 1 2 8 7 1 6 9 5 3 4 5 2 1 9 7 4 3 6 8 4 3 8 5 2 6 9 1 7 7 9 6 3 1 8 4 5 2
耗時更近一步降至 6 秒，效率又在一次提升 10 倍。
事實上，現在的演算法還可以再透過下面的優化更進一步：
- 當任何一個過程中，若是出現填錯數字或無法填入數字的情形，便要提前結束遞迴，回溯到其他可能的分支。
- 紀錄過程中的候選數表並隨時更新，而非每次都用 getCandid 重新建立。
- 降低 tri 呼叫的次數，利用變數紀錄已經取得的宮格座標
- 建立 sudoMain 將上述所有函式包起來，以共用匿名函式 tri
%% sudoMain.m function sudo = sudoMain(sudo) tri = @(x) 3*ceil(x/3-1) + (1:3); candid = getCandid(sudo); sudo = sudoSolver(sudo,candid); function sudo = sudoSolver(sudo,candid) sudoTmp = []; while ~isequal(sudoTmp,sudo) sudoTmp = sudo; [sudo,candid,fail] = newSudo(sudo,candid); if fail; return; end end if ~all(sudo(:)) sudo = Guess(sudo,candid); end end function sudo = Guess(sudo,candid) [r,c] = find(~sudo,1); for sol = find(candid(r,c,:))' sudoTmp = sudo; sudoTmp(r,c) = sol; candidTmp = newCandid(sudoTmp,r,c,candid); sudoTmp = sudoSolver(sudoTmp,candidTmp); if all(sudoTmp(:)) sudo = sudoTmp; return end end end function candid = newCandid(sudo,r,c,candid) n = sudo(r,c); candid(r,c,:) = 0; %self del candid(r,:,n) = 0; %row del candid(:,c,n) = 0; %col del candid(tri(r),tri(c),n) = 0; %tri del end function candid = getCandid(sudo) candid = ones(9,9,9); [rs,cs] = find(sudo); for i = 1:numel(rs) candid = newCandid(sudo,rs(i),cs(i),candid); end end function [sudo,candid,chk] = newSudo(sudo,candid) chk = false; for n = 1:9 for i = 1:9 j = find(candid(i,:,n)); if numel(j) == 1 sudo(i,j) = n; candid = newCandid(sudo,i,j,candid); end j = find(candid(:,i,n)); if numel(j) == 1 sudo(j,i) = n; candid = newCandid(sudo,j,i,candid); end end candidN = candid(:,:,n); for r = 3:3:9 rtri = tri(r); for c = 3:3:9 ctri = tri(c); [rtmp,ctmp] = find(candidN(rtri,ctri)); if numel(rtmp) == 1 sudoTmp = sudo(rtri,ctri); sudoTmp(rtmp,ctmp) = n; sudo(rtri,ctri) = sudoTmp; candid = newCandid(sudo,rtri(1)+rtmp-1,ctri(1)+ctmp-1,candid); end end end end [rs,cs] = find(~sudo); for i = 1:numel(rs) r = rs(i); c = cs(i); candidTmp = find(candid(r,c,:)); if numel(candidTmp) == 1 sudo(r,c) = candidTmp; candid = newCandid(sudo,r,c,candid); elseif numel(candidTmp) == 0 chk = true; return end end end end
而 sudoMain 的測試結果如下
%% sudoMain Test >> sudo sudo = 8 0 0 0 0 0 0 0 0 0 0 3 6 0 0 0 0 0 0 7 0 0 9 0 2 0 0 0 5 0 0 0 7 0 0 0 0 0 0 0 4 5 7 0 0 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 0 6 8 0 0 8 5 0 0 0 1 0 0 9 0 0 0 0 4 0 0 >> tic; sudo = sudoSolver(sudo); toc Elapsed time is 0.807993 seconds. >> sudo sudo = 8 1 2 7 5 3 6 4 9 9 4 3 6 8 2 1 7 5 6 7 5 4 9 1 2 8 3 1 5 4 2 3 7 8 9 6 3 6 9 8 4 5 7 2 1 2 8 7 1 6 9 5 3 4 5 2 1 9 7 4 3 6 8 4 3 8 5 2 6 9 1 7 7 9 6 3 1 8 4 5 2
最終，我們使用不到 100 行的程式，花費不到 1 秒便解出了世界上最難的數獨。相較原本純粹使用回溯法的 sudoBacktracker，最終版的 sudoMain 效率高出 1000 倍。而這份程式碼一定也尚有可以改進的空間，就留給讀者自行鑽研了。
Program - C.Y.C 