/kakuro-csp-model-solver

Modeling and solving Kakuro as a Constraint Satisfaction Problem (CSP)

Primary LanguagePythonOtherNOASSERTION

Modelling Kakuro as CSP and Solving Kakuro Puzzles

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.

Algorithms for CSP

The algorithms tested are combinations of:

  • BT (Backtracking-Search)
  • FC (Forward-Checking)
  • MAC (Maintaining-Arc-Consistency)
  • MRV (Minimum-Remaining-Values)
  • LCV (Least-Constraining-Value)

Usage

$ python3 kakuro.py

Implementation

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.

Kakuro Puzzles

The Kakuro puzzles are taken from here and here.

Runtime and Number of Assignments

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