Brool brool (n.) : a low roar; a deep murmur or humming

Ocaml Golfing

 |  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.ml

There’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!

Discussion

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

There are no comments on this article.

Add a comment