Sudoko

[TravisWolf]

I am working on a sudoko program and the final grade is based off of how well the program solves sudoku puzzles. I believe that the only way for the program to solve any solvable puzzle is to use a brute force algorithm. Please give me advice on how do to do this. What should I learn before attempting?

[CS Student]

There are several methods for solving Sudoku. A few are here: http://en.wikipedia.org/wiki/Sudoku_solving_algorithms
If you use a brute-force method of solving it, it will take longer than using a "smart" algorithm.

[dhayden]

I wrote a sudoku solver several years ago. It was a lot of fun. You definitely want to apply some smart algorithms. Mine, which isn't particularly fast, can solve a board on a hand-held calculator in less than 1/4 second.

Here are some pointers:

- create a Board class to represent the board.
Most algorithms work on a "group" of numbers: a single row, column or 3x3 box. To simplify this sort of algorithm, write the algo taking an array of pointers to the 9 squares that make up a group:
bool someAlgo(Square *squares[9]);

Then create a Board method that will call a function like this for each group:

typedef bool (*algoFunc)(Square *squares[9]);
Board::apply(algoFunc func) {
{
    Square *squares[9];
    // for each row
    //     populate sqaures[] with the pointers to squares in this row
    //     call func(squares);

    // do the same for each column
    // do the same for each box
}

You may find that you need to pass other arguments to the algo functions. Add them as needed.