8 puzzle Problem using Branch And Bound - GeeksforGeeks (2024)

// 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 <bits/stdc++.h>

using namespace std;

#define N 3

// state space tree nodes

struct Node

{

// stores the parent node of the current node

// helps in tracing path when the answer is found

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 matrix

int 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 node

Node* newNode(int mat[N][N], int x, int y, int newX,

int newY, int level, Node* parent)

{

Node* node = new 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

swap(node->mat[x][y], node->mat[newX][newY]);

// 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, right

int row[] = { 1, 0, -1, 0 };

int col[] = { 0, -1, 0, 1 };

// Function to calculate the number of misplaced tiles

// ie. number of non-blank tiles not in their goal position

int 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 coordinate

int isSafe(int x, int y)

{

return (x >= 0 && x < N && y >= 0 && y < N);

}

// print path from root node to destination node

void printPath(Node* root)

{

if (root == NULL)

return;

printPath(root->parent);

printMatrix(root->mat);

printf("\n");

}

// Comparison object to be used to order the heap

struct comp

{

bool operator()(const Node* lhs, const Node* rhs) const

{

return (lhs->cost + lhs->level) > (rhs->cost + rhs->level);

}

};

// Function to solve N*N - 1 puzzle algorithm using

// Branch and Bound. x and y are blank tile coordinates

// in initial state

void solve(int initial[N][N], int x, int y,

int final[N][N])

{

// Create a priority queue to store live nodes of

// search tree;

priority_queue<Node*, std::vector<Node*>, comp> pq;

// create a root node and calculate its cost

Node* root = newNode(initial, x, y, x, y, 0, NULL);

root->cost = calculateCost(initial, final);

// Add root to list of live nodes;

pq.push(root);

// Finds a live node with least cost,

// add its childrens to list of live nodes and

// finally deletes it from the list.

while (!pq.empty())

{

// Find a live node with least estimated cost

Node* min = pq.top();

// The found node is deleted from the list of

// live nodes

pq.pop();

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

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.push(child);

}

}

}

}

// Driver code

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;

}

// Java 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

import java.io.*;

import java.util.*;

class GFG

{

public static int N = 3;

public static class Node

{

// stores the parent node of the current node

// helps in tracing path when the answer is found

Node parent;

int mat[][] = new int[N][N];// stores matrix

int x, y;// stores blank tile coordinates

int cost;// stores the number of misplaced tiles

int level;// stores the number of moves so far

}

// Function to print N x N matrix

public static void printMatrix(int mat[][]){

for(int i = 0; i < N; i++){

for(int j = 0; j < N; j++){

System.out.print(mat[i][j]+" ");

}

System.out.println("");

}

}

// Function to allocate a new node

public static Node newNode(int mat[][], int x, int y,

int newX, int newY, int level,

Node parent){

Node node = new Node();

node.parent = parent;// set pointer for path to root

// copy data from parent node to current node

node.mat = new int[N][N];

for(int i = 0; i < N; i++){

for(int j = 0; j < N; j++){

node.mat[i][j] = mat[i][j];

}

}

// move tile by 1 position

int temp = node.mat[x][y];

node.mat[x][y] = node.mat[newX][newY];

node.mat[newX][newY]=temp;

node.cost = Integer.MAX_VALUE;// set number of misplaced tiles

node.level = level;// set number of moves so far

// update new blank tile coordinates

node.x = newX;

node.y = newY;

return node;

}

// bottom, left, top, right

public static int row[] = { 1, 0, -1, 0 };

public static int col[] = { 0, -1, 0, 1 };

// Function to calculate the number of misplaced tiles

// ie. number of non-blank tiles not in their goal position

public static int calculateCost(int initialMat[][], int finalMat[][])

{

int count = 0;

for (int i = 0; i < N; i++)

for (int j = 0; j < N; j++)

if (initialMat[i][j]!=0 && initialMat[i][j] != finalMat[i][j])

count++;

return count;

}

// Function to check if (x, y) is a valid matrix coordinate

public static int isSafe(int x, int y)

{

return (x >= 0 && x < N && y >= 0 && y < N)?1:0;

}

// print path from root node to destination node

public static void printPath(Node root){

if(root == null){

return;

}

printPath(root.parent);

printMatrix(root.mat);

System.out.println("");

}

// Comparison object to be used to order the heap

public static class comp implements Comparator<Node>{

@Override

public int compare(Node lhs, Node rhs){

return (lhs.cost + lhs.level) > (rhs.cost+rhs.level)?1:-1;

}

}

// Function to solve N*N - 1 puzzle algorithm using

// Branch and Bound. x and y are blank tile coordinates

// in initial state

public static void solve(int initialMat[][], int x,

int y, int finalMat[][])

{

// Create a priority queue to store live nodes of search tree

PriorityQueue<Node> pq = new PriorityQueue<>(new comp());

// create a root node and calculate its cost

Node root = newNode(initialMat, x, y, x, y, 0, null);

root.cost = calculateCost(initialMat,finalMat);

// Add root to list of live nodes;

pq.add(root);

// Finds a live node with least cost,

// add its childrens to list of live nodes and

// finally deletes it from the list.

while(!pq.isEmpty())

{

Node min = pq.peek();// Find a live node with least estimated cost

pq.poll();// The found node is deleted from the list of live nodes

// if min is an answer node

if(min.cost == 0){

printPath(min);// print the path from root to destination;

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])>0)

{

// create a child node and calculate

// its cost

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, finalMat);

// Add child to list of live nodes

pq.add(child);

}

}

}

}

