Implementation of Heuristic Technique and Genetic Algorithms in Shikaku Puzzle Problem

Abstract:

Shikaku is a logic puzzle published by Nikoli at 2005. Shikaku has a very simple rule. This puzzle is played on a rectangular grid. Some of the squares in the grid are numbered. The main objective is to create partitions inside the grid. Each partition must have exactly one number, and the number represents the area of the partition. Then the partition’s shape must be a rectangular or a square. The aim of this research is discussing how can computer software be able to solve the Shikaku problem by implementing heuristic technique and genetics algorithms. Initially the Shikaku problem is inputted into the system. Firstly, the software will solve the problem by applying heuristics methods with some logic rules. All logic rules are created and implemented into the software so that the software can minimize the partitions possibilities to the problem. If this heuristics method still can not solve the problem then genetic algorithms will be executed to find the solution. This paper elaborates from how the problem be modelled and also be implemented until software testing to ensure that the solver worked as expected. The implementation consists of a virtual puzzle board with three different size, genetic algorithms parameters, and ability to create, save, load, and solve puzzle. Software testing is conducted to find how fast the system can solve the problem.

• Periodical: Applied Mechanics and Materials (Volumes 58-60)
• Pages: 1860-1865
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.58-60.1860
• Online since: June 2011
• Authors: Samuel Lukas, Arnold Aribowo, Steven Christian Halim
• Keywords: Genetic Algorithm (GA), Heuristic Search, Shikaku Puzzle

References

[1] Adrianysah, Yusuf. Kombinasi Tiga Algoritma untuk Puzzle Shikaku. http: /www. informatika. org/~rinaldi/Stmik/2009-2010/Makalah2009/MakalahIF3051-2009-045. pdf; Internet; accessed on August 15, (2010).

[2] Wikipedia. Shikaku. http: /en. wikipedia. org/wiki/Shikaku; Internet; accessed on August 27, (2010).

[3] Nikoli. com. Sample Problems Of Shikaku. http: /www. nikoli. com/en/puzzles/shikaku; Internet; accessed on August 30, (2010).