Solving and Modeling Ken-ken Puzzle byUsingHybridGeneticsAlgorithm

Abstract

Kenken is logic puzzle which similar to Sudoku. The basic rules are same as Sudoku. As in sudoku, the goal of each puzzle is to fill a grid with digits 1 through 4 for a 4Ã4 grid, 1 through 5 for a 5Ã5, etc. No digit appears more than once in any row or column. Grids range in size from 3Ã3 to 9Ã9. Unlike sudoku, KenKen grids are divided into heavily outlined groups of cells often called âcagesâ and the numbers in the cells of each cage must produce a certain âtargetâ number when combined using a specified mathematical operation (addition, subtraction, multiplication or division). ). For example, a three-cell cage specifying addition and a target number of 6 in a 4Ã4 puzzle might be satisfied with the digits 1, 2, and 3. Digits may be repeated within a cage, as long as they are not in the same row or column. No operation is relevant for a single-cell cage: placing the "target" in the cell is the only possibility. The target number and operation appear in the upper left-hand corner of the cage. Initially, none of the cell in a cage in Kenken has value. Kenken is such a simple logic puzzle, but finding the solution is quite complex, especially for harder problem. Therefore, research is conducted to develop software which can solve Kenken problem.The research will produce software that can solve kenken puzzle byusingheuristic search and hybrid genetic algorithm. Heuristic search will be done by applying certain logic rules. If the puzzle is still not being able to be solved then hybrid genetic algorithm will be run. How can the software solve the kenken problem will be explained in this paper.After conducting some researchs and implementing the software and doing the testing, some experiments were conducted and it proved that the hybrid genetics algorithm can solve the kenken puzzle and bbased on experiment result, the size of puzzle and the difficulty of problems affect the time needed to find a solution