利用
利用利用
利用 MATLAB 解數獨
解數獨解數獨
解數獨
By Cleve Moler, MATLAB
發明人
人腦和電腦程式兩者是使用非常不同的求解方法來解數獨
(Sudoku)
問題。用人工手算找出數獨
答案的魅力，在於玩家能夠自行發現以及掌握無數的微妙組合，和提供最後解答的線索模式；而
這種人腦的模式識別能力和解題過程，是很不容易用電腦程式複製的。由於這個原因，大多數解
數獨的電腦程式用的是另一種不同的方式：仰賴電腦近乎無限的運算能力去進行反覆試驗、不斷
摸索
(trial and error)
；在這邊我用的方法，就是用
MATLAB
®
解題。
解
解解
解數獨的挑戰
數獨的挑戰數獨的挑戰
數獨的挑戰
正如你所可能知道，解一則數獨需要填滿
9x9
的方格，而每一行、每一列、以及所分出的
9
個
主要
3x3
區塊，必須包含
1
到
9
所有數字。題目一開始有些方格會先填有數字，這些數字為解
題的線索。相較於魔方陣
(magic squares)
和其他數字謎題，數獨並不需要算術，格子中所要填
的內容，也可以改成是英文字母或是其他符號。
圖一為題目開始的方格。我特別喜歡這個例子中的對稱性，這個題目是由
University of Western
Australia
的
Gordon Royle
所設計的。圖二則是這個例子的解答。
用遞迴回溯法
用遞迴回溯法用遞迴回溯法
用遞迴回溯法
(Recursive Backtracking)
解數獨
解數獨解數獨
解數獨
我們的
MATLAB
程式只使用一個樣本
(pattern)---
單一物件
(singletons)
，連同基本的電腦科學技
術
---
遞迴回溯法。
要了解該程式如何運行，我們可以先用一個簡單的
4x4
方格
(
含有
2x2
區塊
)
為例說明。這類的謎
題另被稱作
Shidoku
，而不叫
Sudoku(
數獨
)
，因為「
Shi
」在日文是「四」的意思。
圖一：數獨題目範例，線索數字以藍字
標示。這個例子中有討人喜歡的對稱
性。
圖二：完整解答。其他空格都已填滿
數字，使每行、每列、和主要
3×3
的
區塊都包含數字
1
到
9
。
- 1
- 2
前往页