數獨
游戲簡介
數獨(すうどく,Sudoku)是一種運用紙、筆進行演算的邏輯游戲。玩家需要根據9×9盤面上的已知數字,推理出所有剩余空格的數字,并滿足每一行、每一列、每一個粗線宮內的數字均含1-9,不重復。 每一道合格的數獨謎題都有且僅有唯一答案,推理方法也以此為基礎,任何無解或多解的題目都是不合格的。
游戲起源
既然“數獨”有一個字是“數”,人們也往往會聯想到數學,那就不妨從大家都知道的數學家歐拉說起,但凡想了解數獨歷史的玩家在網絡、書籍中搜索時,共同會提到的就是歐拉的“拉丁方塊(Latin square)”,如下圖:
拉丁方塊的規則:每一行(Row)、每一列(Column)均含1-N(N即盤面的規格),不重復。這與前面提到的標準數獨非常相似,但少了一個宮的規則。
游戲組成
九宮格(Grid)
水平方向有九橫行,垂直方向有九縱列的矩形,畫分八十一個小矩形,稱為九宮格(Grid)
單元(Unit)畫分
2.1 水平方向的每一橫行有九格,每一橫行稱為行(Row)
2.2 垂直方向的每一縱列有九格,每一縱列稱為列(Column)
2.3 三行與三列相交之處有九格,每一單元稱為小九宮(Box、Block),簡稱宮
2.4 上述行、列、宮統稱為單元(Unit)
2.5 由三個連續宮組成大區塊(Chute),分大行區塊(Floor)及大列區塊(Tower)。
第一大行區塊:由第一宮、第二宮、第三宮組成。
第二大行區塊:由第四宮、第五宮、第六宮組成。
第三大行區塊:由第七宮、第八宮、第九宮組成。
第一大列區塊:由第一宮、第四宮、第七宮組成。
第二大列區塊:由第二宮、第五宮、第八宮組成。
第三大列區塊:由第三宮、第六宮、第九宮組成。
格位(Cell)編號
格位按所處的行列單元賦予坐標值
坐標有多種標示法,有橫行 A..I,縱列 1..9(如中國),也有橫行 1..9,縱列 A..I(如日本),這兩種標示容易混淆,故最被廣泛使用的是橫行R1..R9,縱列C1..C9的標示法。
提示數(Clue)
在九宮格的格位填上一些數字,做為填數判斷的線索(Hint),稱為提示數(Clue)
解題方式
解題的本質有二:隱性唯一解(Hidden Single)及顯性唯一(Naked Single),他們的名稱是在候選數法的基礎上命名的。
根據解題本質發展出來的解題方法有二種:
摒除法
1.摒除法:用數字去找單元內唯一可填空格,稱為摒除法,數字可填唯一空格稱為摒余解(隱性唯一解)。
根據不同的作用范圍,摒余解可分為下述三種:
1.1 數字可填唯一空格在「宮」單元稱為宮摒余解(Hidden Single in Box),這種解法稱宮摒除法。
1.2 數字可填唯一空格在「行」單元稱為行摒余解(Hidden Single in Row),這種解法稱行摒除法。
1.3 數字可填唯一空格在「列」單元稱為列摒余解(Hidden Single in Column),這種解法稱列摒除法。
1.4 行摒余解和列摒余解合稱行列摒余解(Hidden Single in Line)。
1.5 得到行列摒余解的方法稱為行列摒除法。
余數法
2.余數法:用格位去找唯一可填數字,稱為余數法,格位唯一可填數字稱為唯余解(Naked Single)。
余數法是刪減等位群格位(Peer)已出現的數字的方法,每一格位的等位群格位有 20 個,如圖七所示。
輔助解法
3.上述方法稱為基礎解法(Basic Techinques),其他所有的解法稱為進階解法(Advanced Techniques),是在補基本解法之不足,所以又稱輔助解法。
進階解法包括:區塊摒除法(Locked Candidates)、數組法(Subset)、四角對角線(X-Wing)、唯一矩形(Unique Rectangle)、全雙值墳墓(Bivalue Universal Grave)、單數鏈(X-Chain)、異數鏈(XY-Chain)及其他數鏈的高級技巧等等。已發展出來的方法有近百種之多。
其中前兩種加上基礎解法為一般數獨書中介紹并使用的方法,同時也是大部分人可以理解并掌握的數獨解題技法。
4.通過基礎解法出數只需一種解法,摒除法或唯余法,超出此范圍而需要施加進階解法時,解題點需要進階解法協助基礎解法來滿足隱性唯一或顯性唯一才能出數,該解題點的解法需要多個步驟協力完成,因此稱做組合解法。
5.解題必須以邏輯為依歸,猜測的方法被稱為“暴力型”解法(Brute Force),這不是提倡數獨的本意。