// This is another brute force with backtracking approach. // Instead of going cell by cell, it does what a human would do and // tries to pick a cell with the least number of possible values to fill in. // If there is only one possibility it picks it, if there is more than one it picks // the minimum value. Then when it gets into a state where it can't progress, it undoes // picks until it gets to one that had more than one possibility and picks the next one // then continues. import { Sudoku } from "https://esm.town/v/saolsen/sudoku"; type Cell = { row: number; col: number; }; type Val = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9; type PossibleValues = Array | null>>; type Constraint = { cell: Cell; value: Val }; function constrainRow(possible_values: PossibleValues, row: number, value: Val): Constraint[] { const constrained: Constraint[] = []; for (let col = 0; col < 9; col++) { const set = possible_values[row][col]; if (set !== null && set.has(value)) { set.delete(value); constrained.push({ cell: { row, col }, value }); } } return constrained; } function constrainCol(possible_values: PossibleValues, col: number, value: Val): Constraint[] { const constrained: Constraint[] = []; for (let row = 0; row < 9; row++) { const set = possible_values[row][col]; if (set !== null && set.has(value)) { set.delete(value); constrained.push({ cell: { row, col }, value }); } } return constrained; } function constrainBox(possible_values: PossibleValues, row: number, col: number, value: Val): Constraint[] { const constrained: Constraint[] = []; const box_row = Math.floor(row / 3); const box_col = Math.floor(col / 3); for (let row = box_row * 3; row < box_row * 3 + 3; row++) { for (let col = box_col * 3; col < box_col * 3 + 3; col++) { const set = possible_values[row][col]; if (set !== null && set.has(value)) { set.delete(value); constrained.push({ cell: { row, col }, value }); } } } return constrained; } function undoConstraints(possible_values: PossibleValues, constraints: Constraint[]) { for (const { cell: { row, col }, value } of constraints) { possible_values[row][col]!.add(value); } } // Lets try a "solve like a human" algorithm. export function solve(sudoku: Sudoku): Sudoku | null { sudoku = Sudoku.parse(sudoku); const possible_values: PossibleValues = []; for (let row = 0; row < 9; row++) { const row_possible_values: Set[] = []; for (let col = 0; col < 9; col++) { row_possible_values.push(new Set([1, 2, 3, 4, 5, 6, 7, 8, 9])); } possible_values.push(row_possible_values); } // Constrain the possible values based on the initial values. for (let row = 0; row < 9; row++) { for (let col = 0; col < 9; col++) { if (sudoku[row][col] !== 0) { const value = sudoku[row][col] as Val; // No possible values for this cell, it is already filled in. possible_values[row][col] = null; // Remove the value from the possible values for the row, column, and box. constrainRow(possible_values, row, value); constrainCol(possible_values, col, value); constrainBox(possible_values, row, col, value); } } } const selections: { row: number; col: number; val: Val; remaining_choices: Val[]; constraints: Constraint[]; }[] = []; while (true) { let min_size = Infinity; let selected_row = Infinity; let selected_col = Infinity; let selected_value: Val = 1; let remaining_choices: Val[] = []; let all_slots_filled = true; // Find the first cell with the minimum number of possible values. find_slot: for (let row = 0; row < 9; row++) { for (let col = 0; col < 9; col++) { const set = possible_values[row][col]; if (set !== null) { all_slots_filled = false; if (set.size === 0) { // Unsolvable Puzzle, backtrack. while (true) { const last_selection = selections.pop(); if (last_selection === undefined) { console.log("Unsolvable"); return null; } const { row: bt_row, col: bt_col, val: bt_val, remaining_choices: bt_choices, constraints } = last_selection; undoConstraints(possible_values, constraints); sudoku[bt_row][bt_col] = 0; possible_values[bt_row][bt_col] = new Set([bt_val, ...bt_choices]); if (bt_choices.length === 0) { // No more choices, backtrack further. continue; } selected_row = bt_row; selected_col = bt_col; remaining_choices = bt_choices; selected_value = remaining_choices.shift()!; break; } break find_slot; } else if (set.size < min_size) { selected_row = row; selected_col = col; min_size = set.size; remaining_choices = [...set.values()]; remaining_choices.sort((a, b) => a - b); selected_value = remaining_choices.shift()!; } } } } if (all_slots_filled) { return sudoku; } sudoku[selected_row][selected_col] = selected_value; possible_values[selected_row][selected_col] = null; const constrained_rows = constrainRow(possible_values, selected_row, selected_value); const constrained_cols = constrainCol(possible_values, selected_col, selected_value); const constrained_boxes = constrainBox(possible_values, selected_row, selected_col, selected_value); const constraints = [...constrained_boxes, ...constrained_cols, ...constrained_rows]; selections.push({ row: selected_row, col: selected_col, val: selected_value, remaining_choices, constraints, }); } }

sudoku_solver_human_search