アルゴリズムの練習: 数独の基本解法

アルゴリズムの練習: 数独の基本解法

数独は紙とペンを使って遊ぶ論理ゲームです。プレイヤーは、9×9 のボード上の既知の数字に基づいて残りのすべてのスペースの数字を推測し、各行、列、太線の宮殿の数字に重複なく 1 ～ 9 が含まれていることを確認する必要があります。 認定された数独パズルには必ず 1 つの答えがあり、推論方法はこれに基づいています。 解答が 1 つもないか、複数の解答がある問題は認定されません。

下の図に示すように、これは数独の問題です。

数独の詳しい紹介については、「Baidu 百科事典 - 数独」を参照してください。

数独の基本的な解法はルール消去法を使うことである

いくつかの定義

各行は「数独行」 、各列は「数独列」 、各小さな 9 マスのグリッドは「数独マス」と呼ばれます。数独の基本的なルールは、各行、各列、各マスに 1 から 9 までの数字が 1 回だけ現れるというものです。

上図のセルを表すには (行, 列) を使用します。たとえば、(1, 1) は 1 行目と 1 列目のセルを表し、(2, 4) は 2 行目と 4 列目のセルを表します。

上の図に示すように、各空白セルに入力できる数には制限があります。

たとえば、(1, 1) には 7 と 8 しか入れられません。また、(6, 4) には 8 しか入れられません。

1つの数字しか入れられない空白のセルをユニーク数セルと呼びます。上の図では、(6, 4) がユニーク数セルです。

問題を解く順番は、固有の番号を持つセルから始めます。固有の番号を持つセルには 1 つの番号しか入力できないため、まずこのセルに番号を入力します。このセルに数字を入力してください。ルールの定義により、このセルが配置されている行、列、宮殿内の他のセルにこの数字を入力することはできません。これらのセルに入力できる数字の数は少なくなります。新しい一意の番号セルが生成される可能性もあります。

多くの数独パズルでは、一意の数字が書かれたセルから始めて、一意の数字が書かれたセルを埋めていくことで数独を解くことができます。

問題を解く過程で、空白のセルに数字を記入する必要がないことがわかった場合、そのようなセルは「解けないセル」と呼ばれます。これは、数独パズルに解答がないか、前の問題解決プロセスに問題があり、前の問題解決プロセスに戻って確認する必要があることを意味します。

しかし、数独の問題の中には、解くときに空白のセルはあるものの、一意の数字を持つセルが見つからないものも多くあります。つまり、各空白のセルに埋めることができる数字が少なくとも 2 つあるということです。これを、セルの数が一意ではない状況と呼びます

こういう時どうすればいいでしょうか？最も小さい数字の空白セルを 1 つ見つけます (これには明確な答えはありません。最も小さい数字の空白セルの場合もあれば、最初の空白セルの場合もあれば、最も大きい数字の空白セルの場合もあります。どの空白セルを選択するかがその後の問題解決に影響するかどうかは証明されていないため、結論を出すことは困難です。感覚に基づいて最も小さい数字の空白セルを選択するのが最善の選択です)。記入できる数字は複数あるため、まず現在の状態を保存し、次に記入可能な数字から数字を選択し (最小から最大まで選択)、問題を解き続けます。最終結果が解けた場合、現在の選択が正しいことを意味します。その後の解決プロセスで問題が発生した場合、現在の数字の選択に問題があることを意味します。その場合は、別の数字を選択して入力し、解決を続けます。どの選択肢でも最終的な答えが得られない場合は、数独パズルに解答がないか、または前の解答プロセスに問題があり、戻って前の解答プロセスを確認する必要があることを意味します。最終的な答えが得られるまでこのプロセスを繰り返します。

極端な状況が発生する（可能性は低い）。つまり、現在の空白セル内のすべての可能な数字が選択されており、解はありません。そして、これまでに固有の数値セルが存在しない状況は一度もありませんでした。つまり、この数独にはまったく解法がないということです。

次の図は数独を解くフローチャートです。

このアルゴリズムの具体的な実装についてお話ししましょう

1. 数独の状態の表現

コンピュータを使用して数独を解きます。基本的なポイントは、数独の状態をどのように表現するかです。

整数1次元配列を使用して数独の状態を表す

Num(80)は数独の状態を表すために使用されます（配列の添え字は0から始まります）。数独は2次元の表ですが、配列は1次元の配列です。次に、1次元と2次元の間の変換があります

1次元配列の添字インデックス（添字は0から始まる）と2次元の添字X、Y（添字は0から始まる）間の変換式

  1. 1次元から2次元への変換
  2.  
  3.  X=Int（インデックス/ 9 ） 
  4.  
  5.  Y=インデックス mod 9  
  6.  
  7.  2Dから1Dへの変換
  8.  
  9. インデックス=X* 9 +Y

配列内の各整数は、数独パズル内の対応するセルの状態を表します。

正の数は、空白のセルに入力できる数値の組み合わせを 2 進数で表します。ビットを使用して、セルを対応する数字で埋めることができるかどうかを示します。1 は埋めることができることを意味し、0 は埋めることができないことを意味します。

例えば、記事の冒頭にある数独のセル（1, 1）には7と8が記入されているので、7番目と8番目の数字は1（数字は後ろから前に数えます）で、残りは0です。整数形式では、Num（0）= 011000000 2 = 192です。

セルに数字が入力されるたびに、対応する行、列、または四角形の残りのセルからその数字が削除されます。

