當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

数独问题流程图_算法实践——数独的基本解法

發布時間：2023/12/10 编程问答 39 豆豆

生活随笔收集整理的這篇文章主要介紹了数独问题流程图_算法实践——数独的基本解法小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

數獨(Sudoku)是一種運用紙、筆進行演算的邏輯游戲。玩家需要根據9×9盤面上的已知數字，推理出所有剩余空格的數字，并滿足每一行、每一列、每一個粗線宮內的數字均含1-9，不重復。每一道合格的數獨謎題都有且僅有唯一答案，推理方法也以此為基礎，任何無解或多解的題目都是不合格的。

如下圖所示，就是一個數獨的題目

關于數獨的詳細介紹，參看“百度百科——數獨”

數獨的基本解法就是利用規則的摒棄法

一些定義

每一行稱為數獨的行，每一列稱為數獨的列，每一個小九宮格稱為數獨的宮。數獨的基本規則就是每一行、每一列、每一宮中，1-9這9個數字都只出現一次。

用(行，列)表示上圖的單元格，例如(1，1)表示第一行第一列的單元格，(2，4)表示第二行第四列的單元格

如上圖，每個空白單元格中能填的數字都是有限制的。

例如：(1，1)就只能填7和8；而(6，4)，只能填8；

那些只能填一個數字的空白單元格，我們稱之為唯一數單元格，上圖中(6，4)就是唯一數單元格

解題的順序，就是從唯一數單元格開始，由于唯一數單元格只能填一個數，故先在這個單元格里填數。在這個單元格里填數，由于規則的定義，那么這個單元格所在的行、所在的列、所在的宮的其他單元格就不能再填這個數了。這些單元格能填的數的可能性就少了。有可能會產生新的唯一數單元格。

在相當的一些的數獨題目中，從唯一數單元格開始填數，不停的在唯一數單元格填數就可以把數獨解出來。

如果在解題的過程中，發現某些空白單元格沒有數字能填這樣的單元格稱之為無解單元格，那就說明：要么這個數獨沒有解；要么之前的解題過程有問題，需要返回檢查之前的解題過程查看。

但是還有不少的數獨的題目，在解題的過程中，在還有空白單元格的情況下，卻找不到唯一數單元格，也就是意味著每個空白單元格中能填的數字至少有2個。我們稱之為無唯一數單元格的狀況

這個時候怎么辦？我們找到其中一個可能數最少的空白單元格(這個沒有定論，可以是可能數最少的空白單元格；也可以是第一個空白單元格；也可以是可能數最多的空白單元格，選哪個空白單元格對后面的解題是否有影響，沒有證明過，不好妄下定論。憑感覺選可能數最少的空白單元格是最好的選擇)，由于能填的數字不止一個，先把當前的狀態保存起來，再在能選的數字中選擇一個數字填寫(從小到大選擇)，然后繼續求解下去。如果能解出最后的結果，說明當前的選擇是正確的；如果后面的求解過程有問題，說明當前的數字的選擇有問題，那么再挑選另一個數填寫，繼續求解。如果，所有的選擇都求不出最后的結果，還是說明：要么這個數獨沒有解；要么之前的解題過程有問題，需要返回檢查之前的解題過程查看。如此反復，直到求出最終的答案。

會有種極端的情況(可能性不大)。那就是在當前的空白單元格的所有可能的數字都選擇了一遍，都沒有解。而之前又沒有出現無唯一數單元格的狀況。那就說明這個數獨根本就沒有解

下圖是數獨求解的流程圖

下面談談該算法的具體實現

1、數獨狀態的表示

用計算機來求解數獨。基本的一點就是如何表示數獨的狀態。

用整形一維數組來表示數獨的狀態

用Num(80)表示數獨的狀態(數組的下標從0開始)，數獨是一個二維表格，而數組是一維數組。那么就存在一維和二維之間的轉換

