• DSA for Beginners
  • DSA Tutorial
  • Data Structures
  • Linked List
  • Dynamic Programming
  • Binary Tree
  • Binary Search Tree
  • Divide & Conquer
  • Mathematical
  • Backtracking
  • Branch and Bound
  • Pattern Searching

8 puzzle problem solving

  • Explore Our Geeks Community
  • Branch and Bound Algorithm
  • Introduction to Branch and Bound - Data Structures and Algorithms Tutorial
  • 0/1 Knapsack using Branch and Bound
  • Implementation of 0/1 Knapsack using Branch and Bound

8 puzzle Problem using Branch And Bound

  • Job Assignment Problem using Branch And Bound
  • N Queen Problem using Branch And Bound
  • Traveling Salesman Problem using Branch And Bound

We have introduced Branch and Bound and discussed the 0/1 Knapsack problem in the below posts. 

  • Branch and Bound | Set 1 (Introduction with 0/1 Knapsack)
  • Branch and Bound | Set 2 (Implementation of 0/1 Knapsack)

In this puzzle solution of the 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 the final configuration using the empty space. We can slide four adjacent (left, right, above , and below) tiles into the empty space. 

For example, 

8puzzle

1. DFS (Brute-Force)   We can perform a depth-first search on state-space (Set of all configurations of a given problem i.e. all states that can be reached from the initial state) tree.   

image(6)

In this solution, successive moves can take us away from the goal rather than bringing us closer. The search of state-space tree follows the leftmost path from the root regardless of the initial state. An answer node may never be found in this approach.

2. BFS (Brute-Force)   We can perform a Breadth-first search on the 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 the backtracking technique but uses a 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 the least cost. The cost function is defined as 

The ideal Cost function for an 8-puzzle Algorithm :  We assume that moving one tile in any direction will have a 1 unit cost. Keeping that in mind, we define a cost function for the 8-puzzle algorithm as below: 

An algorithm is available for getting an approximation of h(x) which is an unknown value.

Complete Algorithm:  

The below diagram shows the path followed by the above algorithm to reach the final configuration from the given initial configuration of the 8-Puzzle. Note that only nodes having the least value of cost function are expanded.  

8 puzzle problem solving

Output : 

The time complexity of this algorithm is O(N^2 * N!) where N is the number of tiles in the puzzle, and the space complexity is O(N^2) .

Sources:   www.cs.umsl.edu/~sanjiv/classes/cs5130/lectures/bb.pdf   https://www.seas.gwu.edu/~bell/csci212/Branch_and_Bound.pdf

If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to [email protected]. See your article appearing on the GeeksforGeeks main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above  

  • DSA in Java
  • DSA in Python
  • DSA in JavaScript

Please Login to comment...

  • Akanksha_Rai
  • Kirti_Mangal
  • shruti456rawal
  • shreymaurya2000
  • jatishay444
  • kevinjoshi46b
  • mitalibhola94
  • shivamgupta310570
  • vikramshirsath177
  • How to Allocate RAM to Minecraft
  • How To Download Instagram Stories [Multiple Ways]
  • How To Check IMEI Number
  • Top 10 best Low-Code and No-Code AI Platforms Examples
  • 10 Best Free AI Art Generators to Create Image From Text [Free & Paid]
  • 30 OOPs Interview Questions and Answers (2023)

Improve your Coding Skills with Practice

 alt=

  • PRO Courses Guides New Tech Help Pro Expert Videos About wikiHow Pro Upgrade Sign In
  • EDIT Edit this Article
  • EXPLORE Tech Help Pro About Us Random Article Quizzes Request a New Article Community Dashboard This Or That Game Popular Categories Arts and Entertainment Artwork Books Movies Computers and Electronics Computers Phone Skills Technology Hacks Health Men's Health Mental Health Women's Health Relationships Dating Love Relationship Issues Hobbies and Crafts Crafts Drawing Games Education & Communication Communication Skills Personal Development Studying Personal Care and Style Fashion Hair Care Personal Hygiene Youth Personal Care School Stuff Dating All Categories Arts and Entertainment Finance and Business Home and Garden Relationship Quizzes Cars & Other Vehicles Food and Entertaining Personal Care and Style Sports and Fitness Computers and Electronics Health Pets and Animals Travel Education & Communication Hobbies and Crafts Philosophy and Religion Work World Family Life Holidays and Traditions Relationships Youth
  • Browse Articles
  • Learn Something New
  • Quizzes Hot
  • This Or That Game New
  • Train Your Brain
  • Explore More
  • Support wikiHow
  • About wikiHow
  • Log in / Sign up
  • Hobbies and Crafts
  • Puzzles and Memory Games
  • Mathematical Puzzles

How to Solve 8 Puzzle

Last Updated: March 18, 2018

wikiHow is a “wiki,” similar to Wikipedia, which means that many of our articles are co-written by multiple authors. To create this article, volunteer authors worked to edit and improve it over time. This article has been viewed 71,539 times. Learn more...

8 puzzle is a type of sliding puzzle. It may take normal people a few minutes to solve it. In this article, you will learn how to solve 8 puzzle fast. After you master the steps, you will be able to solve it within a minute!

Solving the First Row

Step 1 WH.performance.clearMarks('image1_rendered'); WH.performance.mark('image1_rendered');...

Solving the Second and Third Row

Step 1 Put 7 under 1.

Expert Q&A

You might also like.

Solve Hard Sudoku Puzzles

About This Article

  • Send fan mail to authors

Did this article help you?

8 puzzle problem solving

Featured Articles

Apply for a Blue Badge

Trending Articles

Which Kardashian Am I Quiz

Watch Articles

Give Yourself a Facial Massage

  • Terms of Use
  • Privacy Policy
  • Do Not Sell or Share My Info
  • Not Selling Info

wikiHow Tech Help Pro:

Level up your tech skills and stay ahead of the curve

Puzzle pieces was swapped, cannot be solved.

Please check if all of the puzzle pieces are in correct place. Switching one pair of the puzzle pieces when in complete state makes the puzzle impossible to solve.

8 Puzzle Solver

Step 1: upload template (optional), step 2: arrange puzzle to solve.

Drag and Drop the puzzle pieces to match your current puzzle obstacle.

Step 3: The solution

Here is your solution!

Step 4: Share Solution

You may share this solution to your friends.

8 puzzle problem solving

How its done?

To get the best possible solution, we uses 3 types of algorithm with an iteration limit of up to only 5,000. Our AI-powered solver find and save the shortest path of all solved problems and matches these path faces with the new path to reuse the solution, that way it gives answers in second and less iteration.

A-star Search Algorithm

Uses pathfinding to check each nodes and keeps tracks of the visited nodes until it finds the solution. The longest depth we used is up to 10,000 nodes.

Breadth-first Search Algorithm

If other algorithm cannot solve the problem, we uses traversing or a search tree structure to find solution. The depth is limited to 10,000 nodes.

Depth-first Search Algorithm

Lastly, this algorithm find the solution from a node branch as far as possible with a limit of 15,000 nodes for each. Giving you answers for all possible combinations.

  • Pathfinding
  • Solving 8 puzzle problem using A* star search
  • May 17, 2020 March 17, 2023

Solving 8 puzzle problem using A* star search in C++

This tutorial will solve the 8 puzzle problem using the A* (star) search algorithm. We will approach the solution by first modelling the problem, building the fundamental blocks and finally applying a solver to solve the puzzle.

Part 1 of this tutorial provides the introduction, the background information and the approach towards the solution from the algorithmic point of view.

Part 2 of this tutorial provides an implementation of the algorithm and the solution using C++ for a console program. Read Part 2, “Solving 8 puzzle problem using A* star search in C++” .

Part 3 of this tutorial provides an implementation of the algorithm and the solution using C# for the Unity project. Read Part 2, “ 8-Puzzle Problem Using A* in C# and Unity “ .

Tutorials on Pathfinding and a WebGL Playground for experimenting pathfinding.

8 puzzle problem solving

Download the 8 Puzzle Unlimited App from Google Play .

8 puzzle problem solving

Part 1 – Introduction

Typically A* (Astar) is used in a grid-based pathfinding problem. However, as a general rule, any pathfinding algorithm (A* included) can be used to solve any graph-based problem. For a very detailed understanding of path-finding, I suggest the brilliant tutorial maintained by Amit on Stanford’s site . In this tutorial, I will not go through the theory of A* pathfinding, but rather, I would implement all necessary functions for A* pathfinding to solve the 8 puzzle problem.

