人工智能完成總結(jié)報(bào)告

1、完成總結(jié)報(bào)告項(xiàng)目名稱：數(shù)獨(dú)游戲設(shè)計(jì)與實(shí)現(xiàn)組 員：王鄭合 2014204081欒杰 2014204080文寬 2014204104二二年三月二十四日1問(wèn)題描述1.1問(wèn)題說(shuō)明數(shù)獨(dú)游戲起源于瑞士，由十八世紀(jì)的瑞士數(shù)學(xué)家歐拉發(fā)明，是一種數(shù)字拼圖 游戲，其游戲規(guī)則是： 在9X9的大九宮格內(nèi)，已給定若干數(shù)字，其他宮位留白，玩家需自己按 照邏輯推敲出剩下的空格里是什么數(shù)字。必須滿足的條件：每一行與每一列都有1到9的數(shù)字，每個(gè)小九宮格里也有1到9的數(shù)字，并且一個(gè)數(shù)字在每行、每列及每個(gè)小九宮格里只能出現(xiàn)一次, 既不能重復(fù)也不能少。每個(gè)數(shù)獨(dú)游戲都可根據(jù)給定的數(shù)字為線索，推算解答出來(lái)71B4342T7.114305

2、9113：21Ba11.2數(shù)獨(dú)求解描述由于數(shù)獨(dú)游戲的推廣與普及，在當(dāng)今世界上有著大量的數(shù)獨(dú)愛(ài)好者， 本項(xiàng)目 的目的就是按照數(shù)獨(dú)的游戲規(guī)則，通過(guò)對(duì)數(shù)據(jù)結(jié)構(gòu)的分析和人工智能算法的研 究，利用計(jì)算機(jī)程序來(lái)實(shí)現(xiàn)對(duì)已知數(shù)獨(dú)游戲的快速求解。1.3數(shù)獨(dú)出題描述數(shù)獨(dú)游戲挑戰(zhàn)者的水平各異，對(duì)數(shù)獨(dú)題目的難度要求各不相同，所以本項(xiàng)目 致力于設(shè)計(jì)一種算法，使其在盡可能短的時(shí)間內(nèi)生成不同難度等級(jí)的數(shù)獨(dú)題， 以 滿足不同水平游戲者的需求。同時(shí)，該算法還要考慮到三個(gè)方面要求： 可變化的 難度、解的唯一性和算法復(fù)雜度最小化。2功能分析2.1數(shù)獨(dú)求解數(shù)獨(dú)雖然號(hào)稱是數(shù)學(xué)問(wèn)題，但在求解時(shí)幾乎用不上數(shù)學(xué)運(yùn)算方法，事實(shí)上它 更像是一種

3、思維方式。數(shù)獨(dú)游戲開(kāi)始后，要想在空格中填入正確的數(shù)字，先要根 據(jù)數(shù)獨(dú)游戲規(guī)則對(duì)1-9分別進(jìn)行邏輯判斷，然后選擇正確的數(shù)字填入空格。另外， 由于某個(gè)格子填入數(shù)據(jù)時(shí)，有可能還要對(duì)原來(lái)已填入的數(shù)據(jù)進(jìn)行修正， 所以可以 考慮使用遞推和回溯搜索來(lái)求解數(shù)獨(dú)問(wèn)題。2.2數(shù)獨(dú)出題出題時(shí)，要能保證算法生成的數(shù)獨(dú)題具有可變化的難度和唯一解 ，該算法內(nèi) 部應(yīng)該包含有對(duì)數(shù)獨(dú)題的求解和評(píng)級(jí)功能。 本項(xiàng)目使用了一種基于“挖洞”思想 的數(shù)獨(dú)題生成算法，將該算法的設(shè)計(jì)工作分為評(píng)級(jí)、求解和生成三部分工作。利 用隨機(jī)數(shù)出現(xiàn)的概率不同來(lái)確定不同的難度， 通過(guò)避免重填一個(gè)被“挖去”的格 子，或者回溯到一個(gè)曾經(jīng)無(wú)法“挖去”的格子，來(lái)降

