﻿ Vector, the Journal of the British APL Association

Current issue

Vol.26 No.4

Volumes

British APL Association

Archive articles posted online on request: ask the archivist.

Volume 21, No.4

A Sudoku Solver

Fill the grid so that each row, column, and 3 by 3 box contains the digits 1 through 9.

```  +-----+-----+-----+
|2 0 0|6 7 0|0 0 0|
|0 0 6|0 0 0|2 0 1|
|4 0 0|0 0 0|8 0 0|
+-----+-----+-----+
|5 0 0|0 0 9|3 0 0|
|0 3 0|0 0 0|0 5 0|
|0 0 2|8 0 0|0 0 7|
+-----+-----+-----+
|0 0 1|0 0 0|0 0 4|
|7 0 8|0 0 0|6 0 0|
|0 0 0|0 5 3|0 0 8|
+-----+-----+-----+
```

Welcome to Sudoku.

Sudoku is a popular puzzle in Japan (su is number, doku is place), to where it was imported from the U.S. It was popularized in the West by Wayne Gould, a New Zealander living in Hong Kong. He maintains a website http://www.sudoku.com where you can find descriptions, examples, tutorials, and download a puzzle player. In a November 2004 article in the Times, http://www.timesonline.co.uk/article/0,,18209-1354181,00.html, Gould was quoted as saying that some Sudoku puzzles are so difficult that you can’t solve them if your life depended on it.

The following Sudoku solver uses a simple but effective strategy. Even puzzles rated as “very hard” require no more than 15 milliseconds and 30 Kbytes on a 500 MHz Pentium 3 computer.

```j      =. (]/. i.@#) ,{;~3#i.3
r      =. 9#i.9 9
c      =. 81\$|:i.9 9
b      =. (,j{9#i.9) { j

I      =: ~."1 r,.c,.b
R      =: j,(,|:)i.9 9

regions=: R"_ {"_ 1 ]
free   =: 0&= > (1+i.9)"_ e."1 I&{
ok     =: (27 9\$1)"_ -:"2 (0&= +. ~:"1)@regions

ac     =: +/ .*&(1+i.9) * 1: = +/"1

ar     =: 3 : 0
m=. 1=+/"2 R{y.
j=. I. +./"1 m
k=. 1 i."1~ j{m
i=. ,(k{"_1 |:"2 (j{R){y.) #"1 j{R
(1+k) i}81\$0
)

assign =: (+ (ac >. ar)@free)^:_"1

guessa =: 3 : 0
if. -. 0 e. y. do. ,:y. return. end.
b=. free y.
i=. (i.<./) (+/"1 b){10,}.i.10
y. +"1 (1+I.i{b)*/i=i.81
)

guess  =: ; @: (<@guessa"1)
sudoku =: guess @: (ok # ]) @: assign ^:_ @ ,

see1   =: (;~9\$1 0 0)&(<;.1) @ ({&'.123456789') @ (9 9&\$) @ ,
see    =: <@see1"1`see1@.(1:=#@\$)
diff   =: * 0&=@}:@(0&,)```

A grid is the ravel of a 9 9 matrix of cells of i.10 . A box is a 9-element subset of a grid, the ravel of one of the 3 3 regions.

A region is a row, column, or box. The object of Sudoku is to assign numbers to the zero cells of a grid x while leaving unchanged the non-zero cells in x, so that each region has exactly the elements 1+i.9 .

j are the indices in a ravelled grid for each box. r are the indices for each row. c are the indices for each column. b are the indices for each box. Finally, I are the indices in a ravelled grid for regions that contain a cell, for each cell of a grid.

regions x computes a 27 9 matrix of the 27 regions of grid x . free x computes a 81 9 boolean array y such that (<((9*i)+j),k){y is 1 if 1+k can be assigned to cell i,j of grid x . ok applies to one or more grids and returns a 1 for each valid grid.

ac and ar apply to the free list of a grid. ac assigns numbers to cells that have only one candidate. ar looks for a number which occurs exactly once in the candidates for a region, and assigns that to the cell for which it is a candidate. ac and ar correspond to “forced moves”. (When ac or ar is applied to an “impossible” grid, the result can be assignments that are obviously in error.) assign repeatedly applies ac and ar to one or more grids until there are no more changes.

guessa x applies to to grid x and returns one or more grids with cells fill in with all possible candidates, for a cell that has the smallest set of candidates. guess applies guessa to one or more grids and returns all the grids generated thereby.

sudoku x finds all solutions for grid x . An error is signalled if x has no solution.

```x=: , 0 ". ] ;._2 (0 : 0)
2 0 0  6 7 0  0 0 0
0 0 6  0 0 0  2 0 1
4 0 0  0 0 0  8 0 0
5 0 0  0 0 9  3 0 0
0 3 0  0 0 0  0 5 0
0 0 2  8 0 0  0 0 7
0 0 1  0 0 0  0 0 4
7 0 8  0 0 0  6 0 0
0 0 0  0 5 3  0 0 8
)
see x, sudoku x
+-------------+-------------+
|+---+---+---+|+---+---+---+|
||2..|67.|...|||283|671|945||
||..6|...|2.1|||976|548|231||
||4..|...|8..|||415|392|876||
|+---+---+---+|+---+---+---+|
||5..|..9|3..|||567|419|382||
||.3.|...|.5.|||834|267|159||
||..2|8..|..7|||192|835|467||
|+---+---+---+|+---+---+---+|
||..1|...|..4|||321|786|594||
||7.8|...|6..|||758|924|613||
||...|.53|..8|||649|153|728||
|+---+---+---+|+---+---+---+|
+-------------+-------------+
```

The following phrases show the intermediate steps leading to a solution.

 f=: + (ac >. ar)@free one step of assign see t=: f^:a: x forced moves leading from grid x see diff t differences from one grid to the next see assign x same as the last grid above see g=: guess (ok#]) assign x guesses after exhausting forced moves see t0=: f^:a: 0{g forced moves leading from guess 0 see diff t0 differences from one grid to the next see t1=: f^:a: 1{g forced moves leading from guess 1 see diff t1 differences from one grid to the next; note the obviously invalid assignments

```script began 10:44:57
caching off
debug mode off
cache time 3600 sec
cached index is fresh
recompiling index.xml
index compiled in 0.3139 secs