Shortest Sudoku Solver in Python
Well over two years ago on this blog (have I really been around that long?), I posted a link to a story that Sudoku had been solved. (The original link to the Math-Forge Story is broken, so here in alternative version of the story.) While just about every computer scientist and programmer I know has thought up a quick little code to solve a Sudoku puzzle, the interesting element of the above story is that the algorithm solving Sudoku was connected to techniques used in diffraction microscopy.
Now, when I say “quick little code”, I meant an easy algorithm to implement, but not necessarily an elegant or amazingly small code that would accomplish the solution. Here is definitely the smallest (shortest) code I’ve seen that will do it.
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])
Here’s one that is slightly longer (185 bytes as opposed to the 178 above)
use integer;sub R{for$i(grep!$A[$_],@x=0..80){ %t=map{$_/27-$i/27|$_%9/3-$i%9/3&&amp;amp; $_/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
HT: Scott's Blog