N Puzzle

[Ovidiu]

Greetings. I must admit that although i searched the forum to see if there already is any subject similar to mine, i only find one that wasnt too relevant. I have a project to do for college. For this project i am supposed to create a N puzzle game + GUI. I havent reached the GUI part yet. A N puzzle is like an 8 puzzle or 15 puzzle just that i have to do it generally. A 8 puzzle is represented by a table or 2d array, however you want to see it, that it starts from an innitial state like

1, 2, 3
4, 5, 6
7, 8, 0(empty) , gets shuffled and you must reach the original state, witch is all numbers in ascending order starting from upper left. After some researches i found out that most of the time those things are done with A* algorithm. So i implemented something. Now my problem is the following. Somehow i get infinite loops like

1 2 0->1 0 2-> 1 2 0
x x x x x x x x x
x x x x x x x x x

This is happens not just on the first line, but randomly

void CAstar::checkNeighbourState(CPuzzle* goal, CPuzzle* previous,  CPuzzle* curr, vector<CPuzzle*> *open, vector<CPuzzle*> *closed)
{
	bool openFlag = false;
	bool better = false;
	


	curr->updateAll(); 
	
	for (int i = 0; i < closed->size(); i++)
	{
		if (curr == closed->at(i))
		{
			return;
		}
	}
         
        if(curr == previous)
              return
       
        int g = curr->g + 1;


	for (int i = 0; i < open->size(); i++)
	{
		if (curr == open->at(i))
		{
			openFlag = true;
			
		}
	}
	
	
        curr->g = g;	curr->h = manhattan(goal, curr);
	curr->f = curr->g + curr->h;

        if (curr->h < previous->h)
	{
		better = true;
	}
	

	else if (openFlag == false)
	{
		better = true;
	}

 

        else
		return;


	if (better == true)
	{
		if (openFlag == false)
		{	
			open->push_back(curr);
		}
        }
}

I know that i have somehow to keep some track of the parent, but im doing this already, and anyway im putting explored nodes in closed vector, always searching for smallest hieuristic, so i think they shouldnt be explored again. dunno how it happens or how to fix it. I would apreciate any hint or help . Thank you for your attention

[Ovidiu]

class CPuzzle{
    
    int* values;
    int zeroIndex;
    int upIndex;
    int downIndex;
    int leftIndex;
    int rightIndex;
    int h;
    int g;
    int f;


public:
    CPuzzle(){
        values = new int[N*N];
    }
    
    CPuzzle(int* _values, int _zeroIndex, int _upIndex, int _downIndex, int _leftIndex, int _rightIndex, int _g, int _h, int _f)
    {    
        values = new int[N*N];
        for (int i = 0; i < N*N; i++)
        {
            values[i] = _values[i];
        }


        zeroIndex = _zeroIndex;
        upIndex = _upIndex;
        downIndex = _downIndex;
        leftIndex = _leftIndex;
        rightIndex = _rightIndex;
        g = _g;
        h = _h;
        f = _f;
    }
    
    ~CPuzzle(){
    }    
    
    void operator=(const CPuzzle &x);
    bool operator==(const CPuzzle &x);
    
    void updateZero();
    bool updateUp();
    bool updateDown();
    bool updateLeft();
    bool updateRight();
    
    void updateAll();
    
    void moveUp();
    void moveDown();
    void moveRight();
    void moveLeft();    
    
    void printTable();
    void shuffleTable(int times);


    friend class CAstar;
};

class CPuzzle;


class CAstar{


public:


	int manhattan(CPuzzle* goal, CPuzzle* curr);
	void checkNeighbourState(CPuzzle* goal, CPuzzle* previous, CPuzzle* curr, vector<CPuzzle*> *open, vector<CPuzzle*> *closed);
	void solvePuzzle(CPuzzle* goal, CPuzzle* curr);


};

theese are my classes, i do the operations on array value

[Ovidiu]

I did some changes and now it doesnt get into loops any more. but it was getting stuck because it couldnt find a < hieuristic value so he could insert in open list. So i went for <=. and this is what happens

void CAstar::checkNeighbourState(CPuzzle* goal, CPuzzle *parent, CPuzzle* curr, vector<CPuzzle*> *open, vector<CPuzzle*> *closed)
{
	bool openFlag = false;
	bool better = false;


	curr->updateAll(); 
	
	for (int i = 0; i < closed->size(); i++)
	{
		if (curr == closed->at(i))
		{
			return;
		}
	}


	curr->g = parent->g + 1;


	for (int i = 0; i < open->size(); i++)
	{
		if (curr == open->at(i))
		{
			openFlag = true;
			
		}
	}
	
	curr->h = manhattan(goal, curr);
	/*
	if (openFlag == false)
	{
		better = true;
	}*/
	if (curr->h <= parent->h )
	{
		better = true;


	}
	else
	
		return;


	if (better == true)
	{
		if (openFlag == false)
		{	
			curr->f = curr->g + curr->h;
			open->push_back(curr);
		}


	}
}

