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

 

 

Published 25 September 05 01:57 by BradA
Filed under:

Comments

# James McNellis said on September 25, 2005 6:11 PM:
I suppose the best one would allow for the solving of any arithmetic square (e.g., not just a 9x9 puzzle... include support for a 100x100 puzzle).
# David Betz said on September 26, 2005 12:19 AM:
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.
# David Betz said on September 26, 2005 12:21 AM:
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!
# Joe Duffy said on September 26, 2005 1:17 AM:
Check out:
http://www.websudoku.com/
# Gary Short said on September 26, 2005 8:55 AM:
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 :)
# Val Savvateev said on September 27, 2005 10:12 AM:
Looks like one of those TopCoder's 500 point tasks... ;)
# Gal Kahana said on September 27, 2005 1:56 PM:
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
# Steve said on September 30, 2005 6:05 AM:
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.
# Bart De Smet said on October 9, 2005 7:18 PM:
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
# Brad Abrams said on April 2, 2006 10:39 PM:
I just noticed that Stephen Toub posted a great Suduko game.  The tablet\ink integration is really...
# College Fun Facts » Brad Abrams : Sudoku fun on the plane… said on March 31, 2008 3:43 PM:

PingBack from http://collegefunfactsblog.info/brad-abrams-sudoku-fun-on-the-plane/

New Comments to this post are disabled

Search

Go

This Blog

Syndication

Page view tracker