Pages

18/04/2014

如果數獨是RPG遊戲


曾經有個想法,就是以數獨為基礎,弄一個遊戲
那個遊戲不是普普通通玩完一關又一關的數獨,計劃加入劇情、RPG以及讓玩家之間互動的元素,不然,玩家很快就會厭倦。至少同時作為玩家的自己先厭倦,就好像每日一篇一樣,很快就沒有動力堅持下去。

所以單單只是按一個[玩]的按鈕,系統便生成一個隨機數獨。玩完又再重覆按一次,多無聊呀。盡使可以讓玩家自己選擇難度,還是挺悶。所以那種模式一定不可取,那是一種不能持久的遊戲設計。


如果數獨是RPG遊戲

好,有一個方向就要開始爬文。
首先,在數學上數獨組合都有盡頭。不如就將那個盡頭作為遊戲的終結啦。

原來9x9的數獨,全部組合總共5,524,751,496,156,892,842,531,225,600
一個令人卻步的數字,平凡的一生靠打工如果只可以得到8位數,那個數字真是遙不可及。
一個27位數英文叫作Octillion(short scale) = 10^27,以上的組合即 55 Octillion,才55個,事情立即明郎化。
===================================================================
首先預到第一個難題 - 關於重覆的數獨
===================================================================

忽然想到一個狀況

舉個例子,現在有道數獨難題。你解決完後,我把問題對稱反射,對你說那是另一道新的題目,你接受嗎?
相信很多人也不接受我那個說法,如果那兩道題目出現在你買回來的一本書"100題數獨難題",原本只有50題,商家把那50題反轉成了新的50題。總共100題,你更加會直指那是騙財。
不是50題,不是50多與少的問題,發現1題應該也接受不了。
同樣道理,
為此我們必須在55 Octillion中,除去對稱和其它類似手法的組合,例如是將5和7對調等等的手法。

接下來就是數據時間

如果有系統地把數字相互調換(好比以1換2、以2換7等),又或者如果把兩列或兩行交換。假設以這種化約的形式,那麼55 Octillion就會縮少成為377,597,570,964,258,816個組合,這是貝米耳(Stanley E. Bammel)與羅思坦(Jerome Rothstein)1975年發表在《離散數學期刊》(Discrete Mathematics)在美國俄亥俄州立大學期間的研究成果。

然後你很快又留意到了,除以上的手法。還有
如果將9x9分成A、B、C三區,調亂次序成B、C、A。數獨玩家也視為相同謎題。如此類推。


把重覆的組合再從組合中取除,那獨一無二的數獨組合總共5,472,730,538

一般而言,遊戲其中一種推動力就是要賦予玩家一個實在,可達到的目標。
假設遊戲目標定位成,破解所有唯一解的數獨。
基於唯一解的數獨已經由原來共 55 Octillion 個組合 縮小成 5,472,730,538,
目標立即可接受得多了。
另一方面,組合大減可以惠及系統設計及運作時,減輕數據負擔。

好,遊戲目標就訂在擊破 5,472,730,538 個擁一解的數獨
總共 5兆4億個數獨,那個數字已經縮到最少了,之後就要考慮出題的困難。

===================================================================
難題 - 生成數獨
===================================================================
首先大家要認識一下初盤,終盤。
完成一道數獨迷題,那個完成品就是終盤。唯一解的數獨是純種的數獨,初盤(解題前的模樣)只有一個排列方法,填滿數字後的最終形態就是終盤。

數獨出謎題的方法太多,其中一個十分常用的方式是需要終盤和初盤。
1. 隨機終盤,隨機圖形(初盤)
2. 隨機終盤,固定圖形(初盤)
3. 固定終盤,隨機圖形(初盤)

終盤如何獲得不重要,不是電腦有一大堆終盤就是胡亂試出來。
而初盤就是一道謎題的模樣。如下圖。

說到那裡已經真相大白,你可能經常玩一份報紙的數獨,然後發覺那個數獨好像玩過了。
那極之有可能是使用了固定終盤,隨機初盤的結果。
即是最終的答案一樣,只是給你作為提示的數字不一樣。

因此之故,二、三等等一些使用千篇一律的(終盤/初盤)都不可取,唯有使用 隨機終盤,隨機初盤
根據遊戲設計的其中一種特質就是由淺入深,
遊戲的數獨由難易度劃分,假設分成三級,入門都玩到級、有挑戰性級、瘋狂級、
現在我們要做的是將 5兆4億個數獨 按照難易度歸入以上三級,然後讓玩家選擇想挑戰的難度。

玩家的解謎能力因人而異,更會隨著時間變化。

一個數獨的難度,簡單來說取決於數獨提供了多少格數字。但是如果粗略地將提供60格為入門級、17格為瘋狂級
假設分成那樣
41~60格 入門級
21~40格 挑戰級
17~20格 瘋狂級
不過有些時候,一個數獨有30格玩起來超易,另一個同樣30格玩起來就很吃力。
目前大約有十多種解數獨的技巧,就好像小學生和大學生的課程有區別一樣。
有些技巧很少用到,有些技巧需要更多腦力去運用。
一個數獨使用10種小學生技巧便可以解決,
另一個則要使用10種大學生技巧才可解決。

