吹鼓吹小站 主頁
論壇首頁 論壇首頁 > 學術理論 > 心裁專欄
  最近新文章 最近新文章 RSS - 自創的解數獨程式
  幫助 幫助  搜索論壇   註冊 註冊  登錄 登錄

自創的解數獨程式

 發表回覆 發表回覆 頁  123>
發表人
內容
  主題 搜索 主題 搜索  主題功能 主題功能
孫心裁 顯示下拉菜單
特級會員
特級會員
頭像

註冊時間: 2000 Aug 21
狀態: 離線
積分: 7940
文章功能 文章功能   引用 孫心裁 引用  發表回覆回覆 點擊鏈接返回原帖 主題: 自創的解數獨程式
    發表:  2006 Mar 18 10:08am
何謂「數獨」?
「數獨」(su doku)源自日文
数字は独身に限る(Suji wa dokushin ni kagiru),
意思是「獨立的數位」。
此名字由號稱「數獨教父」的日本人
鍜治真起所創,
(他是日本數字猜謎權威
Nikoli出版社的董事長,)
但概念源自「拉丁方塊」,
是十八世紀瑞士數學家
歐拉(1707∼1783) 發明的。

在一個大九宮格裡,
每一大格中
又各有一個小九宮格
構成一個共81格的「拉丁方塊」
謎題會在一部份的小格中
填上若干數字,
(其他小格留白,)
玩家得自行依遊戲規則
用邏輯推敲出所有剩下的空格裡
各應是什麼數字?
而遊戲規則只有兩個:

1.每一直行/每一橫列/每個小九宮格裡
都有1到9的數字,
2,同一個數字,在同行/同列/同小九宮格裡
就只能出現一次。

規則雖說有兩個
實則這兩個規則是互訊的
----既然九格中
只有1到9這九個數字
則當然是不可能重複的
但要在九格中
填入不同的九個數字
卻是可有多種選擇的
(譬如0-8就也是另一種選擇)
中國時報的A12版每天都會刊出不同的題目,
供讀者試答,
以下是某日數獨的題目與答案:

返回頂部
flowofsoul 顯示下拉菜單
初級會員
初級會員


註冊時間: 2005 Aug 18
狀態: 離線
積分: 84
文章功能 文章功能   引用 flowofsoul 引用  發表回覆回覆 點擊鏈接返回原帖 發表:  2006 Mar 18 12:11pm
這種問題用遞迴的寫法來解是最方便的了,但通常要跑上很久就是了。
改成用for迴圈會更快,但要寫出非常複雜的邏輯。
有一段時間也很興致寫一堆演算法來解問題,
但因我的數學不好,程式寫出來沒效率,
導致挫折感十足,後來就沒再碰這個了。
孫老師有看過充分、清晰的介紹數學的書嗎?
最好是每一個方程式都有詳細的推算、解釋過程的那種。
返回頂部
孫心裁 顯示下拉菜單
特級會員
特級會員
頭像

註冊時間: 2000 Aug 21
狀態: 離線
積分: 7940
文章功能 文章功能   引用 孫心裁 引用  發表回覆回覆 點擊鏈接返回原帖 發表:  2006 Mar 18 3:52pm
據說
原始的「拉丁方塊」遊戲比較容易,
故並沒有得到世人的注目,
(我猜它只有(2^4=)16格
而非現在的(3^4=)81格
《每日電訊報》宣稱將要推出3D的同類游戲
茍依我的程式邏輯
就算是(4^4=)256格
甚至(5^4=)625格
.........
用電腦來解
也只須一瞬間即能完成)
1979年,
美國的侯活更斯
將此「拉丁方塊」遊戲
命名為「填入數字」遊戲,(Number Place)
開始刊於一本數學邏輯雜誌內,
1984年一本日本游戲雜誌
(Puzzle Tsusgin Nokili)出版商
在這本美國雜誌上看到這個遊戲,
帶回日本後,
命名為sudoku
(中文忽略最後的Ku音
將之譯為「數獨」)
成為全日本最流行的猜謎遊戲,
超過一百萬人成為數獨玩家。
把數獨「發揚光大」、
創造出全球今天這股數獨熱的
是紐西蘭裔英國香港退休法官
韋恩.古德(Wayne Gould)
(有另譯為高樂德,或戈登者)。

