Excel+VBA製作數獨（三）：實現篇

上篇文章已經把單元格類創建完，數獨類也可以依樣畫葫蘆添加自己的功能。

一、實例化方法

我們已經說過Class_Initialize是一個類在實例化時自動運行的系統方法，如果需要在實例化時傳入參數我們需要自己創建一個帶參數的Init方法，在類實例化後手動調用，就像單元格類中的setValue方法。

數獨類中暫時沒有這樣的需求，所以我們可以直接在Class_Initialize方法中將我們需要的內容進行初始化，代碼如下：

Private Sub Class_Initialize()nnReDim row_list(1 To 9, 1 To 9) As IntegernReDim col_list(1 To 9, 1 To 9) As IntegernReDim box_list(1 To 9, 1 To 9) As IntegernnReDim cell_arr(1 To 9, 1 To 9)nReDim num_arr(1 To 9, 1 To 9) As IntegernnDim r%, c%, b%nnFor r = 1 To 9n For c = 1 To 9n row_list(r, c) = 1n col_list(r, c) = 1n box_list(r, c) = 1n n Dim Cell As New Celln Set Cell = New Celln Set cell_arr(r, c) = Celln Next cnNext rnnEnd Subn

這裡基本把之前聲明的屬性都初始化了，row_list/col_list/box_list 分別用來存儲每行、每列、每九宮格中可使用的數字，num_arr用來存放每個單元格的數字進行回溯，cell_arr用來存放每個單元格的狀態，這個數組的每個元素都是一個cell類。

二、創建數獨

1、剪枝方法

在第一篇講方法的文章中我們說過了，每一個單元格都是隨機填數，由於空間巨大，我們剪枝的方法是隨機可填入的數字，而不是在填入之後判斷數字是否符合要求。這個可填入數字的集合，我們row_list/col_list/box_list 以及這個單元格不可填入的數字數組求交集，代碼如下：

Public Function get_num_list(ByVal row As Integer, ByVal col As Integer, ByVal box As Integer) As CollectionnnDim unable_num_list, i%nSet get_num_list = New CollectionnIf Me.cell_arr(row, col).sum = Me.sum Thenn unable_num_list = Me.cell_arr(row, col).unable_num_listnElsen unable_num_list = Array(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)nEnd IfnnFor i = 1 To 9n If Me.row_list(row, i) = 1 And Me.col_list(col, i) = 1 And Me.box_list(box, i) = 1 And unable_num_list(i) = 1 Then get_num_list.Add i, key:=CStr(i)nNext innEnd Functionn

這個方法傳入了三個參數，分別代表行、列、九宮格數。一開始先判斷該單元格是否已有內容，因為cell類的sum屬性只有在被創建後才會計算出來。如果有內容代表該單元格正在進行回溯，會有一個unable_num_list，如果沒有的話我們也要給這個列表賦一個全部數字都可用的值。接下來遍歷1到9，當四個數組都顯示該數字可用時，才加入集合中。

2、回溯方法

一般因為需要回溯，具體循環次數不確定，都會使用DO LOOP來進行循環。對於數獨，我們也可以使用FOR NEXT進行循環，進行回溯時只需要把循環變數-2就可以了。代碼框架如下：

Public Sub creat_Sudoku()nDim r%, c%, b%, d%, value%, retry%, sum%nnretry = 0nnFor sum = 1 To 81n 循環體n If sum < 1 Then MsgBox "無解！", , "錯誤": Exit SubnNext sumnnSheet1.Range("A1:I9") = num_arrnEnd Subn

在循環體中，首先我們要根據循環變數計算出行、列、九宮格，然後通過這三個變數得到可使用的數字集合，代碼如下：

Me.sum = sumn r = Int((sum - 1) / 9) + 1n c = (sum - 1) Mod 9 + 1n b = Int((r - 1) / 3) * 3 + Int((c - 1) / 3) + 1n n If retry > 0 Then sum = sum - 2n n Dim num_list As Collectionn Set num_list = New Collectionn Set num_list = get_num_list(r, c, b)n d = num_list.Countn

用總數計算行列數，其實是一種將一維數組變為二維的演算法，通過行列數計算九宮格數演算法剛好相反，是將二維數組降為一維的演算法。上一篇文章里提到一維數組的讀寫會比二維數組更快，所以一二維的轉換演算法要熟悉。

當num_list存在可以使用的數字時，我們需要將數字存入數組，並且改變其他數組的狀態，否則進行回溯。