4、低算法的復(fù)雜性。2.3題目保存當(dāng)用戶需要退出卻仍沒(méi)有完成數(shù)獨(dú)題目的解答時(shí)，可以選擇是否保存當(dāng)前的求解進(jìn)度。如果需要，本系統(tǒng)會(huì)幫助用戶將目前未完成的數(shù)獨(dú)題目的解答進(jìn)度保 存起來(lái)，以便用戶下次使用本系統(tǒng)時(shí)，可以繼續(xù)解答上次未完成的題目。2.4題目讀取用戶可以在程序開(kāi)始運(yùn)行后，選則讀取一道之前保存起來(lái)的題目進(jìn)行解答， 被讀取的題目將會(huì)顯示到程序界面上。3.1功能結(jié)構(gòu)圖3系統(tǒng)設(shè)計(jì)數(shù)獨(dú)游戲諭入輸出解題邈目檢殮本程序主要有數(shù)獨(dú)求解和數(shù)獨(dú)出題兩個(gè)功能，數(shù)獨(dú)求解包括題目檢驗(yàn)、解題 和輸入輸出，數(shù)獨(dú)出題包括答案檢驗(yàn)、難度選擇、出題和輸入輸出。3.2業(yè)務(wù)流程圖3.3類圖t>rc(1010J- ini qud

5、o貿(mào)時(shí) irt 冊(cè)盟 i嚴(yán) mm腓ale【覽"耐int nvbewfBl irr+ randoimQ *口詔+ hideQ - void+ mateProbierifiOvo«dSudokuDIg類：程序的界面類Solve類：實(shí)現(xiàn)數(shù)獨(dú)題目求解功能Make類：實(shí)現(xiàn)數(shù)獨(dú)題目出題功能 Pre類：對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。3.4界面設(shè)計(jì)3.5算法設(shè)計(jì)數(shù)獨(dú)求解算法解決該數(shù)獨(dú)求解問(wèn)題時(shí)的要考慮的主要方面有： 判斷題目合法性，即驗(yàn)證給出數(shù)據(jù)本身是否符合游戲規(guī)則， 行、列以及小 九宮中從不重復(fù)地出現(xiàn)數(shù)字1-9 ； 采用遞推算法，若可以填入數(shù)字則填入數(shù)字，并入棧以便回溯，否則回溯 至前面填入數(shù)字處重

6、新填數(shù)； 所有空白處都要填滿數(shù)據(jù)；其中，最重要的就是如何通過(guò)遞推算法填入正確的數(shù)字，或者通過(guò)回溯算法 重新填入數(shù)字并得到最終解，這是本算法的核心內(nèi)容?；厮莘ㄊ墙鉀Q數(shù)獨(dú)問(wèn)題的有效方法，有著較快的解題速度。然而一般的常用 的回溯算法仍然有不足之處，比如會(huì)進(jìn)行重復(fù)的運(yùn)算。所以在采用回溯法之前， 還可以利用一點(diǎn)小技巧，以縮短回溯算法的運(yùn)行時(shí)間，甚至可將運(yùn)行時(shí)間縮短接 近于0。這個(gè)小技巧即在回溯算法的基礎(chǔ)上，采用有限遞推算法進(jìn)行預(yù)處理。算法活動(dòng)圖如下：說(shuō)取鵡目數(shù)獨(dú)出題算法要想設(shè)計(jì)一個(gè)算法用以生成各種難度等級(jí)的數(shù)獨(dú)題，通過(guò)對(duì)游戲規(guī)則的分 析，首先從三個(gè)方面定義難度等級(jí)，分別是已知格總數(shù)、已知格的分布和窮舉

7、搜 索復(fù)雜度。本算法采用“挖洞”思想，經(jīng)過(guò)以下步驟生成數(shù)獨(dú)題: 用隨機(jī)算法生成一個(gè)數(shù)獨(dú)題目; 用求解算法生成終盤(pán); 根據(jù)難度挖去部分?jǐn)?shù)字；整個(gè)生成數(shù)獨(dú)題的算法分為兩步執(zhí)行：先利 用拉斯維加斯隨機(jī)算法隨機(jī)生成一個(gè)填滿數(shù)字 且符合游戲規(guī)則的終盤(pán)；而后根據(jù)所需求的難度 等級(jí)抹去一些數(shù)字，難度等級(jí)由隨機(jī)數(shù)出現(xiàn)的概 率來(lái)決定。算法活動(dòng)圖如下：4系統(tǒng)實(shí)現(xiàn)4.1開(kāi)發(fā)平臺(tái)本項(xiàng)目基于Visual Studio 2010平臺(tái)的MFC采用C+語(yǔ)言進(jìn)行開(kāi)發(fā)與測(cè)試。4.2運(yùn)行環(huán)境本項(xiàng)目可在各個(gè)版本的 Win7系統(tǒng)或者Windows XP系統(tǒng)下運(yùn)行。4.3數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。通常情況下，精心選擇

