More on Sudoku; a continuation of my previous post.

I see they've updated the Shortest Sudoku Solver site; now the winner is a 134 character Ruby program.  That's very impressive.

The algorithm they use is actually a very straightforward and brute force approach.  (Make a recursive tree for trying each of the empty spaces with the digits 1..9, test each case, return the first one that works.)  But in reducing the character count the programs are obfuscated to the point where they're nearly impossible to figure out.

For instance, at the very end of the Python function definition, they want to write:

for m in '123456789'

Or:

for m in range(1,10)

But instead they save a single character by utilizing this little gem:

for m in '%d'%5**18

With somewhat reduced efficiency.  (5^18 is 3814697265625.)  Man, oh man...

Of course I'm really tempted to write and submit a Lisp version of the Sudoku Solver.

Or better yet, APL.  I'll bet there's an amazingly tiny APL solution.  And unlike the Ruby and Python approaches, the APL version might be readable.  Well, no less readible than any other APL program :-).  Unfortunately I haven't looked at the language for several decades, so I'm probably not the one to do this.

(For you youngsters, APL is a computer language that was created in 1962.  The Wikipedia APL entry does an impressive job of describing it.  The language is completely insane.  In several ways.)

Since the Sudoku programs presented on that page are brute force approaches, they're really slow.  Really, really slow.  So I'm thinking it's John Henry time.  Man Vs. Machine.  Sunday!  Funny cars!

So I tried it, and it turns out that the Python program takes several hours to run on a real world Sudoku puzzle.  So that's plenty of time to beat the computer.  (Feh, that takes all the fun out of it.)