Developing a Kakuro Puzzle Solver Using Swarm Intelligence
Open Access
- Author:
- Shuster, Matthew
- Area of Honors:
- Software Engineering (Behrend)
- Degree:
- Bachelor of Science
- Document Type:
- Thesis
- Thesis Supervisors:
- Xiaocong Fan, Thesis Supervisor
Wen Li Wang, Thesis Honors Advisor
Xiaocong Fan, Thesis Supervisor - Keywords:
- ant colony optimization
artificial intelligence
swarm intelligence
kakuro
logic puzzle - Abstract:
- Kakuro is a non-polynomial (NP) complete, highly-coupled numerical puzzle that visually resembles a crossword puzzle, but involves mathematical combinations. The primary motivation for solving it stems from the fact that such a solution can be modified to solve other real-world problems, such as data storage utilization, circuit wiring, and multiprocessor scheduling, which are also considered NP-complete problems. The Kakuro-solver developed is based on the concept of swarm intelligence, an artificial intelligence (AI) built on the communication and learning that occur between numerous problem-solving agents. These interactions are facilitated via shared conflict data. Through learning, these agents are able to find better possible answers based on a set of heuristics, eventually developing the puzzle's correct solution. These heuristics govern the modifications made to a potential solution, and are vital to solving success. Experimental results show that the program created is time-efficient, and is capable of solving several puzzles. Also, a discussion is presented for the advantages and disadvantages of the algorithmic-based and AI-based solving approaches. Future work will focus on observing solving patterns and modifying the AI to increase solving efficiency based on these findings.