8、的數(shù)據(jù)結(jié) 構(gòu)可以帶來(lái)?yè)碛懈叩倪\(yùn)行或存儲(chǔ)效率的算法。一般認(rèn)為，一個(gè)數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來(lái)的，對(duì)數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的 邏輯結(jié)構(gòu)；數(shù)據(jù)必須在計(jì)算機(jī)內(nèi)存儲(chǔ)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)形式， 是其在計(jì)算機(jī)內(nèi)的表示。數(shù)獨(dú)從形式上看是一個(gè)方陣 ，十分適合用數(shù)組來(lái)表示。431 主要數(shù)組本項(xiàng)目中所用到的主要數(shù)組有： int sudoku82該數(shù)組的用途是存儲(chǔ)題目以及保存最終結(jié)果，所有的9X 9個(gè)數(shù)字被依次存儲(chǔ) 在該數(shù)組中，空白處則初始化為0。之所以把數(shù)組范圍設(shè)計(jì)成82而不是81,是為 了程序的易讀性，使得數(shù)組元素的最大下標(biāo)可達(dá) 81,下同。 int fix82該數(shù)組的用

9、途是若sudoku數(shù)組中某位置的數(shù)字不為空，則fix數(shù)組相應(yīng)位置 的元素值為1,否則為0,即fix數(shù)組是用來(lái)記錄哪些位置的數(shù)字是已經(jīng)確定下來(lái) 的。 in t possible8210該數(shù)組的用途是記錄所有未確定數(shù)字的所有可能性，possible數(shù)組各元素的 值在初始化時(shí)被初始化為與其第二維的下標(biāo)一致，即 0-9 （其中0表示空值）；在 中間計(jì)算過(guò)程中，若發(fā)現(xiàn)第一維某位置的某種可能性已不復(fù)存在， 則將第一維下 標(biāo)是該位置而第二維下標(biāo)是該不再可能的數(shù)字的元素值改為 -1。 in t review82該數(shù)組的用途類似于棧，在回溯算法過(guò)程中起到至關(guān)重要的作用?；厮葜?， 要把所有fix數(shù)組中值為0的位

10、置依次存放進(jìn)review數(shù)組；回溯中，由低到高依次 逐漸確定這些位置的數(shù)值，無(wú)法確定者（即1-9的數(shù)字都不適合者）則應(yīng)當(dāng)回退到前一個(gè)位置，并修改其fix數(shù)組中的值，依次類推，直至review數(shù)組所存放的 所有位置的值都能確定（即題目完成），或回退到最初點(diǎn)的前一個(gè)位置（即題目 有誤）。相關(guān)函數(shù)本項(xiàng)目中為實(shí)現(xiàn)算法的數(shù)據(jù)結(jié)構(gòu)所用到的主要函數(shù)如下： void setPossible（）該函數(shù)是用來(lái)設(shè)置possible數(shù)組中元素的值，其具體功能是：對(duì)于fix數(shù)組中每一個(gè)值為0的位置（即對(duì)于每一個(gè)沒(méi)有確定下數(shù)字的位置），考察其可能 的數(shù)字是哪些，并記錄下來(lái)?？疾斓姆椒ㄊ牵涸?-9這些數(shù)字中除去在當(dāng)前行、列

11、、九宮中已有的數(shù)字，剩下的即為可能的取值對(duì)象。 bool fixPossible（）該函數(shù)是用來(lái)修改fix數(shù)組和possible數(shù)組中元素的值，其返回值表示了在 此次運(yùn)行該函數(shù)過(guò)程中是否執(zhí)行了修改。其具體功能是：對(duì)于fix數(shù)組中每一個(gè)值為0的位置（即對(duì)于每一個(gè)沒(méi)有確定下數(shù)字的位置），考察其可能的數(shù)字的個(gè)數(shù)， 若為1,則將fix數(shù)組該位置的值改為1且sudoku數(shù)組該位置的值改為該唯一可能 的數(shù)字（即該位置的值已確定下來(lái)），且返回真；若沒(méi)有只有一種可能性的位置， 則返回假。 bool isExist （int i ，int j ）該函數(shù)用于回溯過(guò)程中，其用途是：判斷 sudoku數(shù)組中位置為i的

