# Sudoku (Brain Teaser)

This is driving me crazy. For the last week, they have been putting these puzzles in the paper. I got bored with them pretty quickly (after solving one or two), but I thought it would be good programming practice to write a program to solve the puzzles. So that’s what I spent my day doing. My program has successfully solved (in under a second) all of the puzzles that I tested it with, except this one which was in the Sunday paper this morning.

I am convinced that, using logic alone, you can’t come to a solution. You’d have to guess after figuring out 49 of the boxes.

If any of you are into this kind of thing (or have a little time to kill), here are the rules (the puzzle is posted below).

You must use the numbers 1-9 only.
Each digit is used only once in each row, column, and 3x3 box.

The 3x3 boxes are arranged as follows:

``````
xxx xxx xxx
xxx xxx xxx
xxx xxx xxx

xxx xxx xxx
xxx xxx xxx
xxx xxx xxx

xxx xxx xxx
xxx xxx xxx
xxx xxx xxx

``````

Here’s the puzzle that’s driving me crazy:

``````
x7x xxx 2x9
xxx 57x x61
xxx xx9 x3x

xx2 85x 7xx
7xx xxx xx4
xx1 x67 9xx

x5x 6xx xxx
98x x45 xxx
2x4 xxx x5x

``````

If anybody wants, I can show you the dead end that I (and my program) hit. There are 49 boxes filled out of the 81 when I hit the dead end.

(The paper says this puzzle is “Black Belt” difficulty - the hardest of the three levels, so if anyone is interested in starting out, but not tackling a tough one yet, google sudoku, there will be tons of matches)