1997年Gould旅遊日本時,
買了一本數獨遊戲書,
並對其受歡迎程度大感驚訝,
從此就迷上了,
於是用了六年時間,
發明了一套電腦程式
以設計不同難度的謎題,
自己開始製作謎題。
現在且經營了自己的數獨網站:
www.sudoku.com

2004年11月
他向英國《泰晤士報》推介此遊戲,
並開始每日一題地
供稿給英國《泰晤士報》,
立刻讓英國人陷入瘋狂。
因為英國等歐美國家
本就有玩字謎的傳統,
故在英國的公車公園......內、
常可以看到某些乘客,遊客低著頭、
據精會神渾然忘我的在玩自謎遊戲!
而數獨數這種遊戲
只是各式各樣字謎中的一種而已。
只是數獨因有著一種獨特的魅力。
終使得它得已一炮而紅,
據說英國《泰晤士報》的銷量
因為刊登「數獨」
而打破銷售紀錄。
最近英國政府出資的「教師」雜誌
甚至建議把「數獨」引進課堂,
作為學生鍛鍊腦力的教材。
稍後除《泰晤士報》外,
英國《每日郵報》也開始連續刊載此拼圖遊戲,
數獨遂在英國正式掀起熱潮,
更推廣至世界各地。
在英國還出現了數獨類的電視節目,
外國更有電視直播的數獨比賽。
http://images.google.com/imgres?imgurl=http://www.takungpao.com/news/images/06/03/13/ym-21.jpg&imgrefurl=http://www.takungpao.com/news/06/03/13/YM-537405.htm&h=339&w=500&sz=26&tbnid=VWevE-93vEioWM:&tbnh=86&tbnw=127&hl=zh-TW&start=1&prev=/images%3Fq%3D%25E6%2595%25B8%25E7%258D%25A8%25E6%25AF%2594%25E8%25B3%25BD%26svnum%3D10%26hl%3Dzh-TW%26lr%3D

(包括較簡單的<古典數獨>、
較複雜與最困難的變體
例如<機械數獨>和<額外區域數獨>。)
數獨在英國爆紅後,
這股數獨風又吹回美國、日本及歐洲各國。
「數獨」受歡迎的程度
可說已迅速「全球化」。
繼古爾德之後
蕭茨也在美國掀起另一股熱潮。
如今,蕭茨有五本數獨著作躋身於《今日美國報》
一百五十本暢銷書排名榜之行列。
一部有關蕭茨的電影《文字遊戲》
也正在「太陽舞」電影節上首映,
很快就會在美國各地公映。
隨著數獨熱潮的吹襲全球,
香港的數獨熱潮也在去年火速興起,
多本報章及雜誌都有刊登數獨遊戲。
雖然在英國和別的國家
也有其他人製作數獨謎題,
但是古德始終是最「正宗」、最受歡迎的。
(他通過自己的網站
與他的智力遊戲著作
已賺得一百萬美元)
他現在供稿給全球幾十家報社,
也另外製作新謎題出書,
台灣的中國時報和時報出版
則是台灣手個獲得他獨家授權的媒體。
且出板了兩本數獨書刊:

隨著「電子數獨機」的面世,
(數獨遊戲 (SuDoku) 下載地方:
www.info.com.tw
210.209.26.19)
玩家可隨時「開始」和「儲存」謎題,
將數獨熱潮進一步推高。
返回頂部
孫心裁 顯示下拉菜單
特級會員
特級會員
頭像