//Driver Code

public static void main (String[] args)

{

// Initial configuration

// Value 0 is used for empty space

int initialMat[][] =

{

{1, 2, 3},

{5, 6, 0},

{7, 8, 4}

};

// Solvable Final configuration

// Value 0 is used for empty space

int finalMat[][] =

{

{1, 2, 3},

{5, 8, 6},

{0, 7, 4}

};

// Blank tile coordinates in initial

// configuration

int x = 1, y = 2;

solve(initialMat, x, y, finalMat);

}

}

// This code is contributed by shruti456rawal

# Python3 program to print the 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

# Importing copy for deepcopy function

import copy

# Importing the heap functions from python

# library for Priority Queue

from heapq import heappush, heappop

# This variable can be changed to change

# the program from 8 puzzle(n=3) to 15

# puzzle(n=4) to 24 puzzle(n=5)...

n = 3

# bottom, left, top, right

row = [ 1, 0, -1, 0 ]

col = [ 0, -1, 0, 1 ]

# A class for Priority Queue

class priorityQueue:

# Constructor to initialize a

# Priority Queue

def __init__(self):

self.heap = []

# Inserts a new key 'k'

def push(self, k):

heappush(self.heap, k)

# Method to remove minimum element

# from Priority Queue

def pop(self):

return heappop(self.heap)

# Method to know if the Queue is empty

def empty(self):

if not self.heap:

return True

else:

return False

# Node structure

class node:

def __init__(self, parent, mat, empty_tile_pos,

cost, level):

# Stores the parent node of the

# current node helps in tracing

# path when the answer is found

self.parent = parent

# Stores the matrix

self.mat = mat

# Stores the position at which the

# empty space tile exists in the matrix

self.empty_tile_pos = empty_tile_pos

# Stores the number of misplaced tiles

self.cost = cost

# Stores the number of moves so far

self.level = level

# This method is defined so that the

# priority queue is formed based on

# the cost variable of the objects

def __lt__(self, nxt):

return self.cost < nxt.cost

# Function to calculate the number of

# misplaced tiles ie. number of non-blank

# tiles not in their goal position

def calculateCost(mat, final) -> int:

count = 0

for i in range(n):

for j in range(n):

if ((mat[i][j]) and

(mat[i][j] != final[i][j])):

count += 1

return count

def newNode(mat, empty_tile_pos, new_empty_tile_pos,

level, parent, final) -> node:

# Copy data from parent matrix to current matrix

new_mat = copy.deepcopy(mat)

# Move tile by 1 position

x1 = empty_tile_pos[0]

y1 = empty_tile_pos[1]

x2 = new_empty_tile_pos[0]

y2 = new_empty_tile_pos[1]

new_mat[x1][y1], new_mat[x2][y2] = new_mat[x2][y2], new_mat[x1][y1]

# Set number of misplaced tiles

cost = calculateCost(new_mat, final)

new_node = node(parent, new_mat, new_empty_tile_pos,

cost, level)

return new_node

# Function to print the N x N matrix

def printMatrix(mat):

for i in range(n):

for j in range(n):

print("%d " % (mat[i][j]), end = " ")

print()

# Function to check if (x, y) is a valid

# matrix coordinate

def isSafe(x, y):

return x >= 0 and x < n and y >= 0 and y < n

# Print path from root node to destination node

def printPath(root):

if root == None:

return

printPath(root.parent)

printMatrix(root.mat)

print()

# Function to solve N*N - 1 puzzle algorithm

# using Branch and Bound. empty_tile_pos is

# the blank tile position in the initial state.

