#breadth-first

In this tutorial, we will solve the 8 puzzle problem using A* (star) search or pathfinding algorithm. Besides, the primary algorithm (A*), we will also use breadth-first, depth-first and greedy best-first search algorithms to find a solution for the 8 puzzle problem. We will approach the solution by first modelling the problem, then by building the fundamental blocks and finally applying a solver to solve the puzzle. Read Also: How to Generate Mazes Using Depth-First Algorithm This tutorial will provide the solution both from the algorithmic perspective as well as by providing the implementation of the algorithms using C++ for a console program and C# for Unity scripting. Finally, we will implement an 8 puzzle game using Unity and solve a random state of the puzzle by applying the A* algorithm. Click to Play the Unity Game

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 in his Stanford’s site. In this tutorial I am not going to 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 popularized 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 with the blank sometimes at the start or at the end. The diagram above shows one possible initial configuration and the goal. To reach the goal state you are permitted to slide blocks horizontally or vertically into the blank square.

Before we can solve the puzzle 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 problems. 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 optimizing 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 sort of modelling techniques to reduce the problem in terms of rigorously defined abstract structures such as graphs, trees, permutations, sets and so on. For our 8 puzzle problem let’s see how we can model the problem. Let’s take a random state of the 8 puzzle as given in the diagram below. From this random state, we can either slide tile 8 up, slide tile 3 right or slide tile 6 left to create three variant states.

Each of these three states will produce subsequent more states (3 for the first, 1 for the second and 1 for the third) and so on. This continues until we find the goal state. Hence, we can see that we can transform the various possible states of the 8 puzzle problem into a tree data structure.

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

The 8 Puzzle State

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 the 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 integer array to represent a state. The indices of the array 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.

Thus, we see that by using a one-dimensional array we can represent any state of the puzzle. 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 of these indices 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 so on until index 8 with tile 2. Points to Ponder Can we implement the state using a 2-dimensional array?How will you represent the tile indices using a 2-dimensional array?Can you try out a few examples using a 2-dimensional array? We can thus see that by manipulating the values on the array, with the constraint of where the empty tile slides into for each move, we can arrive at the goal state.

Goal State

Goal state index array Design of State class Implement a class called State that will represent a unique combination of tiles. While implementing the class think about the range of functionality and behaviour that this class should expose. Give it a try before you look at the code.Implement a constructor or multiple constructors.Implement a copy constructor (if using C++)Implement a function that will return the index of the empty tile.Implement a function that will randomize the tiles to create a unique configuration of the puzzle.Any other functions that you can think of? Implementing State Class in C++ The class State comprises two variables (a) the integer array that defines the index array to represent the state and (b) the number of rows or cols. For 8 puzzle problem, this value is 3. Constructors The constructors for the C++ class is given below. We have implemented three constructors, viz., the (a) explicit default constructor that takes in the num_rows_or_cols, (b) the constructor that takes in the num_rows_or_cols and an initial state of the array and (c) a copy constructor.

Operators The operator for the State class is given below. We have implemented the assignment, equal to and not equal to operators.

FindEmptyTileIndex This function returns the index of the empty tile for any given state of an 8 puzzle.

SwapWithEmpty This is the function that will be used whenever we slide the empty tile. By sliding the empty tile to an adjacent position we are essentially swapping the values of the index of the empty tile with the value of the adjacent tile.

Other Helper Methods The other helper methods include the Randomize function that randomizes the state of the puzzle.

The Get and Set methods for getting and setting the index array of the state.

The print method for printing the state to an output stream. This is useful for debugging and/or showing output for the state.

