數獨

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢
一條普通嘅數獨謎題...
... 同個答案(紅色嗰啲係由玩家填落去嘅數)。

數獨粵拼sou3 duk6英文sudoku / number place日文数独すうどく(sūdoku))係種組合性邏輯解謎遊戲[1]。數獨有好多隻進階變種,喺最基本上,一條標準嘅數獨謎題會[2][3]

  • 有個 9 × 9 嘅方陣,個方陣分做 9 個細方陣(boxes / blocks),每個細方陣 3 格 × 3 格;
  • 某啲格經已有喺裏面;
  • 玩家要做嘅嘢係將數字填入方陣嘅空格嗰度,目標係要令方陣每條直行有齊 1 至 9、每條橫行有齊 1 至 9、同埋每個 3 × 3 細方陣入面有齊 1 至 9;
  • 噉講即係話,一條解咗嘅數獨謎題會係個拉丁方陣(Latin square);

數獨謎題有唔少畀人覺得係得意嘅數學特性:數獨謎題可以用某啲演算法解,又可以用相對簡單嘅演算法創造;數獨謎題嘅呢啲數學特性,仲吸引咗好多數學同電腦科學嘅工作者對佢哋做研究

數獨源於 19 世紀:19 世紀經已有法國嘅報紙喺度出啲類似數獨嘅遊戲俾讀者玩,而早喺 1979 年經已有美國建築師喺度整數獨遊戲;打後數獨喺 1980 年代由日本一間整遊戲嘅公司普及化,最後令數獨呢種遊戲擴散到全世界,而日本人幫呢種遊戲改嗰個名-數獨-就畀人一路用到而家[註 1]。到咗廿一世紀初,數獨已經風行全世界,由日本至印度歐洲都有人搞數獨比賽[4][5]

演算法[編輯]

一個數獨遊戲可以用相對簡單嘅演算法產生,例如以下呢段虛擬碼[6]

 產生一個 9 × 9 嘅拉丁方陣,而且每個 3 × 3 嘅細方陣都有齊 1 至 9;
 while 完結條件未達到,係噉做
   是但攞走方陣當中其中一個數字;
   用演算法檢查吓呢個方陣仲有冇可能解到;
   if 個方陣冇可能解到或者有多過一個可能答案, # 一個整得好嘅數獨遊戲會淨係得一個可能答案。
     將攞走咗嗰個數字擺返返去;
   if 完結條件達到 # 完結條件係「經已總共攞走咗 n 個數字」,當中 n 數值愈大,個遊戲難度愈高。
     結束程式;

因為數獨遊戲容易產生,所以有好多網站同應用程式都能夠輕易係噉整出俾玩家花費時間嘅數獨遊戲,令數獨成為咗一種大受歡迎嘅消遣方式[6]

註釋[編輯]

  1. 呢點搞到好多人以為數獨起源自日本。

睇埋[編輯]

文獻[編輯]

  • 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.

[編輯]

  1. Arnoldy, Ben. "Sudoku Strategies". The Christian Science Monitor.
  2. Schaschek, Sarah (March 22, 2006). "Sudoku champ's surprise victory". The Prague Post.
  3. Lawler, E. L. (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. West Sussex: John Wiley & Sons.
  4. Hayes, Brian (2006). "Unwed Numbers". American Scientist. 94 (1): 12-15.
  5. Smith, David (May 15, 2005). "So you thought Sudoku came from the Land of the Rising Sun..." The Observer.
  6. 6.0 6.1 Sudoku Generator Algorithm. 101 Computing.net.

[編輯]