Last Updated : 18 Jul, 2024

Comments

Improve

** 8-puzzle Problem **is a classic sliding puzzle that consists of a 3×3 board with 8 numbered tiles and one blank space. The goal is to rearrange the tiles to match a target configuration by sliding the tiles into the blank space. The movement can be in four directions: left, right, up, and down.

In this article, we will learn how to solve this using Branch and Bound in C language.

**For Example,**

Initial State:

1 2 3

5 6 0

7 8 4

Target State:

1 2 3

5 8 6

0 7 4

8 Puzzle

### Steps to Solve 8 Puzzle Problem Using Branch and Bound in C

When implementing the 8-puzzle problem using Branch and Bound in C, we need to perform a custom implementation using arrays or linked lists since C does not have built-in priority queue support like C++.

**Approach:**

- First, create a Node structure to represent each state in the puzzle. Include fields for the puzzle matrix, coordinates of the blank space, cost (misplaced tiles), level (depth in the search tree), and parent node reference.
- Implement newNode to create a new puzzle state node. Copy the matrix, simulate tile movement, and set initial values for cost, level, and parent.
- Implement calculateCost to count the number of tiles not in their goal positions between the initial and final puzzle configurations.
- Implement isSafe to verify if a move (up, down, left, right) stays within puzzle boundaries.
- mplement printPath to recursively print the path from the initial state to the goal state once found.
- Implement Comparison Function comp for Priority Queue comp to prioritize nodes in the priority queue (pq) based on cost + level for efficient exploration.
Main Function (solve):

- Initialize a priority queue (pq) to manage live nodes.
- Create the initial node, calculate its cost, and add it to pq.
- Use a loop to process nodes until the solution is found or all possibilities are exhausted:

- Sort pq to retrieve the node with the lowest estimated cost.
- If the node is a goal state (cost is zero), print the path using printPath and exit.
- Generate child nodes for valid moves, calculate their costs, and add them to pq.
:In main

- Define the initial and final puzzle configurations.
- Specify the coordinates of the blank space.
- Call solve with these parameters to find and print the solution path.

8 Puzzle using Branch and Bound

### C Program to Solve 8 Puzzle Problem Using Branch and Bound

The below program implements the above approach to solve the 8 Puzzle Problem in C language.

// C Program to print path from root node to destination// node for N*N -1 puzzle algorithm using Branch and Bound// The solution assumes that instance of puzzle is solvable#include <limits.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 3// state space tree nodesstruct Node { // stores the parent node of the current node // helps in tracing path when the answer is found struct Node* parent; // stores matrix int mat[N][N]; // stores blank tile coordinates int x, y; // stores the number of misplaced tiles int cost; // stores the number of moves so far int level;};// Function to print N x N matrixvoid printMatrix(int mat[N][N]){ for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) printf("%d ", mat[i][j]); printf("\n"); }}// Function to allocate a new nodestruct Node* newNode(int mat[N][N], int x, int y, int newX, int newY, int level, struct Node* parent){ struct Node* node = (struct Node*)malloc(sizeof(struct Node)); // set pointer for path to root node->parent = parent; // copy data from parent node to current node memcpy(node->mat, mat, sizeof(node->mat)); // move tile by 1 position int temp = node->mat[x][y]; node->mat[x][y] = node->mat[newX][newY]; node->mat[newX][newY] = temp; // set number of misplaced tiles node->cost = INT_MAX; // set number of moves so far node->level = level; // update new blank tile coordinates node->x = newX; node->y = newY; return node;}// bottom, left, top, rightint row[] = { 1, 0, -1, 0 };int col[] = { 0, -1, 0, 1 };// Function to calculate the number of misplaced tiles// i.e. number of non-blank tiles not in their goal positionint calculateCost(int initial[N][N], int final[N][N]){ int count = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (initial[i][j] && initial[i][j] != final[i][j]) count++; return count;}// Function to check if (x, y) is a valid matrix coordinateint isSafe(int x, int y){ return (x >= 0 && x < N && y >= 0 && y < N);}// print path from root node to destination nodevoid printPath(struct Node* root){ if (root == NULL) return; printPath(root->parent); printMatrix(root->mat); printf("\n");}// Comparison function to be used to order the heapint comp(const void* lhs, const void* rhs){ struct Node* l = *(struct Node**)lhs; struct Node* r = *(struct Node**)rhs; return (l->cost + l->level) - (r->cost + r->level);}// Function to solve N*N - 1 puzzle algorithm using// Branch and Bound. x and y are blank tile coordinates// in initial statevoid solve(int initial[N][N], int x, int y, int final[N][N]){ // Create a priority queue to store live nodes of search // tree struct Node* pq[100000]; // Priority queue with sufficient size int pqSize = 0; // create a root node and calculate its cost struct Node* root = newNode(initial, x, y, x, y, 0, NULL); root->cost = calculateCost(initial, final); // Add root to list of live nodes pq[pqSize++] = root; // Finds a live node with least cost, // add its children to list of live nodes and // finally deletes it from the list. while (pqSize > 0) { // Sort priority queue based on cost + level qsort(pq, pqSize, sizeof(struct Node*), comp); // Find a live node with least estimated cost struct Node* min = pq[0]; // The found node is deleted from the list of live // nodes for (int i = 1; i < pqSize; i++) pq[i - 1] = pq[i]; pqSize--; // if min is an answer node if (min->cost == 0) { // print the path from root to destination printPath(min); return; } // do for each child of min // max 4 children for a node for (int i = 0; i < 4; i++) { if (isSafe(min->x + row[i], min->y + col[i])) { // create a child node and calculate its // cost struct Node* child = newNode( min->mat, min->x, min->y, min->x + row[i], min->y + col[i], min->level + 1, min); child->cost = calculateCost(child->mat, final); // Add child to list of live nodes pq[pqSize++] = child; } } }}int main(){ // Initial configuration // Value 0 is used for empty space int initial[N][N] = { { 1, 2, 3 }, { 5, 6, 0 }, { 7, 8, 4 } }; // Solvable Final configuration // Value 0 is used for empty space int final[N][N] = { { 1, 2, 3 }, { 5, 8, 6 }, { 0, 7, 4 } }; // Blank tile coordinates in initial configuration int x = 1, y = 2; solve(initial, x, y, final); return 0;}

**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

** Time Complexity:**O(N^2 * N!)where N is the number of tiles in the puzzle

**O(N^2)**

**Auxiliary Space:**Next Article

N Queen Problem Using Branch and Bound in C