摘要：KenKen是一種類似于數(shù)獨(dú)的數(shù)字游戲，是數(shù)獨(dú)游戲與數(shù)學(xué)運(yùn)算規(guī)則的巧妙結(jié)合。它既能像數(shù)獨(dú)游戲那樣鍛煉人的邏輯思維能力，又能同時(shí)訓(xùn)練人的數(shù)學(xué)運(yùn)算能力。該文針對(duì)KenKen問題提出了一種高效、可行的生成算法，該算法包括三個(gè)部分的內(nèi)容：基于矩陣的初等變換生成滿足KenKen規(guī)則的解矩陣、運(yùn)用改進(jìn)的合并算法生成“盒子”和隨機(jī)生成“提示”?？苫谠撍惴ㄩ_發(fā)成型的軟件產(chǎn)品，用于啟蒙、教學(xué)、娛樂。

關(guān)鍵詞：KenKen；游戲；算法

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）04-0811-04

Study on the Generation Algorithm of KenKen Problem

TU Yang-yang

（Wuhan University of Science and Technology City College，Wuhan 430083，China）

Abstract： KenKen， a digital game similar to Sudoku， is the ingenious combination between Sudoku game and math rules. It not only can train a person's logical thinking ability like Sudoku games， but also can train their mathematical ability. In this paper， an efficient and feasible generation algorithm of KenKen problem has been put forward. This algorithm consists of three parts： generate solution matrix abide by KenKen rules based on elementary transformation of matrix， generate “Box” by improved merging algorithm and generate “Prompt” randomly. Software products can be developed based on this algorithm for enlighten， teaching and entertainment.

Key words： KenKen； game； algorithm

KenKen（又名聰明方格、算獨(dú)、Kendoku），一種類似于數(shù)獨(dú)的數(shù)字益智游戲，由日本東京一位名叫宮本哲也的老師為幫助兒童學(xué)習(xí)算數(shù)而發(fā)明[1]。它的規(guī)則是：給出N×N的方格，用1到N這些數(shù)字填入其中，每一行每一列都不能有重復(fù)的數(shù)字。方格中的黑色粗線框出若干個(gè)限定框，稱為“盒子”，每個(gè)盒子中數(shù)字的和、差、積或商會(huì)標(biāo)注在盒子的左上角，稱為“提示”[2]。例如提示是“6×”，則說明該盒子中的數(shù)字之積為6；提示是“2÷”，則說明該盒子中的大數(shù)除以小數(shù)的商為2；提示是“1”，則說明該盒子中的數(shù)為1，如圖1所示。

本文試圖對(duì)KenKen問題進(jìn)行分析，設(shè)計(jì)算法，達(dá)到實(shí)現(xiàn)利用計(jì)算機(jī)程序自動(dòng)生成KenKen問題的目的。

1 算法整體分析

通過觀察不難發(fā)現(xiàn)，KenKen問題，是由若干個(gè)盒子和與之對(duì)應(yīng)的提示兩個(gè)大的部分所構(gòu)成的。同時(shí)，提示又是根據(jù)其所在盒子內(nèi)的數(shù)字的計(jì)算結(jié)果而確定的，也就是說先得有數(shù)據(jù)，才能根據(jù)數(shù)據(jù)計(jì)算出提示。由此可以得出結(jié)論，要生成一個(gè)KenKen問題，算法必須要完成以下三個(gè)步驟的內(nèi)容：

1）生成一個(gè)滿足KenKen規(guī)則的解矩陣，作為提示的數(shù)據(jù)來源。矩陣為N階方陣，且每一行每一列均為1到N，N個(gè)互不相同的數(shù)字。

2）生成盒子。即對(duì)矩陣進(jìn)行劃分，將矩陣隨機(jī)劃分為若干個(gè)連續(xù)的小區(qū)域。

3）生成提示。根據(jù)每個(gè)盒子內(nèi)數(shù)字的數(shù)量與內(nèi)容，隨機(jī)產(chǎn)生運(yùn)算符號(hào)并計(jì)算運(yùn)算結(jié)果，從而得到提示的內(nèi)容。

2 算法詳細(xì)設(shè)計(jì)

2.1生成滿足KenKen規(guī)則的解矩陣

