We have introduced Branch and Bound and discussed 0/1 Knapsack problem in below posts.
In this puzzle solution of 8 puzzle problem is discussed.
Given a 3×3 board with 8 tiles (every tile has one number from 1 to 8) and one empty space. The objective is to place the numbers on tiles to match final configuration using the empty space. We can slide four adjacent (left, right, above and below) tiles into the empty space.
For example,
1. DFS (Brute-Force)
We can perform depth-first search on state space (Set of all configurations of a given problem i.e. all states that can be reached from initial state) tree.
state space tree for 8 puzzle
In this solution, successive moves can take us away from the goal rather than bringing closer. The search of state space tree follows leftmost path from the root regardless of initial state. An answer node may never be found in this approach.
[ad type=”banner”]
2. BFS (Brute-Force)
We can perform a Breadth-first search on state space tree. This always finds a goal state nearest to the root. But no matter what the initial state is, the algorithm attempts the same sequence of moves like DFS.
3. Branch and Bound
The search for an answer node can often be speeded by using an “intelligent” ranking function, also called an approximate cost function to avoid searching in sub-trees that do not contain an answer node. It is similar to backtracking technique but uses BFS-like search.
There are basically three types of nodes involved in Branch and Bound
1. Live node is a node that has been generated but whose children have not yet been generated.
2. E-node is a live node whose children are currently being explored. In other words, an E-node is a node currently being expanded.
3. Dead node is a generated node that is not to be expanded or explored any further. All children of a dead node have already been expanded.
Cost function:
Each node X in the search tree is associated with a cost. The cost function is useful for determining the next E-node. The next E-node is the one with least cost. The cost function is defined as,
C(X) = g(X) + h(X) where
g(X) = cost of reaching the current node
from the root
h(X) = cost of reaching an answer node from X.
[ad type=”banner”]
Ideal Cost function for 8-puzzle Algorithm :
We assume that moving one tile in any direction will have 1 unit cost. Keeping that in mind, we define cost function for 8-puzzle algorithm as below :
c(x) = f(x) + h(x) where
f(x) is the length of the path from root to x
(the number of moves so far) and
h(x) is the number of non-blank tiles not in
their goal position (the number of mis-
-placed tiles). There are at least h(x)
moves to transform state x to a goal state
An algorithm is available for getting an approximation of h(x) which is a unknown value.
Complete Algorithm:
/* Algorithm LCSearch uses c(x) to find an answer node
* LCSearch uses Least() and Add() to maintain the list
of live nodes
* Least() finds a live node with least c(x), deletes
it from the list and returns it
* Add(x) adds x to the list of live nodes
* Implement list of live nodes as a min heap */
struct list_node
{
list_node *next;
// Helps in tracing path when answer is found
list_node *parent;
float cost;
}
algorithm LCSearch(list_node *t)
{
// Search t for an answer node
// Input: Root node of tree t
// Output: Path from answer node to root
if (*t is an answer node)
{
print(*t);
return;
}
E = t; // E-node
Initialize the list of live nodes to be empty;
while (true)
{
for each child x of E
{
if x is an answer node
{
print the path from x to t;
return;
}
Add (x); // Add x to list of live nodes;
x->parent = E; // Pointer for path to root
}
if there are no more live nodes
{
print ("No answer node");
return;
}
// Find a live node with least estimated cost
E = Least();
// The found node is deleted from the list of
// live nodes
}
}
Below diagram shows the path followed by above algorithm to reach final configuration from given initial configuration of 8-Puzzle. Note that only nodes having least value of cost function are expanded.
[pastacode lang=”c” manual=”%2F%2F%20Program%20to%20print%20path%20from%20root%20node%20to%20destination%20node%0A%2F%2F%20for%20N*N%20-1%20puzzle%20algorithm%20using%20Branch%20and%20Bound%0A%2F%2F%20The%20solution%20assumes%20that%20instance%20of%20puzzle%20is%20solvable%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%23define%20N%203%0A%20%0A%2F%2F%20state%20space%20tree%20nodes%0Astruct%20Node%0A%7B%0A%20%20%20%20%2F%2F%20stores%20parent%20node%20of%20current%20node%0A%20%20%20%20%2F%2F%20helps%20in%20tracing%20path%20when%20answer%20is%20found%0A%20%20%20%20Node*%20parent%3B%0A%20%0A%20%20%20%20%2F%2F%20stores%20matrix%0A%20%20%20%20int%20mat%5BN%5D%5BN%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20stores%20blank%20tile%20cordinates%0A%20%20%20%20int%20x%2C%20y%3B%0A%20%0A%20%20%20%20%2F%2F%20stores%20the%20number%20of%20misplaced%20tiles%0A%20%20%20%20int%20cost%3B%0A%20%0A%20%20%20%20%2F%2F%20stores%20the%20number%20of%20moves%20so%20far%0A%20%20%20%20int%20level%3B%0A%7D%3B%0A%20%0A%2F%2F%20Function%20to%20print%20N%20x%20N%20matrix%0Aint%20printMatrix(int%20mat%5BN%5D%5BN%5D)%0A%7B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20N%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%20N%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20mat%5Bi%5D%5Bj%5D)%3B%0A%20%20%20%20%20%20%20%20printf(%22%5Cn%22)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Function%20to%20allocate%20a%20new%20node%0ANode*%20newNode(int%20mat%5BN%5D%5BN%5D%2C%20int%20x%2C%20int%20y%2C%20int%20newX%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20newY%2C%20int%20level%2C%20Node*%20parent)%0A%7B%0A%20%20%20%20Node*%20node%20%3D%20new%20Node%3B%0A%20%0A%20%20%20%20%2F%2F%20set%20pointer%20for%20path%20to%20root%0A%20%20%20%20node-%3Eparent%20%3D%20parent%3B%0A%20%0A%20%20%20%20%2F%2F%20copy%20data%20from%20parent%20node%20to%20current%20node%0A%20%20%20%20memcpy(node-%3Emat%2C%20mat%2C%20sizeof%20node-%3Emat)%3B%0A%20%0A%20%20%20%20%2F%2F%20move%20tile%20by%201%20postion%0A%20%20%20%20swap(node-%3Emat%5Bx%5D%5By%5D%2C%20node-%3Emat%5BnewX%5D%5BnewY%5D)%3B%0A%20%0A%20%20%20%20%2F%2F%20set%20number%20of%20misplaced%20tiles%0A%20%20%20%20node-%3Ecost%20%3D%20INT_MAX%3B%0A%20%0A%20%20%20%20%2F%2F%20set%20number%20of%20moves%20so%20far%0A%20%20%20%20node-%3Elevel%20%3D%20level%3B%0A%20%0A%20%20%20%20%2F%2F%20update%20new%20blank%20tile%20cordinates%0A%20%20%20%20node-%3Ex%20%3D%20newX%3B%0A%20%20%20%20node-%3Ey%20%3D%20newY%3B%0A%20%0A%20%20%20%20return%20node%3B%0A%7D%0A%20%0A%2F%2F%20botton%2C%20left%2C%20top%2C%20right%0Aint%20row%5B%5D%20%3D%20%7B%201%2C%200%2C%20-1%2C%200%20%7D%3B%0Aint%20col%5B%5D%20%3D%20%7B%200%2C%20-1%2C%200%2C%201%20%7D%3B%0A%20%0A%2F%2F%20Function%20to%20calculate%20the%20the%20number%20of%20misplaced%20tiles%0A%2F%2F%20ie.%20number%20of%20non-blank%20tiles%20not%20in%20their%20goal%20position%0Aint%20calculateCost(int%20initial%5BN%5D%5BN%5D%2C%20int%20final%5BN%5D%5BN%5D)%0A%7B%0A%20%20%20%20int%20count%20%3D%200%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20N%3B%20i%2B%2B)%0A%20%20%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%20N%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20if%20(initial%5Bi%5D%5Bj%5D%20%26%26%20initial%5Bi%5D%5Bj%5D%20!%3D%20final%5Bi%5D%5Bj%5D)%0A%20%20%20%20%20%20%20%20%20%20%20count%2B%2B%3B%0A%20%20%20%20return%20count%3B%0A%7D%0A%20%0A%2F%2F%20Function%20to%20check%20if%20(x%2C%20y)%20is%20a%20valid%20matrix%20cordinate%0Aint%20isSafe(int%20x%2C%20int%20y)%0A%7B%0A%20%20%20%20return%20(x%20%3E%3D%200%20%26%26%20x%20%3C%20N%20%26%26%20y%20%3E%3D%200%20%26%26%20y%20%3C%20N)%3B%0A%7D%0A%20%0A%2F%2F%20print%20path%20from%20root%20node%20to%20destination%20node%0Avoid%20printPath(Node*%20root)%0A%7B%0A%20%20%20%20if%20(root%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20printPath(root-%3Eparent)%3B%0A%20%20%20%20printMatrix(root-%3Emat)%3B%0A%20%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%7D%0A%20%0A%2F%2F%20Comparison%20object%20to%20be%20used%20to%20order%20the%20heap%0Astruct%20comp%0A%7B%0A%20%20%20%20bool%20operator()(const%20Node*%20lhs%2C%20const%20Node*%20rhs)%20const%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20return%20(lhs-%3Ecost%20%2B%20lhs-%3Elevel)%20%3E%20(rhs-%3Ecost%20%2B%20rhs-%3Elevel)%3B%0A%20%20%20%20%7D%0A%7D%3B%0A%20%0A%2F%2F%20Function%20to%20solve%20N*N%20-%201%20puzzle%20algorithm%20using%0A%2F%2F%20Branch%20and%20Bound.%20x%20and%20y%20are%20blank%20tile%20coordinates%0A%2F%2F%20in%20initial%20state%0Avoid%20solve(int%20initial%5BN%5D%5BN%5D%2C%20int%20x%2C%20int%20y%2C%0A%20%20%20%20%20%20%20%20%20%20%20int%20final%5BN%5D%5BN%5D)%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20priority%20queue%20to%20store%20live%20nodes%20of%0A%20%20%20%20%2F%2F%20search%20tree%3B%0A%20%20%20%20priority_queue%3CNode*%2C%20std%3A%3Avector%3CNode*%3E%2C%20comp%3E%20pq%3B%0A%20%0A%20%20%20%20%2F%2F%20create%20a%20root%20node%20and%20calculate%20its%20cost%0A%20%20%20%20Node*%20root%20%3D%20newNode(initial%2C%20x%2C%20y%2C%20x%2C%20y%2C%200%2C%20NULL)%3B%0A%20%20%20%20root-%3Ecost%20%3D%20calculateCost(initial%2C%20final)%3B%0A%20%0A%20%20%20%20%2F%2F%20Add%20root%20to%20list%20of%20live%20nodes%3B%0A%20%20%20%20pq.push(root)%3B%0A%20%0A%20%20%20%20%2F%2F%20Finds%20a%20live%20node%20with%20least%20cost%2C%0A%20%20%20%20%2F%2F%20add%20its%20childrens%20to%20list%20of%20live%20nodes%20and%0A%20%20%20%20%2F%2F%20finally%20deletes%20it%20from%20the%20list.%0A%20%20%20%20while%20(!pq.empty())%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20a%20live%20node%20with%20least%20estimated%20cost%0A%20%20%20%20%20%20%20%20Node*%20min%20%3D%20pq.top()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20The%20found%20node%20is%20deleted%20from%20the%20list%20of%0A%20%20%20%20%20%20%20%20%2F%2F%20live%20nodes%0A%20%20%20%20%20%20%20%20pq.pop()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20if%20min%20is%20an%20answer%20node%0A%20%20%20%20%20%20%20%20if%20(min-%3Ecost%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20print%20the%20path%20from%20root%20to%20destination%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20printPath(min)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20do%20for%20each%20child%20of%20min%0A%20%20%20%20%20%20%20%20%2F%2F%20max%204%20children%20for%20a%20node%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%204%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(isSafe(min-%3Ex%20%2B%20row%5Bi%5D%2C%20min-%3Ey%20%2B%20col%5Bi%5D))%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20create%20a%20child%20node%20and%20calculate%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20its%20cost%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Node*%20child%20%3D%20newNode(min-%3Emat%2C%20min-%3Ex%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20min-%3Ey%2C%20min-%3Ex%20%2B%20row%5Bi%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20min-%3Ey%20%2B%20col%5Bi%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20min-%3Elevel%20%2B%201%2C%20min)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20child-%3Ecost%20%3D%20calculateCost(child-%3Emat%2C%20final)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Add%20child%20to%20list%20of%20live%20nodes%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pq.push(child)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Driver%20code%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Initial%20configuration%0A%20%20%20%20%2F%2F%20Value%200%20is%20used%20for%20empty%20space%0A%20%20%20%20int%20initial%5BN%5D%5BN%5D%20%3D%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%7B1%2C%202%2C%203%7D%2C%0A%20%20%20%20%20%20%20%20%7B5%2C%206%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%7B7%2C%208%2C%204%7D%0A%20%20%20%20%7D%3B%0A%20%0A%20%20%20%20%2F%2F%20Solvable%20Final%20configuration%0A%20%20%20%20%2F%2F%20Value%200%20is%20used%20for%20empty%20space%0A%20%20%20%20int%20final%5BN%5D%5BN%5D%20%3D%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%7B1%2C%202%2C%203%7D%2C%0A%20%20%20%20%20%20%20%20%7B5%2C%208%2C%206%7D%2C%0A%20%20%20%20%20%20%20%20%7B0%2C%207%2C%204%7D%0A%20%20%20%20%7D%3B%0A%20%0A%20%20%20%20%2F%2F%20Blank%20tile%20coordinates%20in%20initial%0A%20%20%20%20%2F%2F%20configuration%0A%20%20%20%20int%20x%20%3D%201%2C%20y%20%3D%202%3B%0A%20%0A%20%20%20%20solve(initial%2C%20x%2C%20y%2C%20final)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]
Output :
1 2 3
5 6 0
7 8 4
1 2 3
5 0 6
7 8 4
1 2 3
5 8 6
7 0 4
1 2 3
5 8 6
0 7 4
[ad type=”banner”]