12、元素的值 是否可能為j，即判斷的是位置i所在的行、列以及九宮中是否已經(jīng)存在數(shù)字j， 若存在則返回真，否則返回假。4.4求解算法實(shí)現(xiàn)有限遞推在執(zhí)行一次fixPossible函數(shù)之后，就可能會(huì)確定下一些原來(lái)沒(méi)有確定的數(shù) 字，那么此時(shí)possible數(shù)組的值必然也會(huì)變動(dòng)。這是因?yàn)榇_定下的數(shù)字越多，某 些位置的可能數(shù)字的數(shù)目就會(huì)減少，那么此時(shí)就應(yīng)再執(zhí)行setPossible函數(shù)修改possible數(shù)組。而修改之后可能又會(huì)出現(xiàn)一些只有一種可能性的位置，那么就應(yīng)該再執(zhí)行fixPossible函數(shù)。于是，只要如此循環(huán)往復(fù)下去，就能最大限度地確 定下根據(jù)題目本身含義和規(guī)則而確定下的內(nèi)容。確定的數(shù)字越多，對(duì)于將

13、來(lái)回溯也就越有利。經(jīng)驗(yàn)表明，有些數(shù)獨(dú)題直接就可以通過(guò)執(zhí)行大約10多次的有限遞推 循環(huán)體解決。一般情況下，有限遞推的循環(huán)結(jié)束只有兩種情況：一是推出了全部結(jié)果；二是fixPossible函數(shù)返回值為假，即不存在只有一種可能性的位置。預(yù)處理的主要代碼見(jiàn)附錄?；厮莼厮菔菙?shù)獨(dú)求解算法中最為關(guān)鍵的部分，其主要步驟是： 按下標(biāo)的由低到高掃描fix數(shù)組，將值為0的位置記錄進(jìn)review數(shù)組，記錄 的順序也是由低到高，最后記錄下fix數(shù)組中為0位置的個(gè)數(shù)再加1； 把review數(shù)組看作棧，記錄棧頂； 先設(shè)置一個(gè)bool型標(biāo)志變量flag并初始化為true，下面各步驟都將在一個(gè)條件始終為真的死循環(huán)中進(jìn)行，該循環(huán)由

14、一條對(duì)flag進(jìn)行真假判斷的語(yǔ)句分成兩 大部分。若當(dāng)前棧頂是經(jīng)過(guò)了回退操作而達(dá)到的，則flag會(huì)已被記錄為false ；否則flag為true。死循環(huán)結(jié)束的條件是review數(shù)組（棧）中top與max的值相等， 即解出最終結(jié)果，或者是無(wú)解，最終top小于0。在死循環(huán)中，若flag為true，則 進(jìn)入步驟，否則進(jìn)入步驟。 若flag為true，則說(shuō)明棧頂是經(jīng)過(guò)正常的假設(shè)而達(dá)到的，并非由回退達(dá)到,那么根據(jù)possible數(shù)組以及isExist函數(shù)對(duì)棧頂所保存位置的可能出現(xiàn)的數(shù)字進(jìn) 行判斷，把遇到的第一個(gè)可能數(shù)字放進(jìn)sudoku數(shù)組，并把fix數(shù)組的該位置的值設(shè)為1,并判斷是否已經(jīng)解出結(jié)果，即rev

15、iew數(shù)組(棧)中top和maX的值是否相 等。若相等，則得出結(jié)果并退出死循環(huán)；若發(fā)現(xiàn)1-9都不可能應(yīng)用在棧頂所保存的位置，則說(shuō)明前面的假設(shè)有錯(cuò)誤，此時(shí)應(yīng)當(dāng)回退。即fix數(shù)組和sudoku數(shù)組的該位置重設(shè)為0，top減1，并將flag的值設(shè)為false。然后結(jié)束本輪循環(huán)體，繼續(xù) 下一輪的循環(huán)。 若flag為false，說(shuō)明是經(jīng)過(guò)了回退才達(dá)到現(xiàn)在這個(gè)棧頂?shù)?，那么若仍?沒(méi)有可能的數(shù)字可以應(yīng)用在當(dāng)前棧頂所保存的位置上，則繼續(xù)執(zhí)行出棧操作，即fix數(shù)組和sudoku數(shù)組的該位置的值重設(shè)為0, top減1 ；否則將遇到的第一個(gè)可能 數(shù)字應(yīng)用到該位置，即再設(shè)好sudoku數(shù)組和fix數(shù)組，將top加1，