一維數組的下標Index(小標從0開始)和二維下標X、Y(下標從0開始)之間的轉換公式

一維到二維的轉換

X=Int(Index/9)

Y=Index mod 9

二維到一維的轉換

Index=X*9+Y

數組中的每個整數表示數獨對應的單元格的狀態

正數表示空白單元格能填的數的組合，用二進制表示。用位來表示該單元格是否能填相應的數字，1表示能填，0表示不能填。

如文章開始的數獨的單元格(1，1)可能填7和8，則第7位和第8位上是1(位數是從后往前數)，其余位都是0，用整數表示就是Num(0)=0110000002=192

每在單元格中填一個數字，則把相應的行、列、宮中其余的單元格把該數字去掉。

我們可以充分利用位運算來簡化去數字的過程。如：要把單元格去掉7這個數字的可能。首先7對應的二進制位0010000002，取其反數得到1101111112，再和目標單元格的數值進行AND的位運算，來實現去除該單元格7這個數字的可能性(由于位運算的便捷，不需要考慮該單元格是否原本包含7這個數字的可能性)。

如：(1，1)=0110000002 AND 1101111112=0100000002，去除7這個可能性，只剩8這個可能性了，也就是成為唯一數單元格

再比如：(1，9)=0100000102 AND 1101111112=0100000102，原本單元格就沒有7這個可能性，執行位運算后，還是原來的可能性，沒有發生變化。

負數表示該單元格已經確定的數，例如：(1，2)=-6，表示該單元格已近填了數字6

0表示該單元格既沒有填確定的數字，也沒有可填數的可能性。也就是上文說的無解單元格

為了算法中計算的方便，事先把這些二進制數都緩存起來，用一個一維的數組表示

用數組V來表示各個位對應的數字

V(0)=0000000012=1

V(1)=0000000102=2

V(2)=0000001002=4

V(3)=0000010002=8

V(4)=0000100002=16

V(5)=0001000002=32

V(6)=0010000002=64

V(7)=0100000002=128

V(8)=1000000002=256

V(9)=1111111112=511

數字7對應的二進制數為V(6)=0010000002=64，7的反數為V(9)-V(6)=1101111112=447

每個單元格初始的值都是V(9)=1111111112=511

2、如何獲得一個單元格的可填數的個數

由于是用二進制來表示單元格的狀態，那么可填數的個數就是該數字中1的個數。我們之前有一個很方便的方法快速計算一個數中1的個數，參看算法的強大——快速計算一個正二進制整數中包含多少個1。

3、狀態的緩存

依據之前的說法，在碰到無唯一數單元格的情況時，要把當前的狀態緩存起來。考慮到實際情況，從算法的角度上來說，用棧(先進后出)這個數據結構來實現比較合適。可以自己寫一個棧的實現。但是，目前很多的編程語言都實現了基本的數據結構，提供了基本的數據結構的類和方法供我們調用。

以Visual Studio為例，它有Stack這個類，實現了棧的基本操作。有兩個棧的方法：Push(壓棧)——把數據寫到棧里面；Pop(出棧)——把數據從棧里提出來，并刪除棧中的數據。

4、代碼說明

基本的變量

Private _Num(80) As?Integer

Private _V(9) As?Integer

Private _S As System.Text.StringBuilder

Private _HasString As?Boolean

_Num數組表示數獨的狀態；_V數組是輔助數組，緩存常用的二進制數

_S是一個文本對象，保存數獨求解的過程；_HasString是個開關變量，表示是否記錄求解過程；這兩個變量是輔助變量，僅僅起到記錄的作用。

類的初始化

Public?Sub?New(Optional?ByVal HasString As?Boolean = True)

Dim I As?Integer

_V(0) = 1

For I = 1 To 8

_V(I) = _V(I - 1) * 2

_V(9) = 511

For I = 0 To 80

_Num(I) = _V(9)

_S = New System.Text.StringBuilder

_HasString = HasString

End?Sub