The 8 Puzzle Problem

The 8 puzzle problem is a puzzle that was invented and popularised by Noyes Palmer Chapman in the 1870s. The 8-puzzle is a smaller version of the slightly better-known 15-puzzle. It comprises a 3-by-3 grid with 8 square blocks labelled 1 through 8 and a blank square.

The goal is to rearrange the blocks so that they are in order. The blank tile can sometimes be at the start or the end. The diagram above shows one possible initial configuration and the goal. You are permitted to slide blocks horizontally or vertically into the blank square to reach the goal state.

Start and goal graphical representation

Before we can solve the 8 puzzle problem, we will need to model the problem. But what is meant by Modelling the Problem?

In generic terms, modelling a problem is the art of formulating the problem at hand in terms of precisely described, well-understood building blocks and logic to reach a solution. In computer science, proper modelling is the key to applying algorithmic design techniques to any real-world problem. Real-world applications involve real-world problems.

You might be working on a system that simulates air traffic in and around an airport, you might be working on optimising the dispatch of delivery vans for an e-commerce application, or you might be working to search through patterns in a large image set. To solve such problems, you will use some modelling techniques to reduce the problem in rigorously defined abstract structures such as graphs, trees, permutations, sets, etc.

For our 8 puzzle problems, let’s see how we can model the problem. Let’s take a random state of the 8 puzzle problem as given in the diagram below. We can either slide tile 8 up, slide 3 right, or slide 6 left to create three variant states from this random state.

The variant states from a given state in 8-puzzle

These three states will produce subsequent more states (3 for the first, 1 for the second and 1 for the third). This continues until we find the goal state.

We can see that we can transform the various possible states of the 8 puzzle problem into a tree data structure.

The state tree for an 8-puzzle

The 8 Puzzle Solution Search Space

The 8-puzzle is the largest possible N-puzzle that can be solved entirely. It is simple and yet has a significant problem space. There are larger variants to the same problem type, like the 15-puzzle. But those cannot be solved to completion. This complexity makes the N x N extension of the 8-puzzle an NP-hard problem.

8 puzzle has 9! possible tile permutation states. Out of these, every second permutation state is solvable. Hence, there is a total of 9!/2 = 181,440 solvable problem states.

Alexander Reinefeld from the Paderborn Center for Parallel Computing , Germany, has shown that the average length of all optimal solution paths is about 22 moves for any given random configuration. For the 181440 solvable configurations, there is a total of 500880 optimal solutions. This gives an average solution density of 2.76 per problem, with the minimum and maximum number lying at 1 and 64 solutions.

The problem lies in creating the possible search tree and then traversing the most optimal tree branch that will lead from the start state to the end state.

So, how do we find the most optimal branch of the tree? Enter the Heuristic Search!

Heuristic Search

A Heuristic search is a technique to solve a search problem faster than classical methods. In many cases, it finds an approximate solution when classical methods cannot. It is thus a generalized and approximate strategy for problem-solving.

In layman’s terms, it can be thought of as a rule of thumb, or a common-sense knowledge, where the answer isn’t guaranteed to be correct but helps to reach a decision quickly. It is a shortcut that we take to trade-off either the optimality, the completeness, the accuracy, or the precision for speed.

Heuristic searches are often associated with heuristic values.

A heuristic value of a node in the construction graph attempts to capture the importance of that node’s value, for example, the cost or the gain. Heuristic search is a type of informed search that uses such a heuristic value for optimising the search .

At each branching step, the search evaluates the heuristic value and decides which branch to follow. It does so by ranking alternatives.

There are many different types of heuristic search algorithms. One of them is the A* search algorithm.

The A* Search

A* search is a computer search algorithm that is widely used for pathfinding and graph traversal. In our case of the 8 puzzle problem, we will be using it for optimal graph traversal. A* works by keeping track of all visited nodes and ignoring them for further traversal. At the same time, it also keeps track of all the nodes that are yet to be explored and chooses one with the least cost to be further explored.

This simple mechanism allows us to find the most optimal tree branch that will lead us from the start state to the end state.

The Heuristic Value (Cost Function) of an 8 Puzzle State

The heuristic value of an 8 puzzle state is a combination of two values. It is often called the cost function f .

h gives how far the goal node is and g the number of nodes traversed from the start node to the current node. For h, we will use the Manhattan distance, and for g, we will use the depth of the current node.

For our A* search, we will use the sum of Manhattan distance and the current depth of the node as the total cost.

Manhattan distance

The Manhattan distance heuristic is used for its simplicity and ability to estimate the number of moves required to bring a given puzzle state to the solution state. Manhattan distance is computed by the sum of the distances of each tile from where it should belong.

For example, the Manhattan distance between “213540678” and “123456780” is 9 and between “647850321” and “123456780” is 21.

The diagram below shows the Manhattan cost for a specific tiles configuration.

Manhattan distance calculation for 8-puzzle state

Software Design for Solving 8 Puzzle Problem

In the following section, I will start creating the building blocks for the puzzle solution and finally try to join them to reach the solution.

The first step towards solving the 8 puzzle problem will require a data type to represent the tiles on the puzzle. I will call this the State of the puzzle. A state is a unique combination of tiles.

During our process of solving, we will need to store hundreds of perhaps thousands of tile states. Each combination of tiles in the puzzle will be a unique state. Each unique state of the tiles will represent a Node in the tree data structure.

I will use an integer array to represent a state. The array indices will refer to a tile location, whereas the value in that index will represent the tile number. Look at the diagram below. In this diagram, a unique state of the tile is shown on the left. On the right, an array representation is shown to store the tile information.

Start state graphics representation and index array representation.

Thus, we see that we can represent any state of the 8 puzzle problem by using a one-dimensional array. The indices of the array, which cannot change, represent the fixed location of the tiles. In our case, we have assumed that array index 0 represents the top-left tile, index 1 as top-centre tile, index 2 as top-right tile and so on until index 8 as the bottom-right tile. The value stored in each index will represent the actual number (or picture) on the tile. For example, in the above case, we have index 0 having tile 0 (or the empty tile), index 1 having tile 3 and until index 8 with tile 2.

We can thus see that we can arrive at the goal state by manipulating the values on the array, with the constraint of where the empty tile slides into for each move.

The graphical representation of 8-puzzle goal state

After State is defined, our next task would be to create the graph of neighbours for the 8 puzzle problem.

We have defined the state in the previous section. Now we will define the neighbours based on where the empty tile is. We will do this for each of the 9 tile indices.

So let’s start with tile index 0. For every index, we will need to store the neighbours (in other words, the indices where the empty tile can move) as a collection of indices.

Looking at the above list, we can now access the neighbours for any tile index. For example, for tile index 6, the neighbours are tile indices 7 and 3.

For the first figure below, we have our empty tile in index 0. So for index 0, the neighbours are index 1 and 3. Please note that I am referring to the index of the array and not the actual value of that element in that index of the array. In the first figure below, index 1 is 3, and index 3 is 4. Neighbours, in this case, are index 1 and index 3.

Neighbour indices for 3 random states of 8-puzzle

Similarly, for the state represented by the second figure, the empty tile index is 2. Neighbours, in this case, are 1 and 5. For the third state, represented by the third figure, the empty index is 1, and neighbours are 0, 2 and 4. We can thus form a dictionary (or map) of neighbours for each of the 9 indices.

Node (or the State Tree)

The state tree is the actual tree that comprises all the valid transitions from one state to another state, ultimately reaching the final goal (if the solution exists).

In computer science, a tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes – source Wikipedia .

Each tree element we call Node will comprise one specific tile for an 8 puzzle for this problem.

Solver for 8 Puzzle

Finally, we look at the Solver framework. The Solver should be able to solve the puzzle based on the A* algorithm. The solver will be implemented simply as a main console function in C++ and a Coroutine in the Unity C# version. The solver class will construct the tree, visit the next best node and collect nodes for the solution until the solution is finally found.

Read Part 2 of the tutorial “Solving 8 puzzle problem using A* star search in C++.”

Read Part 3 of the tutorial “ 8-Puzzle Problem Using A* in C# and Unity. “

