Hi, I just have an idea to solve the Sudoku puzzle. I think this problem can be converted to a "coloring graph" problem. But in that case, you already have node with color. The color in that case are the number 1 to 9 (or 1 to 4 in a simpler version). And in that case, you start to solve with a node wich have the most adjacent colored node... an so on... Do you think that solution can be a good one... I know coloring a graph is a NP-Complet problem. And on your side, have you think of a solution to solve this. Personnally, it is the first solution I work on (only in my head, nothing on paper or computer). I will wait for you opinion on that...

FD prolog can describe the solution to a Su Doku problem fairly easily. You could also convert a Su Doku board to a propositional logic expression and solve it. It's also possible to store all possible values for a given square, and choose a value arbitrarily for the square with fewest possibilities recursively (backtrack when no solutions are possible). Or, as you said, you could use a graph algorithm to set up the colors.

Thanx...

Maybe one day I will check to code my solution for fun... If I have the time :)

Thanx for mentionning the other solution.

A quick wikipedia search on graph coloring actually mentions sudoku:

Quote: from:http://en.wikipedia.org/wiki/Graph_coloring

Graph coloring enjoys many practical applications as well as theoretical challenges. Beside the classical types of problems, different limitations can also be set on the graph, or on the way a color is assigned, or even on the color itself. It has even reached popularity with the general public in the form of the popular number puzzle Sudoku. Graph coloring is still a very active field of research.

So, I'm inclined to say your idea could work, though I wouldn't know how to go about doing it.


I wrote a sudoku solver about 3 months ago. It's possible to do most by pure logic steps(you can find online if you search "solving sudoku"), but it's much much easier to implement about half the logic steps and then brute force it. http://www.angusj.com/sudoku/hints.php
I pretty much used the basics on that page. Then, when those steps are complete if the board is not full, take the first empty square and create boards filled with all possibilities for that square and then run the solver again and repeat until you arrive at a solution. It's actually quite fast because the search tree is so small. Easy puzzles don't usually even make it to the brute force step and the hardest puzzles rarely have more then a depth of 5. My program runs in about a second on a 2gh .

Solving Sudoku puzzles is an example of constraint optimisation, which describes a very wide class of problem. There are many varied approaches to solving such problems, although they tend to be tuned to the particular problem instance one is solving. That does mean though, that you could take a solution methodology for one brach of CO problems and apply it to another. How successful/efficient it is will depend on the problem structural similarities.

Cheers,

Timkin

Mathematically, Sudoku is not just a graph coloring problem, though it can be formulated as one. It is rather a Latin Square, or a variation to the latin square. The extra rule with the 3x3 satifying a specific requirement is what makes it slightly different, but the solution itself is still a latin square. The numbers that appear visible for each problem is a determining set (if I'm not remembering wrong). The open question right now is how to prove the minimum determining set.

Solving it with "logic" is probably the best way as there are specific strategies used to fill in numbers. If you do enough, you'll figure them out too. A backtracking method is another approach, which has been used to generate latin squares too.