数独問題を解くには人工知能や量子コンピューティングを使うべきでしょうか?

楽しいボードゲームとして誕生してから 100 年経った今、数独はどのようにして計算研究の焦点となったのでしょうか。人工知能や量子コンピューターを使用して、スマートな数独ソルバーをゼロから作成する方法を学びます。

詳しく調べる前に、まず歴史を理解しましょう

マルク・ブロックは「歴史は学問の母と呼ばれている」と言いました。それでは、有名な数独ゲームがどのように生まれたのかについてお話ししましょう。この物語は19世紀後半に遡り、フランスで始まりました。フランスの日刊紙「ル・シエクル」は、論理ではなく算術を必要とし、1～9ではなく2桁の数字を使用する9x9の推測ゲームを掲載した。ゲームの性質は数独に似ており、行、列、対角線の数字を足すと、同じ数字が得られます。引退した建築家でパズル愛好家のハワード・ガーンズは、現代の数独ゲームを考案したとされており、このゲームは 1979 年に「Sudoku」という名前でデル マガジンに初めて掲載されました。このパズルは、1986 年に日本のパズル会社ニコリによって「数独」という名前で初めて出版されました。

数独パズルを解く際の問題の枠組み

数独は、変数セット、ドメイン、制約セットがすべて有限であるため、制約充足問題 (CSP) の実際の例です。各行、各列、および各 3x3 サブテーブルに 1 つの数字のみが含まれるように、9x9 テーブルに 1 ～ 9 の数字を入力する必要があります。数独の別のバリエーションとして、対角数独も存在します。これは、表の各対角線に追加の制約セットを課し、各数字がその特徴を 1 回だけ持たなければなりません。 制約充足領域についてはわかっていますが、最適なソリューションはすべての制約を満たす必要があります。より具体的には、ゲームのルールに従う必要があります。 最適な解決策はセット内のすべての制約を満たすため、パズルは解けます。

計算的には、数独を解くための制約は、いくつかの非常に特殊なブルート フォース アルゴリズムを使用して解決できるため、非決定性多項式時間 (NP) で解決できます。また、問題への入力が多項式長の解の集合に関連付けられている場合、解集合の妥当性も多項式時間でテストできます。 完全に解かれた数独は、ラテン方陣（オイラーによって説明された、n 個の異なる記号で満たされた nxn 配列）の例です。 数独問題はグラフの色付け問題として考えることができます。グラフの色付けには 9 色のみを使用する必要があり、露出した文字は部分的な色として考えることができます。

制約を満たすために設定された人工知能アルゴリズムを使用する

計算科学の基本原理は、特定の制約を満たすために論理に頼る能力です。 数独を解くときは、基本的なルールに加えて、特定の勝ちパターンを探すようにソルバーをトレーニングする必要があります。 つまり、問題は、システムがルールに盲目的に従うだけでなく、短期的および長期的な影響を考慮しながらいくつかの決定を下していることです。 これらのパターンはヒューリスティックと呼ばれます。 ゲームの知識やスキルを偶然発見した熟練プレイヤーと同様に、基本的なルールを知っているだけではゲームのエキスパートにはなりません。 したがって、アルゴリズムを開発して問題を解決するときは、有用なヒューリスティックを念頭に置く必要があり、プログラムにそれらを組み込んで、よりスマートで、勝つために役立つものにする必要があります。

数独ソルバーでは、81 個の数字のシーケンスを ' で区切られた文字列として入力します。 ' (ピリオド) は未解決の番号を示します。 この問題を解決するには、「.」をそのセルに収まるすべての可能な数字に置き換えます。

数独の制限により、行、列、またはセルの近くの 3x3 サブスクエアで同じ数字を複数回使用することはできません。 対角数独の場合も、同じ制約を考慮する必要があります。 まず、ピリオドを 1 から 9 までのすべての数字に置き換えます。次のgrid_values関数を使用して、これをプログラムで実行します。

 #計算のために行を取ります 英数字と列として​ 数値。
