Kakuro is a logic puzzle that is often referred to as a mathematical transliteration of the crossword. The aim of this work is to see how certain algorithms behave through solving this game.
Kakuro is a logic puzzle that is often referred to as a mathematical transliteration of the crossword. The puzzle is played in a grid of filled and barred cells, “black” and “white” respectively. The black cells contain a diagonal slash from upper-left to lower-right and a number in one or both halves, such that each horizontal entry has a number in the black half-cell to its immediate left and each vertical entry has a number in the black half-cell immediately above it. The objective of the puzzle is to insert a digit from 1 to 9 inclusive into each white cell such that the sum of the numbers in each entry matches the clue associated with it and that no digit is duplicated in any entry.
There are four different puzzles to be solved and there have been 3 different algorithms to achieve that.
The algorithms are:
Those algorithms were forked by AIMA (https://github.com/aimacode/aima-python).
The file of my code is kakuro.py and all the rest are also from AIMA.
The time-table:
SIMPLE BACKTRACKING - BT | FORWARD CHECKING - FC | MAINTAINING ARC CONSISTENCY - MACKAKURO1 25 microsec 0,... microsec 1 microsecKAKURO2 2 microsec 0,... microsec 1 microsecKAKURO3 44431 microsec 4 microsec 7 microsecKAKURO4 1097825 microsec 21 microsec 35 microsec
So, we notice that simple backtracking is by far the slowest algorithm, while FC and MAC have close times but obviously faster is FC. This result was expected because the FC and MAC are improvements BT.
In order to run the program you need at least python 3.3