生成一個(gè)滿足KenKen規(guī)則的解矩陣，即對(duì)N階方陣賦值，使其每一行每一列均為1到N，N個(gè)互不相同的數(shù)。一個(gè)可行的辦法是使用拉斯維加斯算法[3]，即在N階方陣中隨機(jī)填入1到N，N個(gè)數(shù)，然后不斷地基于KenKen規(guī)則對(duì)其進(jìn)行求解，直到解出為止。其中，求解過程又可使用多種算法，例如比較排除法[4]、圖搜索策略法[5]、回溯法[6]、遺傳算法[7]等。

上述算法雖然可行，但多存在效率問題。KenKen問題雖與數(shù)獨(dú)問題類似，但是在規(guī)則上有所不同。不同之處在于：數(shù)獨(dú)問題不僅要求每行每列上的數(shù)字不能重復(fù)，還要求在每個(gè)小的3×3的宮格內(nèi)不能重復(fù)[8]；而KenKen問題只要求每行每列的數(shù)字不能重復(fù)。可以此為突破口，尋求更簡(jiǎn)單、更高效的算法來生成滿足KenKen規(guī)則的解矩陣。通過觀察，發(fā)現(xiàn)進(jìn)行矩陣的初等變換，即任意交換KenKen解矩陣的兩行或者兩列后[9]，得到的新矩陣依然滿足KenKen規(guī)則。如圖2所示為一個(gè)滿足KenKen規(guī)則的4階解矩陣，矩陣每行每列無重復(fù)數(shù)字。交換圖2的第一行和第三行得到圖3，交換圖3的第二列和第四列得到圖4。經(jīng)過交換后的圖3和圖4所示的矩陣依然為滿足KenKen規(guī)則的解矩陣。

由此得出結(jié)論，可以使用基于矩陣初等變換的算法來生成滿足KenKen規(guī)則的解矩陣，即可行，又具有較高的效率。具體做法是：首先生成一個(gè)固定的有規(guī)律的初始解矩陣（如圖5所示），然后對(duì)其進(jìn)行一定次數(shù)的隨機(jī)行變換和列變換，從而得到最終結(jié)果。例如對(duì)圖5所示的初始解矩陣進(jìn)行五次初等變換：依次交換第三、四列，第二、四行，第二、三列，第一、二行和第一、三行后，得到一個(gè)滿足KenKen規(guī)則的解矩陣（如圖6所示）。

此算法在實(shí)際操作的過程中存在一個(gè)可商榷的問題，即隨機(jī)初等變換的次數(shù)應(yīng)該如何確定?？上攵?，如果初等變換次數(shù)過少，那么初始的解矩陣會(huì)產(chǎn)生打亂不充分的現(xiàn)象；如果初等變換次數(shù)過多，則會(huì)影響效率且不能確保打亂效果。在此，提出兩點(diǎn)建議：1）通過對(duì)初等變換次數(shù)進(jìn)行大量的嘗試和調(diào)整，發(fā)現(xiàn)當(dāng)變換次數(shù)大于10次時(shí)，有著較好的打亂效果；2）如果想確保打亂效果，可以考慮在初等變換的過程中設(shè)置一個(gè)打亂效果評(píng)價(jià)指標(biāo)，直到滿足該指標(biāo)時(shí)停止變換。

2.2 生成盒子

隨機(jī)生成盒子，即將N階方陣為隨即劃分為若干個(gè)連續(xù)的區(qū)域，每個(gè)區(qū)域包含一定數(shù)量的方格。首先考慮到一個(gè)可行的算法：生成一個(gè)劃分方案，例如{4，3，3，2，2，1，1}，表示擬將方陣劃分為7個(gè)盒子，每個(gè)盒子包含的方格數(shù)量分別為4，3，3，2，2，1，1。然后按照此方案，隨機(jī)在方陣中依次劃分出這7個(gè)盒子，若碰到無法劃分下去的情況則回溯。這種算法對(duì)盒子數(shù)量和其包含的方格數(shù)量要求非常嚴(yán)格，由于回溯機(jī)制，使得算法存在效率上面的問題，并且劃分方案的生成也需要專門的算法設(shè)計(jì)。另外一個(gè)可行的算法是采取合并法，即從第一個(gè)方格1開始向下或向右試探其相鄰的方格2，若方格2不在盒子中就和方格1合并生成新的盒子，反之將方格1合并到方格2所在的盒子中[10]。這種算法不存在回溯，執(zhí)行效率較高，但是也存在一些問題。可想而知，劃分結(jié)束后，方陣內(nèi)的盒子包含的方格數(shù)量只可能為3，2或者1，不可能出現(xiàn)包含方格數(shù)量為3以上的盒子。同時(shí)只包含一個(gè)方格的盒子只可能在方陣底端出現(xiàn)且機(jī)率偏小。這樣一來會(huì)使KenKen問題顯得過分單調(diào)。

