Exact cover Sudoku solver
-------------------------
A Sudoku puzzle may be expressed and solved as an exact cover problem:
sudokuX←{⎕IO←1 ⍝ Exact cover Sudoku solver.
n n←⍴⍵ ⍝ n×n puzzle.
⍺←smat n ⍝ generic ⍵×⍵ constraint matrix.
r←∊(⍵≠0)>(⊂⍳n)∊¨⍵ ⍝ already placed rows.
m←(~r)⌿⍺ ⍝ reduced matrix.
f←X m ⍝ exact cover.
z←(~r)\f ⍝ merge of placements.
n n⍴z/(⍴z)⍴⍳n ⍝ solution matrix.
}
smat←{ ⍝ Matrix for ⍵ ⍵-Sudoku puzzle.
z←,[⍳6],[6+⍳4]⍳10⍴⍵*÷2 ⍝ cell coordinate properties.
row←↓1 1 0 0 1 1 1 1 1 1/↑z ⍝ each row must contain each number.
col←↓0 0 1 1 1 1 1 1 1 1/↑z ⍝ .. col .. .. .. .. .. ..
box←↓1 0 1 0 1 1 1 1 1 1/↑z ⍝ .. box .. .. .. .. .. ..
all←↓1 1 1 1 0 0 1 1 1 1/↑z ⍝ each cell must contain a number.
same←≡/∘(1 0 0 0 1 0 0 0∘⊂) ⍝ matching pairs.
same¨row,col,box,all ⍝ constraints matrix for ⍵ ⍵-puzzle.
}
s99 ⍝ puzzle
0 0 1 6 9 0 5 0 0
4 0 0 2 7 0 0 0 1
0 7 0 0 0 0 0 9 0
0 0 0 0 0 0 0 3 0
0 0 0 4 3 0 0 0 7
0 0 0 7 8 0 6 0 0
0 0 6 0 0 0 8 0 5
0 2 0 1 4 0 0 6 0
0 1 0 3 5 0 0 4 0
sudokuX s99 ⍝ solution.
2 8 1 6 9 3 5 7 4
4 6 9 2 7 5 3 8 1
5 7 3 8 1 4 2 9 6
7 9 2 5 6 1 4 3 8
6 5 8 4 3 9 1 2 7
1 3 4 7 8 2 6 5 9
3 4 6 9 2 7 8 1 5
9 2 5 1 4 8 7 6 3
8 1 7 3 5 6 9 4 2
Technical notes:
Each row in the constraints matrix (smat ⍵) represents the placement of a number
1..9 in one of the 9×9 cells:
9×9×9 → 729 rows.
There are four column groups to code for the requirement that each number 1..9
be represented in each of 9 rows (ColsR), 9 columns (ColsC) and 9 boxes (ColsB),
together with the rule that every cell be occupied (ColsA).
4×9×9 → 324 columns.
This (⍵ 4×⍵*2) boolean constraint matrix is invariant for a square sudoku puzzle
of size ⍵ ⍵ and may be pre-fabricated and used for any number of specific inst-
ances of puzzles of this size.
Labelling the Rows, Cols and Boxes of a shape ⍵ ⍵ Sudoku puzzle: R1..R⍵, C2..C⍵,
B1..B⍵, and calling the four column groups ColsR, ColsC, ColsB and ColsA:
Rows: ⍵×⍵×⍵ possible actions:
Place; 1 in R1C1; place 2 in R1C1; ... place ⍵ in R1C1;
Place; 1 in R1C2; place 2 in R1C2; ... place ⍵ in R1C2;
...
Place; 1 in R⍵C⍵; place 2 in R⍵C⍵; ... place ⍵ in R⍵C⍵.
ColsR ⍵×⍵ requirements (all numbers appear in each puzzle Row):
R1 contains 1; R1 contains 2; ... R1 contains ⍵;
R2 contains 1; R2 contains 2; ... R2 contains ⍵;
...
R⍵ contains 1; R⍵ contains 2; ... R⍵ contains ⍵.
ColsC ⍵×⍵ requirements (all numbers appear in each puzzle Col):
C1 contains 1; C1 contains 2; ... C1 contains ⍵;
C2 contains 1; C2 contains 2; ... C2 contains ⍵;
...
C⍵ contains 1; C⍵ contains 2; ... C⍵ contains ⍵.
ColsB ⍵×⍵ requirements (all numbers appear in each puzzle Box):
B1 contains 1; B1 contains 2; ... B1 contains ⍵;
B2 contains 1; B2 contains 2; ... B2 contains ⍵;
...
B⍵ contains 1; B⍵ contains 2; ... B⍵ contains ⍵.
ColsA ⍵×⍵ requirements (each cell is occupied at most once):
R1C1 occupied; R1C2 occupied; ... R1C⍵ occupied;
R2C1 occupied; R2C2 occupied; ... R2C⍵ occupied;
...
R⍵C1 occupied; R⍵C2 occupied; ... R⍵C⍵ occupied;
Given a specific puzzle to be solved, rows are removed from a copy of this gen-
eric matrix to represent numbers that may not be placed in pre-populated cells.
For example, given the 4×4 puzzle:
0 0 0 0
0 0 2 1
3 0 0 4
0 0 0 0
we would remove 12 rows corresponding to placements of:
m[2;3]←2 → remove 3 rows m[2;3] ∊ 1 3 4
m[2;4]←1 → remove 3 rows m[2;4] ∊ 2 3 4
m[3;1]←3 → remove 3 rows m[3;1] ∊ 1 2 4
m[3;4]←4 → remove 3 rows m[3;4] ∊ 1 2 3
Coding details
--------------
For the solver:
sudokuX←{⎕IO←1 ⍝ Exact cover Sudoku solver.
n n←⍴⍵ ⍝ n×n puzzle.
⍺←smat n ⍝ generic ⍵×⍵ constraint matrix.
r←∊(⍵≠0)>(⊂⍳n)∊¨⍵ ⍝ already placed rows.
m←(~r)⌿⍺ ⍝ reduced matrix.
f←X m ⍝ exact cover.
z←(~r)\f ⍝ merge of placements.
n n⍴z/(⍴z)⍴⍳n ⍝ solution matrix.
}
Taking the lines one at a time:
[0] sudokuX←{⎕IO←1 ⍝ Exact cover Sudoku solver.
Index-origin is set to 1 so that ⍳9 produces numbers 1..9, leaving 0 free for
unoccupied cells.
Migration level is set to 1 for the enlist (∊) function on line[3].
[1] n n←⍴⍵ ⍝ n×n puzzle.
Sets n to the scalar value of the number of rows (and columns) of the square
puzzle. The squareness =/⍴⍵ is not enforced by this statement and in fact n
winds up as the number of columns, irrespective of the number of rows. But the
code at least hints that the number of rows and columns is assumed to be the
same.
[2] ⍺←smat n ⍝ generic ⍵ ⍵-matrix.
A pre-computed generic contraints matrix may be passed as left argument but, if
not, this statement computes it. Doing so takes a second or so, so it is worth-
while storing the value if many puzzles of a particular size are to be solved.
The boolean matrix could be bound (composed) with the solver to derive a new
monadic function, thus:
sx99 ← (smat 9 9)∘sudokuX ⍝ 9 9-sudoku solver.
[3] r←∊(⍵≠0)>(⊂⍳n)∊¨⍵ ⍝ already placed rows.
Give the above 4×4 puzzle,
0 0 0 0
0 0 2 1
3 0 0 4
0 0 0 0
the rightmost segment of this line:
r←∊(⍵≠0)>(⊂⍳n)∊¨⍵ ⍝ already placed rows.
¯¯¯¯¯¯¯¯
produces a matrix of masks for the already placed numbers.
┌→──────┬───────┬───────┬───────┐
↓0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│
├~─────→┼~─────→┼~─────→┼~─────→┤
│0 0 0 0│0 0 0 0│0 1 0 0│1 0 0 0│
├~─────→┼~─────→┼~─────→┼~─────→┤
│0 0 1 0│0 0 0 0│0 0 0 0│0 0 0 1│
├~─────→┼~─────→┼~─────→┼~─────→┤
│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│
└~─────→┴~─────→┴~─────→┴~─────→┘
the second part:
r←∊(⍵≠0)>(⊂⍳n)∊¨⍵ ⍝ already placed rows.
¯¯¯¯¯¯
delivers a matrix of masks of disallowed numbers per cell:
┌→──────┬───────┬───────┬───────┐
↓0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│
├~─────→┼~─────→┼~─────→┼~─────→┤
│0 0 0 0│0 0 0 0│1 0 1 1│0 1 1 1│
├~─────→┼~─────→┼~─────→┼~─────→┤
│1 1 0 1│0 0 0 0│0 0 0 0│1 1 1 0│
├~─────→┼~─────→┼~─────→┼~─────→┤
│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│
└~─────→┴~─────→┴~─────→┴~─────→┘
... the enlist (∊) of which is a boolean mask vector of which rows are to be re-
moved from the constraint matrix for this puzzle instance, as in the following
line:
[4] m←(~r)⌿⍺ ⍝ reduced matrix.
m is a reduced-rows matrix for this puzzle instance.
[5] f←X m ⍝ exact cover.
Line[5] finds the exact cover for the reduced matrix and line[6]:
[6] z←(~r)\f ⍝ merge of placements.
... expands this to a row selection for the presented puzzle, including its pre-
placed numbers. Finally, line[7]:
[7] n n⍴z/(⍴z)⍴⍳n ⍝ solution matrix.
presents this allocation of numbers to cells as a solution in the standard form:
2 1 4 3
4 3 2 1
3 2 1 4
1 4 3 2
For the function that generates the generic constraints matrix:
smat←{ ⍝ Matrix for ⍵ ⍵-Sudoku puzzle.
z←,[⍳6],[6+⍳4]⍳10⍴⍵*÷2 ⍝ cell coordinate properties.
row←↓1 1 0 0 1 1 1 1 1 1/↑z ⍝ each row must contain each number.
col←↓0 0 1 1 1 1 1 1 1 1/↑z ⍝ .. col .. .. .. .. .. ..
box←↓1 0 1 0 1 1 1 1 1 1/↑z ⍝ .. box .. .. .. .. .. ..
all←↓1 1 1 1 0 0 1 1 1 1/↑z ⍝ each cell must contain a number.
same←≡/∘(1 0 0 0 1 0 0 0∘⊂) ⍝ matching pairs.
same¨row,col,box,all ⍝ constraints matrix for ⍵ ⍵-puzzle.
}
Taking the lines one at a time:
[1] z←,[⍳6],[6+⍳4]⍳10⍴⍵*÷2 ⍝ cell coordinate properties.
It is easier to address the cells at square-within-box resolution. For the above
4×4 puzzle:
┌───┬───┬───┬───┐
│ 0 │ 0 │ 0 │ 0 │
├───┼───┼───┼───┤
│ 0 │ 0 │ 2 │ 1 │
├───┼───┼───┼───┤
│ 3 │ 0 │ 0 │ 4 │
├───┼───┼───┼───┤
│ 0 │ 0 │ 0 │ 0 │
└───┴───┴───┴───┘
The cell coordinates would be:
┌─────────────────────┬─────────────────────┐
│┌─────────┬─────────┐│┌─────────┬─────────┐│
││┌───┬───┐│┌───┬───┐│││┌───┬───┐│┌───┬───┐││
│││1 1│1 1│││1 1│1 2│││││1 2│1 1│││1 2│1 2│││
││└───┴───┘│└───┴───┘│││└───┴───┘│└───┴───┘││
│├─────────┼─────────┤│├─────────┼─────────┤│
││┌───┬───┐│┌───┬───┐│││┌───┬───┐│┌───┬───┐││
│││1 1│2 1│││1 1│2 2│││││1 2│2 1│││1 2│2 2│││
││└───┴───┘│└───┴───┘│││└───┴───┘│└───┴───┘││
│└─────────┴─────────┘│└─────────┴─────────┘│
├─────────────────────┼─────────────────────┤
│┌─────────┬─────────┐│┌─────────┬─────────┐│
││┌───┬───┐│┌───┬───┐│││┌───┬───┐│┌───┬───┐││
│││2 1│1 1│││2 1│1 2│││││2 2│1 1│││2 2│1 2│││
││└───┴───┘│└───┴───┘│││└───┴───┘│└───┴───┘││
│├─────────┼─────────┤│├─────────┼─────────┤│
││┌───┬───┐│┌───┬───┐│││┌───┬───┐│┌───┬───┐││
│││2 1│2 1│││2 1│2 2│││││2 2│2 1│││2 2│2 2│││
││└───┴───┘│└───┴───┘│││└───┴───┘│└───┴───┘││
│└─────────┴─────────┘│└─────────┴─────────┘│
└─────────────────────┴─────────────────────┘
For example, the coordinates of the 4 in the third row, fourth column, are:
┌───┬───┐
│2 2│1 2│ box:2 2 ; cell:1 2
└───┴───┘
It is convenient also to represent the numbers to be placed as a base ⍵*÷2 pair.
For a 9×9 puzzle, numbers 1..9 are represented:
┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
│1 1│1 2│1 3│2 1│2 2│2 3│3 1│3 2│3 3│
└───┴───┴───┴───┴───┴───┴───┴───┴───┘
so, for example, the number 4 is represented as 2 1.
This means that the rank-10 array:
z←,[⍳6],[6+⍳4]⍳10⍴⍵*÷2 ⍝ cell coordinate properties.
¯¯¯¯¯¯¯¯
encodes sufficient information to generate the constraint matrix. Ravelling the
first six and last four axes:
z←,[⍳6],[6+⍳4]⍳10⍴⍵*÷2 ⍝ cell coordinate properties.
¯¯¯¯¯¯¯¯¯¯¯¯
produces a rank-2 (⍵ 4×⍵*2)-matrix, each of whose items is a 10-vector of the
properties of that particular constraint:
br bc cr cc hi lo xr xc hi lo
└─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘
│ │ │ │ └─── number: high/low digit.
│ │ │ └────────── row/col coordinate.
│ │ │
│ │ └────────────────── number: high/low digit.
│ └───────────────────────── cell-within-box row/col coords.
└──────────────────────────────── box row/col coords.
Lines[2-5] can then select four coord/number pairs for comparison:
[2] row←↓1 1 0 0 1 1 1 1 1 1/↑z ⍝ each row must contain each number.
[3] col←↓0 0 1 1 1 1 1 1 1 1/↑z ⍝ .. col .. .. .. .. .. ..
[4] box←↓1 0 1 0 1 1 1 1 1 1/↑z ⍝ .. box .. .. .. .. .. ..
[5] all←↓1 1 1 1 0 0 1 1 1 1/↑z ⍝ each cell must contain a number.
Line[6] defines a function for separation and comparison of the items of each
pair:
[6] same←≡/∘(1 0 0 0 1 0 0 0∘⊂) ⍝ matching pairs.
and finally, line[7] applies this function to the catenation of the four column
groups:
[7] same¨row,col,box,all ⍝ constraints matrix for ⍵ ⍵-puzzle.
Back to →X←
See also: sudoku sudoku_bfs X
Back to: contents
Back to: Workspaces