[Ovidiu]

it does 3-4 moves and then that error occurs

[nonpuz]

I think we need to see the function that calls checkNeighborState. Also what exactly are you comparing when you compare two CPuzzle pointers, you sure that's what you want?

[Ovidiu]

I compare the elements from "array"

This is the overloaded operator

bool CPuzzle::operator==(const CPuzzle &x)
{
	bool ok = true;
	for (int i = 0; i < N*N; i++)
	{
		if (values[i] != x.values[i])
		{
			ok = false;
		}
	}
	return ok;
}

This is the function that calculates the manhattan. It calculates the distance of missplaced cells to their goal position.

int CAstar::manhattan(CPuzzle* goal, CPuzzle* curr)
{
	int s = 0;
	
	for (int i = 0; i < N*N; i++)
	{
		for (int j = 0; j < N*N; j++)
		{
			if (goal->values[i] == curr->values[j])
			{
				s =s + abs(i % N - j % N) + abs(i / N - j / N);
				break;
			}
		}
	}


	return s;
}

And this is where i call checkNeighbourState

void CAstar::solvePuzzle(CPuzzle* goal, CPuzzle* curr)
{
	vector<CPuzzle*> open;
	vector<CPuzzle*> closed;


	curr->g = 0;
	curr->h = manhattan(goal, curr);
	curr->f = curr->g + curr->h;


	open.push_back(curr);


	int minFindex = 0;
	while (!open.empty())
	{
		for (int i = 0; i < open.size(); i++)
		{
			if (open[i]->f < open[minFindex]->f)
			{
				minFindex = i;
			}


		}


		CPuzzle *tmp = open[minFindex];
		CPuzzle tmp1(tmp->values, tmp->zeroIndex, tmp->upIndex, tmp->downIndex, tmp->leftIndex, tmp->rightIndex, tmp->g, tmp->h, tmp->f);
		tmp = &tmp1;
		tmp->updateAll();
		
		int k = 1;
		
		system("cls");
		tmp->printTable();


		cout << endl << endl;
		
		if (goal->h == tmp->h)
		{
			cout << "\n\n\t\t    *:*: Puzzle solved! :*:*\n\n";
			return;
		}


		closed.push_back(tmp);
		open.erase(open.begin() + minFindex);


		if (tmp->updateUp() == true)
		{
			CPuzzle *aux = tmp;
			CPuzzle tmp1(aux->values, aux->zeroIndex, aux->upIndex, aux->downIndex, aux->leftIndex, aux->rightIndex, aux->g, aux->h, aux->f);
			aux = &tmp1;
			aux->moveUp();
			checkNeighbourState(goal, tmp, aux, &open, &closed);		
		}


		if (tmp->updateDown() == true)
		{
			CPuzzle *aux = tmp;
			CPuzzle tmp1(aux->values, aux->zeroIndex, aux->upIndex, aux->downIndex, aux->leftIndex, aux->rightIndex, aux->g, aux->h, aux->f);
			aux = &tmp1;
			aux->moveDown();
			checkNeighbourState(goal, tmp, aux, &open, &closed);
		}


		if (tmp->updateLeft() == true)
		{
			CPuzzle *aux = tmp;
			CPuzzle tmp1(aux->values, aux->zeroIndex, aux->upIndex, aux->downIndex, aux->leftIndex, aux->rightIndex, aux->g, aux->h, aux->f);
			aux = &tmp1;
			aux->moveLeft();
			checkNeighbourState(goal, tmp, aux, &open, &closed);
		}


		if (tmp->updateRight() == true)
		{
			CPuzzle *aux = tmp;
			CPuzzle tmp1(aux->values, aux->zeroIndex, aux->upIndex, aux->downIndex, aux->leftIndex, aux->rightIndex, aux->g, aux->h, aux->f);
			aux = &tmp1;
			aux->moveRight();
			checkNeighbourState(goal, tmp, aux, &open, &closed);
		}
	}
}

[Ovidiu]

elements from "values" array sorry.

[Ovidiu]

I tried to remove this

 if (curr->h <= parent->h )
    {
        better = true;


    }

and my code goes back to infinite loops. I think if i solve this problem its done.

[Ovidiu]

Ok i think i found out my problem. but i dont realy know how to fix it :S