綜合分析，考慮將合并算法進(jìn)行改進(jìn)，采取改進(jìn)的合并算法對(duì)方陣進(jìn)行劃分，隨機(jī)生成盒子。為方便表述，用1到16依次對(duì)方陣逐行逐列進(jìn)行編號(hào)（如圖7）。下面以4階方陣為例說明算法思路：

1）給出兩個(gè)限定條件：1）生成的所有盒子中，包含方格數(shù)量的最大值不能超過P。2）生成的所有盒子中有且只有Q個(gè)只包含一個(gè)方格的盒子。這兩個(gè)條件的作用是為了規(guī)避合并算法的缺陷，為后期調(diào)整盒子提供依據(jù)。P值和Q值的確定是一個(gè)需要注意的問題：P值如果設(shè)置得過大，會(huì)使KenKen問題的難度過大，以致失去游戲性；而Q值設(shè)置得過大，會(huì)導(dǎo)致KenKen問題的難度過小，亦會(huì)影響到游戲性。對(duì)于四階的KenKen問題，我們不妨將P設(shè)為4，將Q設(shè)為2。

2）利用合并算法對(duì)方陣進(jìn)行初步劃分，過程如表1所示，劃分結(jié)果如圖8所示。

3）結(jié)合給出的兩個(gè)限定條件，對(duì)初步劃分結(jié)果進(jìn)行調(diào)整。調(diào)整的算法為首先檢測(cè)兩個(gè)限定條件是否成立，如果成立則退出調(diào)整；如果不成立分三種情況處理：1）只有P不成立，將不成立的盒子劃出一部分與相鄰盒子合并，使得剩下的盒子滿足P；2）只有Q不成立，隨機(jī)尋找一個(gè)包含方格最少的盒子，保留一個(gè)方格單獨(dú)成為一個(gè)盒子，將其余部分與相鄰盒子進(jìn)行合并；3）P和Q同時(shí)不成立，調(diào)整辦法與2相同。為提高效率，可在調(diào)整的時(shí)候做一個(gè)預(yù)判，檢測(cè)此次調(diào)整是否會(huì)將不滿足一個(gè)限定條件的情況變?yōu)閮蓚€(gè)條件都不滿足的情況。針對(duì)圖8所示的初步劃分結(jié)果，通過調(diào)整算法，將方格15并入了方格14所在的盒子，將方格12并入了方格8所在的盒子。去掉方格編號(hào)后，結(jié)果如圖9所示。

2.3 生成提示

生成提示需要算法做的事情，就是為方陣中的每個(gè)盒子隨機(jī)生成一個(gè)四則運(yùn)算符號(hào)，并利用運(yùn)算符號(hào)對(duì)盒子中的數(shù)字進(jìn)行運(yùn)算，進(jìn)而根據(jù)運(yùn)算符號(hào)和運(yùn)算結(jié)果生成該盒子的相應(yīng)提示。具體到為某一個(gè)特定的盒子生成提示的時(shí)候，算法需要分三種情況來處理：

1）如果某一個(gè)盒子包含的方格數(shù)量大于2，則只能在“+”和“×”兩種運(yùn)算符號(hào)中隨機(jī)生成一種。然后對(duì)盒子中的數(shù)字進(jìn)行連加或連乘的運(yùn)算，并根據(jù)運(yùn)算結(jié)果生成該盒子的提示。

