8-Puzzle Solver unknown problem

[BaseRev]

Hi all ,

I am working on a 8-Puzzle Solver -using best-first search + Hamming distance(tiles out of place) heuristic- which was required from us as a project.

I first defined a Stat Struct in a separated cpp file which looks like this in the header file :

#ifndef STAT_H_INCLUDED
#define STAT_H_INCLUDED
#include <iostream>

struct Stat
{
    int Board[3][3];
    int depth;
    int Empty[2];
    int Evaluation;
    int operator- (Stat) const; //Overloading operator- to return "Hamming distance"
    void operator= (Stat);
    bool operator== (Stat) const;
    bool operator< (Stat) const;
};

//Used as a compare class for the set container

class Comparor  //Class to Compare between Stats(Default Bigger)
{
    bool Bigger;

public:
    Comparor(const bool& Smaller=1)
    {
        Bigger=Smaller?0:1;
    }
    bool operator() (const Stat& lhs, const Stat& rhs) const
    {
        if (Bigger) return (lhs<rhs?0:1);
        else return (lhs<rhs);
    }
};
std::istream& operator>> (std::istream&,Stat&); //To input the 9-cells as one 
std::ostream& operator<< (std::ostream&,Stat&); //To output the 9-cells as one
#endif // STAT_H_INCLUDED 

Next is the main.cpp file :

#include <vector>
#include <set>
#include <algorithm>
#include <fstream>
#include "Stat.h"

using namespace std;

//Global Variables
Stat Start,Goal,temp;
int Steps=0;
set<Stat,Comparor> Open; //Used so that the Stats will be arranged -by heuristic value- and unique
vector<Stat> Closed;

//Forward Declaration
int Solver();
inline int Generate_Move(char);

int main()
{
    ifstream cin("input.txt");

    cin>>Start>>Goal;
    Start.depth=0;
    Start.Evaluation=Start-Goal;
    Open.insert(Start);
    Solver();
    cout<<temp<<endl;
    cout<<endl<<"Setps to reach the goal = "<<Steps<<endl;
    return 0;
}

int Solver()
{
  set<Stat,Comparor>::iterator it=Open.begin();
  temp=*it;
  if(temp==Goal)
    return Steps;
  cout<<temp<<endl;
  Closed.push_back(temp);
  Open.erase(it);

  Start=temp;
  if(temp.Empty[0]<2) //Up Direction
    Generate_Move('U');
  if(temp.Empty[0]>0) //Down Direction
    Generate_Move('D');
  if(temp.Empty[1]<2) //Right Direction
    Generate_Move('R');
  if(temp.Empty[1]>0) //Left Direction
    Generate_Move('L');

  Steps++;
  Solver();
}

inline int Generate_Move(char Direction)
{
  int Index,Inverse,Row,Coloum;
  int E0=temp.Empty[0],E1=temp.Empty[1];

  if(Direction == 'U'){Index=1;Inverse=0;}
  else if(Direction == 'D'){Index=-1;Inverse=0;}
  else if(Direction == 'R'){Index=0;Inverse=1;}
  else if(Direction == 'L'){Index=0;Inverse=-1;}

  Row=E0+Index;
  Coloum=E1+Inverse;

  swap(temp.Board[E0][E1],temp.Board[Row][Coloum]); //Swapping the empty cell with an adjacent cell
  if(find(Closed.begin(),Closed.end(),temp)!=Closed.end())
  {
      temp=Start;
      return 0;
  }
  //Changing the place of empty cell to the new place
  temp.Empty[0]=Row;
  temp.Empty[1]=Coloum;

  temp.depth++; //Increasing the depth of the stat

  //Setting the heuristic value of the stat
  temp.Evaluation=Goal-temp;
  temp.Evaluation+=temp.depth;

  Open.insert(temp);
  temp=Start;
  return 0;
}

Now when I run the program with a sample Input like this :
2 8 3
1 6 4
7 0 5

1 2 3
8 0 4
7 6 5

It Solves the Puzzle and everything is good.But with every other input I tried
the Open set became empty before reaching the goal despite the fact that there is a solution for those puzzles.

Can anyone please guide me to the part of my program responsible of that.
Thanks in advance.

[cire]

ifstream cin("input.txt");... really?

Solver is supposed to return a value. Sometimes it doesn't, leading to undefined behavior.

You're missing the definition of several member functions for Stat.

[BaseRev]

Thanks for replying.

Is there something wrong with :

ifstream cin("input.txt");

I am just used to it because I usually have a lot of input lines and while testing the program I use files so I can just copy & paste the inputs but after finishing I just comment/ remove the line of ifstream & header which saves me a lot of trouble.

