Kakuro or Kakkuro or Kakoro is a kind of logic puzzle that is often referred to as a mathematical transliteration of the crossword.
We model Kakuro as a CSP and solve Kakuro puzzles with various algorithms. Our goal is to show how different algorithms for CSP behave during the solution of these puzzles.
The algorithms tested are combinations of:
- BT (Backtracking-Search)
- FC (Forward-Checking)
- MAC (Maintaining-Arc-Consistency)
- MRV (Minimum-Remaining-Values)
- LCV (Least-Constraining-Value)
$ python3 kakuro.py
The csp.py, search.py and utils.py files are modified files of aimacode/aima-python.
The kakuro.py file is written by me and it's the modelization of Kakuro as a CSP and the main function.
The Kakuro puzzles are taken from here and here.
| Easy, 4x3 Puzzle | Average Runtime (seconds) | Average Number of Assignments |
|---|---|---|
| BT + FC + MRV | 0.00099 | 20 |
| BT + MAC + MRV | 0.00099 | 15 |
| BT + FC + MRV + LCV | 0.00096 | 15 |
| BT + MAC + MRV + LCV | 0.00401 | 33 |
| Easy, 6x6 Puzzle | Average Runtime (seconds) | Average Number of Assignments |
|---|---|---|
| BT + FC + MRV | 0.00697 | 72 |
| BT + MAC + MRV | 0.00797 | 46 |
| BT + FC + MRV + LCV | 0.00697 | 74 |
| BT + MAC + MRV + LCV | 0.01395 | 46 |
| Easy, 14x14 Puzzle | Average Runtime (seconds) | Average Number of Assignments |
|---|---|---|
| BT + FC + MRV | 2.02458 | 10027 |
| BT + MAC + MRV | 0.20046 | 214 |
| BT + FC + MRV + LCV | 1.33246 | 4949 |
| BT + MAC + MRV + LCV | 0.19248 | 215 |
| Intermediate, 5x7 Puzzle | Average Runtime (seconds) | Average Number of Assignments |
|---|---|---|
| BT + FC + MRV | 0.41786 | 1053 |
| BT + MAC + MRV | 0.50165 | 45 |
| BT + FC + MRV + LCV | 0.38500 | 862 |
| BT + MAC + MRV + LCV | 0.43480 | 45 |
| Hard, 6x6 Puzzle | Average Runtime (seconds) | Average Number of Assignments |
|---|---|---|
| BT + FC + MRV | 2.02458 | 10027 |
| BT + MAC + MRV | 0.20046 | 214 |
| BT + FC + MRV + LCV | 1.33246 | 4949 |
| BT + MAC + MRV + LCV | 0.19248 | 215 |