Thursday, July 13, 2006

Shortest Sudoku solver in Python

Mark Byer's site has some more Sudoku solvers here's a short one in Python that's only 178 bytes long:
def r(a):i=a.find('0');~i or exit(a);[m
in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for
j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]
from sys import*;r(argv[1])
On the site is also shown a longer Perl version at 185 bytes:
use integer;sub R{for$i(grep!$A[$_],@x=0..80){%t=map{$_/27-$i/27|$_%9/3-$i%9/3&&$_
/9-$i/9&&($_-$i)%9?0:$A[$_]=>1}@x;R($A[$i]=$_)for grep!$t{$_},1..9;return$A[$i]=0}
die@A}@A=split//,<>;R
I think the Python version is slightly easier to understand, although they are both quite cryptic.
I'm not sure why I find these programs fascinating. I think it reminds me that any program can be written in such a way that it's cryptic, even in Python. In addition, the code is small enough that you should be able to figure out how it works, and may learn something the process.
Related is:

1 comment:

vfdvgf said...
This comment has been removed by a blog administrator.