Public
Script
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// 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 },
];
}
Val Town is a social website to write and deploy JavaScript.
Build APIs and schedule functions from your browser.
Comments
Nobody has commented on this val yet: be the first!
May 23, 2024