Applying Swarm Intelligence to Solve Heyawake Puzzles

Open Access
Author:
Kriston, Gregory Alan
Area of Honors:
Software Engineering (Behrend)
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
  • Wen Li Wang, Thesis Supervisor
  • Chris Stephen Coulston, Faculty Reader
  • Wen Li Wang, Honors Advisor
Keywords:
  • Heyawake
  • multiple constraint
  • heuristic
  • Ant Colony
  • Swarm Intelligence
Abstract:
Real world applications have many mutual restricted factors. Heyawake is one paper and pencil logic puzzle published by NIKOLI that has multiple constraints and is NP-complete. A heuristic method for solving the puzzle was developed and demonstrated. The method is based on the ant colony swarm intelligence technique. The developed method uses a two phase approach to handle the multiple constraints placed on the puzzle. The two phase approach demonstrated good performance on puzzles with highly restrictive characteristics and poorer performance on puzzles with less restrictive characteristics.