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 = { 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];
int b = y + intMoves[i];

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;
}``````

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.