# Sudoku fun on the plane…

On an airplane ride recently when I ran across a Sudoku puzzle in the local newspaper…. Seemed easy enough… the first few rows and columns went easily enough, but boy it got harder at the end.  The rules are very simple…

Fill in the 9x9 grid so that

every row,

every column, and

every 3 x 3 box

contains the digits 1 through 9.

The grid is initialized with a few values that are not changeable making it a bit harder…

Here is the example I worked…   You can only change the 0’s…

9 0 6   5 0 7   0 2 0

8 0 0   0 0 0   3 7 0

0 0 0   3 0 2   0 0 0

0 6 0   0 0 0   0 0 2

0 9 0   0 7 0   0 4 0

2 0 0   0 0 0   0 9 0

0 0 0   4 0 3   0 0 0

0 1 3   0 0 0   0 0 4

0 4 0   1 0 5   2 0 7

On the 4th time I changed a value in a box, I thought this was an excellent job for a computer!  So I pulled out my laptop and banged out  the core of a solution relatively quickly... another hour of clean up and I have this solution… It is neither the best code, nor optimal solution, but it does solve the puzzles faster than I can ;-).

I’d love to see other’s solutions as well…    Here is one

Tags

1. I suppose the best one would allow for the solving of any arithmetic square (e.g., not just a 9×9 puzzle… include support for a 100×100 puzzle).

2. David Betz says:

I picked up a SuDoku book yesterday… at first I was doing all kinds of tricks and stupid things. After 45 minutes I threw the thing and said forget it. That night I tried it again… without trial and error (don’t do that) and relies solely on deductive logic and I did it in 15 minutes flat with no notes. Ha! Cool… I was a Math major, so it was fairly simple given that it’s equation based. I get it now… At the beginning though seeing the logic peices may be hard and at the end you will be so overwhelmed with information that it’s a (I’m being serious) test of your ability to manage resources.

3. David Betz says:

Also, I’m teaching a design pattern/OOP class in a few weeks and my class demo is going to be a smart SuDuko assistant (each cell has a brain of it’s own to figure out what it thinks it can be from it’s own point of view.) If I remember (not likely), I’ll post the source!

4. Gary Short says:

The best algorithm I’ve seen for this is by Donald Knuth (no surprise there). He converts the problem to an exact cover problem and then uses his Dancing Links alogrithm to solve the boolean matrix. Very nice 🙂

5. Looks like one of those TopCoder’s 500 point tasks… 😉

6. Gal Kahana says:

Glad to find fellow Soduko Solvers!

The sollution i implemented goes like this:

1. each cell can initially have the number 1-9

2. it is constrained by numbers that already exist in its row, col and 3X3 box. so there’s a subset of 1-9 that serve as "possible" values for each cell. if you apply these you might end up with cells that can have only 1 possible value. so you can safely posit the matching value in these cells. This will further constrain the others.

3. each 3X3 box must have all numbers from 1-9. now there might be a case where one (or more) of these numbers, according to the constraints

in 2 can be posited in only one of the cell in that box. So you can safely posit this number in that cell. This will further constrian the other cells (like in 2)

4. each row/col must have all number from 1-9. same logic in 3 follows here – you might have rows/cols in which there’re number from this 1-9 that can be placed in only one of the cells. so you can safely posit this number in that cell.

if you do this "constraining" and positing iteratively you’ll get a "smaller" problem and actually this solves a good portion of the puzzles i know of.

In order to solve the rest you can add a certain backtracking method. you can guess a position based on the possible values for cells and try to further constrain till you get a sollution. if you still don’t get an answer you can guess again etc.

I discovered that if one gives up after 2 depth guesses (i.e. constrain and then guess once, further constrain and then guess again. then constrain and see if you got a complete sollution. if not mark this path as not solving and continue to next guesses in the tree) one can solve *all* puzzles. well…at least i couldn’t find a puzzle that was not solved and quite quickly.

if you’re interested i have a .net sollution that does this – email me at zappa_1@netvision.net.il

7. Steve says:

This is funny – the first thing I did when I first saw a Sudoku was to scribble down an algorithm to solve it. I just couldn’t see the point in actually *solving* one of these, it was much more fun to just to solve the problem in general.

8. Bart De Smet says:

Hi folks,

A little while ago, I’ve developed a "Sudoku reducer" tool in C# 2.0. Read the story (and download the code) on my blog on http://blogs.bartdesmet.net/bart/archive/2005/10/10/3604.aspx.

Cheers,

Bart

9. I just noticed that Stephen Toub posted a great Suduko game.&amp;nbsp; The tabletink integration is really…