行= 'ABCDEFGHI'   
列 = '123456789'  
ボックス = [r + c rの場合 行  for c in columns] #グリッド内の可能なすべてのセルの組み合わせ。
 def grid_values(グリッド): "" "
  未解決の数独のシーケンスを解く そして、最初に未解決のボックスを 全て 
  そのセルに入る可能性のある値。最後に、
価値観 で セルとともにすべてのセル位置。
 「」 「 」
値= [] every_digits = '123456789'  
グリッド内のnの場合:
    if c == '.' : # 最初にすべての未解決の値をすべての可能な値に置き換えます。
 values ​​.append(every_digits) else : # すでに解決されている場合は変更されません。
値​​.append(c) assert len(値​​) == 81
 return dict(zip(boxes, values ​​)) #数独グリッドを返す すべての可能なセル値。

まず、未解決のセルすべてに可能な値を割り当てます。

ここで、未解決のセルを 1 から 9 までのすべての可能な数字に置き換えました。数独の基本ルールから、その行、列、3x3 サブフィールドですでに使用されている数字は 2 回使用できないことがわかります。 したがって、最初にすべての可能な数字で埋めた未解決のグリッドでそれらに遭遇した場合は、それらを排除しましょう。 それでは、Python の消去メソッドを使用して、未解決のセルから無関係な数字を消去する方法を見てみましょう。

 columns_reversed = columns[::-1] #対角単位を計算するために列を反転します。
 def make_combinations(m, n): "" "
  一般的に反復可能な入力を受け取り、すべての可能な組み合わせを作成します それらの。
  引数:
   a : 反復可能な文字列
   b: 反復可能な文字列
戻り値:リスト すべての可能な組み合わせ。
 「」 「 」
 [x + y ( xはm 、 yはn )を返す]
 row_units = [make_combinations(r, columns) rの場合 行]
 column_units = [make_combinations(行数, c)列数がcの場合]
 sub_square_units = [make_combinations(m, n)の場合、 mは( 'ABC' 、 'DEF' 、 'GHI' )
 nが( '123' 、 '456' 、 '789' )の場合]
 diagonal_1_units = [[行数[i]+列数 [i] 、 iが範囲 (len(行数))内にある場合]]
 diagonal_2_units = [[ rows [i]+columns_reversed[i] for i in range(len( rows ))]]
 diagonal_units = diagonal_1_units + diagonal_2_unitsall_units = row_units + column_units + square_units + diagonal_unitsunits = dict((b, [u for u in all_units if b in u]) for b in boxs)
 peers = dict((b, set ( sum (units[b], [])) - {b})、 bがボックス内にある場合)
 def 排除(値): "" "
  数字がすでに1回出現している場合は、未解決のセルから重複した数字を削除します。
現在のセルのピア内。
  ここで行うことは、その冗長な数字が一度だけ現れた場合、未解決の値セルからその数字を消去することです。
 「」 「 」
  解決済みセル = [ボックス内のボックス  values ​​.keys() if len( values ​​[box]) == 1] # セルに数字が1つしかない場合は解決されます
解決済みセル内のボックスの場合:
    value_at_cell = values ​​[box] #そのセルの現在の値を取得します。
 peers[box]内のpeer : #チェック 値が再度表示された場合は、セルのピアに対して実行されます。
値[ピア] =値[ピア]。replace ( value_at_cell , '' )
戻る  values ​​#変更された値の辞書を返します。

したがって、これらの制約を満たしながらも、1 つの数字しか配置できないセルに遭遇することがありますが、その特定のセルにはその数字以外の数字を配置することはもはや不可能です。 まずこれらを記入する必要があります。 適切な解決策があります。 これを「唯一の選択肢」と呼び、数独グリッドセルを解くための最も単純なヒューリスティックです。

 def only_choice(値):
 「」 「 」
  もし 注文 数独パズルの制約を満たすには 実行可能な選択肢は1つだけ 
  そのオプションをセルに入力します のみ それによってセルのソリューションが得られます。 
   
 「」 「 」
 for unit in all_units: #セルの周辺全体を検索します。
