This assignment accounts for ine sixth of your internal 316 marks.

1. (50 marks) Question 1: Implement a Reversi (aka Othello) player based on alpha-beta pruning search.

   Simply use the difference in stones (black-white) as your heuristic function, plus use +100 for a win of black, and -100 for a win of white. For the rules of the game see Reversi on Wikipedia.

   Your program should read from standard in and output to standard out (System.in and System.out in Java).

   Expect to read-in a game position plus an indicator for which side is to move, where ".", "+", "-" are used for "free", "black" player, and "white" player respectively. For instance, the starting position, where "black" is expected to move, would be represented as:

   ........
........
........
...-+...
...+-...
........
........
........
+


   You should output one line with the coordinates of your move, the number of nodes expanded, the max search depth reached, and the minimax estimate, e.g.

   move c 4 nodes 123345 depth 12 minimax 27

   One clarification: if a player cannot move, they pass. If the input position does not allow for any move (i.e. you have to pass), return:

   move a -1 nodes 0 depth 0 minimax 0

   Your program should search for about 3 minutes before terminating.

2. (50 marks) Implement a backtracking Sudoku puzzle solver based on Constraint Propagation.
   Your solver should maintain a set of possible values for each variable, and remove a values appropriately. Also, once a variable has only one value left, assign it immediately (a form of forward checking).

   Also implement the AC-3 consistency checker.

   For ten different Sudoku puzzles (e.g. from online newspapers), use your solver to find a solution. Report the number of nodes backtracking had to expand and the total runtime for all ten puzzles and 3 different ways of solving:

   1. using just backtracking search
   2. using AC-3 as a preprocessing step followed by backtracking search
   3. using AC-3 as both a preprocessing step and inside backtracking search after each single value to variable assignment

1. short reports for the results of 1 and 2
2. source code for 1 and 2

You may use any of the following languages: Java, C, C++, C#, Python, Ruby, Haskell.