CSE471/598 Sping 2009
Project 2: Sudoku with CSP
Assigned [Feb 26, 2009]
Due [Mar 19, 2009]

(Project courtesy Lise Getoor and Mustafa Bilgic)

For this programming assignment, you will be modifying a backtracking
imple- mentation of Sudoku to solve a variant of Sudoku which includes
a diagonal constraint and to solve the Sudoku puzzle more efficiently.

Sudoku

In this game, your goal is to fill a 9x9 grid such that each value in
a column, row, block and main diagonal has a different value from
other entries in the same row, column, block and main diagonal. Each
cell in the grid can be filled with a digit from 1 to 9.  You can gain
some intuition on how to solve this problem by checking:
http://www.websudoku.com

Algorithm

You will solve the Sudoku puzzle as a constraint satisfaction problem
(CSP).  Backtracking has been already implemented. You will need to
modify the code to incorporate a main diagonal constraint and
implement Minimum Remaining Values (MRV) heuristic, Least Constraining
Value (LCV) heuristic, Forward Checking and Arc Consistency. Your goal
is to modify this code to find the solution as efficiently as
possible.

Code Infrastructure

Copy the code from the accompanying link. Read the documentation in
the file thoroughly. A couple of notes on the code:

1. Backtracking is implemented in the function 
(backtracking sudoku mrv lcv fc ac) where:

(a) sudoku - an array representation of a sudoku board (Test cases are
included).
(b) mrv - if mrv = t, do Minimum Remaining Values (MRV)
(c) lcv - if lcv = t, do Least Constraining Value (LCV)
(d) fc - if fc = t, do Forward Checking
(e) ac - if ac = t, do Arc Consistency 

2. You will need to compile the code in order to get results for this
assignment in a timely manner

3. You should be able to run all the provided test cases in under a
few minutes.

4. You are free to modify the underlying infrastructure in order to
improve run time. Document changes in your write up.


Implementation and Discussion

1. Implementation Implement the following functions to solve
the CSP:

(a) Modify the code to check for the main diagonal constraint.
     [**If you have trouble doing part a, go ahead and do the other
        parts**]

(b)  Implement the Minimum Remaining Values (MRV) heuris-
tic. (See Russell and Norvig p. 143)
(c) Implement the Least Constraining Value (LCV)
heuristic.(See Russell and Norvig p. 144)
(d)  Modify the current implementation to support Forward
Checking.
(e)[Optional/Extra Credit] Modify the current implementation to
support Arc Consistency

Make sure that your code is well commented and readable.

2. Results and Discussion Run your code on test cases *test1*--*test6*
from the accompanying test case file.  You may present results from
additional test cases if it helps in your discussion.

Find the number of times an assignment is made (i.e.: Number of times
a value is set on the board during backtracking) and time (i.e.: (time
(back- tracking test4 t nil nil nil))). Discuss and compare how these
statistics change/improve as you use:

(a) Only Backtracking
(b) Backtracking with MRV
(c) Backtracking with LCV
(d) Backtracking with MRV and LCV
(e) Backtracking with forward checking
(f) Backtracking with MRV, LCV and forward checking
(g)[Optional/extra credit] Backtracking with arc consistency
(h)[Optional/extra credit] Backtracking with arc consistency and forward checking
(i)[Optional/extra credit]  Backtracking with MRV, LCV, forward checking and arc consistency.

The write up will be graded for presentation, as well as
correctness. Presentation of your results in tables is highly
encouraged. You may also summarize your results by providing
statistics, such as calculating the average, in addition to presenting
full results.

Additional extra credit portions may be added.