Solver is supposed to return a value. Sometimes it doesn't, leading to undefined behavior.

Solver doesn't return anything in case of the puzzle doesn't have a solution (and I wrote it like this for now just to see if it discovers the goal in solvable puzzles) so in all the cases I tested it against it should return a value which mean that this isn't the problem I think.

You're missing the definition of several member functions for Stat.

Iam not missing them I just posted here the header file without the cpp file because the post was already huge and I think their implementations is irrelevant here but here is the Stat.cpp:

#include "Stat.h"

using namespace std;

int Stat::operator- (Stat x) const
{
    int counter=0;
    for(int a=0;a<3;a++)
    {
       for(int b=0;b<3;b++)
       {
         if(Board[a][b]!=x.Board[a][b] && Board[a][b]!=0) //Empty Space doesn't count as a tile 
            counter++;
       }
    }
    return counter;
}

void Stat:: operator= (Stat x)
{
    for(int a=0;a<3;a++)
    {
       for(int b=0;b<3;b++)
       {
           Board[a][b]=x.Board[a][b];
       }
    }
    depth=x.depth;
    Empty[0]=x.Empty[0];
    Empty[1]=x.Empty[1];
    Evaluation=x.Evaluation;
}

bool Stat::operator== (Stat x) const
{
    if((*this)-x==0)
        return 1;
    else
        return 0;
}

bool Stat::operator< (Stat x) const
{
    return (Evaluation<x.Evaluation);
}

istream& operator>> (istream& in,Stat& x) 
{
    for(int a=0;a<3;a++)
    {
       for(int b=0;b<3;b++)
       {
         in>>x.Board[a][b];
         if(x.Board[a][b]==0)
         {x.Empty[0]=a; x.Empty[1]=b;}
       }
    }
    return in;
}

ostream& operator<< (ostream& out,Stat& x)
{
    out<<"Stat depth = "<<x.depth<<endl;
    out<<"Stat Evaluation = "<<x.Evaluation<<endl;
    for(int a=0;a<3;a++)
    {
       for(int b=0;b<3;b++)
       {
         out<<x.Board[a][b]<<" ";
       }
       out<<endl;
    }
    return out;
}

[BaseRev]

I tried to see the Stats that entered the open set and which didn't so I used the Input below as a sample and that what I got :

Stats entered open :

2 8 3    2 8 3    2 0 3    0 2 3    1 2 3     1 2 3
1 6 4    1 0 4    1 8 4    1 8 4    0 8 4     8 0 4
7 0 5    7 6 5    7 6 5    7 6 5    7 6 5     7 6 5

Which are the steps needed to solve the puzzle.

Stats that was not found in Closed and didn't enter Open:

2 8 3    2 8 3     2 8 3    1 2 3
1 6 4    1 4 0     0 1 4    7 8 4
0 7 5    7 6 5     7 6 5    0 6 5

So , the Open set says that the above stats exists in Open and refuse to input them but there is no such stats in Open and the heuristic values of those states are different On Open(4,4,5,5,5,5) the others(6,6,5,7).

Can someone please tell me why Open refuse to enter those stats as if they already exist.
Thanks.

[BaseRev]

finally I found out what was wrong with the above code it is the set container it doesn't work as I expected.
it determines if an element already exists by searching the keys not the values. So I change it to a Container I implemented inheriting from priority_queue class so I can use the underlying c vector for search and it now works for all the cases except the worst case which produce a run-time error and I don't know why .

[cire]

Solver doesn't return anything in case of the puzzle doesn't have a solution (and I wrote it like this for now just to see if it discovers the goal in solvable puzzles) so in all the cases I tested it against it should return a value which mean that this isn't the problem I think.

Solver promises to return something. Solver doesn't always return something. This results in undefined behavior. In all cases you tested against (the one test case you supplied in the original post) Solver does not always return something.

This results in undefined behavior.

What is Solver supposed to return?

Do you think "Probably the problem you pointed out isn't the problem I'm probably looking for" is a reasonable approach to debugging?

Have you written out the algorithm you're using to solve these problems? It would appear you're trying to generate all possible board states until you generate the one equivalent to your goal.

Of what practical use is the "hamming distance?" It looks like you generate it solely to output it.

Why are you using so many global variables?

[BaseRev]

@cire

In all cases you tested against (the one test case you supplied in the original post) Solver does not always return something

How is that ? wouldn't it keep calling itself until it find the goal then return the steps?

What is Solver supposed to return?

it is supposed to return the Steps which I don't actually need it to return (as steps in the global space) but I prefer it rather than:

