LabVIEW軟件設(shè)計(jì)的金字塔數(shù)獨(dú)求解系統(tǒng)

三亞學(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ú)的求解。

1 設(shè)計(jì)方案

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ì)流程圖

2 LabVIEW程序設(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é)果。