Homework #1

Due date: Nov 15, 2007.

Descriptions: use single agent search methods plus heuristics and
pattern databases to solve 4*4, 9*9 and 16*16 Sudoku games.
Note: Each Sudoku problem input instance has a unique solution.

Various heuristics, such as uniqueness and hidden
uniqueness, are known for solving the game efficiently for the human.
Try to collect these heuristics from web sites and invent new ones
that are suitable for the machine.
Can you think of some kinds of pattern adtabases, or divide and conqure
approach?

Documentation is very important for this project.
We will invite students to explain their ideas in class.

Solution package:
1. code + documents to explain various heuristic used.

2. Do experiments to "guess" why certain Sudoku games are difficult, while
some are easy. factors that may affect the level of difficulties:
  a. number of revealed cells in the starting position
  b. average branching factor
  c. max or min branching factor
  d. depth of search trees: average/min/max depth
  e. heuristics used
  f. number of nodes visited in searching
  g. amount of knowledge used.
  ...
We may want to think that certain tricks are difficult for human,
but easy for the machine, and vice versa.

3. Using your conjectures to test popular Sudoku problem
instances with level of difficulties from easy, average, difficult
to tough.

4. Using your conjectures to generate random
Sudoku problem instances with a given level of difficulties.