Description
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.
-
-
You can attempt this lab in teams of at most 2 members.
-
-
-
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.
-
-
-
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.
-
-
-
Include a README file explaining how to execute the scripts.
-
-
-
Name the ZIP file using the following convention rollnumber_rollnumber_l3.zip
-
-
-
Submissions within 24 hours after the deadline will receive a 30% penalty.
-
-
-
Submissions within 48 hours after 24 hours of the deadline will receive a 50% penalty.
-
-
-
Submissions after 48 hours of the deadline will not be graded and will receive 0 points.
-
-
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)
1
-
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 BS-MAC. (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 format-
rows=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
2
#,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.
3
