An algorithm to solve sudoku

kk_loke86

Hello, I am now interested with SUDOKU games and decided to have an C++ exercise on it...

I want to try to write a C++ program that can solve some simple sudoku question. But the problem is, I can`t figure out what is the algorithm steps to solve a sudoku....anyone can help? Thanks.

AftershockVibe

Sudoku is really easy to solve computationally provided you give it "nice" inputs. I'll explain exactly what I mean by that in a minute.

Basically, after being given a starting state, you look at each square and work out at that point in completion which numbers could possibly go in that square.

When you find a square which has only one possiblity then you fill that square with the number and recalculate all the sqaures which relate to it. Keep going like this until all squares are filled.

It's not quite this simple in real life though. Sometimes you can get puzzles which will force you to guess between two (or more) possibilities for a square. When you start having to deal with this you'll have to start making "save" points where you can go back to if you discover the puzzle is unsolvable from the guess you (or the computer) made.

Similarly, it is possible to make puzzles which are unsolvable.

MrBlueSky

I have been working on a sudoku-solver once. Never finished it tough. There are some algorithms to solve any solvable sudoku, which are explained at this (very interesting) wikipedia item: http://en.wikipedia.org/wiki/Algorithmics_of_Sudoku. There is also a book on creating a sudoku-solver in Visual Basic. The title is "Programming Sudoku". And there was a topic here at frihost about writing a program to solve sudokus. I'll see if I can find it.

kk_loke86

Thanks, I will have a look on it....