def solve(initial, empty_tile_pos, final):

# Create a priority queue to store live

# nodes of search tree

pq = priorityQueue()

# Create the root node

cost = calculateCost(initial, final)

root = node(None, initial,

empty_tile_pos, cost, 0)

# Add root to list of live nodes

pq.push(root)

# Finds a live node with least cost,

# add its children to list of live

# nodes and finally deletes it from

# the list.

while not pq.empty():

# Find a live node with least estimated

# cost and delete it from the list of

# live nodes

minimum = pq.pop()

# If minimum is the answer node

if minimum.cost == 0:

# Print the path from root to

# destination;

printPath(minimum)

return

# Generate all possible children

for i in range(4):

new_tile_pos = [

minimum.empty_tile_pos[0] + row[i],

minimum.empty_tile_pos[1] + col[i], ]

if isSafe(new_tile_pos[0], new_tile_pos[1]):

# Create a child node

child = newNode(minimum.mat,

minimum.empty_tile_pos,

new_tile_pos,

minimum.level + 1,

minimum, final,)

# Add child to list of live nodes

pq.push(child)

# Driver Code

# Initial configuration

# Value 0 is used for empty space

initial = [ [ 1, 2, 3 ],

[ 5, 6, 0 ],

[ 7, 8, 4 ] ]

# Solvable Final configuration

# Value 0 is used for empty space

final = [ [ 1, 2, 3 ],

[ 5, 8, 6 ],

[ 0, 7, 4 ] ]

# Blank tile coordinates in

# initial configuration

empty_tile_pos = [ 1, 2 ]

# Function call to solve the puzzle

solve(initial, empty_tile_pos, final)

# This code is contributed by Kevin Joshi

using System;

using System.Collections.Generic;

class GFG

{

public static int N = 3;

public class Node

{

// Stores the parent node of the current node

// Helps in tracing the path when the answer is found

public Node parent;

public int[,] mat = new int[N, N]; // Stores the matrix

public int x, y; // Stores blank tile coordinates

public int cost; // Stores the number of misplaced tiles

public int level; // Stores the number of moves so far

}

// Function to print N x N matrix

public static void PrintMatrix(int[,] mat)

{

for (int i = 0; i < N; i++)

{

for (int j = 0; j < N; j++)

{

Console.Write(mat[i, j] + " ");

}

Console.WriteLine();

}

}

// Function to allocate a new node

public static Node NewNode(int[,] mat, int x, int y, int newX, int newY, int level, Node parent)

{

Node node = new Node();

node.parent = parent; // Set pointer for the path to root

// Copy data from the parent node to the current node

node.mat = new int[N, N];

for (int i = 0; i < N; i++)

{

for (int j = 0; j < N; j++)

{

node.mat[i, j] = mat[i, j];

}

}

// Move the tile by 1 position

int temp = node.mat[x, y];

node.mat[x, y] = node.mat[newX, newY];

node.mat[newX, newY] = temp;

node.cost = int.MaxValue; // Set the number of misplaced tiles

node.level = level; // Set the number of moves so far

// Update new blank tile coordinates

node.x = newX;

node.y = newY;

return node;

}

// Bottom, left, top, right

public static int[] row = { 1, 0, -1, 0 };

public static int[] col = { 0, -1, 0, 1 };

// Function to calculate the number of misplaced tiles

// i.e., the number of non-blank tiles not in their goal position

public static int CalculateCost(int[,] initialMat, int[,] finalMat)

{

int count = 0;

for (int i = 0; i < N; i++)

{

for (int j = 0; j < N; j++)

{

if (initialMat[i, j] != 0 && initialMat[i, j] != finalMat[i, j])

{

count++;

}

}

}

return count;

}

// Function to check if (x, y) is a valid matrix coordinate

public static int IsSafe(int x, int y)

{

return (x >= 0 && x < N && y >= 0 && y < N) ? 1 : 0;

}

// Print the path from the root node to the destination node

public static void PrintPath(Node root)

{

if (root == null)

{

return;

}

PrintPath(root.parent);

PrintMatrix(root.mat);

Console.WriteLine();

}

// Comparison object to be used to order the heap

public class Comp : IComparer<Node>

{

public int Compare(Node lhs, Node rhs)

{

return (lhs.cost + lhs.level) > (rhs.cost + rhs.level) ? 1 : -1;

}

}

// Function to solve N*N - 1 puzzle algorithm using

// Branch and Bound. x and y are blank tile coordinates

// in the initial state

public static void Solve(int[,] initialMat, int x, int y, int[,] finalMat)

{

// Create a priority queue to store live nodes of the search tree

var pq = new SortedSet<Node>(new Comp());

// Create a root node and calculate its cost

Node root = NewNode(initialMat, x, y, x, y, 0, null);

root.cost = CalculateCost(initialMat, finalMat);

// Add the root to the list of live nodes

pq.Add(root);

// Find a live node with the least cost,

// add its children to the list of live nodes, and

// finally remove it from the list

while (pq.Count > 0)

{

Node min = pq.Min; // Find a live node with the least estimated cost

pq.Remove(min); // The found node is removed from the list of live nodes

// If min is an answer node

if (min.cost == 0)

{

PrintPath(min); // Print the path from the root to the destination

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]) > 0)

{

// Create a child node and calculate its cost

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, finalMat);

// Add the child to the list of live nodes

pq.Add(child);

}

}

}

}

