8 Puzzle Breadth First Algorithm Help

[tokenjoker187]

Please help me. I am having trouble implementing the breadth first search algorithm for the classic 8 puzzle problem. I have some code if anybody can help. Or is there any tutorials or examples that you can link to me?

My problem is that it only solves about 5 different inputs and thats it. Sometimes it runs out of memory, and the others are no solution. Is my algorithm wrong? Or is the algorithm so incomplete that it only solves a select few?

Anyways heres what I have:

statespace.h

#ifndef STATESPACE_H
#define STATESPACE_H
#include <string>
#include <set>
#include <queue>
#include <vector>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;


class StateSpace
{
    public:
// Constant Data

        // Public Data Types
        char chIndex;           // Location of empty or '0' spot
        char chMove;            // Character of intended move
        string matrix;          // The actual state of the current matrix
        StateSpace *parentNode;      // Pointer to parent node
        int expandedNodes;      // Count of all expanded nodes

        // Constructors
        StateSpace( );
        StateSpace( string );
        StateSpace( StateSpace * );

        /* Overloaded Operators */
        // Compare two state spaces
        bool operator==( const StateSpace &x)
        {
            if( this->matrix == x.matrix )
                return true;
            else
                return false;
        }

        // Print the current state of state space
        ostream &operator<<( ostream &output )
        {
            output << "-------\n";

            for( int i = 0; i < 3; i++ )
            {
                output << "|";

                for( int j = 0; j < 3; j++ )
                {
                    output << this->matrix[i * 3 + j];
                }

                output << "|";
            }

            output << "-------\n";
            return output;
        }

        int solvePuzzle( string array )
        {
            const StateSpace doneMoving( "123456780" ); //The Goal State
            const int intMoves[4][2] = { 0, 1,
                                         1, 0,
                                         0, -1,
                                         -1, 0};
            const string strMoves = "URLD";
            bool solutionFound = false;
            queue<StateSpace *> fringe;  // The fringe of StateSpace pointers in a queue
            set<string> visited;         // Set of visited matrices in form of string
            StateSpace *root = new StateSpace( array ); // Start at the beggining of tree
            root->parentNode = NULL;

            fringe.push( root );

            while( !fringe.empty() )
            {
                StateSpace *state = fringe.front(); // Returns top of fringe
                fringe.pop();


                if( *state == doneMoving ) // Test the goal state first
                {
                    solutionFound = true;
                    cout << "Solution found \n";
                    cout << "Expanded nodes: " << root->expandedNodes << endl;
                }


                visited.insert( state->matrix );    // Insert current matrix into matrices visited

                // Expand All Children

                for( int i = 0; i < 4; i++ )
                {
                    int x = state->chIndex / 3;
                    int y = state->chIndex % 3;

                    int a = x + intMoves[i][0];
                    int b = y + intMoves[i][1];

                    if( a >= 0 && a < 3 && b >= 0 && b < 3 )
                    {
                        StateSpace *child = new StateSpace( root );
                        child->chIndex = a * 3 + b;
                        child->chMove = strMoves[i];
                        swap( child->matrix[x*3+y], child->matrix[a*3+b] );
                        fringe.push( child );
                        root->expandedNodes += 1;

                    }
                }
            }
            if(!solutionFound)
                cout<<"No Solution could be found\n";

        }

};
#endif

statespace.cpp

#include <string>
using namespace std;
#include "statespace.h"

StateSpace::StateSpace()
{
    matrix = " ";
    expandedNodes = 0;
}

StateSpace::StateSpace(string puzzle)
{
    matrix = puzzle;
    expandedNodes = 0;
    for (int i = 0; i < matrix.size(); i++ )
    {
        if( matrix[i] == '0')   // Save the index number to chIndex
            chIndex = i;
    }
}
StateSpace::StateSpace(StateSpace *state)
{
    parentNode = state;
    matrix = state->matrix;
}

[alwaysLearning0]

Hi,

First thing is error:

StateSpace *state = fringe.front(); // Returns top of fringe
                fringe.pop(); // and now you are deleting it!!! pop also calls the destructor. so if you are accessing state after this, thats invalid memory access..

if( a >= 0 && a < 3 && b >= 0 && b < 3 ) // you are not checking if this state is arelady visisted

Now i would like to comment about the coding, here coding style is more like c, then c++

I would suggest to implement a local class or structure to keep the state in the class it self.

class BFS{
     struct state{
           //state holder
     }
     
     doTheBFS(){
           
     }  
}

anyway concentrate on the problem first, then you can go for crazy oop :D