ビット演算をフル活用して、数値を 10 進数化するプロセスを簡素化できます。たとえば、セルから数字 7 の可能性を削除します。まず、7 に対応する 2 進数 001000000 2の逆数を取り、 110111111 2を取得します。次に、ターゲット セルの値とビット単位の AND 演算を実行して、セルから数字 7 の可能性を排除します (ビット単位の演算の利便性により、セルに元々数字 7 が含まれていたかどうかを考慮する必要はありません)。

たとえば、(1, 1) = 011000000 2 AND 110111111 2 = 010000000 2の場合、7 の可能性を除外すると 8 のみが残り、これは一意の数値セルになることを意味します。

たとえば、(1, 9) = 010000010 2 AND 110111111 2 = 010000010 2です。元のセルには 7 の可能性はありません。ビット操作を実行した後も、可能性は同じままで変化しません。

負の数は、セルにすでに特定の数字が入力されていることを示します。たとえば、(1, 2) = -6 は、セルに数字 6 が入力されていることを意味します。

0 は、セルに明確な数字がなく、数字が入力される可能性もないことを意味します。これが、上で述べた解決不可能なセルです。

アルゴリズムでの計算を容易にするために、これらの 2 進数は事前にキャッシュされ、 1 次元配列で表されます。

各ビットに対応する数値を表すために配列Vを使用する

  1. V( 0 ) = 0000000012 = 1   
  2.  
  3.  V( 1 ) = 0000000102 = 2  
  4.  
  5.  V( 2 ) = 0000001002 = 4  
  6.  
  7.  V( 3 ) = 0000010002 = 8  
  8.  
  9.  V( 4 ) = 0000100002 = 16  
  10.  
  11.  V( 5 ) = 0001000002 = 32  
  12.  
  13.  V( 6 ) = 0010000002 = 64  
  14.  
  15.  V( 7 ) = 0100000002 = 128  
  16.  
  17.  V( 8 ) = 1000000002 = 256  
  18.  
  19.  V( 9 ) = 11111111112 = 511  

7に対応する2進数はV(6)=001000000 2 =64であり、7の逆数はV(9)-V(6)=110111111 2 =447である。

各セルの初期値はV(9) = 1111111111 2 = 511

2. セルに入力できる数字の数を取得する方法

セルの状態は 2 進数で表されているため、埋めることができる数字の数は、数字内の 1 の数になります。これまで、数値内の 1 の数を素早く計算する非常に便利な方法がありました。強力なアルゴリズムをご覧ください - 正の 2 進整数内の 1 の数を素早く計算します。

3. 状態キャッシュ

前述の説明によれば、セルの数が一意ではない状況に遭遇した場合、現在の状態をキャッシュする必要があります。実際の状況を考慮すると、アルゴリズムの観点からは、スタック（先入れ後出し）データ構造を使用して実装する方が適切です。独自のスタック実装を記述できます。ただし、現在多くのプログラミング言語は基本的なデータ構造を実装し、呼び出すための基本的なデータ構造クラスとメソッドを提供しています。

Visual Studio を例にとると、基本的なスタック操作を実装する Stack クラスがあります。スタック メソッドには 2 つあります: プッシュ - スタックにデータを書き込む; ポップ - スタックからデータを取り出し、スタック内のデータを削除する。

4. コードの説明

基本変数

  1. プライベート_Num( 80 ) 整数
  2.     プライベート_V( 9 )整数
  3.     プライベート _S として System.Text.StringBuilder
  4.     プライベート_HasStringをブール値として

_Num 配列は数独パズルの状態を表します。_V 配列は、よく使用される 2 進数をキャッシュする補助配列です。

_S は、数独を解くプロセスを保存するテキスト オブジェクトです。_HasString は、解くプロセスを記録するかどうかを示すスイッチ変数です。これら 2 つの変数は補助変数であり、記録としてのみ機能します。

クラスの初期化

  1. パブリック Sub New(オプション ByVal HasString As Boolean = True)
  2.     整数としての暗いI
  3.     _V( 0 ) = 1    
  4.     I = 1から8の場合   
  5.         _V(I) = _V(I - 1 ) * 2    
  6.     次
  7.     _V( 9 ) = 511    
  8.  
  9.     I = 0から80の場合   
  10.         _Num(I) = _V( 9 )
  11.     次
  12.  
  13.     _S = 新しい System.Text.StringBuilder
  14.     _HasString = 文字列を持つ
  15. 終了サブ

コードの前半は配列V、_V(9)=511を生成します。後半では、数独配列が初期化されます。空白の数独配列なので、各セルの値は_V（9）です。

特定のセルの数字を削除する可能性のあるコード

  1. プライベート関数 RemoveNum(ByVal Row As Integer、ByVal Col As Integer、ByVal Num2 As Integer) As Integer
  2.     Dim Index As Integer = 行 * 9 + 列
  3.     _Num(Index) > 0の場合、_Num(Index) = _Num(Index) であり、Num2
  4.     _Num(インデックス)を返す
  5. 終了関数

3 つのパラメータ、Row は行、Col は列 (すべての添え字は 0 から始まります)、Num2 は削除する数値の 2 の補数を 2 進数で表します。

たとえば、セル(1, 1)の7の可能性を削除するには、RemoveNum(0, 0, 110111111 2 )を呼び出します。

戻り値はセルの状態値です。0を返す場合、セルが解決不可能なセルになったことを意味し、後続のコードで適切な処理を行う必要があります。