// Driver Code

public static void Main(string[] args)

{

// Initial configuration

// Value 0 is used for empty space

int[,] initialMat =

{

{1, 2, 3},

{5, 6, 0},

{7, 8, 4}

};

// Solvable Final configuration

// Value 0 is used for empty space

int[,] finalMat =

{

{1, 2, 3},

{5, 8, 6},

{0, 7, 4}

};

// Blank tile coordinates in the initial configuration

int x = 1, y = 2;

Solve(initialMat, x, y, finalMat);

}

}

// Program to print path from root node to destination node

// for N*N - 1 puzzle algorithm using Branch and Bound

// The solution assumes that the instance of the puzzle is solvable

const N = 3;

// State space tree nodes

class Node {

constructor(mat, x, y, level, parent) {

// Stores the parent node of the current node

// Helps in tracing the path when the answer is found

this.parent = parent;

// Stores matrix

this.mat = mat.map(row => [...row]);

// Stores blank tile coordinates

this.x = x;

this.y = y;

// Stores the number of misplaced tiles

this.cost = Infinity;

// Stores the number of moves so far

this.level = level;

}

}

// Function to print N x N matrix

function printMatrix(mat) {

for (let i = 0; i < N; i++) {

console.log(mat[i].join(' '));

}

console.log('\n');

}

// Function to allocate a new node

function newNode(mat, x, y, newX, newY, level, parent) {

const node = new Node(mat, x, y, level, parent);

// Move tile by 1 position

[node.mat[x][y], node.mat[newX][newY]] = [node.mat[newX][newY], node.mat[x][y]];

// Update new blank tile coordinates

node.x = newX;

node.y = newY;

return node;

}

// Bottom, left, top, right

const row = [1, 0, -1, 0];

const col = [0, -1, 0, 1];

// Function to calculate the number of misplaced tiles

// i.e., number of non-blank tiles not in their goal position

function calculateCost(initial, final) {

let count = 0;

for (let i = 0; i < N; i++)

for (let 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 coordinate

function isSafe(x, y) {

return x >= 0 && x < N && y >= 0 && y < N;

}

// Print path from root node to destination node

function printPath(root) {

if (!root) return;

printPath(root.parent);

printMatrix(root.mat);

}

// Comparison object to be used to order the heap

class comp {

static compare(lhs, rhs) {

return (lhs.cost + lhs.level) > (rhs.cost + rhs.level);

}

}

// Function to solve N*N - 1 puzzle algorithm using

// Branch and Bound. x and y are blank tile coordinates

// in the initial state

function solve(initial, x, y, final) {

// Create an array to store live nodes of the search tree

const pq = [];

// Create a root node and calculate its cost

const root = newNode(initial, x, y, x, y, 0, null);

root.cost = calculateCost(initial, final);

// Add root to the array of live nodes

pq.push(root);

// Find a live node with the least cost,

// add its children to the array of live nodes, and

// finally delete it from the array

while (pq.length > 0) {

// Find a live node with the least estimated cost

pq.sort(comp.compare);

const min = pq.shift();

// 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 (let i = 0; i < 4; i++) {

if (isSafe(min.x + row[i], min.y + col[i])) {

// Create a child node and calculate its cost

const 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 the array of live nodes

pq.push(child);

}

}

}

}

// Driver code

// Initial configuration

// Value 0 is used for empty space

const initial = [

[1, 2, 3],

[5, 6, 0],

[7, 8, 4]

];

// Solvable Final configuration

// Value 0 is used for empty space

const final = [

[1, 2, 3],

[5, 8, 6],

[0, 7, 4]

];

// Blank tile coordinates in the initial configuration

const startX = 1, startY = 2;

solve(initial, startX, startY, final);

// This code is contributed by shivamgupta310570