Sudoku Solver

Sudoku is a puzzle game that uses a grid of empty squares and N different characters (usually the numbers 1 through N). In and N by N grid, there are N rows and N columns.

If the square root of N is a natural number, then there are also N squares of N boxes inside of the N by N grid.

The goal of sudoku is to fill in empty squares with any of the N different characters such that no character is repeated within a row, column, or subsquare.

Wikipedia has illustrations of this concept: http://en.wikipedia.org/wiki/Sudoku

Program Inputs:

The first argument to your program will be a value, N, that gives the size of the N by N grid and the values to use to fill in the grid. If N does not have a natural number as its square then you cannot construct a sudoku grid, and should return the number 2.

You can use the sqrt() function from #include to do this.

int root = sqrt(n);
if (root != sqrt(n)) { .... }

Additional arguments should come in groups of three, specifying the x coordinate, y coordinate, and value of a square. These squares start off with a given value and cannot be changed.

For full credit you only need to implement the algorithm to solve sudoku with backtracking but without given initial values and solving sudoku with initial values.

Your program must try the numbers in order (1, 2, 3, ...) and your solutions should be the same as the ones in the examples below (Program Output).

Program Output:

This is an example of expected outputs for given inputs:

Without Initial values:

g++ homework4.cpp -o sudoku
./sudoku 4
1 2 3 4
3 4 1 2
2 1 4 3
4 3 2 1

./sudoku 9
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2

With initial values:

./sudoku 4 0 0 2 3 3 4
2 1 4 3
3 4 1 2
4 2 3 1
1 3 2 4

./sudoku 4 0 0 4 1 2 4 2 3 4
4 1 2 3
2 3 1 4
1 4 3 2
3 2 4 1

Evaluation:

• Return 1 when given an incorrect number of arguments
• Return 2 when the given N does not have a natural square.
• Solve sudoku when no initial values are specified for sizes that do no require backtracking (4 or 16).
• Solve sudoku for sizes that require backtracking (9 or 25). You must use a stack to store the partial result and pop values from the stack to backtrack.
• Solve sudoku with initial values specified.
• Comments so I can follow through the code.