數獨Sudoku

在Takol的網站看到『數獨』這個東西，再輾轉連結到一些網頁，對它終於有了認識，立刻讓熱中此道的我躍躍欲試。 很快地做了兩個題目，都不難，而且一步一步地推理，便可以求得唯一的解 (我想不同的問題也許會無解、會有唯一解，或會有多個解)。但求解過程中，倒是激發了不少的連想，包括它的求解是否能有固定程序、是否能由電腦來產生問題、是否能由電腦來解題、是否能有一些法則來歸納每個問題的難易度…… 難易度是件重要的事，因為以電腦隨機出題的演算法很簡單，但出來的題目沒有多大意義。對解題的人而言，如何漸近地找出解題的法則是比較重要的，一個簡單的題目有助於思考，而難度高的題目則必須採用某些啟發式(heuristic)的演算，或者需要某種程度的『可能假設』。萬一不是經由這樣的方式解題，只是胡亂猜一下，則解題過程不僅亂七八糟，而且也無法區分正確及亂猜的是哪些，也導致可能做到一半就再次重來。這樣的解題程序不但無助於思考邏輯的訓練，更是浪費時間。 想在這裡記錄，但在這個blog上，很難寫入html語法，因此很難寫出題目的樣子 (也就是一個9x9的表格)，這就有點傷腦筋了！


迴響

作者 Vincent: 06 八月 2005, 13:39
除了題目和答案是可以用表格表示外，中間解題的過程則不易處理。能夠表達解題的思考及作答過程是重要的，但以文字敘述實在難懂，因此設計幾個符號來表示： Rn 代表第n列 (n=1~9)，R是Row的意思。 Cn 代表第n行(n=1~9)，C是Column的意思。 Bn 代表第n個小區塊(每一個小的9x9的方格的集合為單位)，由左上而右依序為B1,B2,B3，再往下一區塊為B4,B5,B6，最底下一排區塊為B7,B8,B9。B是Box或Block的意思。 以上三種為找答案時，最常觀察的部份，因為每一個Rn, Cn, 或Bn都恰好為9個小格，分別為1到9的不同數字。這也是最原始的定義。 Dn 代表一個數字n，例如D5表示數字5。D是Digit的意思。 Amn 代表一個小格子，例如A43代表第4列第3行的小格，全部的格子由A11到A99共81個小格子。 另外，定義幾個動作： View(X) 代表察看X，X可為Rn、Cn或Bn Fill(Amn,X) 代表在Amn小格子內填入某值X。這個寫法好像很囉嗦，考慮直接用Amn(X)的寫法比較簡單，未定。 目前想到這了，不知這樣的表示是否易懂，也不知是否能用，試試看了。 做這些表示要做什麼呢？算是設計此一系列演算法的前期思考階段吧！


Vincent: 06 八月 2005, 13:39
參考網站： http://tw.knowledge.yahoo.com/question/?qid=1105053101635
參考網站： http://tw.knowledge.yahoo.com/question/?qid=1105053101635


Vincent: 06 八月 2005, 13:40
一個可以在線上選題、答題的網站。其中的題目還有不同的等級。 只是玩了幾個，總覺得同一種難度的題目都有點類似的感覺，該網站的出題模式可能有個固定依循的方向，再多試幾題也許就可以摸出點端倪。 http://www.websudoku.com/


Vincent: 06 八月 2005, 13:40
http://blog.yam.com/yuanlin/archives/cat_20501.html 裡面整理了幾個網站。


作者 nell: 06 八月 2005, 13:41
请人指教，这个游戏的开发算法 1． 游戏规则 「数独」（sudoku）来自日文，但概念源自「拉丁方块」，是十八世纪瑞士数学家欧拉发明的。游戏规则很简单，九个九宫格里，每一直行与每一横列都有１到９的数字，每个小九宫格里也有１到９的数字，但一个数字在每个行列及每个小九宫格里都只能出现一次。谜题会填上若干数字，其它宫位留白，玩家得自行依逻辑推敲出剩下的空格里是什么数字。 2． 游戏等级 分为低、中、高三级 低级：要求至少有一行或一列出题时已填上5个数据，其他可以随机安排，但是每行或每列必须有数据 中级：要求至少有一行或一列出题时已填上4个数据，其他可以随机安排，但是每行或每列必须有数据 中级：要求至少有一行或一列出题时已填上3个数据，其他可以随机安排，但是每行或每列必须有数据


myx: 06 八月 2005, 13:41
http://www.oubk.com/game/sudoku/Puzzles.html 这里可以在线玩