8-puzzle
This project aims to develop a solution for the 8 puzzle problem using 3 path finding and graph traversal algorithms:
1- Breadth First Search algorithm (BFS)
2- A Star algorithm (A*)
Problem Statement
The 8 puzzle consists of numbered, movable tiles set in a 3x3 frame, where one tile is missing and you can move the other tiles into the gap until you get the puzzle into the goal state. The following figures show different states of an 8 puzzle. The solved puzzle is the final state while the remaining two are in unsolved state. The rules of the game are that we need to move the blank tile either left, right, top, center (depending upon its position) so as to achieve the final state. The arrows indicate the possible moves for the blank tile. The blank tile needs to be moved till we reach the goal state. Unsolved Unsolved Goal State
Tree Generation
We will represent this problem using a tree, where the nodes represent potential states of the puzzle and edges represents possible moves. the initial state of the puzzle is considered as the route node. The search for a solution, by expanding the root state using successor function (here it is the possible moves) and generate new research nodes as children of the root node. The search continues by expanding new other nodes in the tree respectively. The search strategy (the algorithms) determines in which order the nodes of the tree are expanded. The search stops when the solution is found
Implementation Technique
The idea is to search the state space and find the shortest route to the goal state.
During the search we need to keep track of two lists of states. The first list is the openList list, which stores nodes, which we have generated by using the rules from an existing node. Nodes in this list are expanded but not generated). The second list is the closedList, which contains the nodes, we have generated and we have also checked/visited.
The node represent a state of the puzzle. It is a data structure with with some extra data required to help us in our search:
1- The state to which the node corresponds (grid)
2- Parent pointer. We need to know how we got to this node, as the end result of finding the GOAL state will be to generate a path back to the start.
3- The action that was applied to the parent to generate this node (index) 4- The cost of the path from the initial state to the node (depth)
Algorithms
As we said before the search strategies are determined by the search algorithms. So, each algorithm has its only strategy to choose what is the next node to expand.
A star or A* algorithm:
Some extra data on the nodes are required to help us in our search: g : a measure if the cost of getting from the initial state to the current node h : The actual cost of getting from the current node to the goal (heuristic value) f : The true evaluation of the node or the priority function we start with openList containing only the initial node. Set the node’s g value to 0, its h’ value to whatever it is (calculated using an heuristic function, see section below), and its f’ value to h’+0, or h’. Set closedList to the empty list. Until a goal node is found, repeat the following procedure: If there are no nodes in openList, report failure. Otherwise, pick the node in openList that have the lowest f’ value (function getBestNode). Call it bestnode. Remove it from openList. Place it in closedList. See if bestnode is the goal node. If so, exist and report a solution ( the path that has been created between the initial state and bestnode, function getSolution). Otherwise, generate the children of bestnode (function getChildNode). For each such child do the following:
- Check if the child is in the closedList. If yes, discard the child ( the child is visited before)
- If not, compute the f, g and h values of the child. Set the depth of child = depth of bestrode +1.
- Check if there is a node with the same grid in openList (i.e. the child has already been generated but not preceded). If yes, check if the g value of this node in the openList is smaller than the g value off the child. If yes, discard the child. If no, replace the node in the
- openLlist with child.
- If the child is not in openList neither in closedList, add it to openList. Set prep too the child to point back to bestnode. These backwards links will make it possible to recover the path once a solution is found.
priority function and heuristic technique
The success of the A star algorithm hinges on the choice of priority function for a search node. The priority function will help us to determine the next node in the tree to visit/process. In this project, the technique I used to evaluate the actual cost of getting from the current node to the goal (the heuristic value h) is the number of displaced titles ( the blank tile is not counted). Ex: h= 6 So, the priority function is the number of blocks in the wrong position, plus the number of moves made so far to get to the search node. Intuitively, a search node with a small number of blocks in the wrong position is close to the goal, and we prefer a search node that have been reached using a small number of moves.
Breadth First Search algorithm (BFS)
The difference between the a star algorithm and the BFS algorithm is how to choose the next node to visit/process. in BFS, the algorithm starts at the tree root (initial node) . It explores all the nodes and process them in a depth first, before moving to the next depth.
Finally
In the 8 puzzle files, there are 2 files ( astar.c and BFS.c). In each file, in the main function, a little scenario to test the two algorithms is implemented. In the scenario, the puzzle { 1, 5, 2, 8, 0, 3, 4, 7, 6} will be the initial node. The algorithms search the solution for this puzzle. Each program will print the solution with the number of moves and the number of nodes generated to find the solution by each algorithm (To see it, just compile and execute astar.c and BFS.c). Note: MAX_DEPTH is set to 10 in the programs. (the maximum depth of the tree to find the solution)