Language: C99

A Sudoku puzzle is a 9 by 9 grid, containing 81 cells. The grid is divided into 9 square boxes, and each box is a 3 by 3 grid.

A valid solution of a Sudoku puzzle must satisfy three constraints.

Row constraint: each integer from 1 to 9 appears exactly once in every row.

Column constraint: each integer from 1 to 9 appears exactly once in every column.

Box constraint: each integer from 1 to 9 appears exactly once in every box.

Our module stores a Sudoku puzzle in a struct with two arrays. When a puzzle is read in, it is stored in both the puzzle and the sol arrays. As you attempt to solve the puzzle, you can modify the sol array until it contains a valid solution.

The rows and columns of a Sudoku puzzle are zero indexed. Each cell is represented by (row,col). For example, for the following puzzle from Wikipedia, cell (0,0) has the value 5, cell (1,3) has the value 1, and cell (0, 2) has the value 0. An empty cell has a value of 0 in it.

The client first reads in a puzzle from input, and then waits for you to enter one of the following commands. See simple.in for the input format of a Sudoku puzzle. Notice that we use "-" instead of "0" to represent an empty cell in the input.

fill ROW COL VALUE tries the fill the cell (ROW,COL) with VALUE, and prints out a message describing whether this was successful or not. See fill_cellbelow for more details.

erase ROW COL resets the cell (ROW,COL) to be empty (to have the value 0).

choices ROW COL considers the cell (ROW,COL) and prints out all the values for the cell that do not violate any of the row, column, and box constraints.

hint prints out a cell (ROW,COL) which only has one possible value that does not violate any of the row, column, and box constraints. Otherwise, it prints out an error message saying that no such cell exists.

solve solves the puzzle by search and backtracking.

reset resets the solution to be the same as the initial puzzle.

print prints out the current solution.

bye exits the program.

You will implement the following four functions to complete the Sudoku program. You are encouraged to write additional helper functions whenever useful.

a) int fill_cell(struct sudoku *s, int row, int col, int num) tries to fill num in the cell (row,col). It returns 0 if doing so does not violate any of the row, column, and box constraints. Otherwise, it returns a negative integer.

b) bool solved_puzzle(const struct sudoku *s) returns true if s has a valid solution to the puzzle, and returns false otherwise. A solution is valid if all the cells in the solution have been filled in and the value of any cell does not violate any of the row, column, and box constraints.

c) void choices_cell(const struct sudoku *s, int row, int col, int choices[], int *num_choices) determines all the possible values for the cell (row,col) that do not violate any of the row, column, and box constraints. It mutates choices to contain the possible values and mutates *num_choices to be the number of possible values.

LANGUAGE FEATURES: For (d), you may use recursion only for the solve function. Every other function must use iteration.

d) bool solve(struct sudoku *s) solves the Sudoku puzzle by search and backtracking. It mutates the puzzle until its solution is complete and valid. It returns true if s has a valid solution to the puzzle, and returns false otherwise. See the section on backtracking in this Wikipedia article. Our implementation of the algorithm uses recursion. Here is an incomplete description of the algorithm.

If the puzzle has not been solved, find an empty cell.

If there is no feasible value for this empty cell ...

For each feasible value for the cell ...

If none of the feasible values for the cell leads to a valid solution ...

Provided Functions:

const int DIM = 9;

static const int EMPTY = 0; static const char BLANK = '-'; static const int MIN = 1; static const int MAX = 9;

static const int SUCCESS = 0; static const int ERROR = -1; static const int ERASE_EMPTY_CELL = -2; static const int ERASE_FILLED_CELL = -3; static const int ERROR_NEXT_CELL = -4; struct sudoku { int puzzle[DIM * DIM]; int sol[DIM * DIM]; }; struct sudoku *read_sudoku(void) { struct sudoku *s = malloc(sizeof(struct sudoku)); char c = 0; for (int row = 0; row puzzle[row * DIM + col] = 0; } else { s->puzzle[row * DIM + col] = c - '0'; } } }

// copy puzzle to solution reset_sol(s);

return s; }

void sudoku_destroy(struct sudoku *s) { assert(s); free(s); }

void print_sol(const struct sudoku *s) { assert(s);

printf(" "); for (int row = 0; row sol[row * DIM + col]; if (num == EMPTY) { printf("%c", BLANK); } else { printf("%d", num); } } printf(" "); } printf(" "); }

void reset_sol(struct sudoku *s) { assert(s);

for (int row = 0; row sol[row * DIM + col] = s->puzzle[row * DIM + col]; } } }

// cell_empty(board, row, col) returns true // if cell (row,col) is empty on board. // requires: board is a valid sudoku puzzle. static bool cell_empty(const int board[], int row, int col) { assert(board); assert(0

return board[row * DIM + col] == EMPTY; }

int erase_cell(struct sudoku *s, int row, int col) { assert(s); assert(0

if (cell_empty(s->sol, row, col)) { return ERASE_EMPTY_CELL; } if (!cell_empty(s->puzzle, row, col)) { return ERASE_FILLED_CELL; } s->sol[row * DIM + col] = EMPTY; return SUCCESS; }

int next_cell(const struct sudoku *s, int *row, int *col) { assert(s); assert(row); assert(col);

int choices[DIM]; int num_choices = 0; for (int i = 0; i sol, i, j)) continue; choices_cell(s, i, j, choices, &num_choices); if (num_choices == 1) { *row = i; *col = j; return SUCCESS; } } } return ERROR_NEXT_CELL; }

316 59 6 2 6 8 316 59 6 2 6 8