三亞學(xué)院理工學(xué)院 繆克俊
三亞市第一中學(xué) 黃麗萍
三亞學(xué)院理工學(xué)院 汪 源 劉永旗
本文基于LabVIEW軟件設(shè)計(jì)了一款求解9×9金字塔數(shù)獨(dú)的系統(tǒng)。在對9×9金字塔數(shù)獨(dú)解題規(guī)則分析的基礎(chǔ)上,建立求解9×9金字塔數(shù)獨(dú)的數(shù)學(xué)模型,在數(shù)學(xué)模型的基礎(chǔ)上采用回溯排除算法設(shè)計(jì)一套求解金字塔數(shù)獨(dú)的算法,并利用LabVIEW軟件進(jìn)行程序的設(shè)計(jì),并得出9×9金字塔數(shù)獨(dú)的求解結(jié)果。
數(shù)獨(dú)起源于18世紀(jì)的瑞士,由著名數(shù)學(xué)家歐拉發(fā)明的拉丁方陣是數(shù)獨(dú)前身,拉丁方陣中每一行和每一列都是由不重復(fù)的n個(gè)數(shù)字或者字母組成的,以拉丁方陣而變更出現(xiàn)在的數(shù)獨(dú),與現(xiàn)在的數(shù)獨(dú)相比少了每一個(gè)宮不重復(fù)的規(guī)則。
標(biāo)準(zhǔn)9×9數(shù)獨(dú)有6 670 903 752 021 072 936 960個(gè)組合,數(shù)獨(dú)游戲難度的差異根據(jù)數(shù)獨(dú)題目提示數(shù)量(N)以及提示數(shù)量(N)的擺放來決定的,每少一個(gè)提示數(shù)量(N),其出題難度會(huì)隨之提高。根據(jù)權(quán)威機(jī)構(gòu)認(rèn)證,目前發(fā)現(xiàn)的最少提示數(shù)9×9標(biāo)準(zhǔn)數(shù)獨(dú)為17個(gè)提示。并且在標(biāo)準(zhǔn)版數(shù)獨(dú)以外,數(shù)學(xué)家們在數(shù)獨(dú)本質(zhì)不變的情況下,去對規(guī)則、表格進(jìn)行變形創(chuàng)造出各種有趣的變形式數(shù)獨(dú),9×9金字塔數(shù)獨(dú)就是其中一種,棋盤如圖1所示。
圖1 9×9金字塔數(shù)獨(dú)棋盤
本文利用圖形化編程軟件LabVIEW進(jìn)行金字塔數(shù)獨(dú)的求解,在金字塔數(shù)獨(dú)解題規(guī)則分析的基礎(chǔ)上,建立求解9×9金字塔數(shù)獨(dú)的數(shù)學(xué)模型,在數(shù)學(xué)模型的基礎(chǔ)上采用回溯排除算法設(shè)計(jì)一套求解金字塔數(shù)獨(dú)的算法,并在LabVIEW軟件中編程實(shí)現(xiàn)求解算法,讓計(jì)算機(jī)自動(dòng)進(jìn)行9×9金字塔數(shù)獨(dú)的求解。
9×9金字塔數(shù)獨(dú)棋盤如圖1所示。其解題規(guī)則為:棋盤中每個(gè)3×3宮內(nèi)填寫1-9的自然數(shù)不重復(fù);且棋盤中每一行填寫1-9的自然數(shù)不重復(fù);且棋盤中每一列填寫1-9的自然數(shù)不重復(fù);且棋盤中每個(gè)黃色金字塔區(qū)域(9個(gè)空)中填寫1-9的自然數(shù)不重復(fù)。針對計(jì)算機(jī)快速運(yùn)算的特點(diǎn),本文采用回溯排除算法進(jìn)行算法設(shè)計(jì)。
回溯排除法是一種搜索算法,其基本思路為:在一個(gè)問題中,根據(jù)題意給出的邊界條件劃定出所有可能解的范圍,根據(jù)題意確定出約束條件。利用計(jì)算機(jī)程序順次在所有可能解中利用約束條件進(jìn)行排除不可能的解,搜索時(shí)按照深度搜索的方式進(jìn)行。即在第1個(gè)需要填寫的單元格[i,j](i,j=1,2,…,9)內(nèi)選擇滿足約束條件的最小可能解Ai,j,1,然后以Ai,j,1為出發(fā)點(diǎn),利用約束條件搜索第2個(gè)需要填寫的單元格[k,l](k,l=1,2,…,9)的最小可能解Ak,l,2。如果搜索到Ak,l,2,則繼續(xù)搜索第3個(gè)需要填寫的單元格的最小可能解。如果第N個(gè)單元格沒有滿足約束條件的解,則返回第N-1個(gè)單元格,搜索比原最小可能解大且滿足約束條件的最小可能解。依次類推,直到所有單元格的可能解都被找到,則得到了該問題的一個(gè)完整解。
對于9×9金字塔數(shù)獨(dú),約束條件包括“行排除”、“列排除”、“宮排除”和“金字塔排除”,其中“行排除”的具體條件是:當(dāng)前搜索的單元格中可以填寫的數(shù)字必須和該單元格所在行的其他8個(gè)單元格中已填的數(shù)字不重復(fù)。其他約束條件可以類似寫出,不再贅述。其中需要強(qiáng)調(diào)的是,“金字塔排除”的約束條件只在搜索的單元格處于某個(gè)金字塔范圍內(nèi)時(shí)才使用?;厮菖懦ǖ乃惴鞒虉D如圖2所示。
圖2 回溯排除法設(shè)計(jì)流程圖
LabVIEW軟件是通過數(shù)據(jù)流編程和圖形化編程實(shí)現(xiàn)編程設(shè)計(jì),數(shù)據(jù)流編程也被稱為G語言,是一種數(shù)據(jù)流編程語言。通過導(dǎo)線連接不同功能的函數(shù)或節(jié)點(diǎn),圖形化的程序框圖結(jié)構(gòu)決定程序如何執(zhí)行。LabVIEW的程序有三個(gè)組成部分:程序框圖(Block Diagram)、前面板(Front Panel)和圖標(biāo)/連接器(Icon/Connector)。
標(biāo)準(zhǔn)數(shù)獨(dú)表格一共擁有81個(gè)表格,從第1個(gè)單元格開始到最后1個(gè)單元格,需要將數(shù)獨(dú)棋盤第1個(gè)單元格開始的每一個(gè)單元格內(nèi)的數(shù)值進(jìn)行識別,識別它是否為已填數(shù)字,已填用1表示,未填用0表示。若為1說明該單元格是有已填數(shù)字,執(zhí)行“單元格+1”步驟,再進(jìn)行下一單元格的判斷;若為0說明該單元格是需要去填入數(shù)值的單元格,在該單元格使用“行排除法”、“列排除法”、“宮排除法”和“金字塔排除法”在整個(gè)數(shù)獨(dú)內(nèi)進(jìn)行判斷,來篩選可填入的1-9之間的最小數(shù)值。該單元格填入排除法篩選出可填入的最小數(shù)值,執(zhí)行“單元格位置+1”步驟,再進(jìn)行下一單元格的判斷。若發(fā)生錯(cuò)誤的情況,即該單元格無法填入1-9之間的任意數(shù)字時(shí),可知該單元格的前序單元格中填入最小數(shù)字并不是這個(gè)數(shù)獨(dú)的解,需要將往前推算,執(zhí)行“單元格位置-1”步驟,并進(jìn)行回溯來判斷之前填入數(shù)字的正確性。依次類推,直到最后一個(gè)單元格可以填入1-9之間的某個(gè)數(shù)字,該結(jié)果即為該數(shù)獨(dú)的解,但該解不一定是唯一解。
在LabVIEW程序中,數(shù)獨(dú)由數(shù)組形式進(jìn)行呈現(xiàn),如圖3所示。其中數(shù)組元素是“圖片下拉列表”控件,控件中插入0-9的10張圖片,索引數(shù)值分別為0-9的數(shù)字。其中9個(gè)紅色線劃分的區(qū)域即為9個(gè)宮,4個(gè)黃色線劃分的區(qū)域即為4個(gè)金字塔。
圖3 前面板中的數(shù)獨(dú)
根據(jù)LabVIEW設(shè)計(jì)算法流程圖可知,一個(gè)標(biāo)準(zhǔn)數(shù)獨(dú)表格一共擁有81個(gè)單元格,以單元格位置小于81為條件建立求解是否完成的判斷條件,單元格位置小于81即該數(shù)獨(dú)還未破解;當(dāng)單元格位置大于等于81時(shí),即該單元格已經(jīng)通過推算將81個(gè)單元格填入解題對應(yīng)數(shù)字,數(shù)獨(dú)求解過程完成,顯示數(shù)獨(dú)答案。
控件傳輸數(shù)據(jù)會(huì)從第0個(gè)單元格開始,因此對于每個(gè)單元格所需要去解析該單元格所在的行列進(jìn)行分析。對單元格位置進(jìn)行商與余數(shù),公式如下:
在此基礎(chǔ)上需要對未填入數(shù)字的單元格進(jìn)行添加數(shù)字。初始狀態(tài)下未填寫數(shù)字的單元格內(nèi)數(shù)字為0,先需要建立子VI來添加該單元格的數(shù)值,輸入端為控件和行、列,輸出端為控件,單元格所得到的行、列來確定該單元格位置,使用元素同址操作結(jié)構(gòu)選定數(shù)獨(dú)數(shù)組、數(shù)獨(dú)數(shù)組單元格位置、該單元格的值。
根據(jù)該單元格所加的數(shù)值進(jìn)行數(shù)獨(dú)規(guī)則的判斷,分別為“行排除法”、“列排除法”、“宮排除法”和“金字塔排除法”。下面以“宮排除法”為例進(jìn)行說明。
宮排除法是需要選中該單元格所包含的宮(3×3)區(qū)域,因此先需要將控件所占的9x9區(qū)域調(diào)整為該單元格所包含的宮(3×3)區(qū)域。在行和列數(shù)值選擇中,有著采集數(shù)獨(dú)9個(gè)宮數(shù)據(jù)的區(qū)別,見表1所示。
表1 “宮排除法”單元格行列對應(yīng)的宮
利用條件結(jié)構(gòu)將行列所在的宮定義好宮第一個(gè)單元格,對單元格所對應(yīng)宮進(jìn)行數(shù)獨(dú)數(shù)據(jù)采集,篩選出宮內(nèi)沒有出現(xiàn)的1-9之間的最小數(shù),并結(jié)合“行排除法”、“列排除法”和“金字塔排除法”的結(jié)果,最終確定可以填入的最小數(shù)。
若一個(gè)單元格通過排除法所得1-9數(shù)值都無法填入,則是該單元格前面序列的單元格填入數(shù)值是錯(cuò)誤的,需要以當(dāng)前單元格位置往前推算,執(zhí)行“單元格位置-1”步驟,并進(jìn)行回溯來判斷之前填入數(shù)字的正確性。依次類推,直到最后一個(gè)單元格可以填入1-9之間的某個(gè)數(shù)字。結(jié)果如圖4所示。
圖4 金字塔數(shù)獨(dú)求解結(jié)果
在標(biāo)準(zhǔn)9×9數(shù)獨(dú)求解的基礎(chǔ)上,基于LabVIEW軟件,設(shè)計(jì)一款求解9×9金字塔數(shù)獨(dú)系統(tǒng),達(dá)到求解數(shù)獨(dú)的目的。在對9×9金字塔數(shù)獨(dú)解題規(guī)則分析的基礎(chǔ)上,利用回溯排除法進(jìn)行了求解金字塔數(shù)獨(dú)的算法設(shè)計(jì),在設(shè)計(jì)算法的基礎(chǔ)上利用LabVIEW軟件進(jìn)行程序的設(shè)計(jì),通過對單元格進(jìn)行“行排除法”、“列排除法”、“宮排除法”和“金字塔排除法”的判斷,最終得出9×9金字塔數(shù)獨(dú)的求解結(jié)果。