多数独AIアプローチ

Question

私は複数のボードがそうのように重なって多数独、と呼ばれる数独の変形のためのソルバー概念化しています：私は正しくゲームを理解していれば

を任意の2つ以上のグリッド間の重なりがそれぞれの解の一部になるように各グリッドを解く必要があります。

私はこれについてどのように考えなければならないのか分かりません。誰もヒント/概念的手がかりを得た？また、人工知能の話題が浮かんできたら、それも聞きたいです。

Answer 1

制約プログラミング（CP）

数独は、典型的な制約プログラミング問題です。あなたは（ここでは数字9から0）ドメインと制約のセットと変数（グリッド内のフィールド）の各セットこれらの変数を超える（数は一度だけ発生しているという事実があります行、列、ブロックなど）。

制約プログラミングの問題を解決するための汎用的な方法は、アーク一貫性（AC）です：あなたは制約を伝播します。最後に伝播がドメインを小さくすることができなくなった場合は、の選択をにする必要があります。この変数は（部分的に）埋め込まれた変数によって決まります。

変数の値を選択します。良い戦略は、可能な値が少量残っている変数を選択することです。次に、あなたはもう一度伝播し、おそらく別の選択肢を作るなどです。

プログラムが選択肢が間違っていることがわかる可能性があります.1つ以上の変数のドメインを空にします。その場合、バックトラック：以前に行った選択（およびその選択の後に行われた伝播）を取り消し、別の値を選択します。

この回答は明らかにトピックの徹底的な概要を提供することを目的としていませんが、Wikipedia pageはより詳細な情報を提供します。

は、1つの単純変数、ドメインと制約を定義することができるなど日食（ないIDE）、MiniZinc、同じようソルバーをプログラミング制約があります。 EclipseのウェブサイトにECLIPSE

の問題を解決する

、あなたはa model for sudokuを見つけることができます。 ECLiPSeに関するいくつかのドキュメントを読むと、このファイルをmulti-sudoku用のモデルにすることができます。私は彼にクレジットので、ヨアヒムSchimpfから数独のモデルを「借り」

% credits to Joachim Schimpf for his model of sudoku 
% http://eclipseclp.org/examples/sudoku.ecl.txt 
:- lib(ic). 
:- import alldifferent/1 from ic_global. 

solve(ProblemName) :- 
    problem(ProblemName,BA,BB), 
    multi_sudoku(3,BA,BB), 
    print_board(BA), 
    print_board(BB). 

multi_sudoku(N,BA,BB) :- 
    sudoku(N,BA,VA), 
    sudoku(N,BB,VB), 
    N2 is N*N, 
    Inc is N2-N, 
    (multifor([I,J],1,N,1),param(BA,BB,Inc) do 
     BA[I+Inc,J+Inc] #= BB[I,J] 
    ), 
    append(VA,VB,Vars), 
    labeling(Vars). 

sudoku(N,Board,Vars) :- 
    N2 is N*N, 
    dim(Board,[N2,N2]), 
    Board[1..N2,1..N2] :: 1..N2, 
    (for(I,1,N2), param(Board,N2) do 
     Row is Board[I,1..N2], 
     alldifferent(Row), 
     Col is Board[1..N2,I], 
     alldifferent(Col) 
    ), 
    (multifor([I,J],1,N2,N), param(Board,N) do 
     (multifor([K,L],0,N-1), param(Board,I,J), foreach(X,SubSquare) do 
     X is Board[I+K,J+L] 
     ), 
     alldifferent(SubSquare) 
    ), 
    term_variables(Board, Vars). 


print_board(Board) :- 
    dim(Board, [N,N]), 
    (for(I,1,N), param(Board,N) do 
     (for(J,1,N), param(Board,I) do 
      X is Board[I,J], 
     (var(X) -> write(" _") ; printf(" %2d", [X])) 
     ), nl 
    ), nl. 


%---------------------------------------------------------------------- 
% Sample data 
%---------------------------------------------------------------------- 