in this part of code, all my closed elements become the same as the one pushed last.
lets say i push a now, i do a cycle then i come and push b. my a becomes b after i push b. i think im messing the memory adresses.

 while (!open.empty())
    {
        for (int i = 0; i < open.size(); i++)
        {
            if (open[i]->f < open[minFindex]->f)
            {
                minFindex = i;
            }


        }


        CPuzzle *tmp = open[minFindex];
        CPuzzle tmp1(tmp->values, tmp->zeroIndex, tmp->upIndex, tmp->downIndex, tmp->leftIndex, tmp->rightIndex, tmp->g, tmp->h, tmp->f);
        tmp = &tmp1;
        tmp->updateAll();

        int k = 1;

        system("cls");
        tmp->printTable();


        cout << endl << endl;

        if (goal->h == tmp->h)
        {
            cout << "\n\n\t\t    *:*: Puzzle solved! :*:*\n\n";
            return;
        }


        closed.push_back(tmp);

[Ovidiu]

i fixed this too, and now it seems something is wrong with my h and f values. they are not calculated as supposed.

[Ovidiu]

Fixed this too by updating open->at(i) if already in open list.

[Ovidiu]

now I get some error : Assertion failed that refers to one of my vectors.

[laserlight]

What is your current code, and what exactly is the assertion failure message?

[Ovidiu]

the message is " vector subscript out of range " . But i think i found the reason for this. my closed an open vectors arent filled corectly. working on this atm

here is my current code. i am not using " == " overloaded anymore. wasnt working corectly.

void CAstar::checkNeighbourState(CPuzzle* goal, CPuzzle *parent, CPuzzle* curr, vector<CPuzzle*> *open, vector<CPuzzle*> *closed)
{
	bool openFlag = false;
	bool better = false;
	int openIndex;
	
	curr->updateAll(); 
	
	for (int i = 0; i < closed->size(); i++)
	{
		int k = 0;
		
		for (int j = 0; j < N*N; j++)
		if (curr->values[j] == closed->at(i)->values[j])
		{
			k++;
		}


		if (k == N*N)
			return;
	}


	curr->g = parent->g + 1;


	for (int i = 0; i < open->size(); i++)
	{
		int k = 0;


		for (int j = 0; j < N*N; j++)
			if (curr->values[j] == open->at(i)->values[j])
			{
				k++;
			}


		if (k == N*N)
		{
			openFlag = true;
			openIndex = i;
		}
	}
	
	curr->h = manhattan(goal, curr);
	curr->f = curr->h + curr->g;




	if (openFlag == false)
	{	
		open->push_back(curr);
	}
	else
	{
		open->at(openIndex)->h = manhattan(goal, curr);
		open->at(openIndex)->g = curr->g;
		open->at(openIndex)->f = open->at(openIndex)->h + open->at(openIndex)->g;
	}


	
}

[Ovidiu]

and also modified a little the function that calls checkNeighbourState

void CAstar::solvePuzzle(CPuzzle* goal, CPuzzle* curr)
{
	vector<CPuzzle*> open;
	vector<CPuzzle*> closed;
	
	
	curr->g = 0;
	curr->h = manhattan(goal, curr);
	curr->f = curr->g + curr->h;


	open.push_back(curr);


	int minFindex = 0;
	while (!open.empty())
	{
		for (int i = 0; i < open.size(); i++)
		{
			if (open[i]->f < open[minFindex]->f)
			{
				minFindex = i;
			}


		}
	
		CPuzzle* tmp = open[minFindex];


		tmp->updateAll();
		
		system("cls");
		tmp->printTable();


		cout << endl << endl;
		
		if (goal->h == tmp->h)
		{
			cout << "\n\n\t\t    *:*: Puzzle solved! :*:*\n\n";
			return;
		}


		closed.push_back(tmp);
		open.erase(open.begin() + minFindex);


		if (tmp->updateUp() == true)
		{
			CPuzzle *aux = tmp;
			CPuzzle tmp1(aux->values, aux->zeroIndex, aux->upIndex, aux->downIndex, aux->leftIndex, aux->rightIndex, aux->g, aux->h, aux->f);
			aux = &tmp1;
			aux->moveUp();
			checkNeighbourState(goal, tmp, aux, &open, &closed);		
		}


		if (tmp->updateDown() == true)
		{
			CPuzzle *aux = tmp;
			CPuzzle tmp1(aux->values, aux->zeroIndex, aux->upIndex, aux->downIndex, aux->leftIndex, aux->rightIndex, aux->g, aux->h, aux->f);
			aux = &tmp1;
			aux->moveDown();
			checkNeighbourState(goal, tmp, aux, &open, &closed);
		}


		if (tmp->updateLeft() == true)
		{
			CPuzzle *aux = tmp;
			CPuzzle tmp1(aux->values, aux->zeroIndex, aux->upIndex, aux->downIndex, aux->leftIndex, aux->rightIndex, aux->g, aux->h, aux->f);
			aux = &tmp1;
			aux->moveLeft();
			checkNeighbourState(goal, tmp, aux, &open, &closed);
		}


		if (tmp->updateRight() == true)
		{
			CPuzzle *aux = tmp;
			CPuzzle tmp1(aux->values, aux->zeroIndex, aux->upIndex, aux->downIndex, aux->leftIndex, aux->rightIndex, aux->g, aux->h, aux->f);
			aux = &tmp1;
			aux->moveRight();
			checkNeighbourState(goal, tmp, aux, &open, &closed);
		}
	}
}