|
CS 3243 - Foundations of Artificial Intelligence > Homework 1 (Individual)
NUS SoC, 2004/2005, Semester II |
|
|
CS 3243 - Foundations of Artificial Intelligence > Homework 1 (Individual)
NUS SoC, 2004/2005, Semester II |
[ IVLE ]
[ Overview ]
[ Syllabus ]
[ Grading ]
[ Homework ]
[ HW 1 ]
[ HW 2T ]
[ >HW 2I ]
[ Misc. ]
(Updated on Wed Mar 16 01:08:26 GMT-8 2005 )
Cross sums are simple logic puzzles similar to cryptarithmetic that we studied in CSP. In cross sums, a grid is laid out with white blank squares and black borders. Each column and row must total a specific amount, denoted in the black border squares, as shown below.
Each column and row have to add up to the specified number in the border to the left or top. Tiles must be filled with a number between 1-9, inclusive, and number may not be repeated in each column and row (E.g., a row with two blanks summing to four must either be filled with '1' '3' or '3' '1'). A sample solution for the above puzzle is then:
Your job is to implement a cross sum solver using Prolog. Prolog is a great language for solving constraint satisfaction problems and can handle these problems with relative ease. Prolog already has an inference engine capable of solving CSPs efficiently. Your job is to encode this assignment in a way that translates the problem effectively. To do this you will have to learn more about Prolog and how it represents constraints and programs. Note that a cross sum can have at most an entry of length 9 and it must be constrained to have a total of 45.
Your program will be given a text file as input, and asked to solve it. The text file will look like this for the sample cross sum above.
-,- 4,- 3,- -,3 _ _ -,4 _ _
Each cross sum input will be a text file consisting of entries separated by one or more spaces. A '-,-' entry indicates a black border square. A '_' entry indicates a number to be filled in. The 'XX,YY' entry indicate a constraint for either a column 'XX' or a row 'YY' or both. For example, the entry '4,-' in the sample file indicates that the column below this cell sums to '4'. We can see by visual inspection that the column sum involves two entries. The cross sums you will be given will not exceed 20 x 20.
Your program is to print out the same input file but with the numbers filled in. For the sample output, it should generate:
-,- 4,- 3,- -,3 1 2 -,4 3 1
The inputs will have a unique solution, so you won't have to use Prolog's facility to generate more than one answer.
Prolog is great at CSPs, but pretty lousy when it comes to input and output. You should create helper programs in another imperative language to transform the input file into constraints to be added to the knowledge base. Then run Prolog on the output of the program. Process the output from Prolog using a second helper program to get it into the correct format for output. A sample output processor has been written for you in perl, if you choose to use it. It requires both the output of a prolog run, in which each blank is coded by a column letter and a row number, and the original input file.
Your pipeline should look like this:
You should install SWI Prolog (see links at the end of this assignment as soon as possible or (better yet) do your assignment on sunfire, where it is already installed for you. Follow a simple tutorial to get started on how to program in Prolog. This may take you about 1-2 hrs on its own.
For me to grade this assignment accordingly, I need you to adhere strictly to the following submission guidelines. They will help me grade the assignment in an appropriate manner. You will be penalized if you do not follow these instructions. Your matric number in all of the following statements should not have any spaces and any letters should be in CAPITALS. You are to turn in the following files:
README-<matric
number>.txt (e.g., README-HT00000X.txt): this is
a text only file that describes any information you want me to
know about your submission. You should not include any
identifiable information about your assignment (your
name, phone number, etc.) except your matric number and email
(I need the email to contact you about your grade, please use
your u*****@nus.edu.sg address, not your email alias).
This is to help you get an objective grade in your assignment,
as I won't associate matrics with student names.
These files will need to be suitably zipped in a single file called submission-<matric number>.zip. Please use a zip archive and not BZIP, RAR or CAB files. Make sure when the archive unzips that all of the necessary files are found in the current directory (please do not nest your files in internal folders). Upload the resulting zip file to the IVLE workbin by the due date: 7 Apr 05, 11:59:59 pm SGT. There absolutely will be no extensions to the deadline of this assignment. Read the late policy if you're not sure about grade penalities for lateness.
Prolog links:
There is a working version of SWI Prolog on sunfire.comp.nus.edu.sg that you can use if you choose to do this assignment in the Sun Solaris UNIX environment. It is located at /home/rsch/rpnlpir/tools/languages/programming/pl/bin/. You should place this in your PATH environment variable.
Cross Sum Links
Min-Yen Kan <kanmy@comp.nus.edu.sg> Mon Mar 7 15:29:26 2005 | Version: 1.0 | Last modified: Thu Mar 17 09:14:02 2005