import { z } from "npm:zod"; const ROWS = 9; const COLS = 9; const Sudoku = z .array(z.array(z.number().gte(0).lte(9)).length(COLS)) .length(ROWS); export type Sudoku = z.infer; export function print(sudoku: Sudoku) { for (let row = 0; row < ROWS; row++) { let line = ""; for (let col = 0; col < COLS; col++) { line += sudoku[row][col] + " "; } console.log(line); } } type Index = { x: number; y: number }; function next_i(i: Index): Index | null { if (i.x === COLS - 1 && i.y === ROWS - 1) { return null; } if (i.x < COLS - 1) { return { x: i.x + 1, y: i.y }; } return { x: 0, y: i.y + 1 }; } function valid_row(sudoku: Sudoku, i: Index): boolean { const seen = new Set(); for (let col = 0; col < COLS; col++) { const val = sudoku[i.y][col]; if (val !== 0) { if (seen.has(val)) { return false; } seen.add(val); } } return true; } function valid_col(sudoku: Sudoku, i: Index): boolean { const seen = new Set(); for (let row = 0; row < ROWS; row++) { const val = sudoku[row][i.x]; if (val !== 0) { if (seen.has(val)) { return false; } seen.add(val); } } return true; } function valid_square(sudoku: Sudoku, i: Index): boolean { const col_offset = Math.floor(i.x / 3) * 3; const row_offset = Math.floor(i.y / 3) * 3; const seen = new Set(); for (let row = 0; row < 3; row++) { for (let col = 0; col < 3; col++) { const val = sudoku[row + row_offset][col + col_offset]; if (val !== 0) { if (seen.has(val)) { return false; } seen.add(val); } } } return true; } export function solve(sudoku: Sudoku): boolean { sudoku = Sudoku.parse(sudoku); // Collect list of empty slots to fill. const slots: Index[] = []; { let slot: Index | null; for (slot = { x: 0, y: 0 }; slot !== null; slot = next_i(slot)) { if (sudoku[slot.y][slot.x] === 0) { slots.push(slot); } } } let i: number = 0; while (0 <= i && i < slots.length) { const slot = slots[i]; if (sudoku[slot.y][slot.x] === 9) { // no solution for this slot, clear and backtrack. sudoku[slot.y][slot.x] = 0; i = i - 1; continue; } // pick next sudoku[slot.y][slot.x] = sudoku[slot.y][slot.x] + 1; // check constraints if ( valid_row(sudoku, slot) && valid_col(sudoku, slot) && valid_square(sudoku, slot) ) { // move to next slot if valid, otherwise slot will be // incremented and tried again. i = i + 1; } } console.assert( i === -1 || i === slots.length, "Backtrack terminated in the middle somewhere." ); return i >= 0; } // Example const sudoku: Sudoku = [ [0, 0, 4, 5, 0, 0, 0, 8, 0], [3, 5, 7, 8, 0, 4, 6, 1, 0], [8, 1, 2, 0, 0, 6, 5, 0, 0], [0, 4, 0, 3, 8, 0, 7, 0, 0], [0, 0, 0, 0, 6, 0, 0, 9, 8], [0, 2, 8, 0, 5, 9, 0, 0, 0], [0, 6, 0, 0, 0, 0, 8, 3, 0], [5, 0, 1, 6, 7, 0, 9, 4, 2], [0, 7, 0, 0, 0, 0, 1, 0, 0], ]; solve(sudoku); print(sudoku);

sudoku_solver_brute_force

Version 3