Sudoku algorithm

[Blazikaen]

hi...
can anyone light me on an algorithm to solve sudoku...actually i did solve a few sudokus to know how this is done. Eventhough i managed to do the sudokus by paper and pencil, i can't figure out an algorithm to solve it. I googled for algorithms but everything ends up with graph colouring which i don't know ( i could only understand this: adjacent nodes are to be coloured differently ). Please someone help.

[geethaa]

Yeah one such algo that I know was backtracking algorithm - but its too old..

[Blazikaen]

Thats ok. I don't mind if its old. Please tell me what it is. Anyway i'll do some improvisation on that.

Thanks in advance.

[Adak]

There are two basic types of algorithms to solve Sudoku:

1) Brute force - relies on making guesses, and typically uses either backtracking or coloring. "Dancing Links" algorithm is especially elegant, imo.

2) Use human type reasoning methods which limit guessing

It is FAR easier to use brute force with backtracking, then anything else. With modern hardware, brute force is also a fast method, if you know how to maximize your code.

Either algorithm will need to check for Naked Singles/Forced Singles, where the value for a square can be determined directly by simple inspection. For instance, if a row has squares with 2 through 9, the remaining square must have a 1 for it's value - entirely forced. Any square with only one remaining possible value, is a Naked Single, and it's value should be assigned, immediately.

Many brute force solvers, are not entirely brute force - they use the most productive human like reasoning to discover the values of empty squares, and if that succeeds in solving the puzzle, then great. But if not, then they switch to a brute force approach, and find one or all of the remaining values.

Note that although the human reasoning will solve many puzzles, it will not solve them all. There is no known algorithm that will solve every puzzle, without some form of guessing.

For more info on this -- way more info, visit the Sudoku Programming Forum:
http://www.setbb.com/sudoku/index.php?mforum=sudoku

It's incredible that such a simple puzzle, would have so many sublime ways of working through it.