Lab 3 Kakuro Solver using CSP

1
CS2180– Artificial Intelligence
Lab 3

Instructions: Upload to your moodle account one zip file containing the following. Please do
not submit hardcopy of your solutions. Late submission is not allowed without prior approval of
the instructor. You are expected to follow the honor code of the course while doing this
homework.
1. You can attempt this lab in teams of at most 2 members.
2. A neatly formatted PDF document with your answers for each of the questions in the
homework. You can use latex, MS word or any other software to create the PDF.
3. Include a separate folder named as ‘code’ containing the scripts for the homework along
with the necessary data files. You will implement this lab in Python 3.
4. Include a README file explaining how to execute the scripts.
5. Name the ZIP file using the following convention rollnumber_rollnumber_l3.zip
6. Submissions within 24 hours after the deadline will receive a 30% penalty.
7. Submissions within 48 hours after 24 hours of the deadline will receive a 50% penalty.
8. Submissions after 48 hours of the deadline will not be graded and will receive 0 points.
1. Kakuro Solver using CSP
The goal for this assignment is to implement a Kakuro solver that treats the puzzle as a
constraint satisfaction problem. Kakuro is a logic puzzle involving placement of digits in
squares satisfying certain constraints. Learn more about the puzzle from the Wikipedia article -
https://en.wikipedia.org/wiki/Kakuro
Your first goal is to formulate the puzzle as a constraint satisfaction problem. Identify the
variables, domains and constraints that define the problem. Automatically convert the n-ary
constraints into binary constraints. (5 points)
2
• Apply node and arc consistencies. (5 points)
• The next step is to write a generic backtracking search without any heuristics. Use this
backtracking search to find a solution to the Kakuro CSP. Let us call this search BS. (10
points)
• Finally, implement and integrate the MAC algorithm into BS. Call this algorithm BSMAC. (10 points)
Our goal is to study the performance of these algorithms on sample Kakuro puzzles. Define
performance metrics (such as search time, memory utilization, number of backtracks) that will
highlight the contrasting aspects of these algorithms. Include a PDF document in your
submission that reports the performance of the different algorithms and your detailed analysis.
Sample puzzles are provided in the simple folder of the zip file. The report carries 5 points.
Input
The input to your code will be the name of the text file containing the Kakuro puzzle. The
puzzle is in the following formatrows=14
columns=12
Horizontal
#,#,#,#,#,#,#,#,#,#,#,#
13,0,0,0,0,#,#,10,0,0,0,0
26,0,0,0,0,0,26,0,0,0,0,0
04,0,0,#,10,0,0,0,#,04,0,0
#,#,#,#,07,0,0,0,#,#,#,#
04,0,0,03,0,0,03,0,0,04,0,0
15,0,0,0,0,0,15,0,0,0,0,0
#,#,04,0,0,#,#,04,0,0,#,#
15,0,0,0,0,0,15,0,0,0,0,0
04,0,0,06,0,0,06,0,0,04,0,0
#,#,#,#,10,0,0,0,#,#,#,#
04,0,0,#,07,0,0,0,#,04,0,0
19,0,0,0,0,0,17,0,0,0,0,0
20,0,0,0,0,#,#,20,0,0,0,0
Vertical
#,06,07,08,16,#,#,#,13,08,06,07
#,0,0,0,0,16,#,17,0,0,0,0
#,0,0,0,0,0,04,0,0,0,0,0
#,0,0,#,#,0,0,0,#,#,0,0
#,08,03,#,15,0,0,0,15,#,08,03
#,0,0,07,0,0,#,0,0,07,0,0
#,0,0,0,0,0,#,0,0,0,0,0
#,06,04,0,0,15,#,15,0,0,06,04
#,0,0,0,0,0,#,0,0,0,0,0
#,0,0,#,0,0,04,0,0,#,0,0
#,07,06,#,#,0,0,0,#,#,07,06
3
#,0,0,08,17,0,0,0,16,08,0,0
#,0,0,0,0,0,#,0,0,0,0,0
#,0,0,0,0,#,#,#,0,0,0,0
First two lines indicates number of rows and columns respectively. The horizontal and vertical
represents one by one filling of respective cells in the row or column format of the board. ‘#’
represents black cells that do not have to be filled. Empty cells in the puzzle that need to be
filled with a number are represented as ‘0’.
Output
Your code must output to a text file the solved puzzle which must appear in the same format
as the puzzle in the input file.
Evaluation
We will compare the output of your program on sample puzzles. Please follow the output
formatting instructions as an automated checker will be used for comparison.