0

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