指定されたセルに数字を入力する

  1. プライベート関数 SetNumPri(ByVal Row As Integer、ByVal Col As Integer、ByVal Num As Integer) As Boolean
  2.     (_V(Num) And _Num(Row * 9 + Col)) = 0の場合は False を返します
  3.     _Num(行 * 9 + 列) = -(Num + 1 )
  4.     数 = _V( 9 ) - _V(数) 
  5.  
  6.     Dim I を整数、J を整数
  7.  
  8.     I = 0から8の場合   
  9.         RemoveNum(I, Col, Num) = 0の場合は False を返す
  10.         RemoveNum(Row, I, Num) = 0の場合は False を返します
  11.     次
  12.  
  13.     Dim R1 As Integer = Int(行 / 3 ) * 3    
  14.     C1を整数として暗記する = Int(Col / 3 ) * 3    
  15.  
  16.     I = R1 から R1 + 2まで   
  17.         J = C1 から C1 + 2まで   
  18.             RemoveNum(I, J, Num) = 0の場合は False を返す
  19.         次
  20.     次
  21.  
  22.     Trueを返す
  23. 終了関数

パラメータは 3 つあります。Row は行、Col は列、Num は埋める数値 (添字は 0 から始まります) を表します。このメソッドは、クラス内の内部呼び出しに使用されます。プログラムの観点からは、1 から始まる添字よりも 0 から始まる添字の方がプログラムが処理しやすくなります。

たとえば、(1, 1)に数字7を入力するには、SetNumPri (0, 0, 6)を呼び出します。

コードの最初の行では、まずビット演算を使用して、現在のセルに指定された数値を入力できるかどうかを判断します。入力できない場合は、False を返します。

2 行目のコードでは、現在のセルを指定された数値に設定します。前述のように、負の数値は塗りつぶされた数値を表すために使用されます。

コードの 3 行目は、セルが配置されている行、列、および宮殿内の他のセルから数字を削除する準備として、現在の数字の逆コードを取得します。

その後に 2 つのループがあります。最初のループは行と列の他のセルの数字を削除します。2 番目の二重ループは宮殿の他のセルの数字を削除します。 RomoveNum メソッドを呼び出したとき、戻り値が 0 の場合は、解決できないセルが存在することを意味し、このセルに数値を入力することは不可能であることを意味するため、False を返します。

すべてのコードが正常に完了すると、このセルに入力された数値が妥当であることを意味し、Trueを返します。

