November 14, 2006 |
coding

I happened across the Shortest Sudoku Solver page, which has programs in various languages that solve the puzzle. Most of the major scripting languages clock in at anywhere from 100 to 200 characters.

It means nothing, of course – it’s just elaborate puzzle solving. The C program is just about as short as Python, for example, whereas in real life C is maybe 4 or 5 times less expressive than Python. Of course, the Java version would be about 18,000 characters.

So, as an exercise in Ocaml (my love and frustration of the
moment), I decided to try and golf Ocaml
Sudoku down to something reasonable. It has to be stated at the outset
that this is not Ocaml’s forte – Ocaml is a *very* terse language, one
of the most expressive that I’ve used, but it is nonetheless short on
operators. The modulo function is “mod” instead of “%”, hashtables don’t
have a convenient notation, there is no built in range () equivalent, so
on and so forth. (In real life, a good deal of these flaws are
resolvable through caml4p – I have a bunch of syntax extensions in my
standard toplevel.)

At any rate, I got it down to 255 characters:

open String let rec s p=try let rec(%)=(mod)and i=index p '0'and b j=i<>j&&(i/9 =j/9||i%9=j%9||i/27=j/27&&i%9/3=j%9/3)&&p.[i]=p.[j]||j<80&&b(j+1)in iter(fun c->p.[i]<-c;if not(b 0)then s p)"948721536";p.[i]<-'0'with _->print_string p let _=s(read_line())Run as in:

echo 000010000301400860900500200700160000020805010000097004003004006048006907000080000 | ocaml sudoku.mlThere’s still room for more cutting, too, although at the edge of my mind it feels like there is a really clever solution that I’m missing. Unfortunately, it’s hard to use the really neat features of Ocaml, since they all have long module names!

Expanded version below, for those who aren’t computers.

open String let rec solve p = try let rec (%) = (mod) (* redefine mod for smaller code *) and i=index p '0' (* find a number we need to guess... *) and illegal j = (* determine if move @ i is legal wrt j *) i <> j && (i/9=j/9 || i%9=j%9 || i/27=j/27 && i%9/3=j%9/3) && p.[i]=p.[j] || j < 80 && illegal (j+1) in iter (* main loop for solution *) (fun c -> p.[i] <- c; if not (illegal 0) then solve p) "948721536"; p.[i] <- '0' with _ -> print_string p let _ = solve(read_line())**Updated November 14**: Down to 270 characters, from 307.

**Updated November 15**: Down to 255. Okay, enough of this!

*Comments are moderated whenever I remember that I have a blog.*

There are no comments on this article.