Udostępnij za pośrednictwem

Sudoku fun on the plane...

  • Artykuł

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…

Comments

  • Anonymous
    September 25, 2005
    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).

  • Anonymous
    September 25, 2005
    The comment has been removed

  • Anonymous
    September 25, 2005
    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!

  • Anonymous
    September 25, 2005
    Check out:
    http://www.websudoku.com/

  • Anonymous
    September 26, 2005
    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 :)

  • Anonymous
    September 27, 2005
    Looks like one of those TopCoder's 500 point tasks... ;)

  • Anonymous
    September 27, 2005
    The comment has been removed

  • Anonymous
    September 29, 2005
    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.

  • Anonymous
    October 09, 2005
    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

  • Anonymous
    April 02, 2006
    I just noticed that Stephen Toub posted a great Suduko game.  The tabletink integration is really...

  • Anonymous
    March 31, 2008
    PingBack from http://collegefunfactsblog.info/brad-abrams-sudoku-fun-on-the-plane/

  • Anonymous
    June 19, 2009
    PingBack from http://debtsolutionsnow.info/story.php?id=12413