If d > 0 Then 存在可用數字n n Randomize (Timer)n value = num_list(Int(d * Rnd) + 1) 隨機取數nn Dim cCell As Celln If retry > 0 Thenn Call Me.add_to_num_list(r, c, b, Me.cell_arr(r, c).value)n Set cCell = Me.cell_arr(r, c)n Elsen Set cCell = New Celln End Ifn n Call cCell.setValue(r, c, b, value) 存入celln Call Me.stack_add(cCell) cell存入棧n n num_arr(r, c) = valuen retry = 0n n n Else 無可用數字n n If retry > 0 Then Call Me.stack_remove(Me.cell_arr(r, c)) 退棧n sum = sum - 2 回退n retry = retry + 1 標記n n End Ifn

這裡的retry變數用來標記單元格重試的次數，如果單元格不是初次嘗試，會有特殊的處理。

3、模擬一個棧

在回溯中，成功填入數字有入棧操作，而無可用數字有退棧操作。VBA中模仿棧一般會用集合這種變數，使用Add和Remove方法可以實現這兩種操作，這裡雖然使用的數組，而且單獨寫了方法，操作明顯更為複雜。

先來看入棧的實現，入棧包括兩部分，一是把單元格類放入cell_arr數組，二是改變其他進行約束條件的數組內容，代碼如下：

Public Sub stack_add(ByVal Cell As Cell)nnDim r%, c%, b%, v$nr = Cell.rownc = Cell.colnb = Cell.boxnv = Cell.valuennSet cell_arr(r, c) = CellnCall Me.del_from_num_list(r, c, b, v)nnEnd SubnnPublic Sub del_from_num_list(ByVal row As Integer, ByVal col As Integer, ByVal box As Integer, ByVal value As Integer)nnrow_list(row, value) = 0ncol_list(col, value) = 0nbox_list(box, value) = 0nnEnd Subn

退棧的操作也是一樣的，不過是把狀態改變反過來，代碼如下：

Public Sub stack_remove(ByVal Cell As Cell)nnDim r%, c%, b%, v$nr = Cell.rownc = Cell.colnb = Cell.boxnv = Cell.valuennCall Me.add_to_num_list(r, c, b, v)nSet cell_arr(r, c) = New CellnnEnd SubnnPublic Sub add_to_num_list(ByVal row As Integer, ByVal col As Integer, ByVal box As Integer, ByVal value As Integer)nnrow_list(row, value) = 1ncol_list(col, value) = 1nbox_list(box, value) = 1nnEnd Subn

add_to_num_list/del_from_num_list 兩個方法都獨立出來，因為會有單獨調用的場景。比如在回溯代碼中，如果是單元格重試，就要先把單元格內原本的數字去掉，並加回各條件數組中。

三、數獨求解

創建數獨的過程已經基本完成，數獨第一篇文章中我們就說過，求解的本質還是生成，不過是在一定條件下生成。我們也可以再加入一個solute_Sudoku方法，不過似乎意義不大，因為主體還是creat_Sudoku的內容。

怎樣在程序完成後進行最小改動加入新的內容，這時候面向對象編程的優勢就顯示出來了。我們給cell類加一個屬性status，在初始化時先讀取整個數獨區域，以此來標記單元格是否已有數字。在循環回溯時碰到這個標記就跳過去，永遠不改變單元格內容，這樣就把創建一個數獨變成創建一個有條件的數獨。

在Cell類模塊中加如一個新的初始化方法：

Public Sub cell_Init(ByVal v As Integer, Optional ByVal s As Integer = 1)nnMe.value = vnMe.status = snnEnd Subn

在Sudoku的實例化方法中先讀取表格區域：

num_arr = Sheet1.Range("A1:I9")n

在循環體中創建Cell類時加入條件判斷：

Dim Cell As New Celln Set Cell = New Celln Call Cell.cell_Init(0, 0)n n If num_arr(r, c) <> "" Thenn Call Cell.cell_Init(num_arr(r, c), 1)n b = Int((r - 1) / 3) * 3 + Int((c - 1) / 3) + 1n Call Me.del_from_num_list(r, c, b, num_arr(r, c))n End Ifn n Set cell_arr(r, c) = Celln

在creat_Sudoku方法計算可用數字集合前加入條件判斷：

If retry > 0 And Me.cell_arr(r, c).status = 1 Then sum = sum - 2n If Me.cell_arr(r, c).status = 1 Then GoTo next_forn

將next_for:節點加到無解判斷前即可。

以上就是數獨的生成+求解內容，數獨題目的生成是個更複雜的內容，有機會單獨拿出來再寫幾篇。數獨的代碼量太多，就不放在附錄中了，會新增一篇文章單獨來展示。