Consider the game Sudoku, where we try to fill a 9 times 9 grid of squares with
ID: 3864109 • Letter: C
Question
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 a of the digits 1, , 9, every column must contain a 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 a. 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? b. 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? c. What, is the difference between "easy" and "hard" Sudoku problems? d. 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 WalkSAT 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?Explanation / Answer
Answer
a.
Set of variables :
1. ni,j : possible domain is digits 1 to 9
2. i : row variable, possible domain is 1 to 9
3. j : column variable, possible domain 1 to 9
4. M : number of digits already provided, possible domain 12 or more digits.
The given constraints looks like second class constraints.
b.
The minimum remaining values heuristic for backtracking search would work better for the given problem because the empty spaces needs to be filled according to the remaining values that needs to be filled.
The branching factor of the search space is the number of nodes generated divided by the number of digits provided initially.
Solution depth is the length of the shortest path taken from the initial node to a goal node
Maximum depth of the search space is the length from the root to leaf in depth first search.