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.
Academic Honesty!
It is not our intention to break the school's academic policy. Projects posted are only used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly fill out the form. Please provide a valid email address and we'll get back to you in less than 24 hours. We will be sending an invoice through PayPal upon confirmation. We are a non profit organization however we need an amount to keep this organization running, and to be able to complete our research and development.