problem(1, [](
    [](_, _, _, _, 6, _, _, _, _), 
    [](_, _, _, 4, _, 9, _, _, _), 
    [](_, _, 9, 7, _, 5, 1, _, _), 
    [](_, 5, 2, _, 7, _, 8, 9, _), 
    [](9, _, _, 5, _, 2, _, _, 4), 
    [](_, 8, 3, _, 4, _, 7, 2, _), 
    [](_, _, _, 2, _, 8, _, _, _), 
    [](_, _, _, 6, _, 4, _, _, _), 
    [](_, _, _, _, 5, _, _, _, _) 
      ), 
      [](
    [](_, _, _, _, 3, _, _, _, _), 
    [](_, _, _, 8, _, 7, _, _, _), 
    [](_, _, _, 1, _, 6, 3, _, _), 
    [](_, 9, 8, _, _, _, 1, 2, _), 
    [](2, _, _, _, _, _, _, _, 3), 
    [](_, 4, 3, _, _, _, 6, 5, _), 
    [](_, _, 7, 3, _, 5, 9, _, _), 
    [](_, _, _, 4, _, 2, _, _, _), 
    [](_, _, _, _, 6, _, _, _, _) 
      ) 
    ). 

：私は、次の迅速かつ汚い溶液を得たいくつかの小さな変更を加えました。さらに、この回答は別のツールでECLiPSeを使用するためのアドバイスではありません。私は、拘束プログラミングについては、Prologツールチェーンをよく知っています。しかし、あなたがC++にもっと興味を持っているなら、Gecodeは、ほぼ同じ（あるいはそれ以上の）パフォーマンスでトリックを行います。出力を生成

：

