Sodoku Solver#
Let’s begin by developing a “contention map”, which shows, for each cell in an ⍵×⍵ Sudoku puzzle, those cells that occupy the same row, column or box:
⍝ CONTENTION MAP
3 3⍴⍳3×3 ⍝ matrix of box numbers
If this expression is not clear, edit and resubmit part of it.
APL functions apply to everything to their right, so you can experiment by removing functions from the left of any expression before continuing with the script.
3/3 3⍴⍳3×3 ⍝ 3-replicated (/) along rows
3⌿3/3 3⍴⍳3×3 ⍝ 3-replicated (⌿) down columns
Based on the above, the following function generates this matrix of box numbers for boxes of shape ⍵ ⍵:
box ← {⍵⌿⍵/⍵ ⍵⍴⍳⍵×⍵} ⍝ fn: box numbers
box 3 ⍝ 3×3 boxes for 9×9 puzzle
We’ll start with a smaller, 4×4 Sudoku:
box 2 ⍝ 2×2 boxes for 4×4 puzzle
Primitive function (⍳) generates an ⍵-array of indices. For a matrix, each 2-vector is a row and column number:
⍳ 4 4 ⍝ row and column numbers
Primitive operator each (¨) applies its operand function between corresponding items of its argument arrays.
Catenating (,) each row-col vector with its box number produces a matrix of row-col-box triples:
(⍳4 4) ,¨ box 2 ⍝ row, column and box numbers
For a square Sudoku puzzle, the box size is the square-root of the puzzle size.
In APL, the square-root of ⍵ is expressed as ⍵ to the power (*) one-half (÷2):
25 49 * ÷2 ⍝ to the power reciprocal 2
… leading to the following function in which ⊃⍵*÷2 means the first (⊃) item of the square-root of the right argument (⍵):
rcb ← {(⍳⍵),¨box⊃⍵*÷2} ⍝ fn: row-col-box numbers
rcb 4 4 ⍝ ... for a 4×4 sudoku puzzle
Contention occurs between cells that contain corresponding row, column or box numbers.
Here are the cells that share a row, column or box with the cell (⊂) in the second row, second column:
(rcb 4 4) = ⊂2 2 1 ⍝ cells that share row-col-box with 2 2
Each (¨) vector in the above, of which 1 is a member (∊), represents a row, column or box contention:
1 ∊¨ (rcb 4 4)=⊂2 2 1 ⍝ cells in contention with cell at 2 2
Outer-product (∘.) produces a rank 4 (4×4×4×4) array of all comparisons. As the leading axes of this 256-item array are displayed down the page, it is rather long:
1 ∊¨ (rcb 4 4) ∘.= rcb 4 4 ⍝ complete contention array
Enclosing (⊂) the first two axes [⍳2] gives us a 4x4 map of 4×4 contention matrices.
⊂[⍳2] 1 ∊¨ (rcb 4 4) ∘.= rcb 4 4 ⍝ map of contention matrices
Abstracting this as a function of rcb 4 4:
{⊂[⍳2] 1∊¨ ⍵∘.=⍵} rcb 4 4 ⍝ contention map
and naming the function:
cmap ← {⊂[⍳2] 1∊¨ ⍵∘.=⍵} ⍝ fn: contention map for ⍵-puzzle
cmap rcb 4 4 ⍝ contention matrices for 4 4 puzzle
Now let’s turn our attention to searching for a solution. We use a breadth-first search technique:
⍝ Breadth-first search
Here is a small Sudoku puzzle to be solved:
⊢s44 ← 4 4⍴ 0 0 0 0 0 0 2 1 3 0 0 4 0 0 0 0 ⍝ 4×4 Sudoku puzzle
The shape (⍴) of s44 is the vector 4 4:
⍴ s44 ⍝ shape of matrix s44
Primitive index function (⌷) selects item(s) from an array. Starting (say) at row 1, column 1:
⊃1 1⌷cmap rcb ⍴s44 ⍝ contention for cell at 1 1
The product (×) of this matrix with the current state shows which numbers may not be placed at 1 1:
s44 × ⊃1 1⌷cmap rcb ⍴s44 ⍝ number(s) excluded from posn 1 1
Excluding (~) these numbers (just the number 3 in this case)
from all possible numbers (⍳4) reveals which
numbers are still available for placing at 1 1:
(⍳4) ~ s44×⊃1 1⌷cmap rcb ⍴s44 ⍝ plays still available at 1 1
with function:
avl ← {(⍳⊃⍴⍵) ~ ⍵×⊃⍺⌷cmap rcb ⍴⍵} ⍝ fn: available plays at ⍺ for state ⍵
1 1 avl s44 ⍝ available plays at 1 1 in s44
We need a way to place a given number at a particular position in a given state matrix.
As this operation requires three arguments (number position state),
it is convenient to code it as an operator with
⍺-number ⍺⍺-posn ⍵-state.
We can place the number in a given position with
primitive function take (↑):
2 3↑99 ⍝ 99 extended downwards and rightwards
¯2 ¯3↑99 ⍝ 99 extended upwards and leftwards
4 4↑¯3 ¯3↑99 ⍝ 99 at 3 3 in empty 4 4 grid
… and adding the current state:
s44 + 4 4↑¯3 ¯3↑99 ⍝ 99 at 3 3 in s44
… giving us this “merge” operator:
at ← {⍵+(⍴⍵)↑(-⍺⍺)↑⍺} ⍝ op: ⍺ at ⍺⍺ in ⍵
99 (3 3 at) s44 ⍝ 99 at 3 3 in s44
Now, merging each (¨) available state:
1 2 4 (1 1 at)¨ ⊂s44 ⍝ next states of s44 at 1 1
Using our avl function to generate the vector of available plays:
(1 1 avl s44) (1 1 at)¨ ⊂s44 ⍝ next states of s44 at 1 1
… suggesting this function for a vector of available states:
nxt ← {(⍺ avl ⍵)(⍺ at)¨⊂⍵} ⍝ fn: next states of ⍵ at ⍺
1 1 nxt s44 ⍝ next states of s44 at 1 1
For the following move, we find each possible next state for each of these states, choosing a second cell at which to play.
In this way, we start to explore the tree of possibilities, one level at a time.
Let’s continue from position 1 2. Notice that we bind (∘)
left argument 1 2 to function nxt, so that the whole of the vector
constitutes the left argument for each (¨) application.
1 2∘nxt¨ 1 1 nxt s44 ⍝ two levels of tree-search
The primitive reduction operator (/), applied to a vector,
has the effect of placing its left operand function between each item of its right argument,
to produce a scalar result.
We can join the sub-vectors with a catenate (,)
reduction (/) of the vector of vectors and disclosing
(⊃) the resulting scalar:
⊃,/ 1 2∘nxt¨ 1 1 nxt s44 ⍝ two levels of tree-search
In order that the initial state is not a special case,
it helps to start with a 1-vector by ravelling (,)
the enclose (⊂) of the puzzle matrix:
⊃,/1 2∘nxt¨ ⊃,/1 1∘nxt¨ ,⊂s44 ⍝ 2-level search
Continuing from position 2 1:
⊃,/2 1∘nxt¨ ⊃,/1 2∘nxt¨ ⊃,/1 1∘nxt¨ ,⊂s44 ⍝ 3-level search
Next, we extract the positions (2 1), (1 2) and (1 1) as left argument (⍺) to a containing function:
For example: ⊃,/1 2∘nxt¨...
becomes: 1 2{⊃,/⍺∘nxt¨⍵}...
nxtv ← {⊃,/⍺∘nxt¨ ⍵} ⍝ fn: next state vector
2 1 nxtv 1 2 nxtv 1 1 nxtv ,⊂s44 ⍝ 3-level search
“Factoring out” the nxtv function as a reduction (/), we recode the above 3-level search as:
⊃nxtv/ (2 1)(1 2)(1 1)(,⊂s44) ⍝ 3-level search
Choosing cell (1 3) for our next step:
⊃nxtv/ (1 3)(2 1)(1 2)(1 1)(,⊂s44) ⍝ 4-level search
The order of selecting the cells for the search is unimportant. Let’s continue from (4 2):
⊃nxtv/ (4 2)(1 3)(2 1)(1 2)(1 1)(,⊂s44) ⍝ 5-level search
… (3 2) …
⊃nxtv/ (3 2)(4 2)(1 3)(2 1)(1 2)(1 1)(,⊂s44) ⍝ 6-level search
… and (1 4):
⊃nxtv/ (1 4)(3 2)(4 2)(1 3)(2 1)(1 2)(1 1)(,⊂s44) ⍝ 7-level search
You might like to take a moment to find the complete solution by extending the above list, one item at a time, using the remaining empty cell coordinates: (4 4) (4 3) (2 2) (3 3) (4 1).
For a complete search, we just need to supply our reduction with a vector of the positions of all empty cells.
Here is the matrix of all cell positions:
⍳⍴ s44 ⍝ matrix of positions
of which, these are the empty ones:
s44=0 ⍝ 1 → empty cell
Primitive function ravel (,) returns a vector of the items of its argument array:
, ⍳⍴ s44 ⍝ vector of positions
, s44=0 ⍝ vector of empties
Replicate (/) selects empty cells:
(,s44=0)/,⍳⍴s44 ⍝ positions of empty cells
giving function:
emt ← {(,⍵=0)/,⍳⍴⍵} ⍝ fn: empty cell positions in state ⍵
emt s44 ⍝ empty cell positions in s44
We can now find a vector of complete states. In general, there may be many solutions although published Sudoku puzzles typically have only one.
⊃nxtv/(emt s44),⊂,⊂s44 ⍝ vector of all solutions.
Abstracting this as a function of the puzzle matrix s44:
svec ← {⊃nxtv/(emt ⍵),⊂,⊂⍵} ⍝ fn: solution vector
svec s44 ⍝ solution(s) for s44
The following little function nests the boxes of a Sudoku state. A 9×9 puzzle will appear as a 3×3 matrix of 3×3 boxes:
(It is left as an “exercise for the student” to figure out how this works.)
sfmt←{⊂[3 4]1 3 2 4⍉(2/(⍴⍵)*÷2)⍴⍵} ⍝ pleasing format
sfmt s44 ⍝ initial state and
sfmt ⊃svec s44 ⍝ ... first (⊃) solution
The coding of svec is rather inefficient because it re-calculates cmap rcb at each step:
svec ⍝ svec calls nxtv for each free cell,
nxtv ⍝ nxtv calls nxt for each state,
nxt ⍝ nxt calls avl and
avl ⍝ avl calls cmap rcb ⍴⍵.
We can arrange to calculate (cmap rcb ⍴⍵) only once and passing it as an additional operand from svec to nxtv to nxt to avl.
We do this by making avl, nxt and nxtv into operators, and receiving additional parameter (cmap rcb ⍴⍵) as operand ⍺⍺. Compare these re-codings with the original versions:
avl←{(⍳⊃⍴⍵)~⍵×⊃⍺⌷⍺⍺} ⍝ op avl: receives (cmap rcb ⍴⍵) as ⍺⍺ from
nxt←{(⍺(⍺⍺ avl)⍵)(⍺ at)¨⊂⍵} ⍝ op nxt: receives (cmap rcb ⍴⍵) as ⍺⍺ from
nxtv←{⊃,/⍺∘(⍺⍺ nxt)¨⍵} ⍝ op nxtv: receives (cmap rcb ⍴⍵) as ⍺⍺ from
svec←{⊃(⍺⍺ ⍴⍵)nxtv/(emt ⍵),⊂⊂⍵} ⍝ op svec: receives (cmap∘rcb) as operand ⍺⍺.
Binding (∘) cmap with rcb as a function operand to svec:
sfmt ⊃ cmap∘rcb svec s44 ⍝ ... first (⊃) solution
Now we’re in a position to try a larger puzzle.
The following sequence specifies each row, starting with a 9×9 matrix of zeros:
s99 ← 9 9⍴0 ⍝ input of 9×9 puzzle ...
s99[1;] ← 0 0 1 6 9 0 5 0 0 ⍝ 1st row
s99[2;] ← 4 0 0 2 7 0 0 0 1 ⍝ 2nd row
s99[3;] ← 0 7 0 0 0 0 0 9 0 ⍝ 3rd row
s99[4;] ← 0 0 0 0 0 0 0 3 0 ⍝ 4th row
s99[5;] ← 0 0 0 4 3 0 0 0 7 ⍝ 5th row
s99[6;] ← 0 0 0 7 8 0 6 0 0 ⍝ 6th row
s99[7;] ← 0 0 6 0 0 0 8 0 5 ⍝ 7th row
s99[8;] ← 0 2 0 1 4 0 0 6 0 ⍝ 8th row
s99[9;] ← 0 1 0 3 5 0 0 4 0 ⍝ 9th row
Display of initial state of 9×9 puzzle:
sfmt s99 ⍝ 9×9 sudoku puzzle
Naming a function for the format of the first (⊃) solution:
sudoku ← {sfmt⊃cmap∘rcb svec ⍵} ⍝ Sudoku solver
sudoku s44 ⍝ first solution of smaller puzzle.
sudoku s99 ⍝ first solution of larger puzzle
A Generalisation#
APL makes it easy to extend functions to arrays of higher rank.
To demonstrate this, let’s convert our code to solve a 3D variant of Sudoku.
⍝ 3D Sudoku
s333 ← 3 3 3⍴0 ⍝ input of 3×3×3 puzzle
s333[1;;] ← 3 3 ⍴ 0 0 0 8 1 0 0 0 2 ⍝ 1st plane
s333[2;;] ← 3 3 ⍴ 0 6 0 0 7 0 9 0 4 ⍝ 2nd plane
s333[3;;] ← 3 3 ⍴ 5 0 0 0 0 3 0 0 0 ⍝ 3rd plane
s333 ⍝ 3D Sudoku puzzle
We choose slightly different contention conditions: there are no “boxes” but numbers must not be repeated in any of the nine x, y, or z planes.
First, we generalise our cmap function:
cmap ⍝ 2D-specific cmap
to enclose (⊂) an appropriate number of axes […].
This is the rank (⍴⍴ the shape of the shape) of the argument array:
cmap ← {⊂[⍳⍴⍴⍵]1∊¨⍵∘.=⍵} ⍝ rank-invariant cmap
Then, using primitive function (⍳) in place of the rcb function, as there are no boxes:
sudoku3D ← {⊃cmap∘⍳ svec ⍵} ⍝ 3D Sudoku solver
Finally, we must generalise avl to return available numbers for a subarray.
For 2D Sudoku this will continue to be the numbers for a row or column vector and for the 3D version it will be those for a whole plane:
avl ⍝ 2D-specific avl
avl ← {(⍳×/1↓⍴⍵)~⍵×⊃⍺⌷⍺⍺} ⍝ rank-invariant avl
1 1 ((cmap rcb ⍴s99 )avl) s99 ⍝ 2D plays at 1 1 for s99
1 1 1 ((cmap ⍳ ⍴s333)avl) s333 ⍝ 3D plays at 1 1 1 for s333
Our 2D Sudoku solver continues to work as before:
sudoku s99 ⍝ 2D solution
and our 3D solver solves the 3D puzzle s333:
sudoku3D s333 ⍝ 3D solution
Notice how few changes were needed to generalise our program for a higher dimensional puzzle.
Conclusion#
There are many ways to solve Sudoku. The method used here illustrates a Pure Functional Programming approach.
The code we have developed consists only of the application of functions and operators to their arguments and operands. In particular, it contains:
No explicit representation of state (no variables).
No explicit control structures (no conditionals, loops, etc).
]defs sudoku -t
For alternative codings of Sudoku in APL, see dfns.dyalog.com/n_sudoku.htm.
Credits#
Algorithm: Arthur Whitney Inspiration: Roger Hui