代碼的前半段生成V這個數組，_V(9)=511。后半段，初始化數獨數組。由于是空白數獨數組，故每個單元格的值都是_V(9)

在給定的單元格里移除某個數字的可能性代碼

Private?Function RemoveNum(ByVal Row As?Integer, ByVal Col As?Integer, ByVal Num2 As?Integer) As?Integer

Dim Index As?Integer = Row * 9 + Col

If _Num(Index) > 0 Then _Num(Index) = _Num(Index) And Num2

Return _Num(Index)

End?Function

3個參數，Row表示行，Col表示列(都是下標從0開始)，Num2表示要去除的數的反碼，以二進制表示。

例如：在(1，1)這個單元格去除7這個可能性，則調用RemoveNum(0，0，1101111112)

返回值是該單元格的狀態值，如果返回0，表示該單元就成了無解單元格，要后面的代碼做適當的處理

在給定的單元格填某個數的代碼

Private?Function SetNumPri(ByVal Row As?Integer, ByVal Col As?Integer, ByVal Num As?Integer) As?Boolean

If (_V(Num) And _Num(Row * 9 + Col)) = 0 Then?Return?False

_Num(Row * 9 + Col) = -(Num + 1)

Num = _V(9) - _V(Num)

Dim I As?Integer, J As?Integer

For I = 0 To 8

If RemoveNum(I, Col, Num) = 0 Then?Return?False

If RemoveNum(Row, I, Num) = 0 Then?Return?False

Dim R1 As?Integer = Int(Row / 3) * 3

Dim C1 As?Integer = Int(Col / 3) * 3

For I = R1 To R1 + 2

For J = C1 To C1 + 2

If RemoveNum(I, J, Num) = 0 Then?Return?False

Return?True

End?Function

3個參數，Row表示行，Col表示列，Num表示要填充的數字(下標從0開始)，這個方法是供類內部調用，從程序的角度來說，程序處理下標，從0開始比從1開始要來得簡單。

例如：在(1，1)中填入數字7，則調用SetNumPri(0，0，6)

代碼的第1行，先利用位運算判斷當前單元格能否填制定的數字，不能填返回False

代碼的第2行，設置當前單元格為指定數字，之前說了，用負數表示已填好的數字

代碼的第3行，獲得當前數字的反碼，為后面去除該單元格所在的行、列、宮的其他單元格的該數字做準備

后面有兩個循環，第一個循環去除行、列的其他單元格的該數字；第二個雙循環去除宮的其他單元格的該數字。在調用RomoveNum方法時，若返回的是0，說明產生了無解單元格，那說明在這個單元格填該數字是不合理的，故返回False

當全部的代碼都能順利完成了，說明這個單元格填該數字是合理的，返回True

該方法的另一個重載形式

Private?Function SetNumPri(ByVal Index As?Integer, ByVal Num2 As?Integer) As?Boolean

Dim Row As?Integer = Int(Index / 9)

Dim Col As?Integer = Index Mod 9

Dim I As?Integer

For I = 0 To 8

If _V(I) = Num2 Then?Exit For

Return SetNumPri(Row, Col, I)

End?Function

這也是一個供內部調用的方法，兩個參數，Index是一維數組的下標；Num2是數字的二進制的形式。整個方法就是參數的轉換，然后調用之前的方法

下面是兩個供外面調用的方法

Public?Function SetNum(ByVal Row As?Integer, ByVal Col As?Integer, ByVal Num As?Integer) As?Boolean

Return SetNumPri(Row - 1, Col - 1, Num - 1)

End?Function

Public?Function SetLine(ByVal Row As?Integer, ByVal?ParamArray Num() As?Integer) As?Boolean

If Num.Length = 0 Then?Return?True

Dim I As?Integer

For I = 0 To IIf(Num.Length - 1 > 8, 8, Num.Length - 1)

If Num(I) > 0 AndAlso SetNumPri(Row - 1, I, Num(I) - 1) = False?Then?Return?False

