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)
• 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
#,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.
3
