|
CS 3243 - Foundations of Artificial Intelligence
NUS SoC, 2004/2005, Semester II |
|
|
CS 3243 - Foundations of Artificial Intelligence
NUS SoC, 2004/2005, Semester II |
[ IVLE ]
[ Overview ]
[ Syllabus ]
[ Grading ]
[ Homework ]
[ HW 1 ]
[ HW 2T ]
[ >HW 2I ]
[ Misc. ]
Su Doku ("number place" in Japanese) are logic puzzles similar to cryptarithmetic that we studied in CSP. In classic su doku, a 9x9 grid is laid out with blank squares. Each column and row must have exactly one instance of each digit, '1' through '9'. In addition, each of the 9 3x3 squares must also obey the same constraint: they must have exactly have one instance of each digit.
A su doku problem comes only with the grid partially filled. The agent's problem is then to fill in the rest of the grid, given the constraints above.
It is easy to see that the 9 digits can be replaced by any number of symbols as long as the number is a perfect square. You can do Su Doku on problems of 2x2 = 4 symbols, 3x3 = 9 symbols (the normal version), 4x4 = 16 symbols, 5x5, etc. You will be creating an agent to solve 4x4 problems, such as the one below.
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.
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 Hex Su Doku above. As the agent will have to solve 16x16 puzzles we will be using hexadecimal (Computer science's favorite base), and using single alphanumeric symbols between 0-9 and A-F. Corrected again on Wed Mar 22 02:59:51 GMT-8 2006)
1--234--B-6---7- --8---7--3--906A -B--0--1-C-A--D- 3--E2--D---9--B- C---8--0-B2-1E-- -A76---F---E--5C ---0-5E--4-8--A- F--59B--1-----8- -2-----C--B58--3 -C--E-3--D8-F--- 58--1---2---C9E- --B4-6F-C--7---5 -3--B---6--4A--F -7--F-5-D--1--2- A1E9--C--2---D-- -D---A-2--C35--B
Each su doku input will be a 16x16 character text file consisting of entries of '-' (blanks to fill in), or the characters '0-9' or 'A-F' (uppercase only).
Your program is to print out the same input file but with the numbers filled in, to solve the su doku.
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 will be written for you (in C), 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 letter, and the original (updated Wed Mar 22 02:59:51 GMT-8 2006)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.
Note that Prolog has its own AllDiff primitive
function, which you are not allowed to use. You must code your
own. If you find 4x4 grids daunting, try some 3x3 or 2x2 grids (there
are tons on the net) as the logic and strategy for solving them is
identical.
This is pretty much cut and pasted from HW #1. 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: 6 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 penalties for lateness.
Here you can find a sample submission zip file with the included sample prolog output, and simple 2x2 su doku grids for input and correct output. The sample submission file contains a sample input and output helper applications. You'll have to modify at least the sample input helper application or write your own.
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.
Su Doku Links
Min-Yen Kan <kanmy@comp.nus.edu.sg> Mon Mar 7 15:29:26 2005 | Version: 1.0 | Last modified: Fri Mar 24 17:34:26 2006