SOLVING PUZZLE PROBLEM USING HEURISTIC SEARCH

Abstract

Puzzle is common example problems in basic Artificial Intelligence study. There are many types of puzzle problems. The one that will be discussed in this paper is one similar to the Tetravex game. The puzzle has nine tiles. Each tile has four faces, top, bottom, left and right. Each tile also contains a number from 1 - 9. In the beginning, the puzzle is empty and the user should put each tile in the puzzle with the only rule is that two tiles can only be placed next to each other if the numbers on adjacent face match. Basically, this problem is just a searching problem or more specifically searching a path put all tiles in the puzzle as quick as possible where adjacent face tile’s will have the same number. There are many ways to get the solution to this problem. The easiest way is using uninformed search or sometimes called blind search, such as Depth First Search or Breadth First Search. However, both searching techniques are not guarantee to get the solution. Even, when a solution is found, it may not have the lowest cost or the shortest path to the solution. To get the better solution, we could use informed search, such as: Hill Climbing Search, Best First Search, Beam Search, Branch and Bound and A* algorithm. Informed search or sometimes called heuristic search is differed to the uninformed search because it uses heuristic function. Informed search use heuristic function to decide which path will be explored next. The best algorithm to get the shortest path or the lowest cost is A* algorithm. In this paper, it will be discussed how to solve the puzzle problem using A* algorithm. To get the best of this algorithm, it should be decided what heuristic function will be used. This paper will show using the calculating correct tiles’ position as the heuristic function. However, the tile will not be placed in random, but first the tiles will be stored in four arrays according to the four face its has, up, bottom, left and right. The placing process is depends on the requirement by looking a tile in the corresponding array starting from center position that has the most adjacent face tiles.. This should reduce the numbers of trials, which hopefully will get the goal quickest than comparing to all possible tiles.