Javascriptを使用して数独を解く方法

出版日: 2024年5月27日

背景

以前のブログ記事では、以下のように完全な数独グリッドを作成する方法について書きました。（この数独グリッドはリアルタイムで作成されるため、このページを訪れるたびにグリッドが変わります）

これは続編の投稿であり、このグリッドから数独ゲームを作成するためにいくつかの数字を削除し、それを解くアルゴリズムを開発します。

数独データ生成

数独ゲームを作成して解く最も難しい部分は、完全なグリッドを作成することです。これはすでに解決済みです。グリッドには81個の数字があり、これらの数字をサイズ81の配列に格納します。生成されたデータは以下のようになります：

let grid = [{ "row": 0, "col": 0, "block": "0-0", "value": 1 },

{ "row": 0, "col": 1, "block": "0-0", "value": 5 },

{ "row": 0, "col": 2, "block": "0-0", "value": 8 },

{ "row": 0, "col": 3, "block": "0-1", "value": 3 },

{ "row": 0, "col": 4, "block": "0-1", "value": 2 },

{ "row": 0, "col": 5, "block": "0-1", "value": 4 },

{ "row": 0, "col": 6, "block": "0-2", "value": 6 },

{ "row": 0, "col": 7, "block": "0-2", "value": 7 },

{ "row": 0, "col": 8, "block": "0-2", "value": 9 },

{ "row": 1, "col": 0, "block": "0-0", "value": 4 },

{ "row": 1, "col": 1, "block": "0-0", "value": 9 },

{ "row": 1, "col": 2, "block": "0-0", "value": 7 },

{ "row": 1, "col": 3, "block": "0-1", "value": 1 },

{ "row": 1, "col": 4, "block": "0-1", "value": 8 },

{ "row": 1, "col": 5, "block": "0-1", "value": 6 },

{ "row": 1, "col": 6, "block": "0-2", "value": 5 },

{ "row": 1, "col": 7, "block": "0-2", "value": 2 },

{ "row": 1, "col": 8, "block": "0-2", "value": 3 },

{ "row": 2, "col": 0, "block": "0-0", "value": 6 },

{ "row": 2, "col": 1, "block": "0-0", "value": 3 },

{ "row": 2, "col": 2, "block": "0-0", "value": 2 },

{ "row": 2, "col": 3, "block": "0-1", "value": 9 },

{ "row": 2, "col": 4, "block": "0-1", "value": 5 },

{ "row": 2, "col": 5, "block": "0-1", "value": 7 },

{ "row": 2, "col": 6, "block": "0-2", "value": 1 },

{ "row": 2, "col": 7, "block": "0-2", "value": 8 },

{ "row": 2, "col": 8, "block": "0-2", "value": 4 },

{ "row": 3, "col": 0, "block": "1-0", "value": 3 },

{ "row": 3, "col": 1, "block": "1-0", "value": 1 },

{ "row": 3, "col": 2, "block": "1-0", "value": 4 },

{ "row": 3, "col": 3, "block": "1-1", "value": 7 },

{ "row": 3, "col": 4, "block": "1-1", "value": 6 },

{ "row": 3, "col": 5, "block": "1-1", "value": 8 },

{ "row": 3, "col": 6, "block": "1-2", "value": 2 },

{ "row": 3, "col": 7, "block": "1-2", "value": 9 },

{ "row": 3, "col": 8, "block": "1-2", "value": 5 },

{ "row": 4, "col": 0, "block": "1-0", "value": 5 },

{ "row": 4, "col": 1, "block": "1-0", "value": 8 },

{ "row": 4, "col": 2, "block": "1-0", "value": 9 },

{ "row": 4, "col": 3, "block": "1-1", "value": 4 },

{ "row": 4, "col": 4, "block": "1-1", "value": 1 },

{ "row": 4, "col": 5, "block": "1-1", "value": 2 },

{ "row": 4, "col": 6, "block": "1-2", "value": 3 },

{ "row": 4, "col": 7, "block": "1-2", "value": 6 },

{ "row": 4, "col": 8, "block": "1-2", "value": 7 },

{ "row": 5, "col": 0, "block": "1-0", "value": 2 },

{ "row": 5, "col": 1, "block": "1-0", "value": 7 },

{ "row": 5, "col": 2, "block": "1-0", "value": 6 },

{ "row": 5, "col": 3, "block": "1-1", "value": 5 },

{ "row": 5, "col": 4, "block": "1-1", "value": 3 },

{ "row": 5, "col": 5, "block": "1-1", "value": 9 },

{ "row": 5, "col": 6, "block": "1-2", "value": 8 },

{ "row": 5, "col": 7, "block": "1-2", "value": 4 },

{ "row": 5, "col": 8, "block": "1-2", "value": 1 },

{ "row": 6, "col": 0, "block": "2-0", "value": 7 },

{ "row": 6, "col": 1, "block": "2-0", "value": 2 },

{ "row": 6, "col": 2, "block": "2-0", "value": 1 },

{ "row": 6, "col": 3, "block": "2-1", "value": 8 },

{ "row": 6, "col": 4, "block": "2-1", "value": 9 },

{ "row": 6, "col": 5, "block": "2-1", "value": 3 },

{ "row": 6, "col": 6, "block": "2-2", "value": 4 },

{ "row": 6, "col": 7, "block": "2-2", "value": 5 },

{ "row": 6, "col": 8, "block": "2-2", "value": 6 },

{ "row": 7, "col": 0, "block": "2-0", "value": 8 },

{ "row": 7, "col": 1, "block": "2-0", "value": 4 },

{ "row": 7, "col": 2, "block": "2-0", "value": 5 },

{ "row": 7, "col": 3, "block": "2-1", "value": 6 },

{ "row": 7, "col": 4, "block": "2-1", "value": 7 },

{ "row": 7, "col": 5, "block": "2-1", "value": 1 },

{ "row": 7, "col": 6, "block": "2-2", "value": 9 },

{ "row": 7, "col": 7, "block": "2-2", "value": 3 },

{ "row": 7, "col": 8, "block": "2-2", "value": 2 },

{ "row": 8, "col": 0, "block": "2-0", "value": 9 },

{ "row": 8, "col": 1, "block": "2-0", "value": 6 },

{ "row": 8, "col": 2, "block": "2-0", "value": 3 },

{ "row": 8, "col": 3, "block": "2-1", "value": 2 },

{ "row": 8, "col": 4, "block": "2-1", "value": 4 },

{ "row": 8, "col": 5, "block": "2-1", "value": 5 },

{ "row": 8, "col": 6, "block": "2-2", "value": 7 },

{ "row": 8, "col": 7, "block": "2-2", "value": 1 },

{ "row": 8, "col": 8, "block": "2-2", "value": 8 }]

