そこで、数独を解くための単純な遺伝的アルゴリズムを書こうとしています (最も効率的な方法ではないことはわかっていますが、進化的アルゴリズムを実践するためのものです)。パズルが解けたかどうか、エラーがいくつあるかをテストするための効率的な評価関数を考え出すのにいくつか問題があります。私の最初の本能は、行列の各行と列 (matlab に似ているオクターブで実行) に一意の要素があるかどうかを確認することです。それらを並べ替え、重複を確認してから元の状態に戻します。これは長いようです。巻いた。何かご意見は？
これが以前に尋ねられた場合は申し訳ありません...
スピードアップ:
並べ替えの代わりにビット演算を使用します。
私は100行の数独ソルバーをcで作成しました。それはかなり高速です。または超高速のために、DLXアルゴリズムを実装する必要があります。そのためのmatlab交換に関するファイルもあります。
http://en.wikipedia.org/wiki/Exact_cover
http://en.wikipedia.org/wiki/Dancing_Links
http://en.wikipedia.org/wiki/Knuth 's_Algorithm_X
#include "stdio.h"
int rec_sudoku(int (&mat)[9][9],int depth)
{
int sol[9][9][10]; //for eliminating
if(depth == 0) return 1;
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
sol[i][j][9]=9;
for(int k=0;k<9;k++)
{
if(mat[i][j]) sol[i][j][k]=0;
else sol[i][j][k]=1;
}
}
}
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(mat[i][j] == 0) continue;
for(int k=0;k<9;k++)
{
if(sol[i][k][mat[i][j]-1])
{
if(--sol[i][k][9]==0) return 0;
sol[i][k][mat[i][j]-1]=0;
}
if(sol[k][j][mat[i][j]-1])
{
if(--sol[k][j][9]==0) return 0;
sol[k][j][mat[i][j]-1]=0;
}
}
for(int k=(i/3)*3;k<(i/3+1)*3;k++)
{
for(int kk=(j/3)*3;kk<(j/3+1)*3;kk++)
{
if(sol[k][kk][mat[i][j]-1])
{
if(--sol[k][kk][9]==0) return 0;
sol[k][kk][mat[i][j]-1]=0;
}
}
}
}
}
for(int c=1;c<=9;c++)
{
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(sol[i][j][9] != c) continue;
for(int k=0;k<9;k++)
{
if(sol[i][j][k] != 1) continue;
mat[i][j]=k+1;
if(rec_sudoku(mat,depth-1)) return 1;
mat[i][j]=0;
}
return 0;
}
}
}
return 0;
}
int main(void)
{
int matrix[9][9] =
{
{1,0,0,0,0,7,0,9,0},
{0,3,0,0,2,0,0,0,8},
{0,0,9,6,0,0,5,0,0},
{0,0,5,3,0,0,9,0,0},
{0,1,0,0,8,0,0,0,2},
{6,0,0,0,0,4,0,0,0},
{3,0,0,0,0,0,0,1,0},
{0,4,0,0,0,0,0,0,7},
{0,0,7,0,0,0,3,0,0}
};
int d=0;
for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(matrix[i][j] == 0) d++;
if(rec_sudoku(matrix,d)==0)
{
printf("no solution");
return 0;
}
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
printf("%i ",matrix[i][j]);
}
printf("\n");
}
return 1;
}
チェックは簡単です。行、列、および 3x3 のセットを作成し、存在しない場合は数字を追加し、存在しない場合はそれに応じてフィットネスを変更します。
ただし、本当の秘訣は、それに応じて「フィットネスを変更する」ことです。いくつかの問題は、GA と ES (進化戦略) に適しているように見えます。つまり、許容範囲内で解決策を探しますが、数独には正確な答えがあります...トリッキーです。
私の最初のクラックは、おそらく可変長の染色体を使用してソリューションを作成することです (固定長でも 9x9 は空白でもかまいません)。フィットネス関数は、ソリューションのどの部分が保証され、どの部分が保証されていないかを判断できる必要があります (非常にタフな数独ゲームでは暗闇の中で推測を行い、うまくいかない場合は元に戻す必要がある場合があります)。可能なブランチごとに子を作成することをお勧めします。
これは再帰的な解決策です。ただし、ボード上のさまざまな位置からスキャンを開始できます。再結合は、ソリューションが重複している検証されていない部分を組み合わせたソリューションを結合します。
この高レベルの気楽なやり方で考えてみると、これを実装するのがいかに精神を曲げることになるかがわかります!
突然変異は一種の推測であるため、たどるパスが複数ある場合にのみ適用されます。
これがsetを使用した私の解決策です。行、ブロック、または列の場合、設定された長さ（たとえば）7を取得すると、適合度は9〜7になります。
この問題を解決したとき、各行、列、サブグリッドの重複の数を数えました（実際、進化演算子は行に重複を導入しないように設計されていたため、列とサブグリッドの重複を数えるだけで済みました） 。重複を検出するためにHashSetを使用しました。より速い方法がありますが、これは私にとって十分に速かったです。
これは私のJavaアプレットで視覚化されています（速すぎる場合は、人口サイズを増やして速度を落とします）。色付きの四角は重複しています。黄色の正方形は他の1つの正方形と競合し、オレンジは他の2つの正方形と競合し、赤は3つ以上の正方形と競合します。
少数の整数セットを操作している場合は、O(n)バケットの並べ替えを使用して並べ替えを行うことができます。
配列を使用tmpして、matlab でこのタスクを実行できます。
function tf = checkSubSet( board, sel ) % % 与えられた 9x9 ボードとセレクション (論理 9x9 sel マトリックスを使用) % ボード(sel) に 9 つの一意の要素があることを検証 % % 仮定: % - ボードは数字 1 の 9x9 です。 2,...,9 % - sel には 9 つの「真」のエントリしかありません: nnz(sel) = 9 % tmp = zeros(1,9); tmp( ボード ( sel ) ) = 1; % 貧乏人のバケツの並べ替え tf = all( tmp == 1 ) && nnz(sel) == 9 && numel(tmp) == 9; % チェック有効性
checkSubSetこれで、ボードが正しいことを確認するために使用できます
function isCorrect = checkSudokuBoard( board )
%
% assuming board is 9x9 matrix with entries 1,2,...,9
%
isCorrect = true;
% check rows and columns
for ii = 1:9
sel = false( 9 );
sel(:,ii) = true;
isCorrect = checkSubSet( board, sel );
if ~isCorrect
return;
end
sel = false( 9 );
sel( ii, : ) = true;
isCorrect = checkSubSet( board, sel );
if ~isCorrect
return;
end
end
% check all 3x3
for ii=1:3:9
for jj=1:3:9
sel = false( 9 );
sel( ii + (0:2) , jj + (0:2) ) = true;
isCorrect = checkSubSet( board, sel );
if ~isCorrect
return;
end
end
end
これが私の解決策です。C++ での数独解決ソリューション
グリッドの数値をインデックスとして使用し、9 要素の長さの配列のそれぞれの要素をインクリメントします => s_array[x]++xはグリッドから取得した数値です。1 行のチェックが終了すると、すべての要素が配列内で 1 である必要があります。配列のどこかに 0 が発生した場合、その行は間違っています。
ただし、これは行単位で問題がないかどうかの単純な健全性チェックです。
PS: 10 年前であれば、ビット操作 (値 1、2、または 3 の 1 ビット目、2 ビット目、3 ビット目など) を使用したアセンブリ ソリューションを提案し、結果が 2^10-1 であるかどうかを確認します。 .
「それらを元に戻す」部分を除いて、良さそうです。パズルの任意の行、列、または正方形の数字をリストに入れて、好きな方法でダブルをチェックするだけです。double がある場合は、エラーがあります。すべての数値が一意である場合、そうではありません。パズルから実際の数字を取り出す必要はないので、元に戻す必要もありません。
さらに、ソルバーを作成している場合は、無効な動きをしてはならないため、このチェックはまったく必要ありません。