16、并將flag的值 設(shè)為true。然后結(jié)束本輪循環(huán)體，繼續(xù)下一輪的循環(huán)?；厮莸闹饕a見(jiàn)附錄。4.5出題算法實(shí)現(xiàn)4.5.1 生成終盤(pán)數(shù)獨(dú)出題時(shí)要先采用拉斯維加斯算法隨機(jī)生成一個(gè)數(shù)獨(dú)題的終盤(pán)。首先，在一個(gè)數(shù)獨(dú)空盤(pán)中隨機(jī)選中n個(gè)格子，在這些格子內(nèi)隨機(jī)填人數(shù)字 1-9 ;然后，調(diào) 用數(shù)獨(dú)求解算法對(duì)這個(gè)已知n格的數(shù)獨(dú)題S(n)進(jìn)行求解。如果S(n)有解，則返 回true，否則返回false。拉斯維加斯算法的思想便是不斷重復(fù)執(zhí)行上述步驟， 直至其返回值為true為止。生成隨機(jī)數(shù)的主要代碼見(jiàn)附錄。挖洞算法挖洞算法的基本思想就是挖去一個(gè)數(shù)獨(dú)終盤(pán)上的一些格子，使其成為有唯一 解的數(shù)獨(dú)題目。然而挖洞的機(jī)制是多種多

17、樣的，本項(xiàng)目為了加快出題算法的速度， 利用不同的隨機(jī)挖洞概率來(lái)區(qū)分不同的難度。挖洞的主要代碼見(jiàn)附錄。4.6程序運(yùn)行截圖數(shù)獨(dú)求解，手動(dòng)輸入題目:數(shù)獨(dú)求解，讀取保存的題目:解出答案:數(shù)獨(dú)出題，選擇難度:得出題目:保存題目:保存和打開(kāi)題目的文件格式:女炸0）嵋竟血feJlQ-j UDO犁助M9 5 14 5 3 2 1674362SS1929&B173B9S53347t13 6a8T12517Z54£362B3417&1962B34 3 7 1 S f F 215測(cè)試5.1解題測(cè)試選取5個(gè)難度共25道不同的數(shù)獨(dú)題目進(jìn)行解題測(cè)試，記錄程序運(yùn)行時(shí)間, 檢驗(yàn)運(yùn)算結(jié)果是否正確，并對(duì)

18、實(shí)驗(yàn)結(jié)果進(jìn)行分析。難度1：題目12345Average時(shí)間14ms13ms22ms22ms20ms18.2ms結(jié)果正確正確正確正確正確-難度2：題目12345Average時(shí)間21ms20ms20ms33ms21ms23.0ms結(jié)果正確正確正確正確正確-難度3：題目12345Average時(shí)間22ms26ms25ms23ms26ms24.4ms結(jié)果正確正確正確正確正確-難度4:題目12345Average時(shí)間28ms24ms35ms29ms26ms28.4ms結(jié)果正確正確正確正確正確-難度5:題目12345Average時(shí)間28ms50ms22ms44ms29ms34.6ms結(jié)果正確正確正確正

19、確正確-通過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)的分析可知： 本算法得出的結(jié)果全部正確，說(shuō)明本算法成功實(shí)現(xiàn)了通過(guò)計(jì)算機(jī)人工智能 方法對(duì)數(shù)獨(dú)問(wèn)題求解； 隨著題目難度加大，平均運(yùn)行時(shí)間逐漸加長(zhǎng)； 本次試驗(yàn)中，運(yùn)行時(shí)間最長(zhǎng)的題目不超過(guò)50ms,大多數(shù)題目在20-30ms內(nèi)完成，說(shuō)明本算法的運(yùn)行速度是比較快捷的。5.2出題測(cè)試5個(gè)難度各進(jìn)行5次數(shù)獨(dú)出題運(yùn)算，記錄運(yùn)行時(shí)間，并比較得出的題目是否 會(huì)有重復(fù)。難度1：題目12345Average時(shí)間9ms10ms6ms7ms9ms8.2ms重復(fù)-無(wú)難度2：題目12345Average時(shí)間9ms8ms9ms7ms8ms8.2ms重復(fù)-無(wú)難度3：題目12345Average時(shí)間9ms9m