数字の​  '123456789' :
      to_be_filled = [セルのセル、ユニット内のユニットの場合 値[単位]]
      if len(to_be_filled) == 1: #ユニット内に1つのセルのみが存在する場合、  解決されていない
values ​​[to_be_filled[0]] = digit #セルに適切な答えを入力します。
戻る 価値観 

これまでの制約充足のプロセスでは、ユニット (行、列、3x3 のサブ正方形など) 内に未解決のセルが 2 つ存在し、残りの特定の数値を 2 つしか割り当てられない状況が発生する可能性があります。 したがって、これら 2 つの数字は、同じセル内の他のセルの可能な数字から実質的に削除されます。 このヒューリスティックは「裸の双子」と呼ばれます。 アルゴリズムの実装では、具体的にはグリッド値のディープ コピーを作成し、裸の双子の実現可能性、つまり 2 つの特定の値のみを受け入れることができる 2 つの未解決セルがあるかどうかをチェックし、ある場合は、先に進んで同じセル内の他のセルからその 2 つの値を削除します。 これを、以下に示す nude_twins 関数を使用してプログラムで実装します。

 def naked_twins(値):
 「」 「 」
    同じユニットに未解決のセルが2つある場合は、  のみ  
    特定の2桁の数字があれば、その2桁の数字は安全に削除できます 同じユニット内の他のすべてのセル。
 「」 「 」
    twins_possible = [ユニットのユニット  values ​​.keys() if len( values ​​[unit]) == 2]
    twins = [[unit1, unit2] for unit1 in twins_possible for unit2 in peers[unit1]
                     if set ( values ​​[unit1]) == ( set ( values ​​[unit2]))] #確認済み 裸の双子
双子の場合:
        ユニット1 = ツイン[0]
        ユニット2 = ツイン[2]
        peers1 =設定(peers[unit1])
        peers2 =設定(peers[unit2])
        common_peers = peers1 & peers2 # 2つの裸の双子要素のピア間の交差を見つける
common_peersのpeerの場合:
            len(値[ピア]) > 1の場合:
価値のために 値[単位1]:
 values ​​[peer] = values ​​[peer] .replace (val, '' )) #値を消去します。
戻る 価値観 

ここで、これら 3 つの制約充足アルゴリズムを繰り返し適用し、パズルが行き詰まってそれ以上減らすことができないかどうかを確認することで、パズルを可能な限り減らそうとします。 これをプログラム的に行うには、reduce_puzzle 関数を使用します。 私たちが行っていることは、for ループで最初の 3 つの関数を呼び出し、グリッド値の入力シーケンスと出力シーケンス内の解決されたセルの数が同じである場合に関数を終了し、制約充足アルゴリズムだけではそれ以上削減できないことを意味します。

 def Reduce_Puzzle(値):
 「」 「 」
    4つの制約充足アルゴリズムを適用して これ以上縮小できません。
    反復間の解決されたセルの数を確認します。
 「」 「 」
    解決された値 = [単位の単位  values ​​.keys() if len( values ​​[unit]) == 1] # 解決されたセルを考慮する
    スタック = False #終了を決定するブールフラグ ループの
    スタックしていない間:
        prev_solved_values ​​= len([unit for unit in   values ​​.keys() if len( values ​​[unit]) == 1]) #チェックポイント1
 values ​​= Elimination( values ​​) # Elimination CSP を適用する
values ​​= only_choice( values ​​) # Only Choice CSPを適用する
values ​​= naked_twins( values ​​) # Naked Twins CSP を適用する
        after_solved_values ​​= len([unit for unit in   values ​​.keys() if len( values ​​[unit]) == 1])
        スタック = after_solved_values ​​== prev_solved_values ​​#抜け出す ループの最後の反復では、解決されたセルの数は前回の反復と同じままです。 
         
        if len([unitのunit in   values ​​.keys() if len( values ​​[unit]) == 0]):
戻る  False #数独グリッドの内部表現に問題がある場合は戻ります 間違い。
戻る  values ​​#縮小されたグリッド値を返します。