以上例子可以知道,單單只靠提供數量劃分難易度,是完全不可靠。
那接下來或者需要為數獨標準化一個難度系數,
透過分析三十多種解數獨的技巧,為終盤計算出只有唯一解的初盤,又根據所使用的技巧數量和複雜程度,為每個初盤算出一個難度系數。

不過那樣做我會想到,有些時候 你認為 數對摒除法 很容易,可能對方認為很難。
那時候我們可能需要一個龐大的統計數據,每人每次玩數獨的時候。都一一記錄他使用了的時間,每次寫下正確數字的順序(那可以推測他所使用的技巧,以及每次寫下正確數字的時間間隔。

如果利用以上的統計數據,可以更準確地為每個數獨的難度數字化。
  1. 數對唯餘法
  2. 唯一法
  3. 宮摒餘法
  4. 二餘法
  5. 三餘法
  6. 四餘法
  7. 數對摒除法
  8. 區塊(或單元)數對唯餘法
  9. 唯餘法
  10. 行列摒餘法
  11. 矩形摒除法
  12. 數偶摒除法
  13. 猜測

===================================================================
實作時很有可能面對的其它難題
===================================================================
上述提到,唯一解的數獨有5,472,730,538,雖然知道那個數字,但是並沒有確切關於那5億個終盤的排列方法

即是說要自己寫一個程式出來,去自動找出或有能力檢查一下那個數獨有沒有唯一解。
如果那個數獨只有唯一解,就把它儲存起來。

假設實例︰

現在已知一個終盤,9x9的數獨以一串文字表示︰123456789587923641496781523315847962968132457274695138642319875759268314831574296

生成數獨的流程
  1. 根據玩家選擇的難易度,電腦決定為玩家提供25個數字作提示。
  2. 電腦隨機在81個字中找25個作為提示
  3. 檢查一下如果只有那25個是否符合唯一解,如果不符合就重覆上一步驟
例如算出初盤是︰000000080000020640006701000005840002900030007200095100000309800059060000030000000

以上所說,難易度不可能只取決於提示的數量,所以 流程應該改成

生成數獨的流程
  1. 根據玩家選擇的難易度,電腦決定為玩家提供25個數字作提示。
  2. 電腦隨機在81個字中找25個作為提示
  3. 檢查一下如果只有那25個是否符合唯一解,符合就記起來,重覆直至找出所有以25個作為提示又有唯一解的組合
例如找到十組,他們的難易度由淺至深,上至下排列。電腦應該很聰明地根據玩家選擇的難易度使用其中一個作為初盤
000000080000020640006701000005840002900030007200095100000309800059060000030000000
000000000080900640090081500305007002000030000200600108002310070059008010000000000
000000080507900600000080503005007002900030007200600100602010000009008304030000000
000006709500020000000001500005040062060030050270090100002300000000060004801500000
000006080580003000006700003000040062900030007270090000600009800000200014030500000
000050080580900600000000003000800960060132050074005000600000000009008014030070000
000006080580900000000700003010040062900030007270090030600009000000008014030500000
023050000000900001490000000010800000908132407000005030000000075700008000000070290
020400700500900040000001003005800002900030007200005100600300000050008004001004090
000006780007900041400080000000007002008030400200600000000010005750008300031500000
000450700007900040000000023005007002060030050200600100640000000050008300001074000

雖然不應只限定25個,不過在想想想的階段先簡單一點。

假設玩家破解了那道謎題,根據定好了的遊戲規劃(即是以5億個謎題作終點),我們必需記錄玩家已攻破的謎題
假設資料結構如下

數獨
數獨編號(PK) 終盤(Unique)
第一號謎題 123456789587923641496781523315847962968132457274695138642319875759268314831574296

玩家攻破記錄
玩家編號(FK) 已攻略的謎題(FK)
玩家A 第一號謎題
玩家A 第N號謎題

接下來,我們就必需填滿那5憶個終盤

可以寫個程式去不斷亂試,程式跑到電腦的壽命結束,可能也找不完?!

或者我認為可以讓玩家提供謎題,增加遊戲與玩家的互動性

無論什麼方法,玩家提供謎題或電腦隨機生成。都會是81個數字的組合,我們都需要另外寫一個程式去驗證一下那個組合是否有效的初盤/終盤
必需確保那個初盤只有唯一解,然後才可以得出那個是新謎題的結論,可以根據順序標示一個名稱- 第N號謎題

困難的是驗證那部份要測試一下,謎題是否和現存的數獨謎題重疊。
換言之,程式要把新謎題的變形全部列出,再把現存的每題謎題都變形,然後再比對。通過比對,才可證明新的謎題不是重覆的題目。

舉例如是電腦已儲存三條終盤,分別是︰
123456789587923641496781523315847962968132457274695138642319875759268314831574296
538697142762145938194283765925468317673521894481739256259374681346812579817956423
426183957578269431319754286287516394635498712941327865894675123163942578752831649

現在有另一個玩家提供一個初盤,電腦先自行破解那個數獨,它必需是唯一解的才可以繼續下去。

電腦算出來的終盤就是(或遊戲直接讓容許玩家提供終盤?!)
534678912672195348198342567859761423426853791713924856961537284287419635345286179

估且先把它分成上、中、下三部份進行變形,假設現在的排列是A-B-C (藍色-黃色-綠色)。
534678912672195348198342567 859761423426853791713924856 961537284287419635345286179
變形分別是
534678912672195348198342567 961537284287419635345286179 859761423426853791713924856
961537284287419635345286179 534678912672195348198342567 859761423426853791713924856
961537284287419635345286179 859761423426853791713924856 534678912672195348198342567
859761423426853791713924856 534678912672195348198342567 961537284287419635345286179
859761423426853791713924856 961537284287419635345286179 534678912672195348198342567

先簡化問題,先不考慮其它的變形,比如是分成3欄、對稱(左右、上下、左斜角對摺、右斜角對摺)、旋轉對稱(90度、180度、270度)……

之後要將電腦存在的三條終盤變形,如上步驟就會多了15個變形

玩家提供的終盤和玩家終盤變形共6個數獨,將那6個數獨續一 和 18個數獨( 電腦存在的3條終盤+15個變形) 一一比較。

當全部的數獨都不是相同的時候,才可將玩家提供的終盤存入電腦。

驗證數獨的效能
如果電腦已經有1000個數獨,玩家每提供一次數獨,每驗證一次,就需要重覆地把1000個數獨變形。變形的結果一定是一樣的了,
流程應該更改成那樣。

舉例二︰

數獨資料庫
數獨(PK), 數獨字串
數獨A, 534678912672195348198342567859761423426853791713924856961537284287419635345286179

變形資料庫
數獨(FK), 變形
數獨A, 534678912672195348198342567 961537284287419635345286179 859761423426853791713924856
數獨A, 961537284287419635345286179 534678912672195348198342567 859761423426853791713924856
數獨A, 961537284287419635345286179 859761423426853791713924856 534678912672195348198342567
數獨A, 859761423426853791713924856 534678912672195348198342567 961537284287419635345286179
數獨A, 859761423426853791713924856 961537284287419635345286179 534678912672195348198342567

現在有另一個玩家提供一個初盤,確保那個是唯一解的數獨後。

將玩家提供的初盤變形後續一搜索 數獨資料庫 和 變形資料庫
如果玩家提供的初盤是有效新的終盤,便可以將新終盤存入數獨資料庫,以及把比對時為新數獨生成的變形都存入變形資料庫。
那可以方便下一個新數獨驗證時,搜索是否與現存的變形相同。

一生人玩5億個數獨
雖然遊戲是玩不完,當初把5億個數獨設為盡頭就是一個特發奇想。如果讓你知道那個是玩不完的遊戲很有可能會撃沉玩的動力。
如果我有100歲壽命,1天玩一個數獨,我人生也只玩到36500個數獨而已。即算你每天玩100個也是玩不完。

那裡有點矛盾就是,遊戲應該宣傳成有終點?!不過那個終點又到不了。

那裡應該巧妙處理一下,如果可以有個公會/團體系統。只有公會的成員玩了5億個數獨,成員就算攻略了遊戲。那個感覺不錯,可以增加玩家之間的互動。
如果工會有100人,每人一天玩100個數獨,每人有100歲壽命。又都是玩了三百萬個數獨,還是距離很遠。

忽然想起,玩寵物小精靈/口袋裡的怪獸,不論叫啥,記得可以放一隻寵物給個老頭訓練。其後自己每走4步,還是5格?忘了,那隻寵物便上升了一經驗值。
或許可以借境一下,每玩10個數獨,電腦幫你完成一個?!按你投放進遊戲的時間計算,每特定時間,電腦幫你完成一個?!你有一隻智能機械人,你可以為你的機械人升級,能夠加快電腦幫你完成一個數獨的過程?!

不過好像還不夠,不如我們將5億個數獨分成十二份
第一份是Sudoku,第二份是Variants,第三份是Killer Sudoku,第四份是Cross Sums Sudoku……
大家投其所好就好,最後也可以集合十二份,那樣也算是攻略遊戲。

最重要是可以吸引其它不只愛玩Sudoku的玩家。

大前提是
要想出驗證的算法(algorithm)相信是一件最好玩的事情,不過光想想就頭痛,現在也有點痛。大家有一個好的算法嗎?
====================================================================
以上是一個曾經"如果將數獨實現成一個RPG遊戲"的想法

No comments:

Post a Comment