20、s6ms5ms9ms7.6ms重復(fù)-無(wú)難度4:題目12345Average時(shí)間10ms9ms8ms6ms11ms8.8ms重復(fù)-無(wú)難度5:題目12345Average時(shí)間7ms9ms10ms5ms10ms8.2ms重復(fù)-無(wú)通過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)的分析可知： 本此實(shí)驗(yàn)中，各組均無(wú)重復(fù)的題目出現(xiàn)，說(shuō)明本算法成功實(shí)現(xiàn)了通過(guò)計(jì)算 機(jī)人工智能方法對(duì)數(shù)獨(dú)問(wèn)題的出題； 程序的運(yùn)行時(shí)間不隨難度增加而加長(zhǎng)，個(gè)難度的運(yùn)行時(shí)間基本一樣； 運(yùn)行時(shí)間基本維持著8-9ms左右，說(shuō)明本算法的運(yùn)行速度是比較快捷的6工作總結(jié) 較好地完成了數(shù)獨(dú)求解和數(shù)獨(dú)出題的算法的設(shè)計(jì)與實(shí)現(xiàn)； 對(duì)算法進(jìn)行功能測(cè)試，驗(yàn)證了算法的有效性，并證明了算法具有良

21、好的時(shí) 間效率； 實(shí)現(xiàn)了良好的用戶界面； 實(shí)現(xiàn)了數(shù)獨(dú)題目的讀取和保存功能； 通過(guò)本項(xiàng)目，對(duì)人工智能技術(shù)有了進(jìn)一步的了解，并初步掌握了 MFC編程; 鍛煉了團(tuán)隊(duì)合作能力。7項(xiàng)目安排任務(wù)負(fù)責(zé)人時(shí)間項(xiàng)目建議書(shū)王鄭合、文寬、欒杰數(shù)獨(dú)求解功能王鄭合、欒杰數(shù)獨(dú)出題功能王鄭合、文寬測(cè)試欒杰中期進(jìn)展報(bào)告王鄭合、文寬、欒杰界面文寬功能集成王鄭合測(cè)試與改進(jìn)文寬、欒杰完成總結(jié)報(bào)告王鄭合、文寬、欒杰參考文獻(xiàn)1 文U曉寶數(shù)獨(dú)游戲的解題算法J.電腦編程技巧與維護(hù)，2007,(5):64- 67.2 嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)M.第二版北京：清華大學(xué)出版社，1993:93-95,43- 45,220221.3 Stanley

22、B Lippma n, Josee Lajoie著，潘愛(ài)民等譯.C+ Primer( 第三版)M. 中國(guó)電力出版社，2002.4王曉東.算法設(shè)計(jì)與分析M.第一版.清華大學(xué)出版社，2003. 王萬(wàn)良人工智能及其應(yīng)用M.第二版.高等教育出版社，2008.附錄預(yù)處理算法的主要代碼：while 種可能性的位置setPossible();if (!fixPossible(sudoku,fix,possible)/ 即不存在只有break;if (isFull(sudoku) /若已推岀全部結(jié)果 break;if (isFull(sudoku)printAll(); / 輸岀結(jié)果回溯算法的主要代碼：if

23、(isFull(sudoku)return true ;int top=0;/所有值為0的位置入棧for (int i=1;i<82;i+)if (fixi=0)reviewtop+=i;int max=top; /記錄最大數(shù)加1top=0; /指向棧頂int temp;bool flag= true ; /是否正常入棧的標(biāo)志while assert(top>=0); /宏定義，用于調(diào)試程序if (flag)int j;for (j=1;j<=9;j+)if (possiblereviewtopj!=-1 &&!isExist(reviewtop,j)fixreviewtop=1;sudokureviewtop=j;toRead(reviewtop); / 實(shí)現(xiàn) readlinerow與sudokui同步+top;if (top>=max)return 1;break;if (j>9) /若該位置所有可能值都不成立，則回退一格-top;if (top<0)prin tAll();return 0;flag= false ; elseif (sudokureviewtop=9) /若當(dāng)前位置的top也沒(méi)有可以選擇的值，則繼續(xù)回退 fixreviewtop=0;sudokureviewtop=0;toRead(revie