Blogs 2005/05/25

(RSS)

2005/05/25 - Sudoku solver in four lines

Slightly silly perhaps but I thought it would be fun to write a piece of code to solve these sudoku puzzles that keep popping up. As that appeared to be trivial I decided to see if it could be done in four lines or less. Here it is:

$a=8;$G{int(++$a/9).$a%9+1}=$_ for split//,<>;@A=1..9;sub c{int(($_[0]-1
)/3)*3}sub G{for$y(@A){for$x(@A){$p=$t=$G{my$c=$y.$x}&&next;$t.=$G{$_.$x
}.$G{$y.$_}for@A;for$f(1..3){$t.=$G{c($y)+$f.c($x)+$_}for 1..3}G($G{$c}=
$_)&&return for grep$t!~m/$_/,@A;return$G{$c}=0}}die map{$G{$_}}9..99}G

Update - there is also an explanation of this code and a three line version.

It is slightly arcane in it's usage but what do you expect from four lines of Perl? The best way to run it is to save it to a file (eg sudoku.pl). You need to feed it the start grid as well. This is one long line with the top row first, the second row next and so on. Use zeros for the blanks. Do not separate the rows with a space, just push them all together.

For example the following puzzle was given in the Economist (21 May 2005) on page 75:

. . . . 1 . . . .
3 . 1 4 . . 8 6 .
9 . . 5 . . 2 . .
7 . . 1 6 . . . .
. 2 . 8 . 5 . 1 .   (dots are used for the blanks)
. . . . 9 7 . . 4
. . 3 . . 4 . . 6
. 4 8 . . 6 9 . 7
. . . . 8 . . . .

This would give you the following line for input:

000010000301400860900500200700160000020805010000097004003004006048006907000080000

If you saved the input in a file called input.txt you could then run the solver like this:

perl sudoku.pl < input.txt

The output is the same format as the input - that is to say all the rows on one line.

It will only work for 9x9 grids containing numbers 1 to 9. Hope you enjoy it.