制約充足問題によって数独グリッドがまだ解決されていない場合は、一部のセルに特定の可能な値が割り当てられている部分的な解決が出力されます。 この場合、検索ツリーを使用して、それらの位置にある最適な数字のセットを検索します。 深さ優先探索 (DFS) アルゴリズムを使用して検索ツリーを走査します。 つまり、基本的には、DFS を使用して、同じグリッドを持つ複数のインスタンスを作成し、未解決のセルごとに異なる可能な割り当てを試しました。 検索結果に基づいてグリッドを縮小するように CSP アルゴリズムに再帰的に要求します。 プログラム的には次のように実装します。

 def search(値):
 「」 「 」
    再帰深さ優先探索：数独のグリッドが それ以上減らすことはできない 制約の充足
    いくつかの細胞は残る さまざまなオプションと  DFSで最適なものを探す
価値観 まだ解決されていない細胞のために。
 「」 「 」
 values ​​= Reduce_puzzle( values ​​) # 削減関数を呼び出します 反復全体の検索結果に基づいてパズルをさらに縮小します。
    値の場合 は 間違い：
戻る 間違い 
    すべてのボックス内のbについて、len( values [b]) == 1の場合:
        print( "数独問題が解けました!" )
戻る 価値観 
    m, n = min ((len( values ​​[b]), b)ボックス内のbの場合、len( values ​​[b]) > 1)
価値のために 値[n]:
        new_sudoku =値.copy()
        new_sudoku[n] = 値
        試行 = search(new_sudoku)
        試みた場合:
返却を試みた

入力文字列シーケンスを 2 次元の 9x9 数独グリッドとして表示するには、display sudoku 関数を使用します。

 def display(値):
 「」 「 」
    値を表示する  2D グリッドとして。
    入力:辞書形式の数独
「」 「 」
    幅 = 1 +最大(len(値[b])、ボックス内のbの場合)
    行 = '+' . join ([ '-' * (幅 * 3)] * 3)
 rの場合 行数:
        print( '' . join ( values ​​[r + c].center(width)+( '|' if c in   '36'  それ以外  '' )
 c in cols))の場合
        rが  'CF' :
            print(行)戻り 

数独シーケンスを解くには、上記の関数を次のように呼び出します。

 __name__ == "__main__"の場合:
    diag_sudoku_grid = '2.............62....1....7...6..8...3...9...7...6..4...4....8....52.............3'  
