提示: 呢篇文講嘅唔係
掃毒 。
數獨 (粵音 :sou3 duk6;日文 :数独 すうどく (sūdoku) )係種組合 性質嘅邏輯 解謎遊戲 [ 1] 。數獨有好多隻進階變種,喺最基本上,一條標準嘅數獨謎題會[ 2] [ 3]
有個 9 × 9 嘅方陣 ,個方陣分做 9 個細方陣 [ 4] ,每個細方陣 3 格 × 3 格; 某啲格經已有數 喺裏面; 玩家要做嘅嘢係將數字填入方陣嘅空格嗰度,目標 係要令方陣每條直行有齊 1 至 9、每條橫行有齊 1 至 9、同埋每個 3 × 3 細方陣入面有齊 1 至 9; 噉講即係話,一條解咗嘅數獨謎題會係個拉丁方陣 ; 數獨謎題有唔少畀人覺得係得意嘅數學 特性:數獨謎題可以用某啲演算法 解,又可以用相對簡單嘅演算法創造;數獨謎題嘅呢啲數學特性,仲吸引咗好多數學同電腦科學 嘅工作者研究佢哋。
數獨源於 19 世紀:19 世紀經已有法國 嘅報紙喺度出啲類似數獨嘅遊戲俾讀者玩,而早喺 1979 年經已有美國 建築師 喺度整數獨遊戲;打後數獨喺 1980 年代由日本 一間整遊戲嘅公司Nikoli 普及化,最後令數獨呢種遊戲擴散到全世界,而日本人 幫呢種遊戲改嗰個名-數獨 -就畀人一路用到而家,而呢點搞到好多人以為數獨起源自日本。到咗廿一世紀初,數獨已經風行全世界,由日本至印度 至歐洲 都有人搞數獨比賽[ 5] [ 6] 。
數獨同好多經典嘅解謎遊戲 一樣,「可能狀態」數量有限,可以透過逐步推理 ,將所有可能性全部審視晒,即係用到好似數學證明 噉嘅演繹推理 方式嚟處理[ 7] 。
譬如係下圖噉:
已知上圖個方陣每一橫行都有齊 1 至 9 而且冇重複,每一直行都有齊 1 至 9 而且冇重複(數獨嘅基本條件),解謎者就可以做以下噉嘅推理:望住左下個 3 × 3 九宮格,紅色 嗰個 9 嘅存在表示,同佢屬同一行直行嘅格冇可能係 9(打戙嘅紅色 線所示)-然後睇埋其餘已經有 9 填咗喺入便嘅格,解謎者可以推理出,左下小區嘅 9 應該係喺油咗綠色 嗰個格仔入便。
數獨遊戲可以用相對簡單嘅演算法 產生,例如以下呢段虛擬碼 [ 8] :
產生一個 9 × 9 嘅拉丁方陣,而且每個 3 × 3 嘅細方陣都有齊 1 至 9;while 完結條件未達到,係噉做 是但攞走方陣當中其中一個數字; 用演算法檢查吓呢個方陣仲有冇可能解到; if 個方陣冇可能解到或者有多過一個可能答案,# 一個整得好嘅數獨遊戲會淨係得一個可能答案。 將攞走咗嗰個數字擺返返去; if 完結條件達到# 完結條件係「經已總共攞走咗 n 個數字」,當中 n 數值愈大,個遊戲難度愈高。 結束程式; 因為數獨遊戲容易產生,所以有好多網站同應用程式都能夠輕易係噉整出俾玩家花費時間嘅數獨遊戲,令數獨成為咗一種大受歡迎嘅消遣方式[ 8] 。
Delahaye, Jean-Paul, "The Science Behind Sudoku ",Scientific American , June 2006. Provan, J. Scott, "Sudoku: Strategy Versus Structure",American Mathematical Monthly , October 2009. Published also as a University of North Carolina technical report UNC/STOR/08/04, 2008.