數獨分類
九宮格數獨，是壹種源自18世紀末的瑞士，後在美國發展、並在日本得以發揚光大的數字謎題。數獨盤面是個九宮，每壹宮又分為九個小格。在這八十壹格中給出壹定的已知數字和解題條件，利用邏輯和推理，在其他的空格上填入1-9的數字。使1-9每個數字在每壹行、每壹列和每壹宮中都只出現壹次。這種遊戲全面考驗做題者觀察能力和推理能力，雖然玩法簡單，但數字排列方式卻千變萬化，所以不少教育者認為數獨是訓練頭腦的絕佳方式。
目錄[隱藏]
數獨的歷史
數獨的基本結構與規則元素構成
規則
基本解法舉例基礎摒除法
唯壹解法
唯余解法
區塊摒除法
余數測試法
隱性唯壹候選數法
三鏈數刪減法
隱性三鏈數刪減法
矩形頂點刪減法
三鏈列刪減法
關鍵數刪減法
變形數獨概述
數獨的近親
給出最少數字且有唯壹解的數獨
求解數獨的程序代碼數獨的歷史
數獨的基本結構與規則 元素構成
規則
基本解法舉例 基礎摒除法
唯壹解法
唯余解法
區塊摒除法
余數測試法
隱性唯壹候選數法
三鏈數刪減法
隱性三鏈數刪減法
矩形頂點刪減法
三鏈列刪減法
關鍵數刪減法
變形數獨概述
數獨的近親
給出最少數字且有唯壹解的數獨
求解數獨的程序代碼
[編輯本段]數獨的歷史
數獨前身為“九宮格”，最早起源於中國。數千年前，我們的祖先就發明了洛書，其特點較之現在的數獨更為復雜，要求縱向、橫向、斜向上的三個數字之和等於15，而非簡單的九個數字不能重復。中國古籍《易經》中的“九宮圖”也源於此，故稱“洛書九宮圖”。而“九宮”之名也因《易經》在中華文化發展史上的重要地位而保存、沿用至今。 1783年，瑞士數學家萊昂哈德·歐拉發明了壹種當時稱作“拉丁方塊”（Latin Square）的遊戲，這個遊戲是壹個n×n的數字方陣，每壹行和每壹列都是由不重復的n個數字或者字母組成的。 19世紀70年代，美國的壹家數學邏輯遊戲雜誌《戴爾鉛筆字謎和詞語遊戲》（Dell Puzzle Mαgαzines）開始刊登現在稱為“數獨”的這種遊戲，當時人們稱之為“數字拼圖”（Number Place），在這個時候，9×9的81格數字遊戲才開始成型。填充完整後 1984年4月，在日本遊戲雜誌《字謎通訊Nikoil》（《パズル通信ニコリ》）上出現了“數獨”遊戲，提出了“獨立的數字”的概念，意思就是“這個數字只能出現壹次”或者“這個數字必須是唯壹的”，並將這個遊戲命名為“數獨”（sudoku）。 壹位前任香港高等法院的新西蘭籍法官高樂德（Wayne Gould）在1997年3月到日本東京旅遊時，無意中發現了。他首先在英國的《泰晤士報》上發表，不久其他報紙也發表，很快便風靡全英國，之後他用了6年時間編寫了電腦程式，並將它放在網站上，使這個遊戲很快在全世界流行。從此，這個遊戲開始風靡全球。後來更因數獨的流行衍生了許多類似的數學智力拼圖遊戲，例如：數和、殺手數獨。 中國大陸是在2007年2月28日正式引入數獨. 2007年2月28日，北京晚報智力休閑數獨俱樂部(數獨聯盟sudokufederation前身)在新聞大廈舉行加入世界謎題聯合會的頒證儀式，會上謎題聯合會秘書長皮特-裏米斯特和俱樂部會長在證書上簽字，這標誌著北京晚報智力休閑俱樂部成為世界謎題聯合會的39個成員之壹，這也標誌著俱樂部走向國際舞臺，它將給數獨愛好者帶來更多與世界數獨愛好者們交流的機會。
[編輯本段]數獨的基本結構與規則
元素構成
數獨基本元素示意圖單元格：數獨中最小的單元，標準數獨中***有81個； 行：橫向9個單元格的集合； 列：縱向9個單元格的集合； 宮：粗黑線劃分的區域，標準數獨中為3×3的9個單元格的集合； 已知數：數獨初始盤面給出的數字； 候選數：每個空單元格中可以填入的數字。
規則
標準數獨的規則為：數獨每行、每列及每宮填入數字1-9且不能重復。
[編輯本段]基本解法舉例
數獨解法全是由規則衍生出來的，基本解法分為兩類思路，壹類為排除法，壹類為唯壹法。更復雜的解法，最終也會歸結到這兩大類中。 下邊以圖示簡單介紹幾種解法，只要妳花幾分鐘看壹遍，馬上就可以開始做數獨了。
基礎摒除法
基礎摒除法就是利用1 ～ 9 的數字在每壹行、每壹列、每壹宮都只能出現壹次的規則進行解題的方法。基礎摒除法可以分為行摒除、列摒除、九宮格摒除。 實際尋找解的過程為： 尋找九宮格摒除解：找到了某數在某壹個九宮格可填入的位置只余壹個的情形；意即找到了 該數在該九宮格中的填入位置。 尋找列摒除解：找到了某數在某列可填入的位置只余壹個的情形；意即找到了該數在該列中的填入位置。 尋找行摒除解：找到了某數在某行可填入的位置只余壹個的情形；意即找到了該數在該行中的填入位置。 基礎摒除法的提升方法是區塊摒除法,是直觀法中使用頻率最高的方法之壹.
唯壹解法
當某行已填數字的宮格達到8個,那麽該行剩余宮格能填的數字就只剩下那個還沒出現過的數字了。成為行唯壹解. 當某列已填數字的宮格達到8個,那麽該列剩余宮格能填的數字就只剩下那個還沒出現過的數字了。成為列唯壹解. 當某九宮格已填數字的宮格達到8個,那麽該九宮格剩余宮格能填的數字就只剩下那個還沒出現過的數字了。成為九宮格唯壹解.
唯余解法
唯余解法就是某宮格可以添入的數已經排除了8個,那麽這個宮格的數字就只能添入那個沒有出現的數字.
區塊摒除法
區塊摒除法是基礎摒除法的提升方法,是直觀法中使用頻率最高的方法之壹.
余數測試法
所謂余數測試法就是在某行或列,九宮格所填數字比較多,剩余2個或3個時,在剩余宮格添入值進行測試的解題方法.
隱性唯壹候選數法
當某個數字在某壹列各宮格的候選數中只出現壹次時，那麽這個數字就是這壹列的唯壹候選數了．這個宮格的值就可以確定為該數字． 這是因為，按照數獨遊戲的規則要求每壹列都應該包含數字1～9，而其它宮格的候選數都不含有該數，則該數不可能出現在其它的宮格，那麽就只能出現在這個宮格了． 對於唯壹候選數出現行,九宮格的情況，處理方法完全相同。
三鏈數刪減法
找出某壹列、某壹行或某壹個九宮格中的某三個宮格候選數中，相異的數字不超過3個的情形， 進而將這3個數字自其它宮格的候選數中刪減掉的方法就叫做三鏈數刪減法。
隱性三鏈數刪減法
在某行，存在三個數字出現在相同的宮格內，在本行的其它宮格均不包含這三個數字，我們稱這個數對是隱形三鏈數．那麽這三個宮格的候選數中的其它數字都可以排除． 當隱形三鏈數出現在列，九宮格，處理方法是完全相同的． －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 修改為：在某行，存在三個候選數字分別出現在三個宮格內， 在本行的其它宮格均不包含這三個數字，我們稱這個數對是隱形三鏈數．那麽這三個宮格的其它候選數都可以排除． 當隱形三鏈數出現在列，九宮格，處理方法是完全相同的 或者： 利用“找出某3個數字僅出現在某行、某列或某壹個九宮格的某三個宮格候選數中的情形，進而將這三個宮格的候選數刪減成該3個數字”的方法就叫做隱性三鏈數刪減法(Hidden Triples)。
矩形頂點刪減法
矩形頂點刪減法和直觀法講到的矩形摒除法分析方法是壹樣的。矩形頂點刪減法在識別時比較不容易找到，所以最好先使用其它的方法。
三鏈列刪減法
三鏈列刪減法是矩形頂點刪減法的擴展，如果不清楚矩形頂點刪減法，可以參考矩形頂點刪減法，以便於更容易理解本節內容。 利用“找出某個數字在某三列僅出現在相同三行的情形，進而將該數字自這三行其他宮格候選數中刪減掉”； 或“找出某個數字在某三行僅出現在相同三列的情形，進而將該數字自這三列其他宮格候選數中刪減掉”的方法 就叫做三鏈列刪減法。
關鍵數刪減法
在進入到解題後期，利用前面講到的唯壹候選數法、隱性唯壹候選數法、 區塊刪減法、數對刪減法、隱性數對刪減法、 三鏈數刪減法、隱性三鏈數刪減法、矩形頂點刪減法、 三鏈列刪減法都無法有進展的時候，可以考慮使用關鍵數刪減法。關鍵數刪減法就是在後期找到壹個數，這個數在行（或列，九宮格）僅出現兩次的數字。我們假定這個數在其中壹個宮格類，繼續求解，如果發生錯誤，則確定我們的假設錯誤。如果繼續求解仍然出現困難，不妨假設這個數在另外壹個宮格，看能不能得到錯誤。這就是關鍵數刪減法. 排除法 當某壹列，某壹行或某壹宮裏已填7個數字時，可采用排除法，排除不可能出現在這個格子的數，從而確定格子裏應該填什麽數。比如某壹行已填1，3，4，5，7，8，9，還剩2，6，而其中壹個空格所在的列上已有了2，可知這個空格裏不可能是2，那麽另外壹個空格裏壹定是2，那麽這個空格裏壹定是6。 當某壹列，某壹行或某壹宮裏已填6個數字時，也可采用排除法。
[編輯本段]變形數獨概述
數獨發展到今天，類型已經多種多樣，如果按不同條件細分絕不下百種，而且數量還在增加中。大家平時可以常見的變形數獨，如：對角線數獨、鋸齒數獨、殺手數獨等等。 對角線數獨鋸齒數獨殺手數獨 所謂變形數獨，即改變壹些標準數獨的條件或規則，形成的新型數獨題目，有的變形數獨也會同時具備多種變形條件，變形條件如下： 1、使用數字的數量不同可以有4字數獨、6字數獨、16字數獨、25字數獨等等； 2、增加限制區域的類別可以有對角線數獨、額外區域數獨、彩虹數獨等等； 3、宮形發生變化有鋸齒數獨；多個數獨疊加起來有連體數獨、武士數獨、超級數獨等等 4、用其它元素代替已知數字有字母數獨、骰子數獨、數碼數獨等等； 5、利用單元格內數字之和或乘積等關系有殺手數獨、邊框數獨、箭頭數獨、魔方數獨、算式數獨等等； 6、利用相鄰單元格內數字的關系有連續數獨、不等號數獨、堡壘數獨、XV數獨、黑白點數獨等等； 7、單元格限制數字屬性有奇偶數獨、大中小數獨等等； 8、利用數獨外提示數字有邊緣觀測數獨、摩天樓數獨等等； 9、按禁止同壹數字位置有無緣數獨、無馬數獨等等； 10、非方形數獨有圓環數獨、立方體數獨、六角數獨、蜂窩數獨等等； 11、需要多個數獨條件配合才能解題的有三合壹數獨、雙胞數獨等等。 以上11種分類並非全部變化條件，只是常見的大類，還有不少變形數獨未舉例，其實變形的條件不會有極限的，只要妳有想象力，可以創造出屬於妳自己的新型變形數獨。雖然數獨條件變換多端，但有壹條始終不變的絕對條件——同壹限制區域內不能出現重復數字。只要符合這個條件，就沒有脫離“數獨”的範疇。
[編輯本段]數獨的近親
謎題（Pazzle）：排除文化差異對做題者的影響，只用數字和圖形表示的邏輯推理遊戲。 數獨是謎題（Pazzle）中的壹個分支，由於其規則簡單、種類眾多從而從眾多謎題脫穎而出，成為大眾熟知的數字謎題。 不過除了數獨以外，還有不少謎題也非常出色，也有眾多的擁護者，而且與數獨有千絲萬縷的關系。數獨愛好者同樣不能錯過這些優秀的邏輯推理遊戲。下面簡單介紹幾類謎題： 數和（Kakuro）：與殺手數獨很像的壹類謎題，規則要求同行、同列（同壹段）數字不能重復，且每段數字之和等於左邊和上邊的提示數字。 數圖（Nonograms\Griddlers)：根據盤面周圍的數字提示，把盤中塗成符合條件的圖案，很像“十字繡”。 數回（Slither Link）：遊戲由0,1,2,3四個數字組成。每壹個數字，代表四周劃線的數目，並在最後成為壹個不間斷、不分岔的回路。 數墻（Nurikabe）：數墻的世界，是壹個非黑即白的二元世界；在遊戲中，妳要決定的是，那些格子需要塗黑，那壹些應該留白。 數連（Number Link）：與數獨壹樣，數連是壹個簡單明快的遊戲。妳只需要把屬於相同數字的同伴，以線連接起來。不過，這個遊戲看起來非常簡單，實際上是很有深度的。 圖獨（tudoku）：數獨的壹種擴展，將數字換成有趣的圖形，看似壹樣，但換成圖形後大大增強了數獨趣味性，使遊戲不會那麽枯燥，很合適小孩子玩，即動腦又鍛煉記憶力。
[編輯本段]給出最少數字且有唯壹解的數獨
數獨初盤最少可以有17個數。 與數獨終盤相對應，壹個數獨遊戲給出的初始條件稱為初盤。由於規則所限，給出的初盤數字個數必須在32以下。 壹般常見的初盤數字個數在22—28之間，而數獨愛好者們常問的壹個問題是：最少給出多少個數字，數獨遊戲才確保有唯壹解？具體地說：最少需要在初盤中給出多少個數字，使得移除其中任何壹個數字該數獨遊戲便沒有唯壹解。 事實上，這個問題是數獨中最有數學趣味的問題之壹，並且至今仍未得到解決。但數學家們估計，這個數字很可能是17.17個數字的最小唯壹解初盤是由壹名日本數獨愛好者發現的。澳大利亞數學家GordonRoyle已經收集了36628個17個數字的唯壹解初盤，而愛爾蘭數學家Gary McGuire則致力於尋找16個數字的唯壹解初盤，但至今仍無發現。部分數學家開始退而求其次，轉而尋找只有兩個解的16個數字初盤。 統計學家根據壹個統計學原理曾隨機地構造了大量17個數字的初盤，發現其中有唯壹解的初盤只有數個未被GordonRoyle教授發現，這意味著，最小唯壹解初盤問題的最終答案可能正是17：因為從理論上說，如果16個數字的唯壹解終盤存在，那麽每壹個必將引起65個17個數字唯壹解終盤的增加，而在研究中至今沒有觀察到這壹效應。17個數的數獨