CMSC 421 Programming Assignment 2Due Date: Thursday, October 17, 5PMFor this programming assignment, you will be modifying a backtracking imple-mentation of Sudoku to solve the Sudoku puzzle more efficiently.SudokuIn this game, your goal is to fill a 4x4, 6x6 or 9x9 grid such that each value in acolumn, row and block has a different value from other entries in the same row,column and block. Each cell in the grid can be filled with a digit from 1 to n(where n is the size of an nxn board).You can gain some intuition on how to solve this problem by checking:http://www.websudoku.comAlgorithmYou will solve the Sudoku puzzle as a constraint satisfaction problem (CSP).You will need to implement Minimum Remaining Values (MRV) heuristic, LeastConstraining Value (LCV) heuristic and Forward Checking. Backtracking hasbeen already implemented. Your goal is to modify this code to find the solutionas efficiently as poss ible.Code InfrastructureCopy the code from http://www.cs.umd.edu/class/fall2006/cmsc421/projects/pa2.tarto your directory. Read the documentation in the file thoroughly. A couple ofnotes on the code:1. Backtracking is implemented in the function (backtracking sudoku mcvlcv fc ac) where:(a) sudoku - a list representation of a sudoku board (Test cases are in-cluded).(b) mcv - if mcv = 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 Consistency2. You will need to compile the code in order to get results for this as signmentin a timely manner (ie: ”:cl sudoku-csp.lisp”)3. You should be able to run all the provided test c ase s in under a minute.4. You are free to modify the underlying infrastructure in order to improverun time. Document changes in your write up.Programming Assignment 2: CMSC 421, Introduction to Artificial Intelligence: Fall 20062Implementation and Discussion1. [30 points] Implem entation Implement the following functions to solvethe CSP:(a) [10 points] Modify the current implementation to supp ort ForwardChecking.(b) [10 points] Implement the Minimum Remaining Values (MRV) heuris-tic. (See Russell and Norvig p. 143)(c) [10 points] Implement the Least Constraining Value (LCV) heuris-tic. (See Russell and Norvig p. 144)Make sure that your code is well commented and readable. Also, makesure to remove all the debugging statements before submitting.2. [70 points] Results and Discussion Run your code on test cases test4,test6, test7, test8 and test9. You may present results from additional testcases if it helps in your discussion.Find the number of times an assignment is made (i.e.: Number of times avalue is set on the board during backtracking) and time (i.e.: (time (back-tracking test4 t nil nil nil))). Discuss and compare how these statisticschange/improve as you use:(a) Only Backtracking(b) Backtracking with MRV(c) Backtracking with LCV(d) Backtracking with forward checking(e) Backtracking with MRV and LCV(f) Backtracking with MRV, LCV and forward checking(Note: The write up will be graded for presentation, as well as correctness.Presentation of your results in tables is highly encouraged. You may also s um-marize your results by providing statistics, such as calculating the average, inaddition to presenting full results.)Extra Credit1. [15 points] Implement Arc Consistency. Note: You must submit the codeand discussion to get full credit.DeliverablesThe deliverables of this project is a single tar file, your-glue-id.tar, containingthe following files.Programming Assignment 2: CMSC 421, Introduction to Artificial Intelligence: Fall 200631. sudoku-csp.lisp - Your modified sudoku-csp.lisp containing your imple-mentation for this project.2. README.txt - A text file containing any implementation notes you wantus to be aware of. If you are unable to complete this assignment, this fileshould include what you were able to accomplish and what the outstandingbugs are.3. DISCUSSION.txt - A text file containing the write up of your results anddiscussions for this assignment.You must submit using your Grace account using ’submit 2006 fall cmsc 4210101 2
View Full Document
Unlocking...