Tree-based Sudoku Solver

Using a depth first search, we will write a program that solves Sudoku puzzles for us.

Your program must:

Ask the user for a size of puzzle and number of empty spaces (it might take a long time to solve with some configurations, but it would be expected to work with any input) o Reject invalid configurations (i.e. bad board sizes and impossible numbers of spaces)

Generate a random unsolved Sudoku puzzle

Use a depth-first search with a tree structure (see the powerpoint) to find the solution to the puzzle

Display the current state of the puzzle being solved as the program works on it o (This is entirely there to look cool, it slows it down horribly, you might want to disable this while testing)

Output the final solved puzzle:

Starting code:

// Generate a boardSize by boardSize puzzle

int ** generatePuzzle(int boardSize, int spaces)

{

// Check board size

int squareSize = sqrt(boardSize) + 0.5;

if(squareSize * squareSize != boardSize)

throw exception("Board size is not a perfect square!");

// Create board array

int ** board = new int*[boardSize];

for (int i = 0; i < boardSize; i++)

board[i] = new int[boardSize];

// Create first row of squares

for (int row = 0; row < squareSize; row++)

for (int x = 0; x < boardSize; x++)

board[row][x] = (x + squareSize * row) % (boardSize) + 1;

// Next rows are a permutation of the square above

for (int row = squareSize; row < boardSize; row++)

for (int x = 0; x < boardSize; x++)

board[row][x] = board[row % squareSize][(x + (row / squareSize)) % boardSize];

// Shuffle board up a bit

srand(time(0));

while (rand() % 42 != 0)

{

int r1, r2, r3;

do

{

r1 = rand() % squareSize;

r2 = rand() % squareSize;

r3 = rand() % squareSize;

} while (r2 == r3);

swap(board[r1 * squareSize + r2], board[r1 * squareSize + r3]);

}

while (rand() % 42 != 0)

{

int r1, r2, r3;

do

{

r1 = rand() % squareSize;

r2 = rand() % squareSize;

r3 = rand() % squareSize;

} while (r2 == r3);

for (int i = 0; i < boardSize; i++)

swap(board[i][r1 * squareSize + r2], board[i][r1 * squareSize + r3]);

}

// Erase some spots

for (size_t i = 0; i < spaces; i++)

{

int x, y;

do

{

x = rand() % boardSize;

y = rand() % boardSize;

} while (board[x][y] == 0);

board[x][y] = 0;

}

return board;

}