Read My Other Tutorials

  • Implement a Generic Pathfinder in Unity using C#
  • Create a Jigsaw Puzzle Game in Unity
  • Generic Finite State Machine Using C#
  • Implement Bezier Curve using C# in Unity
  • Create a Jigsaw Tile from an Existing Image
  • Create a Jigsaw Board from an Existing Image
  • A Configurable Third-Person Camera in Unity
  • Player Controls With Finite State Machine Using C# in Unity
  • Finite State Machine Using C# Delegates in Unity
  • Enemy Behaviour With Finite State Machine Using C# Delegates in Unity
  • Augmented Reality – Fire Effect using Vuforia and Unity
  • Implementing a Finite State Machine Using C# in Unity
  • Solving 8 puzzle problem using A* star search in C++
  • What Are C# Delegates And How To Use Them
  • How to Generate Mazes Using Depth-First Algorithm

Shamim Akhtar

A  committed and optimistic professional who brings passion and enthusiasm to help motivate, guide and mentor young students into their transition to the Industry and reshape their careers for a fulfilling future. The past is something that you cannot undo. The future is something that you can build .

I enjoy coding, developing games and writing tutorials.  Visit my GitHub to see the projects I am working on right now. Educator | Developer | Mentor

5 thoughts on “Solving 8 puzzle problem using A* star search”

8 puzzle problem solving

Simply want to say your article is as astonishing. The clarity in your post is just great and i could assume you’re an expert on this subject.

Fine with your permission allow me to grab your feed to keep up to date with forthcoming post. Thanks a million and please continue the gratifying work.

8 puzzle problem solving

Wow! After all I got a website from where I be capable of actually get useful information regarding my study and knowledge.

8 puzzle problem solving

Wow, incredible blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your site is fantastic, let alone the content!

8 puzzle problem solving

Ꭺwesome post.

8 puzzle problem solving

bookmarked!!, I ⅼove your web site!

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Save my name, email, and website in this browser for the next time I comment.

