Consider the game Sudoku, where we try to fill a 9 times 9 grid of squares with numbers subject to some constraints: every row must contain all of the digits 1, ..., 9, every column must contain all of the digits 1, ..., 9, and each of the 9 different 3 times 3 boxes must also contain all of the digits 1, ..., 9. In addition, some of the boxes are filled with numbers already, indicating that the solution to the problem must contain those assignments. Here is a sample board: Each game is guaranteed to have a single solution. That is, there is only one assignment to the empty squares which satisfies all the constraints. For the purposes of this homework, let's use n_i, j to refer to the number in row i, column j of the grid. Also, assume that M of the numbers have been specified in the starting problem, where M = 29 for the problem shown above. This is an instance of a Constraint Satisfaction Problem. What is the set of variables, and what is the domain of possible values for each? How do the constrains look like? One way to approach the problem, is through an incremental formulation approach and apply backtracking search. Formalize this problem using an incremental formulation. What are the start state, successor function, goal test, and path cost function? Which heuristic for backtracking search would you expect to work better for this problem, the degree heuristic, or the minimum remaining values heuristic and why? What is the branching factor, solution depth, and maximum depth of the search space? What is the size of the state space? What, is the difference between "easy" and "hard" Sudoku problems? Another technique that might work well in solving the Sudoku game is local search. Please design a local search algorithm that is likely to solve Sudoku quickly, and write it in pseudo-code. You may want to look at the Walk SAT algorithm for inspiration. Do you think it will work better or worse than the best incremental search algorithm on easy problems? On hard problems? Why