July 14, 2006
Sudoku!

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

Posted by DonTillman at July 14, 2006 05:43 PM