Return?True

End?Function

第一個方法是公開給外部調用的填數的方法。對外來說，從直觀性上來說，下標是從1開始比較合適，但是內部的方法從0開始比較好。

如在(1，1)填7，調用SetNum(1，1，7)，這個方法轉而調用SetNumPri(0，0，6)

這個方法一般用在初始化數獨時候調用

第二個方法也是公開給外部的方法，一次填寫一行數的方法，如果是空白單元格，則用0替代

如本文開始的數獨，填寫第一行代碼就是SetLine(1，0，6，0，5，9，3，0，0，0)

幾個輔助方法

Private?Sub RestoreNum(ByVal L As?List(Of?Integer))

Dim I As?Integer

For I = 0 To 80

_Num(I) = L.Item(I)

AppendString("Restore Matrix")

End?Sub

恢復L中的數據到數獨數組中，L是之前緩存的數據。AppendString這個方法是將數據記錄到文本對象

Private?Function Get1Count(ByVal Value As?Integer) As?Integer

Dim C As?Integer = 0

Do?While Value > 0

Value = Value And (Value - 1)

C += 1

Loop

Return C

End?Function

獲得一個數中1的個數，也就是獲得一個空白單元格的可填數的數目

例如：(1，1)=0110000002，Get1Count(0110000002)=2，說明(1，1)這個單元格能填2個數

Private?Function GetIndexOfNum(ByVal Num As?Integer, ByVal Index As?Integer) As?Integer

Dim I As?Integer, K As?Integer = 0

For I = 0 To 8

If (_V(I) And Num) <> 0 Then

K += 1

If K = Index Then?Return I + 1

End?If

Return -1

End?Function

獲得指定數Num(二進制形式)的第Index個的可填數

還是以上面的為例，(1，1)=0110000002，

GetIndexOfNum(0110000002，1)=7，表示第1個可填數是7

GetIndexOfNum(0110000002，2)=8，表示第2個可填數是8

GetIndexOfNum(0110000002，3)=-1，表示沒有第3個可填數

輔助記錄函數

這些函數對求解算法沒啥太大的幫助，僅僅是將求解的過程記錄到文本中，以供日后研究參考

Private?Function ReturnNumString(ByVal Num As?Integer) As?String

If Num < 0 Then?Return?"#" & (-Num) & " "

Dim I As?Integer, S As?String = ""

For I = 0 To 8

If (_V(I) And Num) <> 0 Then S &= (I + 1)

Return S.PadRight(10)

End?Function

返回一個數字的文本格式，如果是空白單元格，返回該單元格的所有可填數；如果是已填單元格，返回#+數字的字符串。返回的字符串經過對齊處理。

Private?Function ReturnMatrix() As?String

Dim I As?Integer, J As?Integer, S As?String = ""

For I = 0 To 8

For J = 0 To 8

S &= ReturnNumString(_Num(I * 9 + J))

S &= vbNewLine

Return S

End?Function

返回整個數獨的狀態文本

Private?Sub AppendString(ByVal Text As?String, Optional?ByVal AppendMatrix As?Boolean = True)

If _HasString = False?Then?Exit Sub

_S.AppendLine(Text)

_S.AppendLine()

If AppendMatrix = True?Then

_S.AppendLine(ReturnMatrix)

_S.AppendLine()

End?If

End?Sub

將文本添加到文本對象，并根據AppendMatrix參數來決定是否將整個數獨的狀態添加到文本對象

Private?Function IndexToXY(ByVal Index As?Integer) As?String

Return (Int(Index / 9) + 1) & "-" & (Index Mod 9 + 1) & " Num:" & -_Num(Index)

End?Function

返回指定Index的坐標和已填的數，用于在文本對象中

Public?Function CalculationString() As?String

Return _S.ToString

End?Function

對外公開的方法，返回文本對象，也就是之前記錄的求解過程，共日后研究參考