註冊時間: 2000 Aug 21
狀態: 離線
積分: 7940
文章功能 文章功能   引用 孫心裁 引用  發表回覆回覆 點擊鏈接返回原帖 發表:  2006 Mar 18 4:09pm
>這種問題用遞迴的寫法來解
>是最方便的了,
>但通常要跑上很久就是了。
>改成用for迴圈會更快,
>但要寫出非常複雜的邏輯。
>孫老師有看過數學的書嗎?
>最好是每一個方程式
>都有詳細的推算、解釋過程的那種。
數獨與數學(尤其是方程式)無關呀!
為何要看數學的書呢?
要看那些數學的書呢?
for只是迴圈的一種麼
無論那一種迴圈
(無論多慢啦!)
要解數獨應該一瞬間就能完成吧!?
又何謂遞迴呢?
邏輯麼,還能複雜到那裡去呢?
常用的邏輯符號
不就只有OR,AND,NOT,XOR四種而已麼
數獨的人工解法雖有且須共用多種
但我是單用邏輯符號
(及候選/刪除兩法)
就把它設計完成了
我總認為
把事情作對
比把事情作好
更重要啦
可以談談
您主要是用什麼理念與方法
來設計此數獨解程式的麼?
在我還沒公開發表此程式以前
有網友願發表發表高見的麼?
(簡單說說理念與方法即可)
若與我的構想一樣
又比我晚一步
不是很可惜麼?
>韋恩.戈登用了六年時間,
>發明了一套電腦程式
>以設計不同難度的謎題,
>自己開始製作謎題。

若只是出題的程式
只要幾天就能設計好了呀
韋恩.戈登為何要用六年的時間呢?
他用的是什麼基本設計邏輯呢?
有興趣的網友
對此也可發表一下看法
返回頂部
flowofsoul 顯示下拉菜單
初級會員
初級會員


註冊時間: 2005 Aug 18
狀態: 離線
積分: 84
文章功能 文章功能   引用 flowofsoul 引用  發表回覆回覆 點擊鏈接返回原帖 發表:  2006 Mar 18 5:34pm
遞迴只是一種程式設計方法而已,它是一種可以自己呼叫自己的方程式。
只要把條件式寫好,防呆作好(就是別讓它變成無限迴圈),
它就可以自己不斷的呼叫自己,直到解出設計師給的東西。
用遞迴可以解決很多東西,但若換成for這種迴圈的話,
就會變成要寫出相當複雜的邏輯結構出來。
像著名的河內塔問題,用遞迴寫只要短短幾行就可解(三行),
但若不用遞迴,要寫出相對之下很複雜的程式才解得出來。
至於數學,資料結構及演算法的部份大概都要用到離散數學,
所以數學很重要,雖不是必備,但精通數學的人,
寫出來的程式效率就是高人一等。
而且我也真的很想學好數學,坊間看到的書都是那種還在教邏輯運算式,
就需用上還沒教到的定理,看到這種書真的讓我很火大。
而且定理也沒有解釋清楚,給個名字就帶過了,騙錢的東西。
至於這程式,大概我會用暴力法,基本當然是先弄個二維陣列,
然後用迴圈,從(1.1)(還沒有放資料的陣列)開始試,
先檢查x、y、同小九宮格有的數字,從沒有的開始試,
然後 作(y++,if y > 9 則 x++,y = 1) 跳進。
中間的條件式(函式)是若x、y、同小九宮格都已有經1-9的數字的話,
就跳回上一層(y--)再試不同的數字,if y = 0 則跳至(x-1.y+9)再試。
大概想法是這樣,沒經過驗證說不準行不通,
而且實作上也還有一些技術細節要克服。
但這問題若能用遞迴解,會解得相當漂亮又簡短。
不過這種東西真的要常摸,久了沒用有時連語法都不記得了。
返回頂部
孫心裁 顯示下拉菜單
特級會員
特級會員
頭像

註冊時間: 2000 Aug 21
狀態: 離線
積分: 7940
文章功能 文章功能   引用 孫心裁 引用  發表回覆回覆 點擊鏈接返回原帖 發表:  2006 Mar 18 6:28pm
>遞迴是一種可以自己呼叫自己的“方”(?)程式。
>若換成for這種迴圈的話,
>就要寫出相當複雜的邏輯結構出來。
不懂!
>「資料結構」及「演算法」的部份
>大概都要用到「離散數學」,
更不懂!
解數獨應用不到這些
>坊間看到的書
>都還在教邏輯運算式,
解數獨應用不到這些
>這程式我會用「暴力法」,
(應是蠻幹法)
>基本當然是先弄個二維陣列,
>然後用迴圈,從(1.1)
>(還沒有放資料的陣列)開始試,
>先檢查x、y、同小九宮格有的數字,
>從沒有的開始試,
>然後 作(y++,if y > 9 則 x++,y = 1) 跳進。
>...................................
>但這問題若能用遞迴解,
>會解得相當漂亮又簡短。
恐沒有這麼簡單!
戰術我們先不談
只談戰略問題
您所說的此法
只相當於人工所謂的「唯一法」
──九數字中已有了八個數字
故此格就只能填入那所缺的那一個數字
但此法只可能用於遊戲最後
遊戲一開始時
可能沒有任何一空格可用此法來解
就別說只出現了三四個數字
就算已出現了七個數字
則此格也還是有兩種可能麼!
請問此時
您的程式怎麼辦呢?
返回頂部
flowofsoul 顯示下拉菜單
初級會員
初級會員


