Take the 2-minute tour ×
   #include <iostream> 
using namespace std; 

#include <list> 

//A queue for the working set 
//x,y co-ords of the square, path length so far 
struct square {
    int x;
    int y; 
    int path_length;

list<square> workingset; 

//A 2D array of ints to represent the board (duplicates list)
int board[10][10]; 

void generatelegalmove(square node, int x_offset, int y_offset); 
void printboard(); 

void main()
    //Initialises the board 
    int i, j;
            board[i][j] = 0;

    //The goal position - a number we will never reach 
    board[8][8] = 1337; 

    bool goal_found = false; 

    //Sets up initial position 
    square temp = {3, 7, 1}; 

    //Put initial position in working set and duplicates list
    board[3][7] = 1; 

    //Loop (until a goal is found)
        //Get the head node from the working set
        square nodetocheck = workingset.front();

        //Exit if the goal has been found
        if(board[nodetocheck.x][nodetocheck.y] == 1337)
            goal_found = true;

        //Generate the legal moves 
        generatelegalmove(nodetocheck, -1, 0); //One square to the left
        generatelegalmove(nodetocheck, 0, -1); //One square up
        generatelegalmove(nodetocheck, 1, 0); //One square to the right
        generatelegalmove(nodetocheck, 0, 1); //One square down


    //End Loop

    //Print the Board 

    //Trace back and print Trace back (once implemented) 

    //Print other info 


void generatelegalmove(square node, int x_offset, int y_offset)
    node.x = node.x + x_offset;
    node.y = node.y + y_offset; 
    node.path_length = node.path_length+1; 
    //Is this square on the board
    if((node.x >= 0) && 
       (node.x < 10) && 
       (node.y >= 0) && 
       (node.y < 10) && 
       //Is this square empty
       (board[node.x][node.y] == 0))

        board[node.x][node.y] = node.path_length; 
        //Add to working set
        //Add to duplicates list 
    //(If a graphical animation is added, do it here, by printing the new board after each one, then sleeping for a few seconds) 

I get the runtime error 'list iterator not dereferencable'.

I'm assuming this is to do with workingset.pop_front() being called from within the while loop, but I'm not sure what I should do to remedy this.

Each loop, I want to get the node from the front of the list, work with it a little, then remove that node from the list.

This is the code for generatelegalmove() - as you can see, if the new square is on the board (i.e. within the range of 0-9 in both dimensions of the array, and the square is empty) it will add this new node to the working set and the board[][] (which is effectively a duplicates list in effect)

share|improve this question
It would be worth to add the declaration of the used variable workingset. –  harper Jan 12 '11 at 11:50
Which particular line of the code you posted causes this error? Is it a compiler error or run-time error (debug check)? –  Maxim Yegorushkin Jan 12 '11 at 11:51
What do you mean? It's added earlier in the program, it's a list of the struct square. I didn't add the entirety of my code because it's long and I assumed things such as using the include for a list, declaring the bool goal_found, initialising board[][] and workingset etc. would be assumed... Or do you mean something else?? –  ShimmerGeek Jan 12 '11 at 11:52
It's a Debug Error - and uhm, it says Line 207. But my program is only a little over 100 lines long... –  ShimmerGeek Jan 12 '11 at 11:54
it could be line 207 in some other class (for example in the code that is in std::list). You need to inspect the stack trace to locate the first frame in your code. –  Nim Jan 12 '11 at 12:07
add comment

1 Answer

Given the sample you have provided, I can see one thing wrong. At the end of each loop iteration, you pop the front node. However, you only exit out of your loop if goal_found is true, meaning the line:

square nodetocheck = workingset.front();

... could well access an empty working set. Obviously you have calls to other functions here that might add nodes, but this might be a problem if no nodes existed.

EDIT: I believe your code is not adding another node because you are using the bitwise-and & operator instead of a logical-and && operator, causing your working set not to gain nodes.

share|improve this answer
generatelegalnode() will almost always be adding a node to the set... You're right, I should absolutely only allow it to be popped if the list isn't empty, but i'm pretty positive it can't be empty until the goal state is found –  ShimmerGeek Jan 12 '11 at 12:06
(It's a representation of the Lee algorithm for pathfinding, the working set shouldn't be empty of things to try until the goal square is found, afaik) –  ShimmerGeek Jan 12 '11 at 12:07
calling front() or pop_front() on an empty set would generate a runtime error though. The user is getting a compiler error. –  CashCow Jan 12 '11 at 12:09
@ShimmerGeek, that if(!workingset.empty()) line needs to be checked before you access front(). So, add something like this right after while(true) : if(workingset.empty()) break; to exit the loop. Your goal may not be found, but that's another problem :) –  Moo-Juice Jan 12 '11 at 12:29
@ShimmerGeek, better yet, change the loop to: while(!goal_found && !workingset.empty()). –  Moo-Juice Jan 12 '11 at 12:30
show 15 more comments

Your Answer