{{#message}}{{{message}}}{{/message}}{{^message}}Your submission failed. The server responded with {{status_text}} (code {{status_code}}). Please contact the developer of this form processor to improve this message. Learn More {{/message}}

{{#message}}{{{message}}}{{/message}}{{^message}}It appears your submission was successful. Even though the server responded OK, it is possible the submission was not processed. Please contact the developer of this form processor to improve this message. Learn More {{/message}}

Submitting…

  • Getting started with algorithm
  • Awesome Book
  • Awesome Community
  • Awesome Course
  • Awesome Tutorial
  • Awesome YouTube
  • A* Pathfinding
  • A* Pathfinding through a maze with no obstacles
  • Introduction to A*
  • Solving 8-puzzle problem using A* algorithm
  • A* Pathfinding Algorithm
  • Algo:- Print a m*n matrix in square wise
  • Algorithm Complexity
  • Applications of Dynamic Programming
  • Applications of Greedy technique
  • Bellman–Ford Algorithm
  • Big-O Notation
  • Binary Search Trees
  • Binary Tree traversals
  • Breadth-First Search
  • Bubble Sort
  • Bucket Sort
  • Catalan Number Algorithm
  • Check if a tree is BST or not
  • Check two strings are anagrams
  • Counting Sort
  • Depth First Search
  • Dijkstra’s Algorithm
  • Dynamic Programming
  • Dynamic Time Warping
  • Edit Distance Dynamic Algorithm
  • Equation Solving
  • Fast Fourier Transform
  • Floyd-Warshall Algorithm
  • Graph Traversals
  • Greedy Algorithms
  • Hash Functions
  • Insertion Sort
  • Integer Partition Algorithm
  • Knapsack Problem
  • Knuth Morris Pratt (KMP) Algorithm
  • Kruskal's Algorithm
  • Line Algorithm
  • Longest Common Subsequence
  • Longest Increasing Subsequence
  • Lowest common ancestor of a Binary Tree
  • Matrix Exponentiation
  • Maximum Path Sum Algorithm
  • Maximum Subarray Algorithm
  • Multithreaded Algorithms
  • Odd-Even Sort
  • Online algorithms
  • Pancake Sort
  • Pascal's Triangle
  • Pigeonhole Sort
  • polynomial-time bounded algorithm for Minimum Vertex Cover
  • Prim's Algorithm
  • Selection Sort
  • Shortest Common Supersequence Problem
  • Sliding Window Algorithm
  • Substring Search
  • Travelling Salesman

algorithm A* Pathfinding Solving 8-puzzle problem using A* algorithm

Problem definition :

An 8 puzzle is a simple game consisting of a 3 x 3 grid (containing 9 squares). One of the squares is empty. The object is to move to squares around into different positions and having the numbers displayed in the "goal state".

8-puzzle

Given an initial state of 8-puzzle game and a final state of to be reached, find the most cost-effective path to reach the final state from initial state.

Initial state :
Final state :
Heuristic to be assumed :

Let us consider the Manhattan distance between the current and final state as the heuristic for this problem statement.

Total cost function :

So the total cost function f(n) is given by,

Solution to example problem :

First we find the heuristic value required to reach the final state from initial state. The cost function, g(n) = 0, as we are in the initial state

The above value is obtained, as 1 in the current state is 1 horizontal distance away than the 1 in final state. Same goes for 2 , 5 , 6 . _ is 2 horizontal distance away and 2 vertical distance away. So total value for h(n) is 1 + 1 + 1 + 1 + 2 + 2 = 8. Total cost function f(n) is equal to 8 + 0 = 8.

Now, the possible states that can be reached from initial state are found and it happens that we can either move _ to right or downwards.

So states obtained after moving those moves are:

Again the total cost function is computed for these states using the method described above and it turns out to be 6 and 7 respectively. We chose the state with minimum cost which is state (1). The next possible moves can be Left, Right or Down. We won't move Left as we were previously in that state. So, we can move Right or Down.

Again we find the states obtained from (1).

(3) leads to cost function equal to 6 and (4) leads to 4. Also, we will consider (2) obtained before which has cost function equal to 7. Choosing minimum from them leads to (4). Next possible moves can be Left or Right or Down. We get states:

We get costs equal to 5, 2 and 4 for (5), (6) and (7) respectively. Also, we have previous states (3) and (2) with 6 and 7 respectively. We chose minimum cost state which is (6). Next possible moves are Up, and Down and clearly Down will lead us to final state leading to heuristic function value equal to 0.

Got any algorithm Question?

pdf

  • Advertise with us
  • Privacy Policy

Get monthly updates about new articles, cheatsheets, and tricks.

8-Puzzle Solver

Solving the 8-Puzzle with A* and SimpleAI

Discover Heuristic-Based Problem Solving

Welcome to a comprehensive exploration into the world of Informed Search Heuristics with a captivating use case - the 8-Puzzle . Leveraging Python and its powerful libraries, we’ll delve into solving the 8-puzzle problem. This project covers:

  • The basics of Informed Search Heuristics and their significance in artificial intelligence.
  • Understanding the 8-Puzzle problem and its representation.
  • The implementation of A* algorithm to solve the 8-Puzzle.
  • The application of Manhattan Distance and Misplaced Tiles as heuristics in our problem.
  • A detailed guide to coding the solution with Python .
  • An in-depth analysis of the solution and the impact of different heuristics on the efficiency of the solution.

This insightful journey is beneficial for both AI beginners and seasoned researchers . The project offers a deep understanding of Informed Search Heuristics and their practical implementation in the 8-Puzzle problem .

Informed Search Heuristics

Informed Search Heuristics play a pivotal role in the domain of artificial intelligence. Heuristics are techniques that guide the search process towards more promising regions, thus reducing the search time. They are based on information (hence “informed”) that is available a priori and can provide an estimate to the solution from any given state.

Application in Artificial Intelligence

Heuristics are often used in path-finding problems, scheduling, and in the game industry. They are a cornerstone of the A* search algorithm, which combines the benefits of Breadth-First Search (completeness and optimality) and Depth-First Search (space-efficiency) and is used widely due to its effectiveness and efficiency. For instance, the paper ‘Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem: Summary and Challenges’ discusses various search-based techniques developed for optimally solving Multi-agent pathfinding (MAPF) under the sum-of-costs objective function 1 . Similarly, ‘Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives’ proposes an algorithm for multi-agent pathfinding that utilizes single-agent primitives but allows all agents to move in parallel 2 . These examples illustrate the practical application and effectiveness of heuristics in solving complex problems.

The 8-Puzzle Problem

The 8-Puzzle problem is a puzzle that was invented and popularized by Noyes Palmer Chapman in the late 19th century. It consists of a 3x3 grid with eight numbered tiles and a blank space. The goal is to reach a specified goal state from a given start state by sliding the blank space up, down, left or right.

Visualizing the Program Flow and Execution

We have prepared a series of diagrams to provide a better understanding of the program flow and execution of our 8-puzzle solution, including the utilization of the A* Search Algorithm:

These diagrams help you visualize the flow of control and object, structure of the classes used, and the sequence of operations in our implementation to solve the 8-Puzzle problem.

GitHub Repository

For complete access to the code and resources associated with this project, visit our GitHub repository:

Interactive Document Preview

Immerse yourself in the 8-Puzzle project write-up with our interactive document preview. Navigate, zoom in, scroll through, and engage with the content freely.

To access the project write-up in PDF format for offline reading or printing, download from the link below.

By implementing Informed Search Heuristics and using the A* search algorithm, we’ve developed an efficient solution to the 8-Puzzle problem. This project demonstrates the efficacy of Informed Search Heuristics and A* in problem-solving tasks and provides valuable insights into their workings. As we delve deeper into the field of Artificial Intelligence, we can apply these concepts to other problem-solving tasks and real-world applications.

Join the Discussion

We welcome your thoughts, inquiries, and experiences related to the 8-Puzzle project! Engage in our Disqus forum below. Share your insights, ask questions, and connect with others passionate about Informed Search Heuristics and problem-solving.

Feel free to share your ideas or ask for help; we’re all in this together. Let’s build a vibrant community to discuss, learn, and explore the exciting world of Informed Search Heuristics and their application in problems like the 8-Puzzle.

Do provide us with feedback and share with us how we could make this write-up more beneficial for you! We are always eager to learn and improve.

Recent Trends in Solving the 8-Puzzle Problem

Ieee account.

  • Change Username/Password
  • Update Address

Purchase Details

  • Payment Options
  • Order History
  • View Purchased Documents

Profile Information

  • Communications Preferences
  • Profession and Education
  • Technical Interests
  • US & Canada: +1 800 678 4333
  • Worldwide: +1 732 981 0060
  • Contact & Support
  • About IEEE Xplore
  • Accessibility
  • Terms of Use
  • Nondiscrimination Policy
  • Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

Data Magazine

The 8 Puzzle Problem Solving a Classic Challenge

8 puzzle problem solving

Key Takeaways

  • The 8 puzzle problem is a classic problem in computer science and artificial intelligence.
  • It involves a 3×3 grid with 8 numbered tiles and one empty space, and the goal is to rearrange the tiles to reach a specific configuration.
  • There are various algorithms and techniques that can be used to solve the 8 puzzle problem, including depth-first search, breadth-first search, and A* search.
  • Solving the 8 puzzle problem can have practical applications in areas such as game design, robotics, and optimization.
  • Understanding the 8 puzzle problem can help improve problem-solving skills and algorithmic thinking.

Introduction

The 8 puzzle problem is a fascinating challenge that has intrigued computer scientists and puzzle enthusiasts for decades. It involves a 3×3 grid with 8 numbered tiles and one empty space, and the goal is to rearrange the tiles to reach a specific configuration. This seemingly simple task can actually be quite complex, requiring careful planning and strategic thinking. In this article, we will explore the 8 puzzle problem in depth, discussing its history, algorithms for solving it, and its practical applications.

A Brief History of the 8 Puzzle Problem

The 8 puzzle problem has its roots in the 19th century, when it was introduced as a physical puzzle game. The game consisted of a 3×3 grid with 8 numbered tiles and one empty space, and players had to slide the tiles around to arrange them in numerical order. The puzzle gained popularity and soon became a favorite pastime for puzzle enthusiasts.

The Challenge of Solving the 8 Puzzle Problem

While the 8 puzzle problem may seem simple at first glance, it poses a significant challenge for computer scientists and artificial intelligence researchers. The number of possible configurations of the puzzle is enormous, making it impractical to solve it through brute force. Instead, various algorithms and techniques have been developed to efficiently solve the problem.

Algorithms for Solving the 8 Puzzle Problem

There are several algorithms that can be used to solve the 8 puzzle problem. One popular approach is depth-first search, which involves exploring each possible move until a solution is found. Another approach is breadth-first search, which explores all possible moves at each step before moving on to the next level. A more advanced algorithm is A* search, which uses heuristics to guide the search and find the optimal solution.

Practical Applications of Solving the 8 Puzzle Problem

While the 8 puzzle problem may seem like a purely academic exercise, it actually has practical applications in various fields. In game design, the problem can be used to create challenging puzzles and levels that require players to think strategically. In robotics, solving the 8 puzzle problem can help robots navigate complex environments and plan efficient paths. Additionally, the problem has applications in optimization, where it can be used to find the most efficient solutions to complex problems.

Improving Problem-Solving Skills and Algorithmic Thinking

Studying and understanding the 8 puzzle problem can have significant benefits for individuals looking to improve their problem-solving skills and algorithmic thinking. The problem requires logical reasoning, planning, and the ability to break down complex tasks into smaller, manageable steps. By practicing solving the 8 puzzle problem, individuals can enhance their problem-solving abilities and develop a systematic approach to tackling challenges.

The 8 puzzle problem is a captivating challenge that has captivated puzzle enthusiasts and computer scientists alike. Its simple yet complex nature makes it an ideal problem for studying algorithms and problem-solving techniques. By exploring the history, algorithms, and practical applications of the 8 puzzle problem, we can gain a deeper understanding of its significance and the skills it can help develop. Whether you’re a puzzle enthusiast or a computer science student, the 8 puzzle problem is sure to provide hours of entertainment and intellectual stimulation.

8 puzzle problem solving

Written by Martin Cole

a book with a diagram on it

Understanding Modelling Algorithms Analysis, Prediction, and Applications

8 puzzle problem solving

Creating Logic Architecture Diagrams with HTML Tags

© 2024 by Fupping Media

Username or Email Address

Remember Me

Forgot password?

Enter your account data and we will send you a link to reset your password.

Your password reset link appears to be invalid or expired.

Privacy policy.

To use social login you have to agree with the storage and handling of your data by this website. %privacy_policy%

Add to Collection

Public collection title

Private collection title

No Collections

Here you'll find all collections you've created before.

A sliding block puzzle, whose solution is found using A* Search.

author : sasank mail-id : [email protected] last mod. : 03/01/2017

Note : The distinction between a state and a node is crucial to the understanding of A* Search, which is used to solve the 8Puzzle problem. However, the terms node & state are used interchangebly in this document. In fact, this distinction is important to understand any AI search algorithm.

a. Problem Definition :

In this puzzle, we have a 3x3 grid containing 9 squares containing 8 tiles and 1 blank. The 8 tiles are numbered 1 to 8. The blank can move up, down, left or right depending on it’s position.

Given an arbitrary initial configuration of the grid, the problem solving agent needs to find an optimal sequence of actions that lead to the goal state, if there is one.

The intial state can be any possible configuration of the 3x3 grid. On the other hand, the goal state has a definite order that is discussed later.

b. Problem Formulation :

  • State Description
  • Initial State & Goal State
  • Actions as function of states
  • Transition Model
  • Step Costs & Path Costs

b.1 State Description :

A state is described by the positions of the tiles and blank in a state array.

Basic terminolgy :

square x - location in the grid, x ϵ [0,8] tile x - a square occupied by the number x ϵ [1,8] blank - unoccupied square.

Clearly, there are finite no. of states in this problem.

b.2 Initial State & Goal State :

Initial state is taken as an input. It can be any possible configuration of the grid i.e., any possible state of the problem.

Goal state for 8-Puzzle is defined differently by various authors. We will consider the following state as the goal state.

b.3 Actions as function of States :

Set of all possible actions in the 8 puzzle problem : { UP, LEFT, DOWN, RIGHT }

All of them represent the possible physical movements of the blank in the grid.

We need a function ACTIONS that takes in state of the problem as an argument and returns all the possible actions that are valid in the given state.

For example, consider the following state :

When ACTIONS is called on the above state, it returns UP,LEFT & DOWN.

To make the representation much simpler, let us quantify the actions.

UP : 1 LEFT : 2 DOWN : 4 RIGHT : 8

Now, if ACTIONS is called on the same state, it returns 1+2+4, i.e., 7.

b.4 Transition Model :

We need a transition model that describes how the grid evolves with different actions taken by the agent.

The transition function takes current state and an action as arguments and returns the resulting state.

b.5 Goal Test :

This function GOALTEST takes in a state as an argument and returns a boolean by checking if the state is the goal or not.

The goal test function returns True for the above state.

b.6 Step Costs & Path Costs :

Every action is associated with some cost. Here, we consider step cost to be 1 for each action. Path cost is the sum of all the step costs in the path(sequence of states).

Whenever there is a transition, we find the path cost recursively.

Consider a transition from state a to state b:   path-cost(b) = path-cost(a) + step-cost(a,b)

Path cost for the initial state is taken as zero.

c. Implementation details :

  • Structure of node

c.1 Algorithm :

We use A* Search to find an optimal sequence of actions that lead to the goal state.

A* Search is a well known informed search algorithm. An informed search algorithm has additional knowledge given to it, that is not provided by the problem description itself. This additional knowledge is known as heuristics.

Check out the following link to know more about A* Search. http://web.mit.edu/eranki/www/tutorials/search/

c.2 Heuristics :

Given a state, heuristics of that state indicates an estimated cost to reach the goal state.

A good heuristic function is admissible and consistent.

Check out the following link to know more about heurisitcs. http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

For a node n, h(n) = #misplaced tiles and blank in the grid

The above heuristic is both admissible and consistent.

c.3 Structure of node :

We define a node as a structure that holds following information.

state holds state description

actions() member function, returns a set of actions as a number

parent a pointer to the parent node

path-cost the cost of the path to the current node.

Compilation & Running using g++

g++ astar.cpp puzzle.cpp problem.cpp main.cpp -o excutable-name.exe executable-name.exe

Input/Output Format

Consider the following state as the initial state.

The input is space separated integers representing the positions of the tiles from 0 to 8.

The input for the above initial state is, 4 7 6 2 0 1 3 8 5

The goal state is for this problem is,

The output sequence is a series of states showing the optimal path to the goal state. 8 0 1 2 3 4 5 6 7 . . . 4 7 6 2 0 1 3 8 5

Insight Tribune

Ignite Your Mind and Illuminate Your World

Solving the 8-Puzzle Problem in Artificial Intelligence with Python Code: A Step-by-Step Guide

8 puzzle problem solving

The 8-puzzle problem is a popular puzzle game that has intrigued puzzle enthusiasts for decades. It requires players to move tiles on a board to create a desired final configuration.

In the field of artificial intelligence (AI), the 8-puzzle problem serves as a benchmark for testing search algorithms. It is a classic example of a search problem, where the goal is to find the optimal solution path that minimizes the number of moves required to reach the desired state.

Introduction

The 8-puzzle problem is a classic example of a search problem that is commonly used to demonstrate the efficiency of search algorithms in artificial intelligence. The goal of the puzzle is to rearrange the tiles on an 8×8 grid to fit a specific configuration.

In this article, we will explore the 8-puzzle problem and show how it can be solved using Python code. We will also discuss some of the search algorithms commonly used to solve this problem, including the Breadth First search, Depth First search and A* search.

The 8-Puzzle Problem

The 8-puzzle problem is a game that consists of 9 squares on a 3×3 grid. Each square contains a number from 1 to 8, arranged in random order. The goal of the game is to arrange the squares in numerical order from left to right, top to bottom, with the empty square in the bottom-right corner.

Figure 1 shows an example of an 8-puzzle game.

Figure 1: Example of an 8-puzzle game

There are 9! (362,880) possible configurations of the puzzle, but only half of them are solvable. A configuration is considered solvable if it can be transformed into the goal configuration by sliding tiles one at a time into the empty space, where the empty space is initially in the bottom-right corner.

Solving the 8-Puzzle Problem with Python Code

In this section, We will discuss how to solve the 8-puzzle problem using Python code. We will implement three search algorithms: Breadth First search, Depth First search and A* search.

Breadth First Search

Breadth First search is a search algorithm that explores all possible paths, starting from the initial state, and expands the shallowest node first. It guarantees finding the optimal solution, but is generally slower than other search algorithms.

In the case of the 8-puzzle problem, the state space consists of all possible configurations of the puzzle. We can represent each configuration as a tuple, where each element of the tuple represents the value of each square on the board.

Figure 2 shows the pseudocode for Breadth First search algorithm.

Figure 2: Pseudocode for Breadth First search algorithm

Using this algorithm, we can solve the 8-puzzle problem and find the optimal solution. However, it may take a lot of time and resources to solve larger problems.

Depth First Search

Depth First search is a search algorithm that explores paths as far as possible before backtracking. It searches deeper and deeper until it finds a solution or runs out of memory. Depth First search does not guarantee finding the optimal solution, but is generally faster than Breadth First search.

In the case of the 8-puzzle problem, the Depth First search algorithm can be implemented using a stack to keep track of nodes to be expanded. We can start by pushing the initial state onto the stack, then pop the state from the top and expand its children one by one, pushing them onto the stack. We continue this process until we reach the goal state or empty the stack.

Figure 3 shows the pseudocode for Depth First search algorithm.

Figure 3: Pseudocode for Depth First search algorithm

Using this algorithm, we can solve the 8-puzzle problem, but it may not find the optimal solution. It is suitable for problems with very large state spaces, where the optimal solution is not necessarily the goal.

A* search is a search algorithm that combines the Breadth First search and Depth First search strategies. It uses a heuristic function to evaluate the cost of each node in the search space, and expands the node with the lowest evaluation function value.

The heuristic function estimates the minimum cost of reaching the goal state from the current state. In the case of the 8-puzzle problem, a common heuristic function is the Manhattan distance, which calculates the sum of the horizontal and vertical distances between the current position of each tile and its goal position on the board.

Figure 4 shows the pseudocode for A* search algorithm.

Figure 4: Pseudocode for A* search algorithm

Using this algorithm, we can solve the 8-puzzle problem and find the optimal solution in the shortest time possible. It works well for problems with relatively small state spaces, where the optimal solution is required.

In this article, we explored the 8-puzzle problem and showed how it can be solved using Python code. We discussed three search algorithms commonly used to solve this problem: Breadth First search, Depth First search and A* search. We also discussed the advantages and disadvantages of each algorithm, and when to use them.

The 8-puzzle problem is a classic example of a search problem in artificial intelligence, and serves as a benchmark for testing search algorithms. With the help of Python code, we can solve the problem and find the optimal solution efficiently.

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Save my name, email, and website in this browser for the next time I comment.

Related Posts

8 puzzle problem solving

  • Explorations

Discovering the Fascinating World of Cultural Evolution Dictionary

  • Aiden Scholar
  • June 11, 2023

are you curious about the evolution of culture and how it has influenced society over…

8 puzzle problem solving

The Ultimate Guide: How to Create a Website for My Business in 5 Simple Steps

  • June 15, 2023

if you're a business owner, having a website is a must. not only does it…

8 puzzle problem solving

Understanding the Corporate Culture Definition: 5 Key Elements to Consider

corporate culture is the shared values, beliefs, practices, and behaviors that define how an organization…

8 puzzle problem solving

Get Ready to Feel The Burn with These Poppable Muscle-Boosting Exercises!

  • June 17, 2023

get ready to feel the burn with these poppable muscle-boosting exercises!

Javatpoint Logo

Java Tutorial

Control statements, java object class, java inheritance, java polymorphism, java abstraction, java encapsulation, java oops misc.

JavaTpoint

  • Send your Feedback to [email protected]

Help Others, Please Share

facebook

Learn Latest Tutorials

Splunk tutorial

Transact-SQL

Tumblr tutorial

Reinforcement Learning

R Programming tutorial

R Programming

RxJS tutorial

React Native

Python Design Patterns

Python Design Patterns

Python Pillow tutorial

Python Pillow

Python Turtle tutorial

Python Turtle

Keras tutorial

Preparation

Aptitude

Verbal Ability

Interview Questions

Interview Questions

Company Interview Questions

Company Questions

Trending Technologies

Artificial Intelligence

Artificial Intelligence

AWS Tutorial

Cloud Computing

Hadoop tutorial

Data Science

Angular 7 Tutorial

Machine Learning

DevOps Tutorial

B.Tech / MCA

DBMS tutorial

Data Structures

DAA tutorial

Operating System

Computer Network tutorial

Computer Network

Compiler Design tutorial

Compiler Design

Computer Organization and Architecture

Computer Organization

Discrete Mathematics Tutorial

Discrete Mathematics

Ethical Hacking

Ethical Hacking

Computer Graphics Tutorial

Computer Graphics

Software Engineering

Software Engineering

html tutorial

Web Technology

Cyber Security tutorial

Cyber Security

Automata Tutorial

C Programming

C++ tutorial

Control System

Data Mining Tutorial

Data Mining

Data Warehouse Tutorial

Data Warehouse

Javatpoint Services

JavaTpoint offers too many high quality services. Mail us on [email protected] , to get more information about given services.

  • Website Designing
  • Website Development
  • Java Development
  • PHP Development
  • Graphic Designing
  • Digital Marketing
  • On Page and Off Page SEO
  • Content Development
  • Corporate Training
  • Classroom and Online Training

Training For College Campus

JavaTpoint offers college campus training on Core Java, Advance Java, .Net, Android, Hadoop, PHP, Web Technology and Python. Please mail your requirement at [email protected] . Duration: 1 week to 2 week

RSS Feed

Search code, repositories, users, issues, pull requests...

Provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

  • Notifications

8-puzzle problem using A* algorithm

Siddhipatade/8-puzzle-problem

Name already in use.

Use Git or checkout with SVN using the web URL.

Work fast with our official CLI. Learn more about the CLI .

  • Open with GitHub Desktop
  • Download ZIP

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

N-Puzzle or Sliding Puzzle is a popular puzzle that consists of N tiles where N can be 8, 15, 24 and so on.

The puzzle consists of 8 tiles and one empty space where the tiles can be moved. Start and Goal state of the puzzle are provided. The puzzle can be solved by moving the tiles one by one in the single empty space and thus achieving the Goal state.

The tiles in the initial(start) state can be moved in the empty space in a particular order and thus achieve the goal state.

Rules for solving the puzzle

Instead of moving the tiles in the empty space we can visualize moving the empty space in place of the tile, basically swapping the tile with the empty space. The empty space can only move in four directions viz.,

The empty space cannot move diagonally and can take only one step at a time (i.e. move the empty space one position at a time).

A* Algorithm

A * is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between multiple points, called nodes.

The key feature of the A * algorithm is that it keeps a track of each visited node which helps in ignoring the nodes that are already visited, saving a huge amount of time. It also has a list that holds all the nodes that are left to be explored and it chooses the most optimal node from this list, thus saving time not exploring unnecessary or less optimal nodes.

So I use two lists namely 'Open list' and 'Closed list' the 'Open list' contains all the nodes that are being generated and are not existing in the 'Closed list' and each node explored after it's neighboring nodes are discovered is put in the 'Closed list' and the neighbors are put in the 'Open list' this is how the nodes expand. Each node has a pointer to its parent so that at any given point it can retrace the path to the parent. Initially, the open list holds the start(Initial) node. The next node chosen from the open list is based on its 'f-score' , the node with the least 'f-score' is picked up and explored.

A * uses a combination of heuristic value (h-score: how far the goal node is) as well as the 'g-score' (i.e. the number of nodes traversed from the start node to current node). In 8-Puzzle problem, define the 'h-score' as the number of misplaced tiles by comparing the current state and the goal state or summation of the Manhattan distance between misplaced nodes. 'g-score' will remain as the number of nodes traversed from start node to get to the current node.

Calculate the 'h-score' by comparing the initial(current) state and goal state and counting the number of misplaced tiles.

Thus, h-score = 5 and g-score = 0 as the number of nodes traversed from the start node to the current node is 0.

How A* solves the 8-Puzzle problem

We first move the empty space in all the possible directions in the start state and calculate the 'f-score' for each state. This is called expanding the current state. After expanding the current state, it is pushed into the 'Closed list' and the newly generated states are pushed into the 'Open list' . A state with the least 'f-score' is selected and expanded again. This process continues until the goal state occurs as the current state.

Basically, here we are providing the algorithm a measure to choose its actions. The algorithm chooses the best possible action and proceeds in that path. This solves the issue of generating redundant child states, as the algorithm will expand the node with the least 'f-score' .

  • Python 100.0%

8-Puzzle Problem in Artificial Intelligence

Definition:.

“It has set off a 3x3 board having 9 block spaces out of which 8 blocks having tiles bearing number from 1 to 8. One space is left blank. The tile adjacent to blank space can move into it. We have to arrange the tiles in a sequence for getting the goal state”.

The 8-puzzle problem belongs to the category of “sliding block puzzle” type of problem. The 8-puzzle i s a square tray in which eight square tiles are placed. The remaining ninth square is uncovered. Each tile in the tray has a number on it.

A tile that is adjacent to blank space can be slide into that space. The game consists of a starting position and a specified goal position. The goal is to transform the starting position into the goal position by sliding the tiles around.

The control mechanisms for an 8-puzzle solver must keep track of the order in which operations are performed, so that the operations can be undone one at a time if necessary. The objective of the puzzles is to find a sequence of tile movements that leads from a starting configuration to a goal configuration such as two situations given below.

Figure            (Starting State)                              (Goal State)

The state of 8-puzzle is the different permutation of tiles within the frame. The operations are the permissible moves up, down, left, right. Here at each step of the problem a function f(x) will be defined which is the combination of g(x) and h(x).

i.e. F(x)=g(x) + h (x)

g (x): how many steps in the problem you have already done or the current state from the initial state.

h (x): Number of ways through which you can reach at the goal state from the current state or Or

h (x): is the heuristic estimator that compares the current state with the goal state note down how many states are displaced from the initial or the current state. After calculating the f value at each step finally take the smallest f (x) value at every step and choose that as the next current state to get the goal

Let us take an example.

Figure     (Initial State)                               (Goal State)

f (x) is the step required to reach at the goal state from the initial state. So in the trayeither 6 or 8 can change their portions to fill the empty position. So there will be two possible current states namely B and C. The f (x) value of B is 6 and that of C is 4. As 4 is the minimum, so take C as the current state to the next state.

In this step, from the tray C three states can be drawn. The empty position will contain either 5 or 3 or 6. So for three different values three different states can be obtained. Then calculate each of their f (x) and take the minimum one.

Here the state F has the minimum value i.e. 4 and hence take that as the next current state.

The tray F can have 4 different states as the empty positions can be filled with b4 values i.e.2, 4, 5, 8.

In the step-3 the tray I has the smallest f (n) value. The tray I can be implemented in 3 different states because the empty position can be filled by the members like 7, 8, 6.

Hence, we reached at the goal state after few changes of tiles in different positions of the trays.

This problem requires a lot of space for saving the different trays. Time complexity is more than that of other problems.

The user has to be very careful about the shifting of tiles in the trays. Very complex puzzle games can be solved by this technique.

8 Puzzle Problem and Solution:

We also know the  eight puzzle problem  by the name of  N puzzle problem  or  sliding puzzle problem.

N-puzzle  that consists of N tiles (N+1 titles with an empty tile) where N can be 8, 15, 24 and so on.

In our example  N = 8.  (that is  square root of  (8+1) = 3 rows and 3 columns ).

In the same way, if we have N = 15, 24 in this way, then they have Row and columns as follow  (square root of (N+1) rows  and square root of (N+1) columns).

That is if  N=15  than number of rows and columns= 4,   and if  N= 24  number of rows and columns= 5.

So, basically in these types of problems we have given a  initial state or initial configuration (Start state) and a Goal state or Goal Configuration.

Here We are solving a problem  of 8 puzzle  that is  a 3x3 matrix.

Initial state                                                                      Goal state

8 puzzle problem solving

The puzzle can be solved by moving the tiles one by one in the single empty space and thus achieving the Goal state.

Rules of solving puzzle

Instead of moving the tiles in the empty space we can visualize moving the empty space in place of the tile.

The empty space can only  move in four directions  (Movement of empty space)

The empty space  cannot move diagonally  and can take  only one step at a time .

All possible move of a Empty tile

8 puzzle problem solving

o- Position  total possible moves are  (2) ,  x - position  total possible moves are  (3)  and 

#-position  total possible moves  are (4)

Let's solve the problem without  Heuristic Search  that is  Uninformed Search or Blind Search ( Breadth First Search and Depth First Search)

Breath First Search to solve Eight puzzle problem

8 puzzle problem solving

Note:  If we solve this problem with depth first search, then it will go to depth instead of exploring layer wise nodes.

Time complexity:  In worst case time complexity in  BFS is O(b^d) know as order of b raise to power d.   In this  particular case it is (3^20). 

b- branch factor

d- depth factor

Let's solve the problem with  Heuristic Search  that is  Informed Search (A* , Best First Search (Greedy Search))

To solve the problem with Heuristic search or informed search we have to calculate Heuristic values of each node to calculate  cost function. (f=g+h)

Note:  See the initial state and goal state carefully all values except (4,5 and 8) are at their respective places.  so, the heuristic value for first node is 3. (Three values are misplaced to reach the goal). And l et's take actual cost (g) according to depth.

8 puzzle problem solving

Note: Because of quick solution time complexity is less than that of Uninformed search but optimal solution not possible. 

8 puzzle problem solving

  • Toys & Games
  • Novelty & Gag Toys
  • Fidget Toys
  • Fidget Blocks

Amazon prime logo

Enjoy fast, free delivery, exclusive deals, and award-winning movies & TV shows with Prime Try Prime and start saving today with fast, free delivery

Amazon Prime includes:

Fast, FREE Delivery is available to Prime members. To join, select "Try Amazon Prime and start saving today with Fast, FREE Delivery" below the Add to Cart button.

  • Cardmembers earn 5% Back at Amazon.com with a Prime Credit Card.
  • Unlimited Free Two-Day Delivery
  • Instant streaming of thousands of movies and TV episodes with Prime Video
  • A Kindle book to borrow for free each month - with no due dates
  • Listen to over 2 million songs and hundreds of playlists
  • Unlimited photo storage with anywhere access

Important:  Your credit card will NOT be charged when you start your free trial or if you cancel during the trial period. If you're happy with Amazon Prime, do nothing. At the end of the free trial, your membership will automatically upgrade to a monthly membership.

  • Free returns are available for the shipping address you chose. You can return the item for any reason in new and unused condition: no shipping charges
  • Learn more about free returns.
  • Go to your orders and start the return
  • Select the return method

8 puzzle problem solving

Image Unavailable

Rubik’s Cube, The Original 3x3 Color-Matching Puzzle Classic Problem-Solving Challenging Brain Teaser Fidget Toy, for Adults & Kids Ages 8 and up

  • To view this video download Flash Player

Rubik’s Cube, The Original 3x3 Color-Matching Puzzle Classic Problem-Solving Challenging Brain Teaser Fidget Toy, for Adults & Kids Ages 8 and up

8 puzzle problem solving

Purchase options and add-ons

About this item.

  • THE ORIGINAL RUBIK’S CUBE: A combination of mathematics, art and science - the iconic Rubik’s Cube challenges your mind and problem-solving skills. The classic 3x3 Rubik’s Cube is the world’s best-known addictive puzzle and has fascinated fans since its launch in 1980. A true icon.
  • TURN, TWIST & REPEAT: The Rubik’s Cube features six different coloured sides, each made up of nine squares. Once the faces are jumbled up, you are going to need to twist, turn and rotate the Rubik’s Cube until each of the six faces has only one colour.
  • A MUST HAVE FOR PUZZLE LOVERS: This original cube has 43,252,003,274,489,856,000 combinations, but only one solution. Do you have what it takes to solve the world’s favourite puzzle?
  • IMPROVED PLAY: All the features of the original cube but with faster, smoother and more reliable play. No more frustrating snagging or popping core.
  • CLASSIC PUZZLE-SOLVING GAMEPLAY: This challenging puzzle is the same retro toy that you remember from your childhood. Brain teaser, fidget toy, or travel puzzle- this brain puzzle is your new go-to.
  • Includes: 1 Rubik's 3x3 Cube
  • Covered by the Spin Master Care Commitment. See below for full details

Frequently bought together

Rubik’s Cube, The Original 3x3 Color-Matching Puzzle Classic Problem-Solving Challenging Brain Teaser Fidget Toy, for Adults

Similar items that may ship from close to you

Rubik's Mini, Original 2x2 Rubik's Cube 3D Puzzle Fidget Cube Stress Relief Fidget Toy Brain Teasers Travel Games for Adults

Product information

Product description.

The Rubik’s Cube is a classic colour-matching puzzle that can be enjoyed at home or on the move. The original, classic 3x3 cube is a highly addictive brain teaser that has fascinated fans all around the world for decades. The Rubik’s Cube features six different sides, each made up of nine colourful squares. A must for puzzle lovers, the aim is to try twist and turn the Rubik’s Cube to its original state, with every side having one solid colour. There are... wait for it... 43,252,003,274,489,856,000 ways of arranging the squares, and only one of these is the solution. Turn and twist away – can you solve it? The new and improved Rubik’s Cube features a mechanism that results in a smoother, faster and more reliable play. The traditional stickers have been replaced with plastic tiles which means no fading, peeling or cheating!

Important information

To report an issue with this product or seller, click here .

From the brand

rubik's background

Shop Original Cubes

Visit the Store

twist

Shop Novelty Cubes

capture pack & go

Shop Multiplayer Games

From the manufacturer.

packaging

RUBIK'S ORIGINAL 3X3 CUBE

A must-have for puzzle lovers.

The original Rubik’s Cube has 43,252,003,274,489,856,000 combinations, but only one solution. Do you have what it takes to solve the world’s favorite puzzle… now with a fresh twist.

THE ORIGINAL RUBIK’S CUBE

A combination of mathematics, art, and science - the iconic Rubik’s Cube challenges your mind and problem-solving skills. The classic 3x3 Rubik’s Cube is the world’s best-known addictive puzzle and has fascinated fans since its launch in 1980.

VARIETY OF USES

  • Brain teaser
  • 3D puzzle game
  • Travel activity

What's in the box

Videos for this product.

Video Widget Card

Click to play video

Video Widget Video Title Section

What I love most about this rubiks cube

Kristiahna Clark

8 puzzle problem solving

Rubik's Cube Review

IansInsights

8 puzzle problem solving

Rubik’s Cube, The Original 3x3 Color-Puzzle

8 puzzle problem solving

Honest Mom Review & Why We Love This One!

Kylie Prescott

8 puzzle problem solving

Everything We Love About the Classic 3x3 Rubiks Cube

Benjamin and Ashley

8 puzzle problem solving

Pros and cons of this basic starter puzzle cube!

🎉 Robbie and Sarah 🎉

8 puzzle problem solving

Honest review of rubix cube

Inspired Home

8 puzzle problem solving

Rubik's Cube -Patterns with my 6 six year old.

Sonya Marin Designs

8 puzzle problem solving

Rubik's Cube - Timeless Fun

Moms Need This

8 puzzle problem solving

The Original Rubik's

Spin Master, Inc

Looking for specific info?

Customer reviews.

Customer Reviews, including Product Star Ratings help customers to learn more about the product and decide whether it is the right product for them.

To calculate the overall star rating and percentage breakdown by star, we don’t use a simple average. Instead, our system considers things like how recent a review is and if the reviewer bought the item on Amazon. It also analyzed reviews to verify trustworthiness.

Reviews with images

Customer Image

Submit a report

  • Harassment, profanity
  • Spam, advertisement, promotions
  • Given in exchange for cash, discounts

Sorry, there was an error

  • Sort reviews by Top reviews Most recent Top reviews

Top reviews from the United States

There was a problem filtering reviews right now. please try again later..

8 puzzle problem solving

Top reviews from other countries

  • Amazon Newsletter
  • About Amazon
  • Accessibility
  • Sustainability
  • Press Center
  • Investor Relations
  • Amazon Devices
  • Amazon Science
  • Start Selling with Amazon
  • Sell apps on Amazon
  • Supply to Amazon
  • Protect & Build Your Brand
  • Become an Affiliate
  • Become a Delivery Driver
  • Start a Package Delivery Business
  • Advertise Your Products
  • Self-Publish with Us
  • Host an Amazon Hub
  • › See More Ways to Make Money
  • Amazon Visa
  • Amazon Store Card
  • Amazon Secured Card
  • Amazon Business Card
  • Shop with Points
  • Credit Card Marketplace
  • Reload Your Balance
  • Amazon Currency Converter
  • Your Account
  • Your Orders
  • Shipping Rates & Policies
  • Amazon Prime
  • Returns & Replacements
  • Manage Your Content and Devices
  • Your Recalls and Product Safety Alerts
  • Conditions of Use
  • Privacy Notice
  • Your Ads Privacy Choices

IMAGES

  1. The 8-Puzzle

    8 puzzle problem solving

  2. Solving The 8-Puzzle Problem With Hill Climbing

    8 puzzle problem solving

  3. 8 puzzle problem solved example

    8 puzzle problem solving

  4. Solving 8-Puzzle using A* Algorithm

    8 puzzle problem solving

  5. Heuristic Search : 8-Puzzle Problem

    8 puzzle problem solving

  6. Solving 8-puzzle problem using A algorithm

    8 puzzle problem solving

VIDEO

  1. Can You Solve This Problem? I Math Puzzle

  2. draw the puzzle problem solving video| The thife gaming draw the puzzles game #sort

  3. draw the puzzle problem solving video| The triki thife gaming draw the puzzles game #sort

  4. Can You Solve This Problem? I Math Puzzle

  5. Can you solve this puzzle l maths puzzle#shorts 🤔

  6. Puzzle problem solved ||#youtubeshorts #shortvideo #shorts

COMMENTS

  1. 8 puzzle Problem using Branch And Bound

    Practice We have introduced Branch and Bound and discussed the 0/1 Knapsack problem in the below posts. Branch and Bound | Set 1 (Introduction with 0/1 Knapsack) Branch and Bound | Set 2 (Implementation of 0/1 Knapsack) In this puzzle solution of the 8 puzzle problem is discussed.

  2. What can be the efficient approach to solve the 8 puzzle problem?

    19 The 8-puzzle is a square board with 9 positions, filled by 8 numbered tiles and one gap. At any point, a tile adjacent to the gap can be moved into the gap, creating a new gap position. In other words the gap can be swapped with an adjacent (horizontally and vertically) tile.

  3. How to Solve 8 Puzzle (with Pictures)

    8 puzzle is a type of sliding puzzle. It may take normal people a few minutes to solve it. In this article, you will learn how to solve 8 puzzle fast. After you master the steps, you will be able to solve it within a minute! Part 1 Solving the First Row Download Article 1 Put 1 on its original place. 2 Place 3 right next to 1. 3 Place 2 under 3. 4

  4. 8-Puzzle Solver

    8 puzzle solver and tree visualizer. Supports breadth-first, uniform-cost, depth-first, iterative-deepening, greedy-best and A* search algorithms.

  5. 8 Puzzle Solver

    8 Puzzle Solver AI-powered puzzle solver, let you find the solution of the sliding 8-puzzle in just a second. Step 1: Upload Template (Optional) To get started, upload your image template below. UPLOAD IMAGE Step 2: Arrange Puzzle to Solve Drag and Drop the puzzle pieces to match your current puzzle obstacle. 1 2 3 4 5 6 7 8

  6. Solving 8 puzzle problem using A* star search

    May 17, 2020 This tutorial will solve the 8 puzzle problem using the A* (star) search algorithm. We will approach the solution by first modelling the problem, building the fundamental blocks and finally applying a solver to solve the puzzle.

  7. algorithm Tutorial => Solving 8-puzzle problem using A* algorithm

    algorithm A* Pathfinding Solving 8-puzzle problem using A* algorithm. Solving 8-puzzle problem using A* algorithm. Help us to keep this website almost Ad Free! It takes only 10 seconds of your time: > Step 1: Go view our video on YouTube: EF Core Bulk Insert. > Step 2: And Like the video. BONUS: You can also share it!

  8. 8-Puzzle AI Solver

    Solve the 8puzzle game interactively with our AI-powered solver. Improve your skills and track progress with real-time feedback. Perfect for beginners and pros alike

  9. Solving the 8-Puzzle with A* and SimpleAI

    The 8-Puzzle problem is a puzzle that was invented and popularized by Noyes Palmer Chapman in the late 19th century. It consists of a 3x3 grid with eight numbered tiles and a blank space. The goal is to reach a specified goal state from a given start state by sliding the blank space up, down, left or right.

  10. Recent Trends in Solving the 8-Puzzle Problem

    Recent Trends in Solving the 8-Puzzle Problem Abstract: The 8-puzzle problem is a well-known artificial intelligence problem consisting of a 3x3 grid with 8 tiles numbered 1-8 and one blank space. The goal is to move the tiles around to achieve a specific goal configuration.

  11. The 8 Puzzle Problem Solving a Classic Challenge

    Introduction The 8 puzzle problem is a fascinating challenge that has intrigued computer scientists and puzzle enthusiasts for decades. It involves a 3×3 grid with 8 numbered tiles and one empty space, and the goal is to rearrange the tiles to reach a specific configuration.

  12. 8-Puzzle Solver

    A* search algorithm implementation for solving 8-puzzle problem. Includes code modularization, performance optimization and solvability checking features. - GitHub - sminerport/eight-puzzle-solver: A* search algorithm implementation for solving 8-puzzle problem. Includes code modularization, performance optimization and solvability checking features.

  13. Sai Sasank

    The 8 tiles are numbered 1 to 8. The blank can move up, down, left or right depending on it's position. Given an arbitrary initial configuration of the grid, the problem solving agent needs to find an optimal sequence of actions that lead to the goal state, if there is one. The intial state can be any possible configuration of the 3x3 grid.

  14. 8-puzzle · GitHub Topics · GitHub

    FawadJawaid / 8-puzzle-solver-AI. This is an Artificial Intelligence project which solves the 8-Puzzle problem using different Artificial Intelligence algorithms techniques like Uninformed-BFS, Uninformed-Iterative Deepening, Informed-Greedy Best First, Informed-A* and Beyond Classical search-Steepest hill climbing.

  15. 8 Puzzle problem in Python

    The 8 puzzle problem solution is covered in this article. A 3 by 3 board with 8 tiles (each tile has a number from 1 to 8) and a single empty space is provided. The goal is to use the vacant space to arrange the numbers on the tiles such that they match the final arrangement.

  16. 8-Puzzle

    8-puzzle game is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing.

  17. 8-puzzle-solver · GitHub Topics · GitHub

    The 8-puzzle problem is a puzzle invented and popularized by Noyes Palmer Chapman in the 1870s. It is played on a 3-by-3 grid with 8 square blocks labeled 1 through 8 and a blank square. Your goal is to rearrange the blocks so that they are in order. github python code bfs breadth-first-search 8-puzzle fixed moves 8-puzzle-solver 8puzzle-game 8 ...

  18. Solution to 8-Puzzle through A* Algorithm

    How A* solves the 8-Puzzle problem. We first move the empty space in all the possible directions in the start state and calculate the F (n) for each state. This is called expanding the...

  19. Solving the 8-Puzzle Problem in Artificial Intelligence with Python

    The 8-Puzzle Problem. The 8-puzzle problem is a game that consists of 9 squares on a 3×3 grid. Each square contains a number from 1 to 8, arranged in random order. The goal of the game is to arrange the squares in numerical order from left to right, top to bottom, with the empty square in the bottom-right corner. Figure 1 shows an example of ...

  20. 8 Puzzle problems in Java

    The best puzzle size is 8. Cost-based algorithm: To move one tile in any direction, we assume this will cost one unit. As a result, we define the cost function as follows for an algorithm like the 8-puzzle method: c (x) = f (x) + h (x) where. f (x) is the distance between the root and x in the path (the number of moves so far) and.

  21. 8-puzzle problem using A* algorithm

    8-puzzle problem using A* algorithm. N-Puzzle or Sliding Puzzle is a popular puzzle that consists of N tiles where N can be 8, 15, 24 and so on. In our example N = 8. The puzzle is divided into sqrt (N+1) rows and sqrt (N+1) columns. 8-Puzzle will have 3 rows and 3 columns. The puzzle consists of 8 tiles and one empty space where the tiles can ...

  22. 8-Puzzle Problem in Artificial Intelligence

    The 8-puzzle problem belongs to the category of "sliding block puzzle" type of problem. The 8-puzzle i s a square tray in which eight square tiles are placed. The remaining ninth square is uncovered. Each tile in the tray has a number on it. A tile that is adjacent to blank space can be slide into that space.

  23. Prolog for eight puzzle

    Prolog for eight puzzle Ask Question Asked 2 years, 7 months ago Modified 2 years, 7 months ago Viewed 4k times -1 %999 represent Blank tile. goal ( [999,0,1, 2,3,4, 5,6,7]). %To move left in any row ther are two cases: %Case_1: Blank tile in the second index.

  24. Amazon.com: Rubik's Cube, The Original 3x3 Color-Matching Puzzle

    1 offer from $8.98. Rubik's Blocks, Original 3x3 Cube with a Twist Challenging Problem-Solving Puzzle Retro Brain Teaser Fidget Toy, for Adults & Kids Ages 8 and up. 4 offers from $12.99. Rubik's Edge, 3x3x1 Rubik's Cube for Beginners Single Layer Puzzle Retro Educational Brain Teaser Travel Fidget Toy for Adults & Kids Ages 8+.