1. (from http://www-nlp.stanford.edu/~grenager/cs121//handouts/hw1.pdf)
   Consider the popular game Sudoku, in which one tries to fill a 9 × 9 grid of squareswith 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 × 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.
   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 ni,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
   1. Formalize this problem as an incremental search problem. What are the start state, successor function, goal test, and path cost function?
   2. What is the branching factor, solution depth, and maximum depth of the search space? What is the size of the state space?
   3. Assuming we don’t use a heuristic, which of the following would you recommend for solving the incremental search formulation of this problem: DFS, BFS, or Iterative Deepening (ID)? Why? What’s the worst-case time and space complexity of your algorithm for this problem? (Provide a number for each, not an algebraic expression.)
   4. Assuming we use the incremental search formulation, is heuristic search possible? If so, provide a heuristic. If not, why not?
2. AIMA Ex 3.5
3. AIMA Ex 3.8
4. AIMA Ex 4.1