void function(){return;}

Do you think "Probably the problem you pointed out isn't the problem I'm probably looking for" is a reasonable approach to debugging?

Well,no but I meant that the most important task now is to find the major problem and fix it then fix this problem because there is no need to fix this problem if I can't get the algorithm to run correctly.

Have you written out the algorithm you're using to solve these problems? It would appear you're trying to generate all possible board states until you generate the one equivalent to your goal.

Yes.I use best-first-search to expand the search space in the most promising branch while keeping the other stats on open to recover from failure (local min,dead end ,etc) but in the worst case the search will turn to breadth-first-search.

Of what practical use is the "hamming distance?" It looks like you generate it solely to output it.

It is the heuristic function here.
It gives each stat a value upon which the expanding direction is determined.

Why are you using so many global variables?

I access them from different functions and I rather use global variables than passing them as arguments.

[BaseRev]

I added this header file to the project and replaced the set in the main.cpp file with Container and now It works for all cases except the worst case which produces a segmentation fault which I can't detect where it happens:

#ifndef CONTAINER_H_INCLUDED
#define CONTAINER_H_INCLUDED
#include <vector>
#include <queue>
#include "Stat.h"

template <class T>
class Container : public std::priority_queue<T,std::vector<T>,Comparor>
{
public:
    std::priority_queue<T,std::vector<T>,Comparor> q;

    Container(){}
    ~Container(){};

    void insert(T x)
    {
      if(!Contains(x))
        q.push(x);
    }
    bool Contains(T x)
    {
      for(unsigned a=0;a<(this->c).size();a++)
      {
          if(this->c[a]==x)
            return 1;
      }
      return 0;
    }
    T begin()
    {
        return q.top();
    }
    void erase()
    {
        q.pop();
    }
};


#endif // CONTAINER_H_INCLUDED

and here is the test cases the program ran against :

Goal Stat

1 2 3
8 0 4
7 6 5

Start Stat

1 3 4     2 8 1    2 8 1   5 6 7
8 6 2     0 4 3    4 6 3   4 0 8
7 0 5     7 6 5    0 7 5   3 2 1

ُEasy  Medium   Hard   Worst

Steps & Goal depth for each input :

5 5    29 9   92  12   Run time error

[cire]

How is that ? wouldn't it keep calling itself until it find the goal then return the steps?

Every time it calls itself it does what? Does it return? Without returning the value it promises to return, resulting in undefined behavior? While it's on my mind, why does Generate_Move return a value if the value is always the same value and is never checked?

it is supposed to return the Steps which I don't actually need it to return it(as steps in the global space) but I prefer it rather than:

What does preference have to do with it? This isn't a matter of style. Your function is wrong. Fix it.

Re: "hamming distance"

It is the heuristic function here.
It gives each stat a value upon which the expanding direction is determined.

Ahh, I see. You're relying on the set ordering.

bool Stat::operator== (Stat x) const
{
    if((*this)-x==0)
        return 1;
    else
        return 0;
}

This is most certainly wrong (and probably explains your troubles with std::set.)

bool Stat::operator== (Stat x) const
{
    for ( unsigned i=0; i<3; ++i )
        for ( unsigned j=0; j<3; ++j )
            if ( Board[i][j] != x.Board[i][j] )
                return false ;

    return true ;
}

seems more appropriate.

[BaseRev]

@cire

Every time it calls itself it does what? Does it return? Without returning the value it promises to return, resulting in undefined behavior? While it's on my mind, why does Generate_Move return a value if the value is always the same value and is never checked?

I changed both functions to void , used return; and added
this line in Solver:

if(Open.q.empty())
    return;

Note:Open now is a Container Data type not a set and q is the priority queue inside it.

What does preference have to do with it? This isn't a matter of style. Your function is wrong. Fix it.

Done.

This is most certainly wrong (and probably explains your troubles with std::set.)

Yes,I noticed it while I was writing the Container Class beside the fact that it takes more time , this line messed everything up :

 if(temp==Goal)

So I changed it as you mentioned.

But still the program ends with a segmentation fault in the case of worst case or the puzzle can't be solved.

Sorry if I asks too much and thanks for helping.

[BaseRev]

Finally, the program is running and solving all the solvable puzzles .

the problem with the segmentation fault was the stack overflow.

I don't know how didn't I notice earlier as it was working for the easy to hard puzzles just fine so it couldn't have been an access out of boundaries.

The final step now is to optimize the code as it takes more than 5 minutes !!! to solve the worst cases.

Thanks again for the help .

[cire]

Finally, the program is running and solving all the solvable puzzles .

Glad to hear it.