8 puzzle Problem - 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 nodesstruct 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 matrixint 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 nodeNode* 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, rightint 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 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(Node* root){ if (root == NULL) return; printPath(root->parent); printMatrix(root->mat); printf("\n");}// Comparison object to be used to order the heapstruct 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 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; 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 codeint 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 solvableimport 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 functionimport copy# Importing the heap functions from python # library for Priority Queuefrom 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, rightrow = [ 1, 0, -1, 0 ]col = [ 0, -1, 0, 1 ]# A class for Priority Queueclass 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 structureclass 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 positiondef 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 countdef 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 matrixdef 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 coordinatedef isSafe(x, y): return x >= 0 and x < n and y >= 0 and y < n# Print path from root node to destination nodedef 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 spaceinitial = [ [ 1, 2, 3 ], [ 5, 6, 0 ], [ 7, 8, 4 ] ]# Solvable Final configuration# Value 0 is used for empty spacefinal = [ [ 1, 2, 3 ], [ 5, 8, 6 ], [ 0, 7, 4 ] ]# Blank tile coordinates in # initial configurationempty_tile_pos = [ 1, 2 ]# Function call to solve the puzzlesolve(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 solvableconst N = 3;// State space tree nodesclass 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 matrixfunction printMatrix(mat) { for (let i = 0; i < N; i++) { console.log(mat[i].join(' ')); } console.log('\n');}// Function to allocate a new nodefunction 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, rightconst 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 positionfunction 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 coordinatefunction isSafe(x, y) { return x >= 0 && x < N && y >= 0 && y < N;}// Print path from root node to destination nodefunction printPath(root) { if (!root) return; printPath(root.parent); printMatrix(root.mat);}// Comparison object to be used to order the heapclass 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 statefunction 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 spaceconst initial = [ [1, 2, 3], [5, 6, 0], [7, 8, 4]];// Solvable Final configuration// Value 0 is used for empty spaceconst final = [ [1, 2, 3], [5, 8, 6], [0, 7, 4]];// Blank tile coordinates in the initial configurationconst startX = 1, startY = 2;solve(initial, startX, startY, final);// This code is contributed by shivamgupta310570