主求解函數——算法的核心

下面的3個函數是算法的核心

Private?Function FindMinCell() As?Integer

Dim I As?Integer, C As?Integer

Dim tP As?Integer = -1, tMin As?Integer = 20

I = 0

If _Num(I) > 0 Then

C = Get1Count(_Num(I))

If C = 1 Then

If SetNumPri(I, _Num(I)) = False?Then?Return -2

AppendString("SetNum " & IndexToXY(I))

If I = tP Then

tP = -1

tMin = 20

End?If

I = -1

Else

If C < tMin Then

tP = I

tMin = C

End?If

I += 1

Loop?Until I > 80

Return tP

End?Function

該函數是獲得最少可能數的單元格(可填數大于2的空白單元格)

該函數返回值有3個可能性

返回值：-1，沒有找到這樣的單元格，函數從某個唯一數單元格開始填數，依次填下去，并且把所有的空白單元格都填滿。這說明，求解結束。

返回值：-2，沒有找到這樣的單元格，函數從某個唯一數單元格開始填數，依次填下去，產生了無解單元格。說明之前的求解過程有錯誤或者說該數獨無解

返回值：0-80，找到這樣的單元格，并且當前的數獨數組中不再存在唯一數單元格(函數直接會在唯一數單元格上填數)

Public?Function Calculate() As?Integer()

Dim I As?Integer

Dim K As?Integer

Dim Q As?New?Stack(Of?List(Of?Integer))

Dim L As?List(Of?Integer)

_S = New System.Text.StringBuilder

AppendString("Init Matrix")

K = FindMinCell()

Do?While K <> -1

If K = -2 Then

If Q.Count = 0 Then

AppendString("Error!!!!!", False)

Return?Nothing

End?If

L = Q.Pop

K = L(82)

L.RemoveAt(82)

I = L(81) + 1

L.RemoveAt(81)

AppendString("Stack Pop " & Q.Count + 1, False)

RestoreNum(L)

K = FindNextK(Q, L, K, I)

Else

L = New?List(Of?Integer)

L.AddRange(_Num)

K = FindNextK(Q, L, K, 1)

End?If

Loop

AppendString("Calculating Complete!!!!")

Dim V(80) As?Integer

For I = 0 To 80

V(I) = -_Num(I)

Return V

End?Function

對外公開的主求解函數，返回最終結果的整形數組

首先解釋一下棧對象Q，由于棧Q每次壓棧的時候只能壓一個對象，而當出現無唯一數單元格的情況的時候，需要將當前的數據緩存起來。需要緩存的內容有三個部分，分別是數獨數組、找到的最少可能數的單元格的下標、最少可能數的單元格的選擇填的第幾個數。故用一個List(of Integer)對象將之前的三個內容緩存起來。L(0)—L(80)表示是數獨數組，L(81)是最少可能數的單元格的下標，L(82)是最少可能數的單元格的選擇填的第幾個數。

該函數的主要是判斷K的值，如上個函數所述，K的值主要有3種

K=-1，說明沒有空白單元格，數獨已經完美的求解完成，直接返回結果

K=-2，說明有無解單元格，那么判斷棧Q中的數據，如果棧Q中沒有數據，說明該數獨無解；如果棧Q中有數據，那么把數據提出來，把數獨的狀態恢復到之前的情況。并從上次緩存的最少可能數單元格中，提取下一個可填數去繼續進行嘗試。

舉例說明，緩存了0，1。說明上次嘗試的是第1個單元格(下標從0開始)的第1個可填數。由于出現了無解單元格，說明第1個可填數是不正確的，那么繼續嘗試第2個可填數。調用的方法：FindNextK(Q, L, K, I)，之前I已經加過1了。

K=0-80，得到最少可能數的單元格的下標。從該單元格的第1個可填數開始嘗試。調用的方法：FindNextK(Q, L, K, 1)

