" free(): invalid pointer:" 8-puzzle BFS

Question

I am trying to write a breadth first search program to solve the 8-puzzle. When I run the following code I get the following error:

* Error in `/home/a.out': free(): invalid pointer: 0x0000000001f81430 *
Aborted

I am pretty sure the issue is with the usage of the this pointer and how i store the parent nodes. Any help?

 #include <iostream>
 #include <string>
 #include <iostream>     
 #include <algorithm>    
 #include <vector>       
 #include <queue>
 using namespace std;
 class Node {
 public:

vector<Node> children;
vector<int> puzzle;
vector<int> goal = {1, 2, 3, 4, 5, 6, 7, 8, 0};
Node *parent;

Node(vector<int> _puzzle, Node *_parent){   // constructor for node
    puzzle=_puzzle;
    parent=_parent;
}

void moveUp(){    //function to move up
    int zPos = findZero();
    vector<int> temp = puzzle;
    if ( zPos != 0 || zPos != 1 || zPos != 2 )
    std::swap(temp[zPos], temp[zPos-3]);
    Node child = Node(temp, this);
    children.push_back(child);      
}

void moveDown(){    //function to move down
    int zPos = findZero();
    vector<int> temp = puzzle;
    if ( zPos != 6 || zPos != 7 || zPos != 8 )
    std::swap(temp[zPos], temp[zPos+3]);
    Node child = Node(temp, this);
    children.push_back(child); 
}

void moveRight(){    //function to move right
    int zPos = findZero();
    vector<int> temp = puzzle;
    if ( zPos != 2 || zPos != 5 || zPos != 8 )
    std::swap(temp[zPos], temp[zPos+1]);
    Node child = Node(temp, this);
    children.push_back(child);
}


void moveLeft(){     //function to move left
    int zPos = findZero();
    vector<int> temp = puzzle;
    if ( zPos != 0 || zPos != 3 || zPos != 6 )
    std::swap(temp[zPos], temp[zPos-1]);
    Node child = Node(temp, this);
    children.push_back(child); 
}

void printPuzzle() {    //function to print the puzzle
    int count = 0;
    for (auto i: puzzle) {
    if ( count % 3 == 0)
    std::cout << std::endl;
    std::cout << i << ' ';
    count++;   
}
}

int findZero(){    // function to find the location of zero
    std::vector<int>::iterator it;
    it = find (puzzle.begin(), puzzle.end(), 0);
    auto z = std::distance(puzzle.begin(), it);
    return (int)z;
}

bool isGoal(){  //function to check if goal state is reached
    bool goalFound = false;
    if(puzzle == goal)
    goalFound = true;
    return goalFound;
}

};


bool contains(std::queue<Node> q, Node n){   // checks repeated nodes
    std::queue<Node> tempQ = q;
    bool exist = false;
    while (!tempQ.empty()){
        if (tempQ.front().puzzle == n.puzzle)
        exist = true;
        tempQ.pop();
    }
    return exist;
}

int main()
{
std::vector<int> initial = {3, 5, 8, 1, 0, 4, 2, 7, 6};
Node init = Node(initial, NULL);
std::queue<Node> openList;
std::queue<Node> closedList;
openList.push(init);
bool goalFound = false;
while(!openList.empty() && !goalFound){
    Node currentNode = openList.front();
    closedList.push(currentNode);
    openList.pop();       
    currentNode.moveUp();
    currentNode.moveDown();
    currentNode.moveRight();
    currentNode.moveLeft();

    for (auto i: currentNode.children){
        Node currentChild = i;
        if (currentChild.isGoal()){
            std::cout << "Goal Found." << endl;
            goalFound = true;           
        }
        if (!contains(openList, currentChild) && !contains(closedList, currentChild))
            openList.push(currentChild); 
    }      
}
}

Right now I am only focusing on finding the goal. I am yet to implement the path to the goal and print the final solution.

You copy nodes all over the place, but you don't have a well-behaved copy constructor or assignment operator. Most of your `parent` pointers are invalid (they point to an old `currentNode` that has already been destroyed). — melpomene, Feb 19 '18 at 04:32
I just commented out all the lines concerning the parent pointers. I still get the same error. Maybe the problem is elsewhere. — pi47, Feb 19 '18 at 04:38
`parent` will get you later. `vector`s is an awesome and wonderful tool, but you have to be anally retentive when storing pointers to items in one. More reading on that: http://en.cppreference.com/w/cpp/container/vector#Iterator_invalidation and https://stackoverflow.com/questions/6438086/iterator-invalidation-rules — user4581301, Feb 19 '18 at 04:44
could you please explain in a little more detail where I am going wrong, if not too inconvenient. — pi47, Feb 19 '18 at 04:58
Read the links, but the general issue is vectors contain copies of what you put in. A copy has a different address from the original. As you move stuff inside a `vector` around, the item's address changes according to when in the `vector` it winds up. One swap and the `parent` pointers point to the wrong place. Plus as you add stuff to a `vector`, sooner or later it has to allocate more storage and copy what it currently contains into the new storage.the `parent` pointers point to the old storage, and the `vector` deletes that when it's done with it. Trying to access deleted memory is bad. — user4581301, Feb 19 '18 at 05:17

user4581301 · Answer 1 · 2018-02-19T04:44:57.870

0

if (zPos != 0 || zPos != 1 || zPos != 2)

Should be

if (zPos != 0 && zPos != 1 && zPos != 2)

And ditto for its brothers and sisters in the other move functions.

TL;DR explanation:

in moveUp

if (zPos != 0 || zPos != 1 || zPos != 2)

fails to do what you want. The body will always be executed because zPos cannot be 0, 1 and 2 all at the same time. Eg if zPos is zero then

if (0 != 0 || 0 != 1 || 0 != 2)
    false  || true

One true is sufficient.

This means that

std::swap(temp[0], temp[0-3]);

will swap 0, -3 and go out of bounds. All sorts of weird can happen when you mess with memory outside the bounds, and I think this time you're overwriting some of the book-keeping for the vector's storage buffer. As soon as the vector is freed, kaBlamo!

edited Feb 19 '18 at 04:44

answered Feb 19 '18 at 04:36

user4581301

33,082
7
33
54

great catch! Thanks. Don't get that error anymore. Been running on a loop for a while. – pi47 Feb 19 '18 at 04:53
I popped the revised code into a debugger and the best I can tell you is it's not finding your goal. If it's spinning around in a cycle of values, it's a very large cycle. I recommend doing what I'm doing and running the program in [whatever debugger came with your development environment](https://en.wikipedia.org/wiki/Debugger) with an eye out for where your program goes left when you think it should have gone right. – user4581301 Feb 19 '18 at 05:07
When I run the loop for just a couple of iterations and print the puzzle at the top of the open list and it corresponding parent, I get garbage values for the parent puzzle. – pi47 Feb 19 '18 at 05:23
@pi47 This is what we're talking about in the comments below your question. It is next to impossible to maintain that `parent` pointer without changing how you store the nodes. If you can possibly avoid needing the `parent` pointer, a recursive backtracking solution for example, do it. Otherwise Ask a new question about how to preserve the `parent` pointer. I can think of a few ways to do it, some easy and some not so easy, but way out of scope for this question. Try to keep questions to one problem at a time. They are more useful to the programmers who come after you that way. – user4581301 Feb 19 '18 at 05:29
Got it. Thanks For all the help. – pi47 Feb 19 '18 at 05:31
@pi47 Not a problem. Happy coding. – user4581301 Feb 19 '18 at 05:32
I am sorry just one last doubt. The corrupt parent pointers should not stop the solution to converge correct? If i let the loop run for long enough it should it not find the solution as it is independent of the parent? – pi47 Feb 19 '18 at 05:38
@pi47 To be honest I don't know. I didn't dive into the algorithm far enough to figure that out. Your current algorithm doesn't use them, that's for sure. – user4581301 Feb 19 '18 at 05:46

" free(): invalid pointer:" 8-puzzle BFS

1 Answers1