このメソッドの別のオーバーロード形式

  1. プライベート 関数SetNumPri( ByValインデックスAs  整数、 ByVal Num2 As  整数）として ブール    
  2.     暗くした行 整数= Int(インデックス / 9) 
  3.     暗色列As  整数= インデックスmod 9 
  4.     暗くI As  整数   
  5.      I = 0から8の場合
  6.          _V (I) = Num2の場合 出口 のために   
  7.     次   
  8.      SetNumPri(Row, Col, I)を返す
  9. 終わり 関数   

これも内部呼び出しのメソッドで、2 つのパラメータを持ちます。Index は 1 次元配列の添字、Num2 は数値の 2 進形式です。メソッド全体はパラメータを変換し、前のメソッドを呼び出すことです

外部通話には2つの方法があります

  1. 公共 関数SetNum( ByVal行As  整数、 ByVal列As  整数、 ByVal数値​ 整数）として ブール    
  2.      SetNumPri(行 - 1、列 - 1、番号 - 1) を返します
  3. 終わり 関数   
  4.  
  5. 公共 関数SetLine( ByVal Row As  整数、 ByVal  パラメータ配列Num()として 整数）として ブール   
  6.      Num.Length = 0の場合 戻る 真実   
  7.  
  8.     暗くI As  整数   
  9.  
  10.      I = 0の場合、IIf(Num.Length - 1 > 8, 8, Num.Length - 1)になります。 
  11.          Num(I) > 0 の場合、またSetNumPri(Row - 1, I, Num(I) - 1) = False  それから 戻る 間違い   
  12.     次   
  13.  
  14.     戻る 真実   
  15.  
  16. 終わり 関数  

最初の方法は、外部呼び出しに公開される数値を入力する方法です。外部的には、添え字を 1 から始める方が直感的ですが、内部的には 0 から始める方が適切です。

たとえば、(1, 1)に7が入力されると、SetNum(1, 1, 7)が呼び出され、このメソッドはSetNumPri(0, 0, 6)を呼び出します。

このメソッドは通常、Sudoku を初期化するときに呼び出されます。

2 番目の方法も外部に公開されています。一度に 1 行ずつ入力し、空白のセルがある場合は 0 に置き換えます。

たとえば、この記事の冒頭にある数独パズルでは、コードの最初の行はSetLine(1, 0, 6, 0, 5, 9, 3, 0, 0, 0)です。

#p#

いくつかの補助的な方法

  1. プライベート  Sub RestoreNum( ByVal L As List(Of Integer )) 
  2.     暗くI As  整数   
  3.      I = 0から80の場合
  4.         _Num(I) = L.アイテム(I) 
  5.     次   
  6.  
  7.     AppendString( "マトリックスを復元" )
  8. 終わり サブ  

L のデータを Sudoku 配列に復元します。ここで、L は以前にキャッシュされたデータです。 AppendString は、テキスト オブジェクトにデータを記録するメソッドです。

  1. プライベート 関数Get1Count( ByVal値As  整数）として 整数    
  2.     暗いC As  整数= 0 
  3.     する 値 > 0 の場合
  4.         値 = 値And (値 - 1)
  5.         C + = 1 
  6.     ループ   
  7.     リターンC
  8. 終わり 関数  

数字の中の1の数、つまり空白のセルに入力できる数字の数を取得します。

たとえば、(1, 1) = 011000000 2 、Get1Count (011000000 2 ) = 2 は、セル (1, 1) に 2 つの数字を入力できることを示します。

  1. プライベート 関数GetIndexOfNum( ByVal Num As  整数、 ByValインデックス​ 整数）として 整数    
  2.     暗くI As  整数、K As  整数= 0 
  3.      I = 0から8の場合
  4.          (_V(I)かつNum) <> 0の場合   
  5.             1 に
  6.              K = インデックスの場合  I + 1を返す
  7.         終わり もし   
  8.     次   
  9.     戻り値-1
  10. 終わり 関数   

指定された数値NumのIndex番目の位置で利用可能なフィルの数を取得します（バイナリ形式）

上記の例を引き続きとると、(1, 1) = 011000000 2 、

GetIndexOfNum（011000000 2 ，1）=7、つまり最初の利用可能な数字は7である。

GetIndexOfNum（011000000 2 ，2）=8、つまり2番目に利用可能な数字は8である。

GetIndexOfNum（011000000 2 ，3）=-1、3番目の数字が入力されていないことを示す

補助録音機能

これらの関数はアルゴリズムを解くのにはあまり役立ちません。将来の研究の参考のために、解のプロセスをテキストで記録するだけです。

  1. プライベート 関数ReturnNumString( ByVal Num As  整数）として 弦    
  2.     数値<0の場合 戻る  "#" & (-数字) & " "    
  3.     暗くI As  整数、S As  文字列= ""    
  4.      I = 0から8の場合
  5.          (_V(I) And Num) <> 0 の場合、 S &= (I + 1) 
  6.     次   
  7.      S.PadRight(10)を返す
  8. 終わり 関数  

数値のテキスト形式を返します。空白セルの場合は、セルに入力できるすべての数値を返します。入力済みのセルの場合は、#+数値の文字列を返します。返される文字列は整列されます。

  1. プライベート 関数ReturnMatrix()として 弦    
  2.     暗くI As  整数、 JAs  整数、S As  文字列= ""    
  3.      I = 0から8の場合
  4.          J = 0 ～ 8の場合
  5.             S &= ReturnNumString(_Num(I * 9 + J)) 
  6.         次   
  7.         S &= vbNewLine 
  8.     次   
  9.     リターンS
  10. 終わり 関数  

数独パズル全体のステータステキストを返します

  1. プライベート  Sub AppendString( ByValテキストAs  文字列、オプション  ByVal行列の追加 ブール値= True ) 
  2.      _HasString = Falseの場合 それから 出口 サブ   
  3.     _S.AppendLine(テキスト)
  4.     _S.行の追加() 
  5.      AppendMatrix = Trueの場合 それから   
  6.         _S.AppendLine(行列を返す)
  7.         _S.行の追加() 
  8.     終わり もし   
  9. 終わり サブ  

テキストオブジェクトにテキストを追加し、AppendMatrixパラメータに基づいて、数独の状態全体をテキストオブジェクトに追加するかどうかを決定します。

  1. プライベート 関数IndexToXY( ByValインデックスAs  整数）として 弦    
  2.      (Int(Index / 9) + 1) & "-" & (Index Mod 9 + 1) & " Num: " & -_Num(Index)を返します。
  3. 終わり 関数  

テキストオブジェクトで使用される指定されたインデックスの座標と塗りつぶされた番号を返します。

  1. 公共 関数CalculationString()として 弦    
  2.      _S.ToStringを返す
  3. 終わり 関数  

このメソッドは公開されており、将来の研究の参考のために以前に記録された解決プロセスであるテキストオブジェクトを返します。

メインソルバー関数 - アルゴリズムの核

次の3つの関数がアルゴリズムの中核となる。

  1. プライベート 関数FindMinCell()として 整数    
  2.     暗くI As  整数、C As  整数   
  3.     薄暗いtP  整数= -1、tMin As  整数= 20 
  4.  
  5.     私 = 0 
  6.  
  7.     する   
  8.          _Num(I) > 0の場合   
  9.             C = Get1Count(_Num(I)) 
  10.              C = 1の場合   
  11.                  SetNumPri(I, _Num(I)) = Falseの場合 それから 戻る-2 
  12.  
  13.                 文字列の追加( "SetNum " & IndexToXY(I)) 
  14.  
  15.                  I = tPの場合   
  16.                     tP = -1
  17.                     最小値 = 20 
  18.                 終わり もし   
  19.  
  20.                 私 = -1 
  21.             それ以外   
  22.                  C < tMinの場合   
  23.                     tP = 私
  24.                     t最小値 = C 
  25.                 終わり もし   
  26.             終わり もし   
  27.         終わり もし   
  28.         私 += 1 
  29.     ループ  80歳を超えるまで
  30.  
  31.      tPを返す
  32. 終わり 関数  

この関数は、最小の数値を持つセルを取得します（2より大きい数値を持つ空白セルは埋めることができます）

この関数には 3 つの戻り値があります。

戻り値: -1、そのようなセルが見つからない場合、関数は一意の数値セルから数値の入力を開始し、すべての空白セルが埋められるまで順番に数値を入力し続けます。これはソリューションが完了したことを意味します。

戻り値: -2、そのようなセルは見つからない場合、関数は一意の数値セルから数値の入力を開始し、数値を 1 つずつ入力していき、解のないセルが生成されます。これは、前の解決プロセスにエラーがあるか、数独に解決法がないことを意味します。

戻り値: 0-80、そのようなセルが見つかり、現在の数独配列に一意の数字セルがありません (関数は一意の数字セルに数字を直接入力します)

  1. 公共 関数Calculate()として 整数() 
  2.     暗くI As  整数   
  3.     暗いK As  整数   
  4.     暗いQA​  新しいスタック(リスト(整数)) 
  5.      Dim L Asリスト(整数) 
  6.  
  7.     _S =新しいSystem.Text.StringBuilder
  8.     AppendString( "初期行列" ) 
  9.  
  10.     K = 最小セルの検索() 
  11.  
  12.     する  K <> -1の場合
  13.          K = -2の場合   
  14.              Q.Count = 0の場合   
  15.                 AppendString( "エラー!!!!!" , False ) 
  16.                 戻る 何もない   
  17.             終わり もし   
  18.  
  19.  
  20.             L = Q.ポップ
  21.  
  22.             Ｋ＝Ｌ（８２）
  23.             L.削除(82) 
  24.  
  25.             私 = L(81) + 1
  26.             L.削除(81) 
  27.  
  28.             AppendString( "スタックポップ " & Q.Count + 1, False ) 
  29.  
  30.             復元数(L) 
  31.  
  32.             K = FindNextK(Q, L, K, I) 
  33.  
  34.         それ以外   
  35.             L =新しいリスト(整数)
  36.             L.AddRange(_Num) 
  37.  
  38.             K = 次のKを検索(Q, L, K, 1) 
  39.  
  40.         終わり もし   
  41.  
  42.     ループ   
  43.  
  44.     AppendString( "計算完了!!!!" ) 
  45.  
  46.     暗V(80) As  整数   
  47.      I = 0から80の場合
  48.         V(I) = -_Num(I) 
  49.     次   
  50.     リターンV
  51. 終わり 関数  

公開されている主なソリューション関数は、最終結果の整数配列を返します。

まず、スタックオブジェクト Q について説明します。スタック Q は一度に 1 つのオブジェクトしかプッシュできないため、セルの数が一意ではない状況が発生すると、現在のデータをキャッシュする必要があります。キャッシュする必要があるコンテンツには、数独配列、見つかった最小の数字のセルの下付き文字、および最小の数字のセルを埋めるために選択された数字の 3 つの部分があります。したがって、前の 3 つのコンテンツをキャッシュするには、List (Integer) オブジェクトが使用されます。 L(0)-L(80)は数独配列を表し、L(81)は最小の数字が含まれるセルの下付き文字であり、L(82)は最小の数字が含まれるセルを埋めるために選択された数字です。

この関数の主な目的は、K の値を決定することです。前の関数で説明したように、K には主に 3 つの値があります。

K=-1は空白のセルがないことを示し、数独は完全に解かれ、結果が直接返されます。

K=-2 は、解セルがあるかどうかを示し、スタック Q 内のデータを確認します。スタック Q にデータがない場合、数独に解がないことを意味します。スタック Q にデータがある場合は、データを取り出し、数独の状態を以前の状態に戻します。そして、前回キャッシュされた最小の数字を持つセルから次の入力可能な数字を抽出して、試行を続行します。

たとえば、0 と 1 がキャッシュされます。これは、最後の試行が最初のセルの最初の利用可能な番号を使用して行われたことを意味します (下付き文字は 0 から始まります)。解けないセルがあるので、最初の可能な数字が間違っているということになります。そのため、2 番目の可能な数字を試し続けます。呼び出されるメソッドは FindNextK(Q, L, K, I) です。ここで、I は 1 増加されます。

K=0-80、可能な限り最小の数字を持つセルの下付き文字を取得します。まず、セル内の最初の可能な数字を試します。呼び出されたメソッド: FindNextK(Q, L, K, 1)

可能な数字を試す関数は FindNextK で、戻り値も -1、-2、0～80 の 3 種類に分かれています。意味は上記と同じです

  1. プライベート 関数FindNextK( ByVal Q As Stack(Of List(Of Integer )), ByVal L As List(Of Integer ), ByVal K As  整数、 ByValインデックス​ 整数）として 整数    
  2.  
  3.     暗いJ As  整数= GetIndexOfNum(_Num(K), インデックス) 
  4.  
  5.     する  J <> -1の場合
  6.          SetNumPri(K, _V(J - 1)) = Trueの場合 それから   
  7.             AppendString( "スタックプッシュ " & Q.Count + 1, False )
  8.             AppendString( "SetNum MayBe " & IndexToXY(K)) 
  9.  
  10.             L.Add(インデックス)
  11.             L.追加(K)
  12.             Q. 押す（L） 
  13.  
  14.             K = 最小セルの検索() 
  15.  
  16.             出口 する   
  17.         終わり もし   
  18.  
  19.         復元数(L)
  20.         インデックス += 1
  21.         J = GetIndexOfNum(_Num(K), インデックス) 
  22.     ループ   
  23.      J = -1の場合、 K = -2 
  24.     リターンK
  25. 終わり 関数  

可能な数値を試した結果を得るための補助関数

まず、GetIndexOfNum を使用して現在使用可能なフィールドの数を取得します。戻り値が-1の場合は、記入する数字がなく、解けないセルがあることを意味するので、戻り値はそのまま-2になります。

次に、SetNumPri(K, _V(J - 1)) を呼び出して、現在のセルに数字を入力しようとします。True を返すと、数字を入力できることを意味し、現在の状態をスタック Q にキャッシュし、FindMinCell 関数を使用して次の可能な K 値を取得して返します。False を返すと、数字を入力できないことを意味し、データを Sudoku 配列に復元し、次の数字を試し続けます。

これまで、このアルゴリズム クラスのコードは完全に説明されました。

このアルゴリズムでは、最も基本的な解決方法である消去法のみが使用されます。一意の番号を持つセルに遭遇した場合は、その番号を直接入力します。一意の番号を持たないセルに遭遇した場合は、データをキャッシュし、数独が解けるまでそのセルのすべての可能な番号を試します。

スタック Q を使用してデータをキャッシュすると、システム リソースが大幅に占有され、問題を解決できなくなるのではないかと疑問に思う人もいるかもしれません。現状を踏まえて、私はこのアルゴリズムを使って「プログラマーは世間に理解されない真の天才か？ - この数独の解法を見てください」の最も難しい数独を解き、解法をファイルに保存して解析のために開きました。スタック Q のキャッシュは 20 ステップを超えないことが分かりました。20 ステップを例にとると、各ステップは 83*4 バイトなので、合計は 20*83*4=6640 バイト < 7K バイトです。システムの許容範囲をはるかに下回ります。したがって、システムの耐久性について心配する必要はありません。

優れた数独アルゴリズムをお持ちの方がいらっしゃいましたら、ぜひその経験を私と共有してください。

実際に結果を見てみましょう。このアルゴリズムを使用して、この記事の冒頭にある数独を解いてみましょう。コードは次のとおりです。

  1. ディムtS  新しいclsSudoku 
  2.  
  3.  tS.SetLine(1, 0, 6, 0, 5, 9, 3, 0, 0, 0)
  4.  tS.SetLine(2, 9, 0, 1, 0, 0, 0, 5, 0, 0)
  5.  tS.SetLine(3, 0, 3, 0, 4, 0, 0, 0, 9, 0)
  6.  tS.SetLine(4, 1, 0, 8, 0, 2, 0, 0, 0, 4)
  7.  tS.SetLine(5, 4, 0, 0, 3, 0, 9, 0, 0, 1)
  8.  tS.SetLine(6, 2, 0, 0, 0, 1, 0, 6, 0, 9)
  9.  tS.SetLine(7, 0, 8, 0, 0, 0, 6, 0, 2, 0)
  10.  tS.SetLine(8, 0, 0, 4, 0, 0, 0, 8, 0, 7)
  11.  tS.SetLine(9, 0, 0, 0, 7, 8, 5, 0, 1, 0) 
  12.  
  13.  tS.計算() 
  14.  
  15.  My.Computer.FileSystem.WriteAllText( "1.txt" 、 tS.CalculationString、 False )

この数独は比較的シンプルで、最後まで1 つのセルしかありません。

結果は次のとおりです。

計算完了!!!!

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

#p#

以下はアルゴリズムクラスの完全なコードです

  1. 公共 クラスclsSudoku 
  2.     プライベート_Num(80 )  整数   
  3.     プライベート_V(9 )  整数   
  4.     プライベート_SとしてSystem.Text.StringBuilder 
  5.     プライベート_HasStringAs​  ブール   
  6.  
  7.     公共 サブ 新規（オプション  ByVal HasStringとして ブール値= True ) 
  8.         暗くI As  整数   
  9.         _V(0) = 1 
  10.          I = 1から8の場合
  11.             _V(I) = _V(I - 1) * 2 
  12.         次   
  13.         _V(9) = 511 
  14.  
  15.          I = 0から80の場合
  16.             _Num(I) = _V(9) 
  17.         次   
  18.  
  19.         _S =新しいSystem.Text.StringBuilder
  20.         _HasString = 文字列を持つ
  21.     終わり サブ   
  22.  
  23.     プライベート 関数Get1Count( ByVal値As  整数）として 整数   
  24.         暗いC As  整数= 0 
  25.         する 値 > 0 の場合
  26.             値 = 値And (値 - 1)
  27.             C + = 1 
  28.         ループ   
  29.         リターンC 
  30.     終わり 関数   
  31.  
  32.     プライベート 関数RemoveNum( ByVal行As  整数、 ByVal列As  整数、 ByVal Num2 As  整数）として 整数   
  33.         暗黙のインデックス 整数= 行 * 9 + 列
  34.          _Num(Index) > 0の場合、 _Num(Index) = _Num(Index)であり、 Num2 
  35.          _Num(インデックス)を返す
  36.     終わり 関数   
  37.  
  38.     公共 関数SetNum( ByVal行As  整数、 ByValColAs​​  整数、 ByVal数値​ 整数）として ブール   
  39.          SetNumPri(行 - 1、列 - 1、番号 - 1) を返します
  40.     終わり 関数   
  41.  
  42.     公共 関数SetLine( ByVal Row As  整数、 ByVal  パラメータ配列Num()として 整数）として ブール   
  43.          Num.Length = 0の場合 戻る 真実   
  44.  
  45.         暗くI As  整数   
  46.  
  47.          I = 0の場合、IIf(Num.Length - 1 > 8, 8, Num.Length - 1)になります。 
  48.              Num(I) > 0 の場合、またSetNumPri(Row - 1, I, Num(I) - 1) = False  それから 戻る 間違い   
  49.         次   
  50.  
  51.         戻る 真実   
  52.  
  53.     終わり 関数   
  54.  
  55.     プライベート 関数SetNumPri( ByVal行As  整数、 ByValColAs​​  整数、 ByVal数値​ 整数）として ブール   
  56.          (_V(Num)かつ_Num(Row * 9 + Col)) = 0の場合 戻る 間違い   
  57.         _Num(行 * 9 + 列) = -(Num + 1)
  58.         数 = _V(9) - _V(数) 
  59.  
  60.         暗くI As  整数、 JAs  整数   
  61.  
  62.          I = 0から8の場合
  63.              RemoveNum(I, Col, Num) = 0の場合 戻る 間違い   
  64.              RemoveNum(Row, I, Num) = 0の場合 戻る 間違い   
  65.         次   
  66.  
  67.         暗R1 As  整数= Int(行 / 3) * 3 
  68.         暗いC1As​  整数= Int(Col / 3) * 3 
  69.  
  70.          I = R1からR1 + 2まで
  71.              J = C1からC1 + 2まで
  72.                  RemoveNum(I, J, Num) = 0の場合 戻る 間違い   
  73.             次   
  74.         次   
  75.  
  76.         戻る 真実   
  77.     終わり 関数   
  78.  
  79.     プライベート 関数SetNumPri( ByValインデックスAs  整数、 ByVal Num2 As  整数）として ブール   
  80.         暗くした行 整数= Int(インデックス / 9) 
  81.         暗色列As  整数= インデックスMod 9 
  82.         暗くI As  整数   
  83.          I = 0から8の場合
  84.              _V (I) = Num2の場合 出口 のために   
  85.         次   
  86.          SetNumPri(Row, Col, I)を返す
  87.     終わり 関数   
  88.  
  89.     プライベート 関数FindMinCell()として 整数   
  90.         暗くI As  整数、C As  整数   
  91.         暗いtP  整数= -1、tMin As  整数= 20 
  92.  
  93.         私 = 0 
  94.  
  95.         する   
  96.              _Num(I) > 0の場合   
  97.                 C = Get1Count(_Num(I)) 
  98.                  C = 1の場合   
  99.                      SetNumPri(I, _Num(I)) = Falseの場合 それから 戻る-2 
  100.  
  101.                     文字列の追加( "SetNum " & IndexToXY(I)) 
  102.  
  103.                      I = tPの場合   
  104.                         tP = -1
  105.                         最小値 = 20 
  106.                     終わり もし   
  107.  
  108.                     私 = -1 
  109.                 それ以外   
  110.                      C < tMinの場合   
  111.                         tP = 私
  112.                         t最小値 = C 
  113.                     終わり もし   
  114.                 終わり もし   
  115.             終わり もし   
  116.             私 += 1 
  117.         ループ  80歳を超えるまで
  118.  
  119.          tPを返す
  120.     終わり 関数   
  121.  
  122.     公共 関数Calculate()として 整数() 
  123.         暗くI As  整数   
  124.         暗いK As  整数   
  125.         暗いQA​  新しいスタック(リスト(整数)) 
  126.          Dim L Asリスト(整数) 
  127.  
  128.         _S =新しいSystem.Text.StringBuilder
  129.         AppendString( "初期行列" ) 
  130.  
  131.         K = 最小セルの検索() 
  132.  
  133.         する  K <> -1の場合
  134.              K = -2の場合   
  135.                  Q.Count = 0の場合   
  136.                     AppendString( "エラー!!!!!" , False ) 
  137.                     戻る 何もない   
  138.                 終わり もし   
  139.  
  140.  
  141.                 L = Q.ポップ
  142.  
  143.                 Ｋ＝Ｌ（８２）
  144.                 L.削除(82) 
  145.  
  146.                 私 = L(81) + 1
  147.                 L.削除(81) 
  148.  
  149.                 AppendString( "スタックポップ " & Q.Count + 1, False ) 
  150.  
  151.                 復元数(L) 
  152.  
  153.                 K = FindNextK(Q, L, K, I) 
  154.  
  155.             それ以外   
  156.                 L =新しいリスト(整数)
  157.                 L.AddRange(_Num) 
  158.  
  159.                 K = 次のKを検索(Q, L, K, 1) 
  160.  
  161.             終わり もし   
  162.  
  163.         ループ   
  164.  
  165.         AppendString( "計算完了!!!!" ) 
  166.  
  167.         暗V(80) As  整数   
  168.          I = 0から80の場合
  169.             V(I) = -_Num(I) 
  170.         次   
  171.         リターンV 
  172.     終わり 関数   
  173.  
  174.     プライベート  Sub RestoreNum( ByVal L As List(Of Integer )) 
  175.         暗くI As  整数   
  176.          I = 0から80の場合
  177.             _Num(I) = L.アイテム(I) 
  178.         次   
  179.  
  180.         AppendString( "マトリックスを復元" ) 
  181.     終わり サブ   
  182.  
  183.     プライベート 関数GetIndexOfNum( ByVal Num As  整数、 ByValインデックス​ 整数）として 整数   
  184.         暗くI As  整数、K As  整数= 0 
  185.          I = 0から8の場合
  186.              (_V(I)かつNum) <> 0の場合   
  187.                 1 に
  188.                  K = インデックスの場合  I + 1を返す
  189.             終わり もし   
  190.         次   
  191.         戻り値-1 
  192.     終わり 関数   
  193.  
  194.     プライベート 関数FindNextK( ByVal Q As Stack(Of List(Of Integer )), ByVal L As List(Of Integer ), ByVal K As  整数、 ByValインデックス​ 整数）として 整数   
  195.  
  196.         暗いJ As  整数= GetIndexOfNum(_Num(K), インデックス) 
  197.  
  198.         する  J <> -1の場合
  199.              SetNumPri(K, _V(J - 1)) = Trueの場合 それから   
  200.                 AppendString( "スタックプッシュ " & Q.Count + 1, False )
  201.                 AppendString( "SetNum MayBe " & IndexToXY(K)) 
  202.  
  203.                 L.Add(インデックス)
  204.                 L.追加(K)
  205.                 Q. 押す（L） 
  206.  
  207.                 K = 最小セルの検索() 
  208.  
  209.                 出口 する   
  210.             終わり もし   
  211.  
  212.             復元数(L)
  213.             インデックス += 1
  214.             J = GetIndexOfNum(_Num(K), インデックス) 
  215.         ループ   
  216.          J = -1の場合、 K = -2 
  217.         リターンK 
  218.     終わり 関数   
  219.  
  220.     プライベート 関数ReturnNumString( ByVal Num As  整数）として 弦   
  221.          Num < 0の場合 戻る  "#" & (-数字) & " "    
  222.         暗くI As  整数、S As  文字列= ""    
  223.          I = 0から8の場合
  224.              (_V(I) And Num) <> 0 の場合、 S &= (I + 1) 
  225.         次   
  226.          S.PadRight(10)を返す
  227.     終わり 関数   
  228.  
  229.     プライベート 関数ReturnMatrix()として 弦   
  230.         暗くI As  整数、 JAs  整数、S As  文字列= ""    
  231.          I = 0から8の場合
  232.              J = 0 ～ 8の場合
  233.                 S &= ReturnNumString(_Num(I * 9 + J)) 
  234.             次   
  235.             S &= vbNewLine 
  236.         次   
  237.         リターンS 
  238.     終わり 関数   
  239.  
  240.     プライベート  Sub AppendString( ByValテキストAs  文字列、オプション  ByVal行列の追加 ブール値= True ) 
  241.          _HasString = Falseの場合 それから 出口 サブ   
  242.         _S.AppendLine(テキスト)
  243.         _S.行の追加() 
  244.          AppendMatrix = Trueの場合 それから   
  245.             _S.AppendLine(行列を返す)
  246.             _S.行の追加() 
  247.         終わり もし   
  248.     終わり サブ   
  249.  
  250.     プライベート 関数IndexToXY( ByValインデックスAs  整数）として 弦   
  251.          (Int(Index / 9) + 1) & "-" & (Index Mod 9 + 1) & " Num: " & -_Num(Index)を返します
  252.     終わり 関数   
  253.  
  254.     公共 関数CalculationString()として 弦   
  255.          _S.ToStringを返す
  256.     終わり 関数   
  257. 終わり クラス  

オリジナルリンク: http://www.cnblogs.com/grenet/p/3138654.html

<<:  OSPFはSPFアルゴリズムを使用してルートを伝播します

>>:  プログラミングアルゴリズムと人生の選択

推薦する

...

人工知能と機械学習でよく使われるアルゴリズムの概要と、よく使われる各アルゴリズムの精度の比較

[[319322]]この記事では、一般的に使用されている機械学習アルゴリズムの概要と、一般的に使用さ...

未来を垣間見るのに役立つ9つの主要な人工知能開発トレンド

人工知能はテクノロジー界でホットな話題となっている。それは人々の生活を変えただけでなく、考えられるあ...

2024 年にビジネスを一変させる可能性のあるテクノロジーはどれでしょうか?

2023 年は、世界中の政府、公共部門、企業、さらには一般大衆の生活を大きく変えるテクノロジーの急...

「最強の脳」に2万5000ドルの賞金 - TalkingDataグローバルアルゴリズムコンペティションがデータの未来を応援

2016年7月12日から9月5日まで、北京TalkingData Technology Co., ...

...

2020年版ネイチャーインデックス年次リストが発表：中国の研究機関がリストを独占、中国科学院は8年連続で1位

科学研究機関の世界総合ランキングでは、中国科学院、中国科学技術大学、北京大学がトップ10にランクイン...

データガバナンスはAIの将来にとって重要

人工知能は、消費者と組織にとって大きな革命的な進歩です。その結果、さらに重要かつ緊急性の高い発見がい...

人工知能技術が教育業界に与える主な影響は何ですか?

今日、人工知能技術は社会のあらゆる分野にますます大きな影響を及ぼしており、教育も例外ではありません。...

...

調達における AI の夜明け: 効率性と洞察力の新時代

McKinsey & Company の画期的なレポートでは、AI を含むデジタル調達ソリュ...

収集する価値のあるAIツールメモ8つ

緊急時のメモとしても使える、コレクションする価値のあるAI写真を8枚シェアします。最初の RTF フ...

テクノロジー大手はAIの研究開発に数十億ドルを費やしているが、かつて人間に勝ったAIが売却されようとしているという自慢が疑問視されている

グーグルやフェイスブックなどのテクノロジー大手は長年にわたり、人工知能（AI）に数十億ドルを投資し、...

OpenAIがChatGPT Enterprise Editionをリリース: GPT-4の無制限使用、より高いセキュリティとプライバシー保護

8月29日、OpenAIは、企業ユーザーのニーズを満たし、より高いセキュリティとプライバシー保護を提...

3分で顔認識を始めましょう

顔認識は、AI 研究が世界にもたらした数多くの驚異のうちの 1 つです。これは多くの技術者にとって興...