嘗試可能數的函數是FindNextK，返回值也是分為3種，-1、-2、0-80。意義和上面一樣

Private?Function FindNextK(ByVal Q As?Stack(Of?List(Of?Integer)), ByVal L As?List(Of?Integer), ByVal K As?Integer, ByVal Index As?Integer) As?Integer

Dim J As?Integer = GetIndexOfNum(_Num(K), Index)

Do?While J <> -1

If SetNumPri(K, _V(J - 1)) = True?Then

AppendString("Stack Push " & Q.Count + 1, False)

AppendString("SetNum MayBe " & IndexToXY(K))

L.Add(Index)

L.Add(K)

Q.Push(L)

K = FindMinCell()

Exit Do

End?If

RestoreNum(L)

Index += 1

J = GetIndexOfNum(_Num(K), Index)

Loop

If J = -1 Then K = -2

Return K

End?Function

輔助函數，獲得嘗試可能數的結果

首先，通過GetIndexOfNum獲得當前可填數。如果返回值-1的話，說明當前已經沒有可填數，出現無解單元格，直接返回值為-2

然后嘗試在當前單元格填數，調用SetNumPri(K, _V(J - 1))，返回True表示該數能填，那么把當前的狀態緩存到棧Q中，并通過FindMinCell函數獲得下一個可能的K值，并返回；返回False表示該數不能填，恢復數據到數獨數組，繼續嘗試下一個數。

至此該算法類的代碼都說明完整了

在該算法中僅僅用了最基本的解法——摒除法。遇見唯一數單元格，就直接填數，如果遇見無唯一數單元格，則緩存數據，并對該單元格的所有可填數做嘗試，直到求解出該數獨為止。

會有人疑問，利用棧Q緩存數據，會不會極大的占用系統資源，導致無法解題的情況。以目前的情況來看，我用該算法求解了“程序員們都是不被世人所理解的真正天才嗎?-請大家看這個數獨的解法”中的號稱最難的數獨，并把求解的結果保存到文件后打開分析了一下，發現棧Q的緩存不超過20步，以20步為例，每步83*4字節，則一共20*83*4=6640字節<7K字節。遠小于系統的承受能力。因此，不必擔心系統的承受能力

如果，誰有好的數獨的算法，歡迎交流，不吝賜教。

讓我們實戰看看成果，用該算法求解本文開頭的數獨，代碼如下：

Dim tS As New clsSudoku

tS.SetLine(1, 0, 6, 0, 5, 9, 3, 0, 0, 0)

tS.SetLine(2, 9, 0, 1, 0, 0, 0, 5, 0, 0)

tS.SetLine(3, 0, 3, 0, 4, 0, 0, 0, 9, 0)

tS.SetLine(4, 1, 0, 8, 0, 2, 0, 0, 0, 4)

tS.SetLine(5, 4, 0, 0, 3, 0, 9, 0, 0, 1)

tS.SetLine(6, 2, 0, 0, 0, 1, 0, 6, 0, 9)

tS.SetLine(7, 0, 8, 0, 0, 0, 6, 0, 2, 0)

tS.SetLine(8, 0, 0, 4, 0, 0, 0, 8, 0, 7)

tS.SetLine(9, 0, 0, 0, 7, 8, 5, 0, 1, 0)

tS.Calculate()

My.Computer.FileSystem.WriteAllText("1.txt", tS.CalculationString, False)

該數獨還是比較簡單的，一路唯一數單元格到底

結果如下：

Calculating Complete!!!!

#7??????? #6??????? #2??????? #5??????? #9??????? #3??????? #1??????? #4??????? #8

#9??????? #4??????? #1??????? #2??????? #7??????? #8??????? #5??????? #3??????? #6

#8??????? #3??????? #5??????? #4??????? #6??????? #1??????? #7??????? #9??????? #2

#1??????? #9??????? #8??????? #6??????? #2??????? #7??????? #3??????? #5??????? #4

