出版日: 2024年5月19日
このブログ記事では、JavaScriptでバックトラッキングアルゴリズムを使用して以下のような完全な数独グリッドを生成する方法を見ていきます。 をクリックしてアルゴリズムを実行してみましょう!
埋められたセルの数:
1
ステップ数:
1
数字を含む完全な数独グリッドを作成するのは簡単だと思うかもしれません。また、これは不完全な数独グリッドを解くことが重要なので、最初から完全なものを作るのは愚かなことだと思うかもしれません。仮に作成するにしても、実際に数独ゲームをプレイできるように数字が欠けているものを作成したいでしょう。
しかし、これらの主張は間違っています。なぜなら:
1. 完全な数独グリッドを作成するのは簡単ではありません。
練習として、ゲームのルールを満たす9x9の数独グリッドを作成してみてください(すなわち、各行、列、ブロックに1-9のすべての数字が繰り返しなしに使われる)。最初の約20個の数字を満たすのは簡単ですが、グリッドの終わりに近づくにつれて難しくなります。
これは、以前に埋めた数字が後のセルで問題を引き起こし、そのセルのためのすべての潜在的な数字を排除してしまうからです。この場合、いくつかのセルをバックトラックし、後のセルが数字で埋められるようにその前のセルの数字を変更する必要があります。
2. 完全な数独グリッドを作成することは無関係ではありません。
完全なグリッドの作成は、数独ゲームボードを作成するための最初のステップです。完全なグリッドを作成し、そのグリッドから数字を削除して、プレイヤーがその数字を埋めるようにします。削除する数字が多ければ多いほど、ゲームは難しくなります。
したがって、完全なグリッドの作成はこのゲームを作成する上で重要な部分です。ゲームに入る前に、グリッド作成のルールを見てみましょう。
9x9の数独の基本ルールは、グリッド内の各行、列、およびブロックに1-9の数字が含まれていることです。行、列、またはブロックには9つのセルがあり、1-9の数字が完全にフィットするため、繰り返しは許されません。
1. 行
下記では、各行がセルごとに行名で強調表示されています。
2. 列
下記では、各列がセルごとに列名で強調表示されています。
3. ブロック
ブロックはグリッドを構成する3x3の正方形です。行や列と同様に、各ブロックには1-9の数字が含まれ、繰り返しは許されません。
下記では、各ブロックがセルごとにブロック名で強調表示されています。
上記のセクションで簡単に触れたように、完全なグリッドを作成するのは手作業では非常に難しいです。これを行うためには、特定のセルに使用する数字から生じる可能性のあるすべての問題を予見する必要があります。
最終的には、行、列、ブロックの条件がすべての可能な数字を除外してしまい、どの数字も使用できないセルに行き着きます。このような場合、バックトラックします。
以下に、このアルゴリズムがどのように実行されるかを示します:
以下はコード版です:
// 変数の初期化
let grid = []; // グリッドデータを保持するため
let numbers = []; // 1-9 の数字
let cellIndex = 0; // セル番号
// グリッドと数字の初期化
for (let i = 0; i < 9; i++) {
// 数字を追加
numbers.push(i + 1);
// 各セルに対して、その行、列、ブロック、初期値、試した値を記録
// 初期値と試した値はそれぞれ '' と [] に初期化
for (let j = 0; j < 9; j++) {
let cell = {};
cell.row = i;
cell.col = j;
cell.block = `${Math.floor(i / 3)}-${Math.floor(j / 3)}`;
cell.value = '';
cell.tried = [];
grid.push(cell);
}
}
// バックトラッキングアルゴリズムでグリッドを埋める関数
function fillGrid() {
// まだ埋めるべきセルが残っている場合のみ続行
while (cellIndex < grid.length) {
// 関連するセルを取得
let cell = grid[cellIndex];
// すべての数字を試した場合、試した値を [] に設定
// そうしないとアルゴリズムがブロックされる
if (cell.tried.length == 9) {
cell.tried = [];
}
// このセルに対して、同じ行、列、ブロックに属するセルを取得
let row = grid.filter((d) => d.row === cell.row).map((d) => d.value);
let col = grid.filter((d) => d.col === cell.col).map((d) => d.value);
let block = grid.filter((d) => d.block === cell.block).map((d) => d.value);
// 数字をシャッフルする、毎回異なるグリッドを作成するため
// そうしないとグリッドは常に同じ出力を生成する
numbers = numbers
.map((value) => ({ value, sort: Math.random() }))
.sort((a, b) => a.sort - b.sort)
.map(({ value }) => value);
// セルに対して実行可能な数字が見つかったかどうかを保持する変数
let found = false;
// ランダムな数字をループする
for (let n = 0; n < 9; n++) {
// ランダムな数字を取得
let number = numbers[n];
// この数字が条件を満たすかどうかを確認
// すなわち、1. まだ試していない
// 2. 同じ行に現れない
// 3. 同じ列に現れない
// 4. 同じブロックに現れない
if (
!cell.tried.includes(number) &&
!row.includes(number) &&
!col.includes(number) &&
!block.includes(number)
) {
// 数字が条件を満たす場合、セルの値をその数字に設定
cell.value = number;
// このセルの試した数字にその数字を追加
cell.tried.push(number);
// 次のセルに進む
cellIndex++;
// 解決策が見つかったので、found を true に設定
found = true;
break;
}
}
// セルに対して数字が見つからなかった場合
// すなわち、上記の4つの条件を満たす数字がない場合
if (!found) {
// このセルの試した値の配列を [] に設定
grid[cellIndex].tried = [];
// 1セル戻る
cellIndex--;
// 他の数字を試すために前のセルの値を "" に設定
grid[cellIndex].value = '';
}
}
}
fillGrid();
さて、上記のコードが以下のグリッドで動作するか見てみましょう。ボタンを使用します:
動作しますよね?そしてバックトラッキングアルゴリズムは非常に効率的で、この問題の解答をほとんどの場合1秒以内に見つけます。
このブログ記事では、完全な数独グリッドを作成することが手作業では不可能であり、数独ゲーム作成の重要な部分であることを見てきました。
このタスクのために、完全な数独グリッドを作成するためのシンプルで効率的なアルゴリズムであるバックトラッキングアルゴリズムを開発しました。通常、81セルの完全な数独グリッドを200ステップ以内に1秒未満で生成できます。
このブログ記事に続いて2つの投稿を予定しています:
それでは、コーディングを楽しんでください!
このブログは英語からChatGPTによって翻訳されました。不明な点がある場合は、お問い合わせページからご連絡ください。
コメントを残す
コメント
その他のブログ
2024/06/19
SvelteとJavaScriptを使用してシンプルで動的なツールチップを作成する
2024/06/17
JavaScriptを用いて東京都のインタラクティブな地図を作成する
2024/06/14
Matplotlibで日本語文字化けを解決できる簡単な方法
2024/06/13
書評 | トーキング・トゥ・ストレンジャーズ 「よく知らない人」について私たちが知っておくべきこと by マルコム・グラッドウェル
2024/06/07
日本語で最もよく使われる3000字の漢字
2024/06/07
VSCodeでRegexを使用してReplaceする方法
2024/06/06
SvelteではReadable Storeを使用するな
2024/06/05
GzipとPakoでデータを圧縮してWebサイトのローディング速度を上げる方法
2024/05/31
JavaScriptを使用してWebページ上でマウスが指している単語を特定する
2024/05/29
SvelteとSVGを用いてインタラクティブな地図を作成する
2024/05/28
書評 | Originals 誰もが「人と違うこと」ができる時代 by アダム・グラント & シェリル・サンドバーグ
2024/05/27
Javascriptを使用して数独を解く方法
2024/05/26
ウェブサイトへのトラフィックを1か月で10倍に増やした方法
2024/05/24
人生はサイクリングに似ている
2024/05/16
Tailwindが素晴らしい理由とWeb開発をいかに楽にするか
2024/05/15
PythonとGitフックを使用してサイトマップを自動的に生成する
2024/05/14
書評 | Range (レンジ) 知識の「幅」が最強の武器になる by デイビッド・エプスタイン
2024/05/13
SvelteとSvelteKitはなんですか?
2024/05/12
SvelteKitで国際化(多言語化)
2024/05/11
SvelteでCachingを用いてDeploy時間を短縮する方法
2024/05/10
SvelteとIntersection Oberverによるレイジーローディング
2024/05/10
遺伝的アルゴリズムで最適な株式ポートフォリオを作る方法
2024/05/09
Pythonを用いてShapeFileをSVGに変換できる方法
2024/05/08
Svelteの反応性:変数、バインディング、およびキー関数
2024/05/07
書評 | 孫子の兵法
2024/05/06
スペシャリストは終了。ゼネラリスト万歳!
2024/05/03
トルコ人の有権者の投票行動をPythonでの分析
2024/05/01
Seleniumを用いてトルコ投票データベースを作る方法
2024/04/30
SvelteとTailwindを使用してInfinite Scrollできる方法
2024/04/29
1年間以内で日本語を駆使できるようになるための方法
2024/04/25
SvelteとTailwindを用いたWebサイトテンプレート
2024/01/29
怠惰なエンジニアとひどいデザイン
2024/01/28
偉大さについて
2024/01/28
MacBook で PDF を PNG に変換する
2023/12/31
2023年振り返り:24冊の読んだ本のまとめ
2023/12/30
Python PILを使用して写真コラージュを作成する方法
2024/01/09
ウェブサイトの訪問者のデバイスとブラウザを検出する方法
2024/01/19
ChatGPT回答の解析