数字を削除して数独ゲームを作成する

今度はランダムにいくつかの数字を削除して、新しいグリッドを作成しましょう。これが私たちの数独ボードになります。

以下のフィールドで削除するセルの数を選択できます。10〜50セルの間で削除できます。

セルを削除するコードは以下にあります：

let dropCount = 20;

function drop(dC) {
	let indicesToBeDropped = Array.from({ length: grid.length }, (_, index) => index)
		.map((value) => ({ value, sort: Math.random() }))
		.sort((a, b) => a.sort - b.sort)
		.map(({ value }) => value)
		.slice(0, dC);

	let nG = grid.map((number, index) => {
		let newNumber = { ...number };
		if (indicesToBeDropped.includes(index)) {
			newNumber.value = '';
			newNumber.empty = true;
		}
		return newNumber;
	});

	return nG;
}

let newGrid = drop(dropCount);

数独ゲームを解く

ここが興味深い部分です。ボードを解いて、完全な状態に戻します。できれば。

ゲームが実際に解けるかどうかは確かではないので、解いてみましょう。データ構造がこのゲームを解くのを非常に簡単にします。各数字には関連する行、列、およびブロック番号があります。同じ行、列、ブロックを共有するデータをフィルタリングし、空のセルに適合する数字を見つけるだけです。

以下はグリッドを解くコードです。ロジックはコード内で説明されていますが、質問がある場合はコメントで教えてください。

// 以前のグリッドをコピーして、修正しないようにする
// $ 記号は、svelteで新しいグリッドを以前のグリッドに基づいてリアクティブにします
$: gameGrid = newGrid.map((n) => {
	return { ...n };
});

// 各番号が埋められるときにスリープするために
// ユーザーがアルゴリズムがステップバイステップで動作しているのを見えるように
let timeout;
function sleep(time) {
	return new Promise((resolve) => {
		timeout = setTimeout(resolve, time);
		return timeout;
	});
}

// 1000回の試行を超えた場合、試行を停止するためのカウントを保持します
let count = 0;

// 解決状況を追跡してメッセージを表示できるようにする
let solved = false;

// ソルバ関数
async function solve() {
	solved = false;

	// 値が ""（つまり空のセル）であるセルがなくなるまで反復を続けます（最大1000回の試行）
	while (gameGrid.filter((n) => n.value === '').length !== 0 && count < 1000) {
		count++;
		// すべてのセルをループします
		for (let cellIndex = 0; cellIndex < gameGrid.length; cellIndex++) {
			let cell = gameGrid[cellIndex];
			// 空のセルの場合
			if (cell.value === '') {
				// このセルと同じ行、列、およびブロックにある数字を見つけます
				let rowNumbers = gameGrid.filter((i) => i.row === cell.row).map((i) => i.value);
				let colNumbers = gameGrid.filter((i) => i.col === cell.col).map((i) => i.value);
				let blockNumbers = gameGrid.filter((i) => i.block === cell.block).map((i) => i.value);

				// 行、列、およびブロックに存在しないこのセルに入れられる数字を見つけます
				let rowPossibleNumbers = numbers.filter((i) => !rowNumbers.includes(i));
				let colPossibleNumbers = numbers.filter((i) => !colNumbers.includes(i));
				let blockPossibleNumbers = numbers.filter((i) => !blockNumbers.includes(i));

				// このセルに対するすべての可能な数字の交差を見つけます
				let possibleNumbers = [rowPossibleNumbers, colPossibleNumbers, blockPossibleNumbers];
				possibleNumbers = possibleNumbers.reduce((a, b) => a.filter((c) => b.includes(c)));

				// 可能な数字が1つだけの場合、正しい数字を見つけました！
				// それを埋めてスリープします
				if (possibleNumbers.length === 1) {
					cell.value = possibleNumbers[0];

					// gameGridを更新してHTML DOMに表示します
					gameGrid = [...gameGrid];
					await sleep(100);
					break;
				}
			}
		}
	}
	clearTimeout(timeout);
	solved = true;
}