三亞學院理工學院 繆克俊

三亞市第一中學 黃麗萍

三亞學院理工學院 汪 源 劉永旗

本文基于LabVIEW軟件設計了一款求解9×9金字塔數(shù)獨的系統(tǒng)。在對9×9金字塔數(shù)獨解題規(guī)則分析的基礎上，建立求解9×9金字塔數(shù)獨的數(shù)學模型，在數(shù)學模型的基礎上采用回溯排除算法設計一套求解金字塔數(shù)獨的算法，并利用LabVIEW軟件進行程序的設計，并得出9×9金字塔數(shù)獨的求解結(jié)果。

數(shù)獨起源于18世紀的瑞士，由著名數(shù)學家歐拉發(fā)明的拉丁方陣是數(shù)獨前身，拉丁方陣中每一行和每一列都是由不重復的n個數(shù)字或者字母組成的，以拉丁方陣而變更出現(xiàn)在的數(shù)獨，與現(xiàn)在的數(shù)獨相比少了每一個宮不重復的規(guī)則。

標準9×9數(shù)獨有6 670 903 752 021 072 936 960個組合，數(shù)獨游戲難度的差異根據(jù)數(shù)獨題目提示數(shù)量（N）以及提示數(shù)量（N）的擺放來決定的，每少一個提示數(shù)量（N），其出題難度會隨之提高。根據(jù)權威機構(gòu)認證，目前發(fā)現(xiàn)的最少提示數(shù)9×9標準數(shù)獨為17個提示。并且在標準版數(shù)獨以外，數(shù)學家們在數(shù)獨本質(zhì)不變的情況下，去對規(guī)則、表格進行變形創(chuàng)造出各種有趣的變形式數(shù)獨，9×9金字塔數(shù)獨就是其中一種，棋盤如圖1所示。

圖1 9×9金字塔數(shù)獨棋盤

本文利用圖形化編程軟件LabVIEW進行金字塔數(shù)獨的求解，在金字塔數(shù)獨解題規(guī)則分析的基礎上，建立求解9×9金字塔數(shù)獨的數(shù)學模型，在數(shù)學模型的基礎上采用回溯排除算法設計一套求解金字塔數(shù)獨的算法，并在LabVIEW軟件中編程實現(xiàn)求解算法，讓計算機自動進行9×9金字塔數(shù)獨的求解。

1 設計方案

9×9金字塔數(shù)獨棋盤如圖1所示。其解題規(guī)則為：棋盤中每個3×3宮內(nèi)填寫1-9的自然數(shù)不重復；且棋盤中每一行填寫1-9的自然數(shù)不重復；且棋盤中每一列填寫1-9的自然數(shù)不重復；且棋盤中每個黃色金字塔區(qū)域（9個空）中填寫1-9的自然數(shù)不重復。針對計算機快速運算的特點，本文采用回溯排除算法進行算法設計。

回溯排除法是一種搜索算法，其基本思路為：在一個問題中，根據(jù)題意給出的邊界條件劃定出所有可能解的范圍，根據(jù)題意確定出約束條件。利用計算機程序順次在所有可能解中利用約束條件進行排除不可能的解，搜索時按照深度搜索的方式進行。即在第1個需要填寫的單元格[i,j](i,j=1,2,…,9)內(nèi)選擇滿足約束條件的最小可能解Ai,j,1，然后以Ai,j,1為出發(fā)點，利用約束條件搜索第2個需要填寫的單元格[k,l](k,l=1,2,…,9)的最小可能解Ak,l,2。如果搜索到Ak,l,2，則繼續(xù)搜索第3個需要填寫的單元格的最小可能解。如果第N個單元格沒有滿足約束條件的解，則返回第N-1個單元格，搜索比原最小可能解大且滿足約束條件的最小可能解。依次類推，直到所有單元格的可能解都被找到，則得到了該問題的一個完整解。

對于9×9金字塔數(shù)獨，約束條件包括“行排除”、“列排除”、“宮排除”和“金字塔排除”，其中“行排除”的具體條件是：當前搜索的單元格中可以填寫的數(shù)字必須和該單元格所在行的其他8個單元格中已填的數(shù)字不重復。其他約束條件可以類似寫出，不再贅述。其中需要強調(diào)的是，“金字塔排除”的約束條件只在搜索的單元格處于某個金字塔范圍內(nèi)時才使用。回溯排除法的算法流程圖如圖2所示。

圖2 回溯排除法設計流程圖

2 LabVIEW程序設計

LabVIEW軟件是通過數(shù)據(jù)流編程和圖形化編程實現(xiàn)編程設計，數(shù)據(jù)流編程也被稱為G語言，是一種數(shù)據(jù)流編程語言。通過導線連接不同功能的函數(shù)或節(jié)點，圖形化的程序框圖結(jié)構(gòu)決定程序如何執(zhí)行。LabVIEW的程序有三個組成部分：程序框圖（Block Diagram）、前面板（Front Panel）和圖標/連接器（Icon/Connector）。