註冊時間: 2005 Aug 18
狀態: 離線
積分: 84
文章功能 文章功能   引用 flowofsoul 引用  發表回覆回覆 點擊鏈接返回原帖 發表:  2006 Mar 18 7:04pm
其實我這法也能算是試誤法,就像有些破解密碼的暴力軟體一樣,
採用不斷嘗試各種字元組合的方式來解碼。
一開始我的程式會找出第一個內部不含資料的座標(x.y),
然後在1-9的數字內選出不是「該x.y軸及同小宮格的數字」。
(從1開始作檢查)
把這個數字填入該座標(x.y),然後它會進行y++,
(if y > 9 ,則 x += 1 , y = 1 )
再度分析「該x.y軸及同小宮格的數字」,
中間若發現即使加至9仍違反到規則,即代表就是上個數字錯,
然後程式會進行(y--),再將此時的(x.y)內含數字再分析並往下加1。
若該內含資料已增至9還是違反規則,則再執行(y--)。
當y為0時,則執行(x -= 1.y = 9)。
也就是說,只要每次發現違反規則,它就不斷往後退然後再執行檢查。
只要程式邏輯沒有出錯的話,每一種組合都會試到的。
也就是說,大概算個幾千萬次就能解出答案。
不過這對電腦來說,算小意思,幾千萬次的for迴圈也不過彈指間。
遞迴說得清楚點,就是寫個function,
然後在function的後面寫上這個function的名字,
這樣這個function就會自己呼叫自己,
設計師只要設定到達某條件function跳出即可。
解數獨的程式就可算是一種演算法了,
至於數學,只是我自己想要知道而已,
跟數獨是沒關係,藉題發問一下而已,孫老師多包涵。
返回頂部
孫心裁 顯示下拉菜單
特級會員
特級會員
頭像

註冊時間: 2000 Aug 21
狀態: 離線
積分: 7940
文章功能 文章功能   引用 孫心裁 引用  發表回覆回覆 點擊鏈接返回原帖 發表:  2006 Mar 18 10:06pm

>我這法是試誤法,
>採用不斷嘗試各種「字元組合的方式」(?)
>來解碼。
>一開始我找出第一個
>內部不含資料的座標(x.y),
也就是空格麼!
>然後(從1開始作檢查)
>選出不是「該x.y軸及同小宮格的數字」。
>把這個數字填入該座標(x.y),
也就是該空格「可能的數字」
但「可能的數字」並不一定只有一個
對不對!
我就是要請問您
當此格可填入的數字
有兩種可能以上時
您的程式怎麼辦呢?
要不要把這些數字
填入該空格(座標)內呢?
>然後它會進行y++,
>(if y > 9 ,則 x += 1 , y = 1 )
>再度分析「該x.y軸及同小宮格的數字」,
也就是依(1,1)→(1,2)→(1,3).....→(1,9)
→(2,1)→(2,2)→(2,3).....→(2.9)
→....................... →(9,9)
的次序麼!
>若發現即使加至9,
>仍違反到規則,
>即代表就是上個數字錯,
“違反”到那一規則?
“上個數字”是那一個數字?
“加至9”,亦謂由1到9逐數去試對麼?
怎麼個”錯法”?
就是不能得到「唯一」的正解對麼!
>然後程式會進行(y--),
>再將此時的(x.y)內含數字
>再分析並往下加1。
(也就是減一,由9到一對麼?!)
>若該內含資料已增至9還是違反規則,
>則再執行(y--)
>當y為0時,則執行(x -= 1.y = 9)。
>也就是說,只要每次發現違反規則,
>它就不斷往後退然後再執行檢查。
>只要程式邏輯沒有出錯的話,
>每一種(red)組合(/red)都會試到的。
也就是依(9,9)→(9,8)→(9,7).....→(9,1)
→(8,9)→(8,8)→(8,7).....→(8.1)
→....................... →(1,1)
的次序麼!
不就只是一個數字一個數字的試麼
那有什麼「組合」呀?
總之老問題還是繼續存在著
此法只能算出
每一空格「可能的」數字集合
但「可能的數字」
(也就是此集合的個數)
並不一定只有一個
當此格有兩種可能以上時
你就是試個千萬遍
此格的可能還是有兩種可能以上麼
能解的固然能解
(根據事實,此種可能實極少)
不能得解的
就始終還是不能得解麼
有什麼理由
有兩種可能以上的
一定會變成只剩一個可能呢?
我懷疑您是否並沒有實際玩過此遊戲喔!
返回頂部
flowofsoul 顯示下拉菜單
初級會員
初級會員


