1. For the Sudoku problem in week 8’s exercise, use the local search with hill climbing to solve it (please give intermediate assignments and how many constraints they violate). Let us say there the rule of hill climbing that 1) always consider the variable which violates the most constraints and 2) swap that variable’s value with a cell, such that the total number of violated constraints can be reduced most. Suppose a randomly generated initial assignment is below (in red). (to simplify the calculation, let us say cell tie is broken first from top to bottom and then from left to right, and number tie is broken numerically)
2. Crossover and mutation are two components in genetic algorithms. Are they both necessary? can we remove one of them during the search?
3. Question 3.1. Give the minimax value at each node for the game tree below.
Question 3.2. Find the nodes of the above tree pruned by alpha‐beta pruning algorithm. Assuming child nodes are visited from left to right. There are four layers and you can use L ‐ to denote the th node from left to right in the layer , e.g., the first node (with value 8) at the bottom layer can be denoted by L4‐1.
3
4
1
2
1
2
3
2
4
3
1
3
4
2
4
1