My boys...

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

'Updated my resume.  No, I'm not looking for a new job, I'm completely happy at my present company.  I just thought it looked a little silly being so out of date.  (And I get headhunter calls almost ever day, so this will cut down on the explaining.)

And I finally incorporated registered comments in this blog.  I would love to have completely free and unencumbered comments, and that's the way the blog was set up initially, but the amount of Blog Comment Spam I was getting was really huge and I simply turned the comments off for a while.  Sigh.

I find myself somewhat addicted to Sudoku; it's a fantastically clever little game.  And the kids have become pretty good at it too.  Here Gregor is doing a puzzle before he goes to bed.

Sudoku has achieved an amazing level of pupularity.  In fact, I'll claim Sudoku is the only thing keeping newspaper circulation from completely plummeting.  Pretty amazing when you think about it, a computer just streams'm out, and that's been keeping the newspaper inducstry afloat.

Solving a Sudoku also gives me a funny feeling of Schroedinger's cat.  (Huh?)  I mean, there is exactly one solution, but while you're solving it there can be a number of simultaneous potentional solutions floating around, each with an equal probability of existing.  And as you solve it you narrow down the selection of possible parallel universes, providing them with logical reasons not to exist.  (Okay, it's a stretch.)

The local daily newspaper prints puzzles from KrazyDad.com.  (KrazyDad.com is a completely amazing web site all by itself.  Seriously, check it out.)

Being a professional engineer for a long time, I've been on both ends of an awful lot of job interviews.  And technical engineering interview questions have always been a big part the interview process.  The screwiest interview question have been referred to as "Microsoft Interview Questions" or "Google Interview Questions".  (See http://www.techinterview.org for some fun examples.)

Well, I think Sudoku is fertile ground for some wicked engineering interview questions:

Here's today's Sudoku.   Solve it.   You have 20 minutes.  While I stare at you in a menacing manner.

How would you write a program to solve a Sudoku puzzle?

The brute force approach takes too long; how about with a set of algorithms?

How would you write a program to create a Sudoku puzzle?

First, how would you write a program to generate the solved puzzle?

Then, how would you leave out a set of numbers yet still be assured that the puzzle has exactly one solution?

How would you assign an easy/medium/hard rating to the puzzle?

What is the most blank numbers a Sudoku puzzle can have and still be solvable?

Interesting stuff, eh?

And here is an example of a Python program to solve Sudoku puzzles that has been distilled down to 178 characters (!!!).

'Need more photos... okay.

Happy Independence Day!  Fireworks at Stanford last night.
Christopher on guitar, Gregor on piano.
Christopher and Gregor at the Exploratorium in San Francisco a month ago.