標準數(shù)獨表格一共擁有81個表格，從第1個單元格開始到最后1個單元格，需要將數(shù)獨棋盤第1個單元格開始的每一個單元格內(nèi)的數(shù)值進行識別，識別它是否為已填數(shù)字，已填用1表示，未填用0表示。若為1說明該單元格是有已填數(shù)字，執(zhí)行“單元格+1”步驟，再進行下一單元格的判斷；若為0說明該單元格是需要去填入數(shù)值的單元格，在該單元格使用“行排除法”、“列排除法”、“宮排除法”和“金字塔排除法”在整個數(shù)獨內(nèi)進行判斷，來篩選可填入的1-9之間的最小數(shù)值。該單元格填入排除法篩選出可填入的最小數(shù)值，執(zhí)行“單元格位置+1”步驟，再進行下一單元格的判斷。若發(fā)生錯誤的情況，即該單元格無法填入1-9之間的任意數(shù)字時，可知該單元格的前序單元格中填入最小數(shù)字并不是這個數(shù)獨的解，需要將往前推算，執(zhí)行“單元格位置-1”步驟，并進行回溯來判斷之前填入數(shù)字的正確性。依次類推，直到最后一個單元格可以填入1-9之間的某個數(shù)字，該結(jié)果即為該數(shù)獨的解，但該解不一定是唯一解。

在LabVIEW程序中，數(shù)獨由數(shù)組形式進行呈現(xiàn)，如圖3所示。其中數(shù)組元素是“圖片下拉列表”控件，控件中插入0-9的10張圖片，索引數(shù)值分別為0-9的數(shù)字。其中9個紅色線劃分的區(qū)域即為9個宮，4個黃色線劃分的區(qū)域即為4個金字塔。

圖3 前面板中的數(shù)獨

根據(jù)LabVIEW設計算法流程圖可知，一個標準數(shù)獨表格一共擁有81個單元格，以單元格位置小于81為條件建立求解是否完成的判斷條件，單元格位置小于81即該數(shù)獨還未破解；當單元格位置大于等于81時，即該單元格已經(jīng)通過推算將81個單元格填入解題對應數(shù)字，數(shù)獨求解過程完成，顯示數(shù)獨答案。

控件傳輸數(shù)據(jù)會從第0個單元格開始，因此對于每個單元格所需要去解析該單元格所在的行列進行分析。對單元格位置進行商與余數(shù)，公式如下：

在此基礎上需要對未填入數(shù)字的單元格進行添加數(shù)字。初始狀態(tài)下未填寫數(shù)字的單元格內(nèi)數(shù)字為0，先需要建立子VI來添加該單元格的數(shù)值，輸入端為控件和行、列，輸出端為控件，單元格所得到的行、列來確定該單元格位置，使用元素同址操作結(jié)構(gòu)選定數(shù)獨數(shù)組、數(shù)獨數(shù)組單元格位置、該單元格的值。

根據(jù)該單元格所加的數(shù)值進行數(shù)獨規(guī)則的判斷，分別為“行排除法”、“列排除法”、“宮排除法”和“金字塔排除法”。下面以“宮排除法”為例進行說明。

宮排除法是需要選中該單元格所包含的宮（3×3）區(qū)域，因此先需要將控件所占的9x9區(qū)域調(diào)整為該單元格所包含的宮（3×3）區(qū)域。在行和列數(shù)值選擇中，有著采集數(shù)獨9個宮數(shù)據(jù)的區(qū)別，見表1所示。

表1 “宮排除法”單元格行列對應的宮

利用條件結(jié)構(gòu)將行列所在的宮定義好宮第一個單元格，對單元格所對應宮進行數(shù)獨數(shù)據(jù)采集，篩選出宮內(nèi)沒有出現(xiàn)的1-9之間的最小數(shù)，并結(jié)合“行排除法”、“列排除法”和“金字塔排除法”的結(jié)果，最終確定可以填入的最小數(shù)。

若一個單元格通過排除法所得1-9數(shù)值都無法填入，則是該單元格前面序列的單元格填入數(shù)值是錯誤的，需要以當前單元格位置往前推算，執(zhí)行“單元格位置-1”步驟，并進行回溯來判斷之前填入數(shù)字的正確性。依次類推，直到最后一個單元格可以填入1-9之間的某個數(shù)字。結(jié)果如圖4所示。

圖4 金字塔數(shù)獨求解結(jié)果

在標準9×9數(shù)獨求解的基礎上，基于LabVIEW軟件，設計一款求解9×9金字塔數(shù)獨系統(tǒng)，達到求解數(shù)獨的目的。在對9×9金字塔數(shù)獨解題規(guī)則分析的基礎上，利用回溯排除法進行了求解金字塔數(shù)獨的算法設計，在設計算法的基礎上利用LabVIEW軟件進行程序的設計，通過對單元格進行“行排除法”、“列排除法”、“宮排除法”和“金字塔排除法”的判斷，最終得出9×9金字塔數(shù)獨的求解結(jié)果。