ECLiPSe Constraint Logic Programming System [kernel] 
Kernel and basic libraries copyright Cisco Systems, Inc. 
and subject to the Cisco-style Mozilla Public Licence 1.1 
(see legal/cmpl.txt or http://eclipseclp.org/licence) 
Source available at www.sourceforge.org/projects/eclipse-clp 
GMP library copyright Free Software Foundation, see legal/lgpl.txt 
For other libraries see their individual copyright notices 
Version 6.1 #199 (x86_64_linux), Sun Mar 22 09:34 2015 
[eclipse 1]: solve(1). 
lists.eco loaded in 0.00 seconds 
WARNING: module 'ic_global' does not exist, loading library... 
queues.eco loaded in 0.00 seconds 
ordset.eco loaded in 0.01 seconds 
heap_array.eco loaded in 0.00 seconds 
graph_algorithms.eco loaded in 0.03 seconds 
max_flow.eco loaded in 0.00 seconds 
flow_constraints_support.eco loaded in 0.00 seconds 
ic_sequence.eco loaded in 0.01 seconds 
ic_global.eco loaded in 0.07 seconds 
    2 1 4 8 6 3 9 5 7 
    8 7 5 4 1 9 2 6 3 
    6 3 9 7 2 5 1 4 8 
    4 5 2 3 7 1 8 9 6 
    9 6 7 5 8 2 3 1 4 
    1 8 3 9 4 6 7 2 5 
    5 4 1 2 3 8 6 7 9 
    7 2 8 6 9 4 5 3 1 
    3 9 6 1 5 7 4 8 2 

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

は約0.11秒私のマシンを取りました。さらに、合計60の有効な解決策があります。

最後の2つの「行列」は、2つの数独の解を示しています。あなたが見ることができるように（私は完全にチェックしていない）、彼らはブロック（同じ出力）を共有し、すべてのスドクの制約が有効です。私はPythonで制約プログラミングライブラリについて知らない

+-----+-----+-----+ 
|2 1 4|8 6 3|9 5 7| 
|8 7 5|4 1 9|2 6 3| 
|6 3 9|7 2 5|1 4 8| 
+-----+-----+-----+ 
|4 5 2|3 7 1|8 9 6| 
|9 6 7|5 8 2|3 1 4| 
|1 8 3|9 4 6|7 2 5| 
+-----+-----+-----+-----+-----+ 
|5 4 1|2 3 8|6 7 9|5 3 4|2 8 1| 
|7 2 8|6 9 4|5 3 1|8 2 7|4 6 9| 
|3 9 6|1 5 7|4 8 2|1 9 6|3 7 5| 
+-----+-----+-----+-----+-----+ 
      |7 9 8|6 5 3|1 2 4| 
      |2 6 5|7 4 1|8 9 3| 
      |1 4 3|2 8 9|6 5 7| 
      +-----+-----+-----+ 
      |8 2 7|3 1 5|9 4 6| 
      |9 1 6|4 7 2|5 3 8| 
      |3 5 4|9 6 8|7 1 2| 
      +-----+-----+-----+ 

、また私は、Pythonへのポート日食を知っていますか：ソリューションのより便利な表現を以下に示します。しかし、私の経験では、現代のプログラミング言語にはすべてこのようなツールがあります。

Gecode ECLIPSE、のような制約プログラミングツールを使用することの利点、...は、それが解決されるか「あなたが着る何かであるあなただけの問題を指定に持っている最初のすべてのです心配する必要はありません。さらに、このようなライブラリは、制約プログラミングに関する30年の研究を実装しています。制約条件や構造を大部分の人々が想像することのできない方法で活用し、バグを含む可能性が低い（カスタムメイドのアルゴリズムよりも）さらに、新しい戦略、アルゴリズム、...が見つかった場合、ECLiPSeの更新により、モデルの処理が高速になります。

欠点は、いくつかのハードの問題は依然として制約プログラミングを使用して解決することができないということです：探索空間は、単に大きすぎる、制約はドメインが小さなセットに複雑で減少していないこと、そして足りないということです有効な解決策を見つけるために十分な処理能力をにしてください。もう一つの欠点は、問題を指定することは必ずしも容易ではないということです。プログラマは良い制約を設計することを目指していますが、使い易い制約が定義されていない複雑な問題が常に存在します。

その他の技術

明らかに、問題を解決するための他のAI技術があります。ハード検索と最適化の問題に取り組むためによく使われる手法は、進化的計算です：いくつかの値が間違っていることを許すスドクを入力して開始し、その後、それぞれの時間ステップで1つ以上のフィールドを修正しようとします。最終的に有効な解決策を見つけるために新しいエラーが導入されることがあります。

Answer 2

異なるアプローチは、遺伝的アルゴリズムを使用することです。生物学的進化に基づいています。遺伝的アルゴリズムは進化的アルゴリズムの一部であり、したがって、類推「フィットネス機能」を共有する。有効な解決策は、組換え、選択および突然変異によって見出される。

基本的な概念は、ランダムに「染色体」からなる複数の解「個体」を初期化することです（解は間違っている可能性があります）。現在の「世代」内のすべての個人の質を評価する「フィットネス機能」を定義する。それらを「子供」のソリューションに再結合させ、新しい世代の一部の個体を低確率で突然変異させることにより、より高い確率でより高い確率でその個体をより高い確率で取り出す。いくつかの基準（max_iteration_count、valid_solution_found）が真になるまで繰り返す。

あなたの問題に遺伝的アルゴリズムを適合させる。次のようなことができます。 3x3または9x9のスドクごとにローカルの正しい解決策を作成します。これらは染色体です。それらを1つのデータ構造に入れます。それは個人です。世代を形成するためにそれらの束を作りなさい。違反している制約によってすべての個人を評価する。対応する確率を計算する。個体を組み換え、いくつかの染色体を突然変異させ、繰り返す。

ローカル最適化とグローバル最適化の組み合わせとして見ることができます。あなたは地方を見つけるために欲張りなアルゴリズム（またはあなたが地方のスドクを解決するために使用したいもの）を必要とし、GAは全体的な最適なものを見つける必要があるでしょう。私は、GAだけを使用してこの問題を解決しようとするのは意味がないと思います。私は最近、コンビナトリアルな問題にGAを実装しました。ローカル最適化がなければ、結果はほとんどの場合非常にひどいものでした。

しかし、GAの良い点は、検索の最初に大きなステップを踏んで、最適化に向かって収束しながらも、検索スペースの大部分をカバーすることです。しかし、いつものようにEAを使うと、パラメータを微調整するのが難しい場合があります。