Sudoku Pluzzle

I think you are going to have to write your own algorythm for this.

The math is beyond me, but off the bat I am going to guess that a brute-force-from-zero approach is not going to work anytime this century. However, if you make an initial elimination pass and then start trying possibilities with recursive elimination passes from there I bet it would chop things down enough that you could just do it that way without any really clever algorythm.

A B C

A 1 ? ?

B ? ? 3

C ? 2 ?

With coordinates given as X,Y - so that the 3 is at C,B.

The number at A,B could be 1, 2, or 3, given only the rules of the game. Your "initial pass" is where you just run through the colum (A) and the row (B) and eliminate possibilities. So we know it cannot be 1 because there is a 1 at A,A and it cannot be 3 because there is a 3 at C,B. In a puzzle this simple that already tells us the answer (since only 1 is left) but obviously this will not be the case in a real puzzle. However, we will still have chopped out a LOT of possibilities.

Next we just pick an order for empty spaces - say left to right, top to bottom. The first one is B,A, so we go there. Then we just pick a number (moving from 1 up) to try out. That number gives us more information, so we make another pass over the entire grid eliminating stuff again. Then we just walk down the grid in a binary search tree type of dealy.

I bet that even a big puzzle would be no problem for a modern computer this way.

Drake

Drake_Duna at 2007-7-13 3:40:45 >

> I'm looking for Algorithms that will solve sudoku

> puzzles. Im trying to write my own program for this

> to get ready for a compition. Would anyone know where

> to find these algorithms or ways to slove sudoku

> puzzles using a system every time? Any suggestions

> are helpfull thank you,

http://www.eddaardvark.co.uk/sudokusolver.html

or Google:

http://www.google.com/search?hl=en&lr=&safe=off&q=programming+%22sudoku+solver%22+algorithm&btnG=Search

prometheuzza at 2007-7-13 3:40:46 >