註冊時間: 2005 Aug 18
狀態: 離線
積分: 84
文章功能 文章功能   引用 flowofsoul 引用  發表回覆回覆 點擊鏈接返回原帖 發表:  2006 Mar 19 4:49am
它一次只會填入一個呀「從1開始算,沒有違反到規則的數字」,
然後會進行(x.y+=1)的跳進,同時一樣再用上面的規則填入數字。
像上面的範例,程式在自動在(1.1)填入3、(1.3)填入4,
然後會在(1.4)填入2(因此時這個2仍沒有違反到規則)。
我們先假設程式跳到(1.6)時,發現不管是填入1-9都會違反到規則好了,
它就會自動回到(1.4),並將(1.4)的內含量+1,再往下繼續試。
所以每一格它都會從1開始試誤,即使有再多可能也還是可解啊。
這不過就是數學上的排列組合而已(9的9次方再9次方再扣掉重覆的)。
總不可能我每一個空格都從1開始試,卻試不出解答吧。
再舉例:如一個人請我猜一9位數,一樣是每個數字都不能重覆。
我的程式第一次就會猜123456789,發現錯誤,
就會換猜123456798,還是錯就是猜123456879。
以此類推,每種組合都會試到的。
返回頂部
孫心裁 顯示下拉菜單
特級會員
特級會員
頭像

註冊時間: 2000 Aug 21
狀態: 離線
積分: 7940
文章功能 文章功能   引用 孫心裁 引用  發表回覆回覆 點擊鏈接返回原帖 發表:  2006 Mar 19 7:11am
哇!您起的比我還早麼?
>如一個人請我猜一9位數,
>一樣是每個數字都不能重覆。
>我的程式第一次就會猜123456789,
>發現錯誤,
>就會換猜123456798,
>還是錯就是猜123456879。
>以此類推,
>每種組合都會試到的。
>總不可能我每一個空格都從1開始試,
>卻試不出解答吧。
為什麼不可能呢?
我還是懷疑您
並未親自完過此遊戲
此遊戲每一題都只有一個正解
只要錯一個格
就不可解得出來了
但你用迴圈去[試誤]的話,
卻幾乎每一格都可有多解
照您這種試法
此多解且多到極驚人的地步
請問您怎麼知道
那一數才是正解呢?
您用什麼方法與標準
排除那些誤解
來求得此正解呢?
您又說每一個空格都從1開始試
那就應只試到9而已麼
怎會有試九位數的須要呢?
難怪您會說
"大概要算個幾千萬次"
(恐怕要千萬的千萬次方次喔!)
但我敢直率的評估
無論如何
您的這個策略
都屬南轅北轍的蠻幹
可能是連一個格子
都解不出答案來的
因為您根本就沒有正解的標準
所以在嘗試的過程中
根本無法篩選出任何一個正解來
且根本連每一空格
在未得到正解前
常有多解的事實
都還不知道
電腦是模擬人工的
單憑絕沒有人
會用/能用此法來解數獨
就已可知
您的此法完全不可行
絕對不會成功
甚至可能連一個格子
都解不出來!
返回頂部
 發表回覆 發表回覆 頁  123>
  分享文章   

論壇跳轉 論壇權限 顯示下拉菜單

Forum Software by Web Wiz Forums® version 10.18
Copyright ©2001-2014 Web Wiz Ltd.

本頁處理時間為 0.203 秒