値= grid_values(diag_sudoku_grid)
値= Reduce_puzzle(値）
値= 検索(値)
    表示(値)

出力は以下のとおりです。ここでは、1 セットのアルゴリズムによって答えが正常に計算されています。

制約充足問題としての数独を解く量子的アプローチ

ここでは、量子シミュレーテッドアニーリングを使用して簡単な数独グリッドを解いてみます。 まず、シミュレーテッド アニーリングとは何でしょうか? このような最適化問題の場合、その考え方は、いくつかの次善のヒューリスティックを使用し、最適なヒューリスティックのセットを取得して最適なソリューションを得るというものです。 ここでは、DWave AQC モデル (糖尿病量子コンピューティング) を使用して、前述の制約を満たす最適なソリューションをサンプリングします。 ...

DWave Kerberos ハイブリッド サンプラーの使用:

この例では、DWave に付属するハイブリッド ソルバーを使用しています。 これは、並列検索を実行して最適なヒューリスティックを見つけることによって行われます。 これは量子コンピューティング機能と古典コンピューティング機能の両方を使用するハイブリッド ソルバーです。 また、処理時に非同期ワークフローを使用する分解サンプラーでもあります。 これは、DWave Systems の Ocean SDK パッケージに含まれています。 ローカル開発を開始するには、システムに Python 3.5 以降がインストールされていることを確認してから、次のコマンドを発行します。

 python -m pip インストール--upgrade pip  
 pip で dwave-ocean-sdk をインストールします

バイナリ二次モデル（BQM）を使用した計算

量子コンピュータに直接入力できる制約を構築することはできません。入力するための中間表現が必要です。 そのため、私たちは BQM を使用します。幸いなことに、DWave Ocean SDK には、制約充足問題を BQM に定式化するために使用できる「Combination」と呼ばれるツールがすでに用意されています。 まず、名前が示すように、バイナリ二次モデル自体は、二次式でバイナリで表現される方程式のシステムです。 量子コンピュータは計算の複雑さが増すため、これらの計算を使用することで開発プロセスを大幅に高速化できます。 そこで、ゲームでは、入力変数と内部変数の k 通りの組み合わせのそれぞれに対して最小となるバイナリ二次モデルを返す dimod の組み合わせツールを使用することにしました。

まず、dwave-ocean-sdk から必要なパッケージをインポートし、実際に Sudoku Grid を読み込む前にいくつかの健全性チェックを実行します。

 dimod をインポートする
インポート数学
インポートシステム
dimod.generators.constraints をインポートし、combinations をインポートします。
 hybrid.referenceからKerberosSampler をインポートします
def prettify(行, 列, 桁):戻り値  "{行}、{列}_{数字}" .format(行、列、数字)
 def read_matrix(ファイル名):   open (filename, 'r' )をf:として開きます。
        all_lines = f.read () 行 = [] all_lines内の行:
        new_line = line.rstrip() の場合、new_line:
            new_line = list(map( int , new_line.split( ' ' )))
            行を追加します(new_line)
戻り行
定義sanity_check(行列): n = len(行列)
    m = int (math.sqrt(n))
    unique_digits = set (範囲(1, 1+n))
行列の行の場合:
        設定(行) != unique_digits の場合:
            print( "行にエラーがあります" , 行)
戻る 間違い 
 jが範囲(n)内にある場合:
        col = [matrix[i][j] iがrange(n)内にある場合]
        (col) != unique_digitsが設定されている場合:
            print( "列にエラーがあります" , col)
    subsquare_idx = [(i, j) iが範囲内(m) jが範囲内(m)]
 r_scalarがrange(m)の場合:
 c_scalarがrange(m)の場合:
            サブスクエア = [matrix[i + r_scalar * m ][j + c_scalar * m] ( i、jはサブスクエアidx内)
            (subsquare) != unique_digitsの場合:
                print( 'サブスクエアにエラーがあります' , サブスクエア)
戻る 真実 
戻る 真実 

ここで、組み合わせツールを使用して、数独グリッドの行、列、サブスクエア インデックスの利用可能なすべての変数の組み合わせを使用して、バイナリ二次モデルを作成します。

 main() を定義します:
    len(sys.argv) > 1の場合:
        ファイル名 = sys.argv[1]
            行列 = read_matrix(ファイル名) n = len(行列)
    m = int (math.sqrt(n))
    数字 = 範囲(1, n+1)
    bqm = dimod.BinaryQuadraticModel({}, {}, 0.0, dimod.SPIN)
範囲(n)内の行の場合:
範囲(n)内の列の場合:
            node_digits = [prettify(row, col, digit) for digits in digits]
            one_digit_bqm = 組み合わせ(ノードの桁数、1)
            範囲(n)の行に対してbqm.update (one_digit_bqm) :
数字の中の数字:
            row_nodes = [prettify(row, col, digit) for col in range(n)]
            row_bqm = 組み合わせ(row_nodes, 1)
            bqm.update (row_bqm)範囲(n)内の列について:
数字の中の数字:
            col_nodes = [prettify(row, col, digit) for row in range(n)]
            col_bqm = 組み合わせ(col_nodes, 1)
            bqm.update (col_bqm) __name__ == "__main__"の場合:
    主要（）

それでおしまい。 私たちは、古典的なコンピューティングを使用したソリューションと、対角の数独グリッドも解くことができる非常に強力な人工知能ヒューリスティックを使用したソリューションの 2 つのインテリジェント ソリューションを実装することに成功しました。 2 番目のアプローチでは、非同期ハイブリッド ヒューリスティック サンプラーを使用します。このサンプラーは、断熱量子計算モデルのシミュレーテッド アニーリングも使用して、制約充足問題をバイナリ二次モデルに変換し、サンプリングして、最適なサンプリング ソリューションを生成します。