HW#1 --- last modified February 07 2019 23:07:54..
Solution set.
Due date: 1_DATE
Files to be submitted:
Hw3.zip
Purpose:To write a CSP solver for Sudoku. To learn more about logic-based agents.
Related Course Outcomes:
The main course outcomes covered by this assignment are:
LO2 -- By code or by hand translate sentences in logic to conjunctive normal form (CNF).
LO3 -- By code or by hand find proofs by using resolution.
LO7 -- Students should be able to explain the advantages and disadvantages of forward checking in constraint satisfaction.
Specification:
Do problems 7.11, 7.12, 7.20. For 7.11, besides your proof give, some examples of applying it to some propositional formulas
to get a CNF. For the coding part of the assignment I want you to write a program that solves sudoku games (if possible).
Put the problems in HWProblems.txt in your Hw3.zip file.
Your program will be run from the command line as follows:
python sudoku.py some_file.txt
where some_file.txt could be any text file that has a sudoku puzzle in it. Such a text file consists of exactly 9 lines using '\n'
as the end-of-line indicator. Each line excluding the line terminator is exactly 9 characters long, where these characters are from
among: 1,2,3,4,5,6,7,8,9,* . * Indicates a blank square. For example,
**3*2*6**
9**3*5**1
**18*64**
**81*29**
7*******8
**67*82**
**26*95**
8**2*3**9
**5*1*3**
Your program should print out a solution in a similar format if a solution exists to the puzzle. It should output "No solution exists" otherwise.
Your program should use the AC-3 algorithm and the backtracking algorithm from class to solve the puzzle. Back-tracking should use the MRV heuristic and forward checking heuristic. Put sudoku.py and any other code files
into your Hw3.zip file.
Point Breakdown
Problems (1pt each, added examples for 7.11 also worth a point) |
4pts
|
PEP 8 coding guidelines followed, code seems reasonably elegant. |
1pt
|
Program makes use of command-line arguments to read in the file supplied. |
1pt
|
AC-3 algorithm implemented correctly, run as a pre-processing step. |
1pt
|
Back-tracking algorithm implemented correctly. |
1pt
|
MRV Heuristic used. |
1pt
|
Forward chaining implmented. |
1pt
|
Total | 10pts |
|