C++ Code for State Class The following section provides the source codes for the class State. You can copy and paste from this section. #include #include #include #include #include //! A typedef of a normal integer array using std::vector for convenience typedef std::vector IntArray; ///class State ///A class to hold the state of the puzzle. ///The state is represented by a simple one dimensional array of integers. ///The value of o represents empty slot. class State { private: IntArray _state; unsigned int _rows_or_cols; public: /// explicit State(unsigned int rows_or_cols) : _rows_or_cols(rows_or_cols) { _state.resize(_rows_or_cols*_rows_or_cols); for (unsigned int i = 0; i { _state = i; } } State(unsigned int rows_or_cols, const IntArray& arr) : _rows_or_cols(rows_or_cols) { assert(arr.size() == _rows_or_cols * _rows_or_cols); _state = arr; } ///copy constructor State(const State& other) { _rows_or_cols = other._rows_or_cols; _state = other._state; } ///assignment operator State& operator = (const State& other) { if (this != &other) { _rows_or_cols = other._rows_or_cols; _state = other._state; } return *this; } ///equal to operator. This will check item by item. friend bool operator == (const State& a, const State& b) { return (a._state == b._state); } ///not equal to operator. This will check item by item. friend bool operator != (const State& a, const State& b) { return (a._state != b._state); } /// find the index of the empty slot inline int FindEmptyTileIndex() const { for (int i = 0; i if (_state == 0) return i; return (int)_state.size(); } /// Randomize teh state. ///NOTE: Not all Randomized states are solvable. ///Need to implement a method to find whether a state is solvable or not. inline void Randomize() { std::random_shuffle(_state.begin(), _state.end()); } ///swap the values of the indices inline void SwapWithEmpty(int i0, int i1) { int tmp = _state; _state = _state; _state = tmp; } inline const IntArray& GetArray() const { return _state; } void SetArray(const IntArray& arr) { _state = arr;; } inline unsigned int GetNumRowsOrCols() const { return _rows_or_cols; } void print(std::ostream& str, bool flat = false) const { for (unsigned int i = 0; i { for (unsigned int j = 0; j { unsigned int index = i * _rows_or_cols + j; if (flat) { str GetState() == _goal) { _solved = true; return; } int zero = current->GetState().FindEmptyTileIndex(); const IntArray& neighbours = graph.GetNeighbours(zero); for (int next : neighbours) { State state = current->GetState(); state.SwapWithEmpty(zero, next); if (!isInArray(state, _closedlist)) { NodePtr n(new Node(state, current, current->GetDepth() + 1)); _openlist.push_back(n); static int s_lineNum = 1; n->print(std::cout, s_lineNum++); //_closedlist.push_back(n); } } } private: typedef std::vector NodeList; NodeList _openlist; NodeList _closedlist; const State& _goal; bool _solved; Type _type; }; C# Code for Solver // The A Star search alogorithm implementation for solving 8 puzzle problem. // This is implemented as a coroutine for Unity. public IEnumerator SearchUsingAStar(State start, State goal) { PriorityQueue openlist = new PriorityQueue(); List closedlist = new List(); Node root = new Node(start, 0, null); root.Parent = null; openlist.Add(root); closedlist.Add(root); while (openlist.Count > 0 && !_solved) { Node current = openlist.GetAndRemoveTop(); if (State.Equals(current.State, goal)) { // fil the solution. Node s = current; do { _solution.Add(s); s = s.Parent; } while (s != null); Debug.Log("Solution found.." + "Total moves needed = " + _solution.Count); _solved = true; _solving = false; _solutionIndex = _solution.Count; break; } int zero = current.State.FindEmptyTileIndex(); int neighbours = Neighbours.Instance.GetNeighbors(zero); foreach (int next in neighbours) { State state = new State(current.State); //state.SwapWithEmpty(next); SwapTiles(next, state, false); if (!IsStateInList(state, closedlist)) { Node n = new Node(state, current.Depth + 1); n.Parent = current; openlist.Add(n); closedlist.Add(n); //n.Print(++s_lineNum); } } yield return new WaitForEndOfFrame(); } _layout.SetState(_solution.State); }

The main() Driver Program

Advanced Algorithms in Java

Course: Advanced Algorithms in Java. Breadth-first search, depth-first search, shortest path, arbitrage, strongly connected components and graph algorithms[su_accordion][su_spoiler title=”Advanced Algorithms in Java” style=”fancy” open=”yes”][su_table]

