JavaScriptでバックトラッキング・アルゴリズムを用いて完全な数独グリッドを生成する

// 変数の初期化
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();