2）如果某一個(gè)盒子包含的方格數(shù)量為2，則可在“+”、“-”、“×”和“÷”四種運(yùn)算符號(hào)中隨機(jī)生成一種。并對(duì)盒子中的數(shù)字進(jìn)行運(yùn)算，進(jìn)而生成該盒子的提示。這里注意兩個(gè)問題：1）在進(jìn)行減法和除法運(yùn)算的時(shí)候需要將較大的那一個(gè)數(shù)調(diào)整到運(yùn)算符號(hào)的左邊，避免在運(yùn)算結(jié)果中出現(xiàn)負(fù)數(shù)或零的情況。2）如果存在大數(shù)除以小數(shù)不能整除的情況，則只能考慮在“+”、“-”和“×”三種運(yùn)算符號(hào)中隨機(jī)生成一種進(jìn)行運(yùn)算。

3）如果某一個(gè)盒子僅包含一個(gè)方格，則不用生成運(yùn)算符號(hào)，直接將方格中的數(shù)字作為提示生成。

將圖6中滿足KenKen規(guī)則的解矩陣填入圖9的盒子中，對(duì)其按照算法生成提示（如圖10所示），再將盒子中的數(shù)字去掉，便生成了一個(gè)KenKen問題（如圖11所示）。

3 結(jié)束語(yǔ)

KenKen是數(shù)獨(dú)游戲與數(shù)學(xué)運(yùn)算規(guī)則的巧妙結(jié)合，不僅更加有趣好玩，同時(shí)也能寓教于樂。該文通過三個(gè)部分：基于矩陣的初等變換生成滿足KenKen規(guī)則的解矩陣、運(yùn)用改進(jìn)的合并算法生成盒子和隨機(jī)生成提示，提出了KenKen問題的高效、可行的生成算法。在經(jīng)濟(jì)文化日益發(fā)展的今天，人們的生活水平得到了很大的提高。生活在鋼筋混凝土大都市里的人群，每天都要面對(duì)各種各樣的生活壓力[11]?；诒舅惴ㄩ_發(fā)出成型的軟件產(chǎn)品，可以緩解人們的壓力，放松大腦，提供最好的思維鍛煉。同時(shí)可用于啟蒙、教學(xué)，對(duì)孩子熟悉四則運(yùn)算，提高邏輯推理能力，激發(fā)對(duì)數(shù)學(xué)的熱愛起到潛移默化的積極推動(dòng)作用。

參考文獻(xiàn)：

[1] 覃琛琛. KenKen：A New Sudoku Puzzle新數(shù)獨(dú)游戲[J].數(shù)學(xué)教學(xué)通訊：數(shù)學(xué)金刊，2009（6）.

[2] 王瑞霖，張惠英.用KenKen游戲提高學(xué)生邏輯運(yùn)算能力與邏輯思維能力[J].教育實(shí)踐與研究：中學(xué)版（B），2012（4）.

[3] 薛源海，蔣彪彬，李永卓.基于“挖洞”思想的數(shù)獨(dú)游戲生成算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2009（21）.

[4] 易珺，朱靜文，曹東.數(shù)獨(dú)求解算法的設(shè)計(jì)與實(shí)現(xiàn)[J].科學(xué)技術(shù)與工程，2010（27）.

[5] 李昊.基于圖搜索策略的數(shù)獨(dú)問題算法與實(shí)現(xiàn)[J]. 通化師范學(xué)院學(xué)報(bào)，2009（10）.

[6] 李盤榮.數(shù)獨(dú)游戲的算法研究與實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)，2008（26）.

[7] 黎永達(dá)，鄧秀勤.基于改進(jìn)的遺傳算法的數(shù)獨(dú)謎題求解[J].計(jì)算機(jī)應(yīng)用與軟件，2011（3）.

[8] 劉曉寶.數(shù)獨(dú)游戲的解題算法[J].電腦編程技巧與維護(hù)，2007（5）.

[9] 陳祥云.矩陣的初等變換及其應(yīng)用[J].高等函授學(xué)報(bào)：自然科學(xué)版，2012（2）.

[10] 金偉，譚勁.一種數(shù)字迷宮游戲程序設(shè)計(jì)[J].計(jì)算機(jī)時(shí)代，2012（7）.

[11] 郭東恩，吳剛.基于Android平臺(tái)的數(shù)獨(dú)游戲設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)與數(shù)字工程，2012（3）.