独自のソリューションで数独ボードをどのように生成しますか？私が考えたのは、ランダムなボードを初期化してから、いくつかの数字を削除することでした。しかし、私の質問は、ソリューションの独自性をどのように維持するかということです。
103717 次
14 に答える
64
これが私自身の数独プログラムがそれを行う方法です：
完全で有効なボード（81個の数字で埋められている）から始めます。
81個のセル位置すべてのリストを作成し、ランダムにシャッフルします。
リストが空でない限り、リストから次の位置を取り、関連するセルから番号を削除します。
高速バックトラッキングソルバーを使用して一意性をテストします。私のソルバーは、理論的にはすべてのソリューションをカウントできますが、一意性をテストするために、複数のソリューションが見つかるとすぐに停止します。
現在のボードにまだ解決策が1つしかない場合は、手順3）に進んで繰り返します。
現在のボードに複数の解決策がある場合は、最後の削除を元に戻し（ステップ3）、リストの次の位置でステップ3を続行します
81の位置すべてをテストしたら、停止します。
これにより、一意のボードだけでなく、ソリューションの一意性を損なうことなく番号を削除できないボードが提供されます。
もちろん、これはアルゴリズムの後半にすぎません。前半は、最初に完全な有効なボードを見つけることです（ランダムに埋められます！）。これは非常によく似ていますが、「反対方向」です。
空のボードから始めます。
空きセルの1つに乱数を追加します（セルはランダムに選択され、数独ルールに従ってこのセルに有効な番号のリストからランダムに選択されます）。
バックトラッキングソルバーを使用して、現在のボードに少なくとも1つの有効なソリューションがあるかどうかを確認します。そうでない場合は、手順2を元に戻し、別の番号とセルで繰り返します。このステップはそれ自体で完全に有効なボードを生成する可能性がありますが、それらは決してランダムではないことに注意してください。
ボードが完全に数字でいっぱいになるまで繰り返します。
于 2011-09-02T07:44:33.377 に答える
35
簡単：
- 効率的なバックトラッキングアルゴリズムを使用してすべてのソリューションを見つけます。
- 解決策が1つしかない場合は、これで完了です。それ以外の場合、複数の解決策がある場合は、ほとんどの解決策が異なる位置を見つけてください。この位置に番号を追加します。
- 1に移動します。
これよりはるかに速い解決策を見つけることができるとは思えません。
于 2011-08-08T15:11:06.150 に答える
22
あなたはごまかすことができます。解決できる既存の数独ボードから始めて、それをいじります。
3つの3x3ブロックの任意の行を他の行と交換できます。3つの3x3ブロックの任意の列を別の列と交換できます。各ブロック行またはブロック列内で、単一行と単一列を入れ替えることができます。最後に、順列がボード全体で一貫している限り、塗りつぶされた位置に異なる番号が存在するように番号を並べ替えることができます。
これらの変更のいずれも、解決可能なボードを解決不可能にすることはありません。
于 2011-08-03T11:29:52.193 に答える
13
P = NPでない限り、1つの解だけで一般的な数独問題を生成するための多項式時間アルゴリズムはありません。
修士論文で矢藤隆之は、別の解決策問題（ASP）を定義しました。目標は、問題といくつかの解決策を与えられて、その問題の別の解決策を見つけること、または何も存在しないことを示すことです。次に、YatoはASP完全性、つまり別の解決策を見つけるのが難しい問題を定義し、数独がASP完全であることを示しました。彼はまた、ASP完全性がNP困難性を意味することを証明しているため、任意のサイズの数独ボードを許可する場合、生成したパズルに一意の解があるかどうかを確認する多項式時間アルゴリズムがないことを意味します（P = NP）。
高速アルゴリズムへの期待を台無しにしてすみません！
于 2011-09-02T07:55:25.620 に答える
8
解決策は2つの部分に分けられます： A。6000億
の数のパターンを
生成するB.マスキングパターンを生成する 〜7e23の組み合わせ
A）数値パターンの場合、バックトレースやテストに時間を費やす ことなく、独自の組み合わせを生成できる最速の方法
ステップ1.すでに存在するマトリックスを選択します。コンピューティングデバイスやソルバーの助けを借りずに人間が簡単に作成できるため、以下のマトリックスを選択しました。
最初の行は昇順の番号です
2番目の行も昇順ですが4から開始してロールアラウンドします
3番目の行も昇順ですが7から開始してロールアラウンドします
行4、5、6：3つのセルの列を上に置き換えます右の列
-258、最後の列の3x3セル内でロール行7、8、9：3つのセルの列を右上の列に置き換えます-3 6 9、最後の列の3x3セル内でロール
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5
ステップ2.数字をシャッフルし、他のすべてのセルで置き換え
ますステップ3.列1、2、および3を内部で
ランダムに再配置しますステップ4.列4、5、および6を内部で
ランダムに再配置しますステップ5.列7、8、および9をランダムに再配置します
ステップ6.行1、2、3を自分自身の中でランダム
に再配置しますステップ7.行4、5、6を自分たちの中で
ランダムに再配置しますステップ8.行7、8、9を自分たちの中で
ランダムに再配置しますステップ9.3列グループにランダムに再配置しますサイズ9x3の
ステップ10.サイズ3x9の3行グループにランダムに再配置します
出来上がり...
5 8 3 1 6 4 9 7 2
7 2 9 3 5 8 1 4 6
1 4 6 2 7 9 3 8 5
8 5 2 6 9 1 4 3 7
3 1 7 4 2 5 8 6 9
6 9 4 8 3 7 2 5 1
4 6 5 9 1 3 7 2 8
2 3 1 7 8 6 5 9 4
9 7 8 5 4 2 6 1 3
B）マスキングパターンの場合、ソルバーアルゴリズムが必要です。すでに非常にユニークな数値グリッドがあるので（これも解決されます！）、これによりソルバーを使用する際のパフォーマンスが向上します
ステップ1：81から15のランダムな場所を選択することから始めます
。ステップ2：ソルバーに一意のソリューションがあるかどうかを確認します
。ステップ3：ソリューションが一意でない場合は、追加の場所を選択します。一意の解決策が見つかるまで、手順2と3を繰り返します。
これはあなたに非常にユニークで速い数独ボードを与えるはずです。
于 2019-03-27T09:02:13.700 に答える
4
これは、他のnxn数独ボードだけでなく、可能な数独ボーラッドを生成できるということでした。
このアルゴリズムの効率については、Javaで100万枚のボードを生成するのに3.6秒かかり、golangで3.5秒かかりました。
- 数独の塗りつぶされたボードを見つけます。（些細なものを使用しても、最終結果には影響しません）
int[][] board = new int[][] {
{1,2,3, 4,5,6, 7,8,9},
{4,5,6, 7,8,9, 1,2,3},
{7,8,9, 1,2,3, 4,5,6},
{2,3,1, 5,6,4, 8,9,7},
{5,6,4, 8,9,7, 2,3,1},
{8,9,7, 2,3,1, 5,6,4},
{3,1,2, 6,4,5, 9,7,8},
{6,4,5, 9,7,8, 3,1,2},
{9,7,8, 3,1,2, 6,4,5}
};
- 1から9までの数字（たとえばnum）ごとに（つまり、1、2、3、5、6、7、8、9）、範囲[1から9]の乱数を取り、ボードをトラバースし、数字をランダムと交換します番号。
void shuffleNumbers() {
for (int i = 0; i < 9; i++) {
int ranNum = random.nextInt(9);
swapNumbers(i, ranNum);
}
}
private void swapNumbers(int n1, int n2) {
for (int y = 0; y<9; y++) {
for (int x = 0; x<9; x++) {
if (board[x][y] == n1) {
board[x][y] = n2;
} else if (board[x][y] == n2) {
board[x][y] = n1;
}
}
}
}
- 次に、行をシャッフルします。3行の最初のグループを取得し、それらをシャッフルして、すべての行に対して実行します。（9 X 9数独で）、2番目のグループと3番目のグループでそれを行います。
void shuffleRows() {
int blockNumber;
for (int i = 0; i < 9; i++) {
int ranNum = random.nextInt(3);
blockNumber = i / 3;
swapRows(i, blockNumber * 3 + ranNum);
}
}
void swapRows(int r1, int r2) {
int[] row = board[r1];
board[r1] = board[r2];
board[r2] = row;
}
- 列を交換し、再び3列のブロックを取得し、それらをシャッフルして、3つのブロックすべてに対して実行します
void shuffleCols() {
int blockNumber;
for (int i = 0; i < 9; i++) {
int ranNum = random.nextInt(3);
blockNumber = i / 3;
swapCols(i, blockNumber * 3 + ranNum);
}
}
void swapCols(int c1, int c2) {
int colVal;
for (int i = 0; i < 9; i++){
colVal = board[i][c1];
board[i][c1] = board[i][c2];
board[i][c2] = colVal;
}
}
- 行ブロック自体を交換します（つまり、3X9ブロック）
void shuffle3X3Rows() {
for (int i = 0; i < 3; i++) {
int ranNum = random.nextInt(3);
swap3X3Rows(i, ranNum);
}
}
void swap3X3Rows(int r1, int r2) {
for (int i = 0; i < 3; i++) {
swapRows(r1 * 3 + i, r2 * 3 + i);
}
}
- 列についても同じことを行い、ブロックごとに交換します
void shuffle3X3Cols() {
for (int i = 0; i < 3; i++) {
int ranNum = random.nextInt(3);
swap3X3Cols(i, ranNum);
}
}
private void swap3X3Cols(int c1, int c2) {
for (int i = 0; i < 3; i++) {
swapCols(c1 * 3 + i, c2 * 3 + i);
}
}
これで完了です。ボードは有効な数独ボードである必要があります
値が非表示のボードを生成するには、バックトラッキング数独アルゴリズムを使用して、解決可能なボードができるまでボードから1つの要素を削除しようとします。要素をあと1つだけ削除しても、解決できなくなるまで削除します。
最終的に生成されたボードを難易度で分類したい場合は、要素を1つずつ削除しながら、ボードに残っている数字の数を数えます。数が少ないほど、解決するのは難しくなります
数独で可能な最小のヒントは17である可能性がありますが、すべての可能な数独ボードは必ずしも17のヒント数独に還元できるわけではありません
于 2020-04-26T14:01:47.423 に答える
2
SWIFT5バージョン
簡単な方法、ここに私のコード：
まず、関数を[[Int]]配列に作成します
func getNumberSudoku() -> [[Int]] {
// Original number
let originalNum = [1,2,3,4,5,6,7,8,9]
// Create line 1 to 9 and shuffle from original
let line1 = originalNum.shuffled()
let line2 = line1.shift(withDistance: 3)
let line3 = line2.shift(withDistance: 3)
let line4 = line3.shift(withDistance: 1)
let line5 = line4.shift(withDistance: 3)
let line6 = line5.shift(withDistance: 3)
let line7 = line6.shift(withDistance: 1)
let line8 = line7.shift(withDistance: 3)
let line9 = line8.shift(withDistance: 3)
// Final array
let renewRow = [line1,line2,line3,line4,line5,line6,line7,line8,line9]
// Pre-shuffle for column
let colSh1 = [0,1,2].shuffled()
let colSh2 = [3,4,5].shuffled()
let colSh3 = [6,7,8].shuffled()
let rowSh1 = [0,1,2].shuffled()
let rowSh2 = [3,4,5].shuffled()
let rowSh3 = [6,7,8].shuffled()
// Create the let and var
let colResult = colSh1 + colSh2 + colSh3
let rowResult = rowSh1 + rowSh2 + rowSh3
var preCol: [Int] = []
var finalCol: [[Int]] = []
var prerow: [Int] = []
var finalRow: [[Int]] = []
// Shuffle the columns
for x in 0...8 {
preCol.removeAll()
for i in 0...8 {
preCol.append(renewRow[x][colResult[i]])
}
finalCol.append(preCol)
}
// Shuffle the rows
for x in 0...8 {
prerow.removeAll()
for i in 0...8 {
prerow.append(finalCol[x][rowResult[i]])
}
finalRow.append(prerow)
}
// Final, create the array into the [[Int]].
return finalRow
}
次に使用法：
var finalArray = [[Int]]
finalArray = getNumberSudoku()
于 2020-11-20T01:56:25.210 に答える
1
一般的な解決策を与えるのは簡単ではありません。特定の種類の数独を生成するには、いくつかのことを知っておく必要があります。たとえば、9つを超える空の9番号グループ（行、3x3ブロック、または列）で数独を作成することはできません。単一ソリューションの数独の最小の与えられた数独（すなわち「手がかり」）は17であると信じられていますが、私が間違っていなければ、この数独の数独の数独は非常に具体的です。数独の手がかりの平均数は約26で、よくわかりませんが、完成したグリッドの数を26になるまで終了し、対称的に残すと、有効な数独になる可能性があります。一方、完成したグリッドからランダムに数値を終了し、OKが表示されるまでCHECKERまたは他のツールでテストすることができます。
于 2011-08-03T10:14:23.353 に答える
1
これが古典的な数独パズルを作る方法です（唯一の解決策を持つ数独パズル。事前に入力された正方形は中央の正方形R5C5を中心に対称です）。
1）完全なグリッドから開始します（グループの塗りつぶしと循環シフトを使用して簡単に取得できます）
2）残りの手がかりを使用してクリアされた正方形を推測できる場合は、2つの対称的な正方形から数字を削除します。
3）すべての番号がチェックされるまで（2）を繰り返します。
この方法を使用すると、プログラミングの有無にかかわらず、非常に簡単な数独パズルを作成できます。この方法を使用して、より難しい数独パズルを作成することもできます。YouTubeで「古典的な数独を作成する」を検索して、段階的な例を示すことをお勧めします。
于 2017-03-05T02:12:43.030 に答える
0
また、一意性を明示的に確認する必要があると思います。与えられたものが17未満の場合、独自の解決策はほとんどありません。ただし、存在するかどうかはまだ明確ではありませんが、まだ何も見つかりません。）
ただし、独自のバックトラッキングアルゴリズムを作成するのではなく、SATソルバーを使用することもできます。そうすることで、解決策を見つけるのがどれほど難しいかをある程度調整できます。SATソルバーが使用する推論規則を制限すると、パズルを簡単に解決できるかどうかを確認できます。「SAT数独を解く」をググってください。
于 2011-09-02T08:33:21.997 に答える
0
数独をより速く生成する1つの方法。
- 存在する数独を見つけます。
- ランダムなグループと値を交換します。
- セルまたは列または行グリッドまたは列グリッドを交換します。
値を交換すると値が異なります。行または列を交換しない場合、数独は本質的に変更されません。
9グリッドで数独にフラグを立てることができます。交換される行と列は、同じグリッドで行う必要があります。row1-3、row4-6、row7-9を交換できるように、row1-4またはrow1-7は交換しないでください。行グリッドを交換することもできます（行1〜3を行4〜6または行7〜9と交換します）。
数独を解きます。可能なすべての値で空を記録し、1から9までの値を確認します。1つの値が一意である場合は、ループから削除します。
于 2019-07-03T04:41:21.733 に答える
0
有効な（塗りつぶされた）パズルから始めて、完全に異なるパズル（塗りつぶされたもの）を生成するように変更できます。数字のグループを並べ替える代わりに、単一のセルを入れ替えることができます。シードパズルと結果のパズルの間に類似点はありません。私はずっと前にVBで簡単なプログラムを書いたので、ここで見つけることができます：https ://www.charalampakis.com/blog/programming-vb-net/a-simple-algorithm-for-creating-sudoku-puzzles-using -visual-basic。どんな言語にも簡単に翻訳できます。
次に、ランダムに徐々にセルを削除し、パズルが解決可能であり、独自の解決策があるかどうかを確認します。ソリューションに必要なルールに応じて、難易度の観点からパズルを評価することもできます。既知のセルを削除すると、解決できないパズルが発生するまで続けます。
HTH
于 2020-11-30T08:27:25.737 に答える
0
次のようなコードが必要になる場合があります。
#pz is a 9x9 numpy array
def PossibleValueAtPosition(pz:[], row:int, col:int):
r=row//3*3
c=col//3*3
return {1,2,3,4,5,6,7,8,9}.difference(set(pz[r:r+3,c:c+3].flat)).difference(set(pz[row,:])).difference(set(pz[:,col]))
def SolvePuzzle(pz:[], n:int, Nof_solution:int):# init Nof_solution = 0
if Nof_solution>1:
return Nof_solution # no need to further check
if n>=81:
Nof_solution+=1
return Nof_solution
(row,col) = divmod(n,9)
if pz[row][col]>0: # location filled, try next location
Nof_solution = SolvePuzzle(pz, n+1, Nof_solution)
else:
l = PossibleValueAtPosition(pz, row,col)
for v in l: # if l = empty set, bypass all
pz[row][col] = v # try to fill a possible value v
Nof_solution = SolvePuzzle(pz, n+1, Nof_solution)
pz[row][col] = 0
return Nof_solution # resume the value, blacktrack
于 2021-03-19T07:22:46.993 に答える
0
速くて汚いが、動作する：
numpyをnpとしてインポートします
数学をインポートする
N = 3
＃https：//www.tutorialspoint.com/valid-sudoku-in-pythonの書き直し
def isValidSudoku（M）：
'''
数独マトリックスを確認します。
9x9の数独行列は、次の場合に有効です。
行には1〜9と
colには1〜9と
3x3には1〜9が含まれます
0は空白のエントリに使用されます
'''
range（9）のiの場合：
行={}
col = {}
ブロック={}
row_cube = N *（i // N）
col_cube = N *（i％N）
範囲内のjの場合（N * N）：
M [i] [j]！=0およびM[i] [j]の行の場合：
Falseを返します
行[M[i][j]] = 1
colのM[j][i]！=0およびM[j] [i]の場合：
Falseを返します
col [M [j] [i]] = 1
rc = row_cube + j // N
cc = col_cube + j％N
ブロック内のM[rc][cc]およびM[rc][cc]！= 0の場合：
Falseを返します
block [M [rc] [cc]] = 1
Trueを返す
def generate_sudoku_puzzles（run_size、seed）：
order = int（math.sqrt（run_size））
カウント=0
有効=0
空=[]
np.random.seed（seed）＃再現性のある結果
範囲（順序）のkの場合：
範囲（順序）のlの場合：
A = np.fromfunction（lambda i、j：（（k * i + l + j）％（N * N））+ 1、（N * N、N * N）、dtype = int）
B = np.random.randint（2、size =（N * N、N * N））
empty.append（np.count_nonzero（B））
C = A * B
カウント+=1
isValidSudoku（C）の場合：
有効な+=1
最後=C
＃print（'C（'、k、l、'）は有効な数独です：'）
＃print（C）＃パズルのコメントを外す
print（'Tried'、count、'valid'、valid、'yield'、round（valid / count、3）* 100、'％'、'Average Clues'、round（sum（empty）/ len（empty）） ）。
return（last）
posTest = np.array（[（0、7、0、0、4、0、0、6、0）、\
（3、0、0、5、0、7、0、0、2）、\
（0、0、5、0、0、0、3、0、0）、\
（0、4、0、3、0、6、0、5、0）、\
（6、0、0、0、0、0、0、0、8）、\
（0、1、0、2、0、8、0、3、0）、\
（0、0、7、0、0、0、4、0、0）、\
（1、0、0、8、0、2、0、0、9）、\
（0、6、0、0、9、0、0、1、0）、\
]）
negTest = np.array（[（0、7、0、0、4、0、0、6、2）、\
（3、0、0、5、0、7、0、0、2）、\
（0、0、5、0、0、0、3、0、0）、\
（0、4、0、3、0、6、0、5、0）、\
（6、0、0、0、0、0、0、0、8）、\
（0、1、0、2、0、8、0、3、0）、\
（0、0、7、0、0、0、4、0、0）、\
（1、0、0、8、0、2、0、0、9）、\
（0、6、0、0、9、0、0、1、0）、\
]）
print（'Positive Quality Control Test：'、isValidSudoku（posTest））
print（'ネガティブ品質管理テスト：'、isValidSudoku（negTest））
print（generate_sudoku_puzzles（10000、0））
出力：
ポジティブ品質管理テスト：真
ネガティブ品質管理テスト：偽
試行10000有効31歩留まり0.3％平均手がかり40
[[0 0 2 3 0 0 0 7 8]
[7 8 9 1 2 0 0 0 0]
[5 0 0 0 9 0 0 3 0]
[0 0 0 6 7 8 0 0 2]
[0 2 0 0 0 0 7 8 9]
[8 0 0 2 3 0 0 0 0]
[0 0 0 0 0 2 3 0 5]
[0 5 6 0 8 9 1 2 0]
[0 3 0 5 0 0 0 9 0]]
パズルソースの2行のコメントを外します。
于 2021-11-05T10:02:40.657 に答える