数独構成が有効かどうかを確認する簡単なアルゴリズムを知っている人はいますか? 私が思いついた最も単純なアルゴリズムは、(サイズ n のボードの場合) Pseudocode です。
for each row
for each number k in 1..n
if k is not in the row (using another for-loop)
return not-a-solution
..do the same for each column
しかし、より優れた (よりエレガントなという意味での) 解決策があるに違いないと確信しています。効率はまったく重要ではありません。
あなたは数独のすべての制約をチェックする必要があります：
それは全部で6つのチェックです..ブルートフォースアプローチを使用します。
ボードのサイズ（つまり、3x3または9x9）がわかっている場合は、ある種の数理最適化を使用できます。
編集：合計制約の説明：最初に合計をチェックする（そして合計が45でない場合は停止する）ことは、重複をチェックするよりもはるかに高速（かつ簡単）です。それは間違った解決策を捨てる簡単な方法を提供します。
Peter Norvigは、数独パズルの解決に関するすばらしい記事を（Pythonで）持っています。
https://norvig.com/sudoku.html
多分それはあなたがやりたいことには多すぎますが、とにかくそれは素晴らしい読み物です
各行、列、およびボックスに 1 ～ 9 の数字が含まれ、重複していないことを確認します。ここでのほとんどの回答では、すでにこれについて説明しています。
しかし、それを効率的に行うにはどうすればよいでしょうか。回答: 次のようなループを使用します
result=0;
for each entry:
result |= 1<<(value-1)
return (result==511);
各数値は、結果の 1 ビットを設定します。9 つの数値がすべて一意である場合は、下位 9 ビットが設定されます。したがって、「重複のチェック」テストは、9 ビットすべてが設定されていることのチェックにすぎません。これは、result==511 のテストと同じです。これらのチェックを 27 回行う必要があります。行、列、およびボックスごとに 1 つです。
ちょっと考えてみてください。各 3x3 の正方形の数字も確認する必要はありませんか?
正しい数独がなくても、行と列の条件が満たされる可能性があるかどうかを把握しようとしています
これはPythonでの私のソリューションです。これが最も短いものであることを嬉しく思います:)
コード：
def check(sud):
zippedsud = zip(*sud)
boxedsud=[]
for li,line in enumerate(sud):
for box in range(3):
if not li % 3: boxedsud.append([]) # build a new box every 3 lines
boxedsud[box + li/3*3].extend(line[box*3:box*3+3])
for li in range(9):
if [x for x in [set(sud[li]), set(zippedsud[li]), set(boxedsud[li])] if x != set(range(1,10))]:
return False
return True
そして実行：
sudoku=[
[7, 5, 1, 8, 4, 3, 9, 2, 6],
[8, 9, 3, 6, 2, 5, 1, 7, 4],
[6, 4, 2, 1, 7, 9, 5, 8, 3],
[4, 2, 5, 3, 1, 6, 7, 9, 8],
[1, 7, 6, 9, 8, 2, 3, 4, 5],
[9, 3, 8, 7, 5, 4, 6, 1, 2],
[3, 6, 4, 2, 9, 7, 8, 5, 1],
[2, 8, 9, 5, 3, 1, 4, 6, 7],
[5, 1, 7, 4, 6, 8, 2, 3, 9]]
print check(sudoku)
行、列、正方形ごとにブール値の配列を作成します。配列のインデックスは、その行、列、または正方形に配置された値を表します。つまり、2 行目の最初の列に 5 を追加すると、rows[2][5] を true に設定し、columns[1][5] と squares[4][5] を指定して、行、列、正方形に5値があることを確認します。
元のボードがどのように表現されているかに関係なく、これは完全性と正確性をチェックする簡単で非常に迅速な方法です。ボードに表示される順序で番号を取得し、このデータ構造の構築を開始するだけです。ボードに数字を配置すると、特定の行、列、または正方形で値が重複しているかどうかを判断する O(1) 操作になります。(各値が正当な数字であることも確認する必要があります。空白または大きすぎる数字が表示された場合は、ボードが完成していないことがわかります。) ボードの最後に到達したら、すべての値が正しいことがわかり、それ以上のチェックは必要ありません。
これを行うには、任意の形式の Set を使用できると誰かが指摘しました。このように配置された配列は、特に軽量でパフォーマンスの高い Set の形式であり、小さくて連続した固定の数値セットに適しています。ボードのサイズがわかっている場合は、ビットマスキングを選択することもできますが、効率がそれほど重要ではないことを考えると、おそらく少し面倒です。
各セットに9つのセルが含まれるセルセットを作成し、垂直列、水平行、および3x3の正方形のセットを作成します。
次に、セルごとに、そのセルが含まれているセットを特定し、それらを分析します。
クラスプロジェクトでこれを1回行いました。各行、列、およびボックスを表すために、合計 27 セットを使用しました。各セットに数字を追加するときに数字をチェックします (数字を配置するたびに、数字が行、列、ボックスの 3 つのセットに追加されます)、ユーザーが数字 1- 9. セットが埋められる唯一の方法は、一意の数字で適切に埋められた場合です。27 セットすべてが埋まれば、パズルは解けました。ユーザー インターフェイスから 27 個のセットへのマッピングを設定するのは少し面倒でしたが、残りのロジックは簡単に実装できました。
セット (行、列、ボックス) 内のすべての値をリストに抽出し、並べ替えてから、'(1, 2, 3, 4, 5, 6, 7, 8, 9) と比較できます。
次のことを確認するのは非常に興味深いでしょう。
when the sum of each row/column/box equals n*(n+1)/2
and the product equals n!
with n = number of rows or columns
これは数独のルールで十分です。これにより、O（n ^ 2）のアルゴリズムが可能になるため、正しいセルを合計して乗算します。
n = 9を見ると、合計は45、積は362880になります。
あなたは次のようなことをします：
for i = 0 to n-1 do
boxsum[i] := 0;
colsum[i] := 0;
rowsum[i] := 0;
boxprod[i] := 1;
colprod[i] := 1;
rowprod[i] := 1;
end;
for i = 0 to n-1 do
for j = 0 to n-1 do
box := (i div n^1/2) + (j div n^1/2)*n^1/2;
boxsum[box] := boxsum[box] + cell[i,j];
boxprod[box] := boxprod[box] * cell[i,j];
colsum[i] := colsum[i] + cell[i,j];
colprod[i] := colprod[i] * cell[i,j];
rowsum[j] := colsum[j] + cell[i,j];
rowprod[j] := colprod[j] * cell[i,j];
end;
end;
for i = 0 to n-1 do
if boxsum[i] <> 45
or colsum[i] <> 45
or rowsum[i] <> 45
or boxprod[i] <> 362880
or colprod[i] <> 362880
or rowprod[i] <> 362880
return false;
少し前に、各行の重複番号、各列の重複番号、各ボックスの重複番号をチェックする数独チェッカーを書きました。ただし、誰かが数行のLinqコードを考え出すことができれば幸いです。
char VerifySudoku(char grid[81])
{
for (char r = 0; r < 9; ++r)
{
unsigned int bigFlags = 0;
for (char c = 0; c < 9; ++c)
{
unsigned short buffer = r/3*3+c/3;
// check horizontally
bitFlags |= 1 << (27-grid[(r<<3)+r+c])
// check vertically
| 1 << (18-grid[(c<<3)+c+r])
// check subgrids
| 1 << (9-grid[(buffer<<3)+buffer+r%3*3+c%3]);
}
if (bitFlags != 0x7ffffff)
return 0; // invalid
}
return 1; // valid
}
行/列の合計と乗算が正しい数 45/362880 に等しい場合
デフソリューション（ボード）：
ボード上の私のために：
合計(i) != 45の場合:
「不正解」を返す
範囲内の i の場合 (9):
temp2 = []
範囲内の x の場合 (9):
temp2.append(ボード[i][x])
合計 (temp2) != 45 の場合:
「不正解」を返す
「正解」を返す
ボード = []
範囲内の i の場合 (9):
inp = raw_input()
temp = [inp の i の int(i)]
board.append(一時)
プリントソリューション（ボード）
intsudoku[0..8,0..8]が数独フィールドだとしましょう。
bool CheckSudoku(int[,] sudoku)
{
int flag = 0;
// Check rows
for(int row = 0; row < 9; row++)
{
flag = 0;
for (int col = 0; col < 9; col++)
{
// edited : check range step (see comments)
if ((sudoku[row, col] < 1)||(sudoku[row, col] > 9))
{
return false;
}
// if n-th bit is set.. but you can use a bool array for readability
if ((flag & (1 << sudoku[row, col])) != 0)
{
return false;
}
// set the n-th bit
flag |= (1 << sudoku[row, col]);
}
}
// Check columns
for(int col= 0; col < 9; col++)
{
flag = 0;
for (int row = 0; row < 9; row++)
{
if ((flag & (1 << sudoku[row, col])) != 0)
{
return false;
}
flag |= (1 << sudoku[row, col]);
}
}
// Check 3x3 boxes
for(int box= 0; box < 9; box++)
{
flag = 0;
for (int ofs = 0; ofs < 9; ofs++)
{
int col = (box % 3) * 3;
int row = ((int)(box / 3)) * 3;
if ((flag & (1 << sudoku[row, col])) != 0)
{
return false;
}
flag |= (1 << sudoku[row, col]);
}
}
return true;
}
ボードが1-nになると仮定しましょう。
検証配列を作成し、それを埋めてから検証します。
grid [0-(n-1)][0-(n-1)]; //this is the input grid
//each verification takes n^2 bits, so three verifications gives us 3n^2
boolean VArray (3*n*n) //make sure this is initialized to false
for i = 0 to n
for j = 0 to n
/*
each coordinate consists of three parts
row/col/box start pos, index offset, val offset
*/
//to validate rows
VArray( (0) + (j*n) + (grid[i][j]-1) ) = 1
//to validate cols
VArray( (n*n) + (i*n) + (grid[i][j]-1) ) = 1
//to validate boxes
VArray( (2*n*n) + (3*(floor (i/3)*n)+ floor(j/3)*n) + (grid[i][j]-1) ) = 1
next
next
if every array value is true then the solution is correct.
私はそこでいくつかのばかげた間違いをしたと確信していますが、それでうまくいくと思います。私はボートを完全に逃したかもしれません。
これが C の私のものです。各マスを 1 回だけ通過します。
int checkSudoku(int board[]) {
int i;
int check[13] = { 0 };
for (i = 0; i < 81; i++) {
if (i % 9 == 0) {
check[9] = 0;
if (i % 27 == 0) {
check[10] = 0;
check[11] = 0;
check[12] = 0;
}
}
if (check[i % 9] & (1 << board[i])) {
return 0;
}
check[i % 9] |= (1 << board[i]);
if (check[9] & (1 << board[i])) {
return 0;
}
check[9] |= (1 << board[i]);
if (i % 9 < 3) {
if (check[10] & (1 << board[i])) {
return 0;
}
check[10] |= (1 << board[i]);
} else if (i % 9 < 6) {
if (check[11] & (1 << board[i])) {
return 0;
}
check[11] |= (1 << board[i]);
} else {
if (check[12] & (1 << board[i])) {
return 0;
}
check[12] |= (1 << board[i]);
}
}
}
次の 2 つの方法で、数独が解けたかどうかを確認できます。
単純な解決策は、すべての正方形を繰り返し、その数が占める行ブロックと列ブロックでその数が一意であるかどうかを確認することです。
しかし、もっと良い方法があります。
これは、数値ごとにチェックするのではなく、すべての行、列、およびブロックをチェックするだけで済みます。簡単な実装は、1 から 9 までの数字のビットフィールドを持ち、列、行、およびブロックを反復するときにそれらを削除することです。不足している数字を削除しようとした場合、または終了時にフィールドが空でない場合、数独は正しく解決されていません。
これは数学教授の JF Crook による論文です:数独パズルを解くための鉛筆と紙のアルゴリズム
この論文は 2009 年 4 月に発行され、明確な数独ソリューションとして多くの宣伝を得ました ("JFCrook Sudoku" のグーグルをチェックしてください)。
アルゴリズムに加えて、アルゴリズムが機能することの数学的証明もあります (教授は、数独はあまり面白くないと認めたので、紙に数学を投げて、より楽しくしました)。
array = [1,2,3,4,5,6,7,8,9]
sudoku = int [][]
puzzle = 9 #9x9
columns = map []
units = map [] # box
unit_l = 3 # box width/height
check_puzzle()
def strike_numbers(line, line_num, columns, units, unit_l):
count = 0
for n in line:
# check which unit we're in
unit = ceil(n / unit_l) + ceil(line_num / unit_l) # this line is wrong - rushed
if units[unit].contains(n): #is n in unit already?
return columns, units, 1
units[unit].add(n)
if columns[count].contains(n): #is n in column already?
return columns, units, 1
columns[count].add(n)
line.remove(n) #remove num from temp row
return columns, units, line.length # was a number not eliminated?
def check_puzzle(columns, sudoku, puzzle, array, units):
for (i=0;i< puzzle;i++):
columns, units, left_over = strike_numbers(sudoku[i], i, columns, units) # iterate through rows
if (left_over > 0): return false
頭のてっぺんから徹底的にチェックしなくても、これは（少しのデバッグで）2回ループするだけで機能するはずです。O(3(n^2)) の代わりに O(n^2)
数独フィールドを受け取り、それが解決策である場合は true/false を返す関数を持つインターフェイスを作成します。次に、制約ごとに単一の検証クラスとして制約を実装します。
検証するには、すべての制約クラスを繰り返し処理し、すべてが数独に合格したときに正しいことを確認します。スピードアップするには、失敗する可能性が最も高いものを前に置き、無効なフィールドを指す最初の結果で停止します。
かなり一般的なパターン。;-)
もちろん、これを拡張して、どのフィールドがおそらく間違っているかなどのヒントを提供することもできます。
最初の制約です。すべてのフィールドが入力されているかどうかを確認してください。(単純なループ) すべての数値が各ブロック内にあるかどうかの 2 番目のチェック (ネストされたループ) 行と列が完全かどうかの 3 番目のチェック (上記とほぼ同じ手順ですが、アクセス スキームが異なります)