Lectures: 77

Length: 9.5 hours

Skill Level: All Levels

Languages: English, captions

Includes: Lifetime access 30 day money back guarantee! Avai…

Week one of Fullstack complete! I am happy to report that so far, so good. I’m sure that it would have been totally possible to learn these concepts on my own, but I’m feeling pretty confident that personally I’m learning things much, much more quickly with a group.

While the first week definitely had a lot of review, and a fair share of obligatory non-program related topics (games, norms, orientation, that sort of thing), I’ve also been introduced to several new topics this week that I’m totally obsessed with right now, that I felt obligated to mention here, if only in a sort of cursory way.

My favorite a-ha this week was probably learning about breadth-first vs depth-first searching. Near the end of this week we tried to recreate (some of) the functionality of the $() selector function in jQuery. In doing so we created what I later learned was a recursive depth-first search function. While for most programmers I’m sure the phrase “recursive depth-first search function” does not seem all that surprising or interesting but as I reflect back I realize that it’s the kind of thing that would have felt super overwhelming to me last month (or even maybe last week). So let’s break it down.

First some (maybe overly obvious) context: websites have what is called the DOM. Which stands for the Document Object Model. The DOM is simply an organizational structure for what to go where on the page. For example how might you tell a computer to put all of your navigation buttons inside a navigation bar? I guess you could just stack each other, but wouldn’t it be nice to instead have the navigation bar own or be the “parent” of each individual button? You can! (and do!). This organizational structure is known as the DOM, and is basically a hierarchal tree. jQuery, a javascript library, allows you to add some nice functionality to your website (think drop-down menus, filters, and other fun things). And jQuery does this by traversing the DOM. Basically it goes through this hierarchal tree and gathers the right elements (maybe only the photos for example) and allows you to do cool stuff with it. We do this in our javascript file by writing something sort of like this:

 $(“stuffYouWantToSelectForGoesInHere”).on(when you click on the selected thing){

            exactly what cool stuff will happen to the selected stuff

}

Ok, ok. So that’s pretty nice. But how exactly does it do this…traversing stuff? How do we walk the DOM and determine “is this the right element?...nah…the next one”? What order do you look for things? Does the order even matter?

In comes our recursive depth-first search. When recreating our $()selector, we made a function that basically does the following:

creates an array which will eventually store all the matching elements

decides that if we haven’t given it an area to search, it takes in the Body of the DOM (the main part of the DOM that we are interested in)

determines if that particular section has any children

if it does, it waits to run this exact same function on those children, and then concatenates whatever is returned from those functions in our array.

then returns the newly filled array of matched items.

Recursion is a cool concept that feels very magical. Which may seem like reason alone to use this type of function. But just because it’s magical doesn’t mean it’s the only way or the best way to solve this problem. This type of search is known as depth-first, which means that it goes down/deep into the DOM tree, then back up and to the right. For example let’s say you’re looking through your family tree to find all the family members that have red hair. With a depth first search you would first search through the eldest great grandmother’s children, grand children, and great grandchildren before going to the great grandmother’s younger brother.  This I find hard to describe in words and easier to describe in pictures.

This differs from say a breadth-first search, which says let’s look at all the great grandparents first, then the grandparents, then the parents, then the children, then the great grandchildren, etc.

But why does it matter? Well in our particular case of recreating the jQuery selector it probably doesn’t really matter that much, what order you find things in. But what if you were searching for something in all of the interwebs? Would you want to return all matches from one particular website’s children’s children’s children? Or would you want to just return the homepages for the most popular websites? Do you want to return your emails that ever mention the word Sarah? Or do you want to first return all emails that are from Sarah first, then have Sarah in the subject, and then have Sarah in the text? These are probably more analogies/metaphor than actual implementations of breadth first searches, but still I think it helps to put in context why we’re learning what we’re learning. Essentially if you need to return all of the matches then depth-first searches are fine, but if you’ve got a huge number of potential matches and would like to return the top results first and continue searching in the background then a breadth-first search might be a better fit.