// Exact Cover Sudoku Solver import { Sudoku } from "https://esm.town/v/saolsen/sudoku"; // An exact cover problem is solved by taking a list of possible constraint // rows and finding a subset of them that covers each column exactly once. // If thought of as a binary matrix, we would want to find a set of rows // such that each column has exactly one 1 in it. // To express sudoku as an exact cover problem, we need to encode all the // possible numbers that can go into each slot, along with their // constraints, in a way that obeys the rules of sudoku. // There will be columns for each slot, row, column, and box, // So there will be a row for each number and slot for each combination of // constraints. // eg [1,0...0, 1,0.....0,...] and // [1,0...0, 0,1,0...0,...] are both solutions with 1 in the first slot, // but the first also says that the 1 is in the first column and the second // says that the 1 is in the second column. This way we can account for the // constraints of the sudoku board and when we find a covering set of rows // we know it is a valid solution to the sudoku board. // The full matrix looks like this // https://www.stolaf.edu/people/hansonr/sudoku/exactcovermatrix.htm // Each column is a constraint, each row is a possible solution // you pick a row to add to the solution, then cover up all the columns // that have been satisfied, and all the rows that conflict with an already // satisfied constraint. Then you have a smaller sub-matrix to continue // picking rows from. // Instead of actually using a matrix with so many columns, we can use a // sparse representation, since most columns will be 0. We can make // nodes for each of the 1s in the matrix and link them together in a // linked list. // By using a doubly linked list for the sparse matrix, we can easily remove // and replace columns and rows from the matrix to make the search for a // solution faster. // The algorithm is called "Dancing Links" and it is actually pretty similar // to the brute force backtracking algorithm. Instead of trying every // possible number in every slot (and backtracking on failures), we select a // slot value that we know doesn't conflict with any of the already resolved // constraints, and then we remove all rows with constraints that are satisfied by // the slot value so there are a lot fewer possibilities to try next and the search // is much faster. // There is some value for row,col // This constraint makes sure the puzzle is fully filled out. type SlotConstraint = { kind: "slot"; row: number; // 0-8 col: number; // 0-8 }; // The value `value` is in row `row`. // This constraint makes sure that each row has each number exactly once. type RowConstraint = { kind: "row"; row: number; // 0-8 value: number; // 1-9 }; // The value `value` is in col `col`. // This constraint makes sure that each column has each number exactly once. type ColConstraint = { kind: "col"; col: number; // 0-8 value: number; // 1-9 }; // The value `value` is in box `box`. // This constraint makes sure that each box has each number exactly once. type BoxConstraint = { kind: "box"; box: number; // 0-8 value: number; // 1-9 }; type Constraint = SlotConstraint | RowConstraint | ColConstraint | BoxConstraint; const NUM_CONSTRAINTS = 324; type Slot = { row: number; // 0-8 col: number; // 0-8 value: number; // 1-9 }; function slotToConstraints(slot: Slot): Constraint[] { console.assert(slot.row >= 0 && slot.row <= 8); console.assert(slot.col >= 0 && slot.col <= 8); console.assert(slot.value >= 1 && slot.value <= 9); const { row, col, value } = slot; const box = Math.floor(row / 3) * 3 + Math.floor(col / 3); return [ { kind: "slot", row, col }, { kind: "row", row, value }, { kind: "col", col, value }, { kind: "box", box, value }, ]; } function constraintsToSlot(constraints: Constraint[]): Slot { console.assert(constraints.length === 4); let row = null; let col = null; let value = null; for (let i = 0; i < constraints.length; i++) { const constraint = constraints[i]; switch (constraint.kind) { case "slot": if (row !== null) { console.assert(row === constraint.row); } if (col !== null) { console.assert(col === constraint.col); } row = constraint.row; col = constraint.col; break; case "row": if (row !== null) { console.assert(row === constraint.row); } if (value !== null) { console.assert(value === constraint.value); } row = constraint.row; value = constraint.value; break; case "col": if (col !== null) { console.assert(col === constraint.col); } if (value !== null) { console.assert(value === constraint.value); } col = constraint.col; value = constraint.value; break; case "box": if (value !== null) { console.assert(value === constraint.value); } value = constraint.value; break; } } console.assert(row !== null && col !== null && value !== null); return { row: row!, col: col!, value: value! }; } function cIndex(constraint: Constraint): number { switch (constraint.kind) { case "slot": return constraint.row * 9 + constraint.col; case "row": return 9 * 9 + constraint.row * 9 + constraint.value - 1; case "col": return 9 * 9 + 9 * 9 + constraint.col * 9 + constraint.value - 1; case "box": return 9 * 9 + 9 * 9 + 9 * 9 + constraint.box * 9 + constraint.value - 1; } } type Node = { head: number; prev: number; next: number; up: number; down: number; }; type Column = Node & { constraint: Constraint; count: number; }; class Matrix { count: number; root: number; nodes: (Node | Column)[]; constructor() { const constraints: Constraint[] = []; for (let row = 0; row < 9; row++) { for (let col = 0; col < 9; col++) { constraints.push({ kind: "slot", row, col }); } } for (let row = 0; row < 9; row++) { for (let value = 1; value <= 9; value++) { constraints.push({ kind: "row", row, value }); } } for (let col = 0; col < 9; col++) { for (let value = 1; value <= 9; value++) { constraints.push({ kind: "col", col, value }); } } for (let box = 0; box < 9; box++) { for (let value = 1; value <= 9; value++) { constraints.push({ kind: "box", box, value }); } } console.assert(constraints.length === NUM_CONSTRAINTS); const nodes: (Node | Column)[] = []; // Create a column header node for each constraint. for (let i = 0; i < constraints.length; i++) { const constraint = constraints[i]; // Assert the constraint order matches the index helper. console.assert(cIndex(constraint) === i); console.assert(i === nodes.length); const head = i; const prev = i === 0 ? NUM_CONSTRAINTS - 1 : i - 1; const next = i === NUM_CONSTRAINTS - 1 ? 0 : i + 1; const up = i; const down = i; const count = 0; nodes.push({ head, prev, next, up, down, constraint, count }); } // For each possible slot value. // Add a row of nodes for each constraint it satisfies. for (let row = 0; row < 9; row++) { for (let col = 0; col < 9; col++) { for (let value = 1; value <= 9; value++) { const slot = { row, col, value }; const constraints = slotToConstraints(slot); console.assert(constraints.length === 4); const i = nodes.length; // Add the nodes as a linked row. nodes.push({ head: cIndex(constraints[0]), prev: i + 3, next: i + 1, up: -1, down: -1 }); nodes.push({ head: cIndex(constraints[1]), prev: i, next: i + 2, up: -1, down: -1 }); nodes.push({ head: cIndex(constraints[2]), prev: i + 1, next: i + 3, up: -1, down: -1 }); nodes.push({ head: cIndex(constraints[3]), prev: i + 2, next: i, up: -1, down: -1 }); // Append each node to its column list. for (let n_i = i; n_i <= i + 3; n_i++) { const node = nodes[n_i] as Node; const column = nodes[node.head] as Column; const last_n_i = column.up; nodes[last_n_i].down = n_i; nodes[n_i].up = last_n_i; nodes[n_i].down = node.head; nodes[node.head].up = n_i; (nodes[node.head] as Column).count++; } } } } this.count = NUM_CONSTRAINTS; this.root = 0; this.nodes = nodes; } isSolvable(): boolean { // If the matrix is empty, then the puzzle is solved. if (this.count === 0) { return true; } // If any uncovered column is empty, then the puzzle is unsolvable. let i = this.root; do { const column = this.nodes[i] as Column; if (column.count === 0) { return false; } i = column.next; } while (i !== this.root); return true; } rowConstraints(n_i: number): Constraint[] { const constraints: Constraint[] = []; let i = n_i; do { const node = this.nodes[i]; const column = this.nodes[node.head] as Column; constraints.push(column.constraint); i = node.next; } while (i !== n_i); return constraints; } shortestColumn(): number { console.assert(this.count > 0); let count = Infinity; let shortest = Infinity; let i = this.root; do { const column = this.nodes[i] as Column; if (column.count === count) { if (i < shortest) { shortest = i; } } else if (column.count < count) { count = column.count; shortest = i; } i = column.next; } while (i !== this.root); return shortest; } cover(c_i: number): void { const column = this.nodes[c_i] as Column; // Remove the column from the list of columns. this.nodes[column.prev].next = column.next; this.nodes[column.next].prev = column.prev; this.count--; // Walk down the column. for (let n_i = column.down; n_i !== c_i; n_i = this.nodes[n_i].down) { // Walk right across the row. for (let i = this.nodes[n_i].next; i !== n_i; i = this.nodes[i].next) { const node = this.nodes[i]; this.nodes[node.up].down = node.down; this.nodes[node.down].up = node.up; (this.nodes[node.head] as Column).count--; } } // If the column is the root, update the root. if (this.root === c_i) { this.root = column.next; } } uncover(c_i: number): void { const column = this.nodes[c_i] as Column; // Walk up the column. for (let n_i = column.up; n_i !== c_i; n_i = this.nodes[n_i].up) { // Walk left across the row. for (let i = this.nodes[n_i].prev; i !== n_i; i = this.nodes[i].prev) { const node = this.nodes[i]; this.nodes[node.down].up = i; this.nodes[node.up].down = i; (this.nodes[node.head] as Column).count++; } } // Return the column from the list of columns. this.nodes[column.prev].next = c_i; this.nodes[column.next].prev = c_i; this.count++; } } export function solve(sudoku: Sudoku): Sudoku | null { sudoku = Sudoku.parse(sudoku); const matrix = new Matrix(); // Cover all columns satisfied by the already filled slots. for (let row = 0; row < 9; row++) { for (let col = 0; col < 9; col++) { const value = sudoku[row][col]; if (value !== 0) { const slot = { row, col, value }; const constraints = slotToConstraints(slot); for (let i = 0; i < constraints.length; i++) { const c_i = cIndex(constraints[i]); matrix.cover(c_i); } } } } if (!matrix.isSolvable()) { console.log("Unsolvable"); return null; } const solution: { slot: Slot; n_i: number }[] = []; while (matrix.count > 0) { let n_i = 0; let node: Node; if (matrix.isSolvable()) { // Pick the column with the fewest nodes const c_i = matrix.shortestColumn(); const column = matrix.nodes[c_i] as Column; // Pick the first node in the column n_i = column.down; node = matrix.nodes[n_i]; } else { // Backtrack do { const last_slot = solution.pop(); if (last_slot === undefined) { console.log("Unsolvable"); return null; } // Uncover the columns. const { slot, n_i: last_n_i } = last_slot; const constraints = slotToConstraints(slot); for (let i = constraints.length - 1; i >= 0; i--) { const c_i = cIndex(constraints[i]); matrix.uncover(c_i); } // Choose the next node in the column. n_i = matrix.nodes[last_n_i].down; node = matrix.nodes[n_i]; } while (n_i === node.head); } const row_constraints = matrix.rowConstraints(n_i); const slot = constraintsToSlot(row_constraints); solution.push({ slot, n_i }); for (let i = 0; i < row_constraints.length; i++) { const c_i = cIndex(row_constraints[i]); matrix.cover(c_i); } } // Fill in the solution slots. for (let i = 0; i < solution.length; i++) { const { slot } = solution[i]; sudoku[slot.row][slot.col] = slot.value; } return sudoku; }

sudoku_solver_exact_cover