#4??????? #7??????? #6??????? #3??????? #5??????? #9??????? #2??????? #8??????? #1

#2??????? #5??????? #3??????? #8??????? #1??????? #4??????? #6??????? #7??????? #9

#3??????? #8??????? #7??????? #1??????? #4??????? #6??????? #9??????? #2??????? #5

#5??????? #1??????? #4??????? #9??????? #3??????? #2??????? #8??????? #6??????? #7

#6??????? #2??????? #9??????? #7??????? #8??????? #5??????? #4??????? #1??????? #3

下面是該算法類的完整代碼

Public?Class?clsSudoku

Private _Num(80) As?Integer

Private _V(9) As?Integer

Private _S As System.Text.StringBuilder

Private _HasString As?Boolean

Public?Sub?New(Optional?ByVal HasString As?Boolean = True)

Dim I As?Integer

_V(0) = 1

For I = 1 To 8

_V(I) = _V(I - 1) * 2

_V(9) = 511

For I = 0 To 80

_Num(I) = _V(9)

_S = New System.Text.StringBuilder

_HasString = HasString

End?Sub

Private?Function Get1Count(ByVal Value As?Integer) As?Integer

Dim C As?Integer = 0

Do?While Value > 0

Value = Value And (Value - 1)

C += 1

Loop

Return C

End?Function

Private?Function RemoveNum(ByVal Row As?Integer, ByVal Col As?Integer, ByVal Num2 As?Integer) As?Integer

Dim Index As?Integer = Row * 9 + Col

If _Num(Index) > 0 Then _Num(Index) = _Num(Index) And Num2

Return _Num(Index)

End?Function

Public?Function SetNum(ByVal Row As?Integer, ByVal Col As?Integer, ByVal Num As?Integer) As?Boolean

Return SetNumPri(Row - 1, Col - 1, Num - 1)

End?Function

Public?Function SetLine(ByVal Row As?Integer, ByVal?ParamArray Num() As?Integer) As?Boolean

If Num.Length = 0 Then?Return?True

Dim I As?Integer

For I = 0 To IIf(Num.Length - 1 > 8, 8, Num.Length - 1)

If Num(I) > 0 AndAlso SetNumPri(Row - 1, I, Num(I) - 1) = False?Then?Return?False

Return?True

End?Function

Private?Function SetNumPri(ByVal Row As?Integer, ByVal Col As?Integer, ByVal Num As?Integer) As?Boolean

If (_V(Num) And _Num(Row * 9 + Col)) = 0 Then?Return?False

_Num(Row * 9 + Col) = -(Num + 1)

Num = _V(9) - _V(Num)

Dim I As?Integer, J As?Integer

For I = 0 To 8

If RemoveNum(I, Col, Num) = 0 Then?Return?False

If RemoveNum(Row, I, Num) = 0 Then?Return?False

Dim R1 As?Integer = Int(Row / 3) * 3

Dim C1 As?Integer = Int(Col / 3) * 3

For I = R1 To R1 + 2

For J = C1 To C1 + 2

If RemoveNum(I, J, Num) = 0 Then?Return?False

Return?True

End?Function

Private?Function SetNumPri(ByVal Index As?Integer, ByVal Num2 As?Integer) As?Boolean

Dim Row As?Integer = Int(Index / 9)

Dim Col As?Integer = Index Mod 9

Dim I As?Integer

For I = 0 To 8

If _V(I) = Num2 Then?Exit For

Return SetNumPri(Row, Col, I)

End?Function

Private?Function FindMinCell() As?Integer

Dim I As?Integer, C As?Integer

Dim tP As?Integer = -1, tMin As?Integer = 20

I = 0

If _Num(I) > 0 Then

C = Get1Count(_Num(I))

If C = 1 Then

If SetNumPri(I, _Num(I)) = False?Then?Return -2

AppendString("SetNum " & IndexToXY(I))

If I = tP Then

tP = -1

tMin = 20

