The problems this week are from http://www-nlp.stanford.edu/~grenager/cs121//handouts/hw1.pdf

1. 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 psuedocode (in C style or in Russell&Norvig style). You may want to look at theWalkSAT 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?
2. We presented simulated annealing in lecture as a local search algorithm which uses randomness to avoid getting stuck in local maxima and plateaus.
   1. For what types of problems will greedy local search (hill climbing) work better than simulated annealing? In other words, when is the random part of simulated annealing no  necessary?
   2. For what types of problems will randomly guessing the state work just as well as simulated annealing? In other words, when is the hill-climbing part of simulated annealing not necessary?
   3. Reasoning from your answers to parts (b) and (c) above, for what types of problems is simulated annealing a useful technique? What assumptions about the shape of the value function are implicit in the design of simulated annealing?