End?If

I = -1

Else

If C < tMin Then

tP = I

tMin = C

End?If

I += 1

Loop?Until I > 80

Return tP

End?Function

Public?Function Calculate() As?Integer()

Dim I As?Integer

Dim K As?Integer

Dim Q As?New?Stack(Of?List(Of?Integer))

Dim L As?List(Of?Integer)

_S = New System.Text.StringBuilder

AppendString("Init Matrix")

K = FindMinCell()

Do?While K <> -1

If K = -2 Then

If Q.Count = 0 Then

AppendString("Error!!!!!", False)

Return?Nothing

End?If

L = Q.Pop

K = L(82)

L.RemoveAt(82)

I = L(81) + 1

L.RemoveAt(81)

AppendString("Stack Pop " & Q.Count + 1, False)

RestoreNum(L)

K = FindNextK(Q, L, K, I)

Else

L = New?List(Of?Integer)

L.AddRange(_Num)

K = FindNextK(Q, L, K, 1)

End?If

Loop

AppendString("Calculating Complete!!!!")

Dim V(80) As?Integer

For I = 0 To 80

V(I) = -_Num(I)

Return V

End?Function

Private?Sub RestoreNum(ByVal L As?List(Of?Integer))

Dim I As?Integer

For I = 0 To 80

_Num(I) = L.Item(I)

AppendString("Restore Matrix")

End?Sub

Private?Function GetIndexOfNum(ByVal Num As?Integer, ByVal Index As?Integer) As?Integer

Dim I As?Integer, K As?Integer = 0

For I = 0 To 8

If (_V(I) And Num) <> 0 Then

K += 1

If K = Index Then?Return I + 1

End?If

Return -1

End?Function

Private?Function FindNextK(ByVal Q As?Stack(Of?List(Of?Integer)), ByVal L As?List(Of?Integer), ByVal K As?Integer, ByVal Index As?Integer) As?Integer

Dim J As?Integer = GetIndexOfNum(_Num(K), Index)

Do?While J <> -1

If SetNumPri(K, _V(J - 1)) = True?Then

AppendString("Stack Push " & Q.Count + 1, False)

AppendString("SetNum MayBe " & IndexToXY(K))

L.Add(Index)

L.Add(K)

Q.Push(L)

K = FindMinCell()

Exit Do

End?If

RestoreNum(L)

Index += 1

J = GetIndexOfNum(_Num(K), Index)

Loop

If J = -1 Then K = -2

Return K

End?Function

Private?Function ReturnNumString(ByVal Num As?Integer) As?String

If Num < 0 Then?Return?"#" & (-Num) & " "

Dim I As?Integer, S As?String = ""

For I = 0 To 8

If (_V(I) And Num) <> 0 Then S &= (I + 1)

Return S.PadRight(10)

End?Function

Private?Function ReturnMatrix() As?String

Dim I As?Integer, J As?Integer, S As?String = ""

For I = 0 To 8

For J = 0 To 8

S &= ReturnNumString(_Num(I * 9 + J))

S &= vbNewLine

Return S

End?Function

Private?Sub AppendString(ByVal Text As?String, Optional?ByVal AppendMatrix As?Boolean = True)

If _HasString = False?Then?Exit Sub

_S.AppendLine(Text)

_S.AppendLine()

If AppendMatrix = True?Then

_S.AppendLine(ReturnMatrix)

_S.AppendLine()

End?If

End?Sub

Private?Function IndexToXY(ByVal Index As?Integer) As?String

Return (Int(Index / 9) + 1) & "-" & (Index Mod 9 + 1) & " Num:" & -_Num(Index)

End?Function

Public?Function CalculationString() As?String

Return _S.ToString

End?Function

End?Class

總結

以上是生活随笔為你收集整理的数独问题流程图_算法实践——数独的基本解法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： VMware虚拟机与宿主无法复制的解决办
下一篇：【开源项目之路】jquery的build