How to properly traverse back up breadth first search search tree?

  artificial-intelligence, c++

I am currently working on a an AI project to solve "8 Square" puzzles. Basically there are 8 tiles and one empty tile on a 3×3 board and you are trying to get the tiles in numerical order by switching the tiles around. My first search algorithm, breadth first search, successfully solves puzzles as it will display a solved puzzle when done. However, it cannot backtrace up to the original node without causing an error. I am not sure if this is because my parent pointer is set up incorrectly or I do not have a proper destructor. If it is an error of not having a destructor, I do not understand how to set one up properly because I do not know how to trace up the tree. Would I need to implement a linked list of some kind? Regardless, my current error is as follows:

 terminating with uncaught exception of type std::length_error: vector

but I also believe there is a memory leak error code 3 before I changed something, I will add this if the first error is solved.

To save you all time, particularly look at my while loop at the end of the main file, this is where the error occurs. Also, the parent assignment occurs during the expand function. Thanks in advance!

square.h:

    #include <vector>
    #include <iostream>          
    #include <cstdlib>
    #include <ctime>
    #include <cmath>

    class Square {
        public:

            // Default constructor, used to generate a random square board of specified size
            // Size refers to the _x_ size of the board, default is 3x3
            Square(int input_size = 3);

            // Constructor for specific board. Used primarily to test on easy to solve boards.
            Square(std::vector<std::vector<int> > input_square){
                square = input_square;
                size = input_square.size();
             };

    

            // Move functions to move blank piece around board
            void moveLeft();
            void moveRight();
            void moveUp();
            void moveDown();

    

            // Expand functions to create new squares by moving the 0 piece
            std::vector<Square> expand();

            // Used to find the position of 0s within a board. This is used to check if a particular expand function
            // can be used without causing an out of bounds error
            int getZeroI();

            int getZeroJ();

    
            // Function to print out the current square in traditional viewing format
            void display();



            // Function to check if board is solved
            bool isSolved();


    
            std::vector<std::vector<int> > getSquare(){ return square; }

            //Used to get the one dimensional version of the square vector
            std::vector<int> getOneDimensionalVector();

            int getSize(){ return size; }

            Square* getParent(){ return parent; }
            void setParent(Square* new_parent){ parent = new_parent; }



            bool operator==(Square& other);

            //Breadth-first-search operator.
            Square bfs();
    
        private:
            int size;
            std::vector<std::vector<int> > square;
            Square *parent;


    };   

square.cc:

 #include "../includes/square.h"

 Square::Square(int input_size){

     size = input_size;

     //Creates a list of all tiles needed based on size
     std::vector<int> tiles;
     for(int i = 0; i < pow(size, 2); i++){
         tiles.push_back(i);
     }

     //Initializes square as a set of empty vectors of appropriate size.
     for(int i = 0; i < size; i++){
         std::vector<int> emptyVector;
         square.push_back(emptyVector);
     }
 
     srand((unsigned) time(0));
     int randomIndex;
     for(int i = 0; i < size; i++){
         for(int j = 0; j < size; j++){
             randomIndex = (rand() % tiles.size());
             square[i].push_back(tiles[randomIndex]);
             tiles.erase(tiles.begin() + randomIndex);
         }
     }


 }

 void Square::display(){
     std::cout << " ___________ " << std::endl;
     for(int i = 0; i < size; i++){
         for(int j = 0; j < size; j++){
             if(j%size == 0){
                 std::cout << "| " << square[i][j] << " | ";
             }
             else if(j%size == size-1){
                 std::cout << square[i][j] << " |" << std::endl << "|___________|" << std::endl;
             }
             else{
                 std::cout << square[i][j] << " | ";
             }
         }
     }
     std::cout << std::endl;
 }

 std::vector<int> Square::getOneDimensionalVector(){
     std::vector<int> returnVect;
     for(int i = 0; i < size; i++){
         for(int j = 0; j < size; j++){
             returnVect.push_back(square[i][j]);
         }
     }
     return returnVect;
 }

 bool Square::isSolved(){
     std::vector<int> oneDimensionalVector = this->getOneDimensionalVector();
     int currentNum = 0;
     for(int i = 0; i < oneDimensionalVector.size(); i++){
         if(oneDimensionalVector[i] != 0){
             if(currentNum + 1 == oneDimensionalVector[i]){
                 currentNum += 1;
             }
             else{
                 return false;
             }
         }
     }
     return true;
 }

 bool Square::operator==(Square& other){
     if(this->getOneDimensionalVector() == other.getOneDimensionalVector()){
         return true;
     }
     else{
         return false;
     }
 }

 void Square::moveLeft(){
     int index_i = -1;
     int index_j = -1;
     for(int i = 0; i < size; i++){
         for(int j = 0; j < size; j++){
             if(square[i][j] == 0){
                 index_i = i;
                 index_j = j; 
                 break;
             }
         }
     }
     square[index_i][index_j] = square[index_i][index_j-1];
     square[index_i][index_j-1] = 0;
 }

 void Square::moveRight(){
     int index_i = -1;
     int index_j = -1;
     for(int i = 0; i < size; i++){
         for(int j = 0; j < size; j++){
             if(square[i][j] == 0){
                 index_i = i;
                 index_j = j; 
                 break;
             }
         }
     }
     square[index_i][index_j] = square[index_i][index_j+1];
     square[index_i][index_j+1] = 0;
 }

 void Square::moveUp(){
     int index_i = -1;
     int index_j = -1;
     for(int i = 0; i < size; i++){
         for(int j = 0; j < size; j++){
             if(square[i][j] == 0){
                 index_i = i;
                 index_j = j; 
                 break;
             }
         }
     }
     square[index_i][index_j] = square[index_i-1][index_j];
     square[index_i-1][index_j] = 0;
 }

 void Square::moveDown(){
     int index_i = -1;
     int index_j = -1;
     for(int i = 0; i < size; i++){
         for(int j = 0; j < size; j++){
             if(square[i][j] == 0){
                 index_i = i;
                 index_j = j; 
                 break;
             }
         }
     }
     square[index_i][index_j] = square[index_i+1][index_j];
     square[index_i+1][index_j] = 0;
 }

 std::vector<Square> Square::expand(){
     std::vector<Square> returnVect;
     std::vector<std::vector<int> > original_square = square;
     try {
         if(getZeroJ() == 0){
             throw 0;
         }
         Square leftSquare(original_square);
         leftSquare.moveLeft();
         leftSquare.setParent(this);
         returnVect.push_back(leftSquare);
     }
     catch(...){
     }
     try {
         if(getZeroJ() == size-1){
             throw 0;
         }
         Square rightSquare(original_square);
         rightSquare.moveRight();
         rightSquare.setParent(this);
         returnVect.push_back(rightSquare);
     }
     catch(...){
     }
     try {
         if(getZeroI() == 0){
             throw 0;
         }
         Square upSquare(original_square);
         upSquare.moveUp();
         upSquare.setParent(this);
         returnVect.push_back(upSquare);
     }
     catch(...){
     }
     try {
         if(getZeroI() == size){
             throw 0;
         }
         Square downSquare(original_square);
         downSquare.moveDown();
         downSquare.setParent(this);
         returnVect.push_back(downSquare);
     }
     catch(...){
     }
     return returnVect;
 }

 int Square::getZeroI(){
     for(int i = 0; i < size; i++){
         for(int j = 0; j < size; j++){
             if(square[i][j] == 0){
                 return i;
             }
         }
     }
     return -1;
 }

 int Square::getZeroJ(){
     for(int i = 0; i < size; i++){
         for(int j = 0; j < size; j++){
             if(square[i][j]==0){
                 return j;
             }
         }
     }
     return -1;
 }

 Square Square::bfs(){
     std::vector<Square> visited;
     visited.push_back(*this);
     std::vector<Square> queue;
     queue.push_back(*this);
     display();
     int visitedNodes = 1;
     std::cout << visitedNodes << std::endl; 
     while(queue[0].isSolved() == 0){
         Square cur_node = queue[0];
         std::vector<Square> expanded_nodes = cur_node.expand();
         for(int i = 0; i < expanded_nodes.size(); i++){
             bool visited_bool = false;
             for(int j = 0; j < visited.size(); j++){
                 if(expanded_nodes[i] == visited[j]){
                     visited_bool = true;
                     break;
                 }
             }
             if(!visited_bool){
                 visited.push_back(expanded_nodes[i]);
                 visitedNodes += 1;
                 std::cout << visitedNodes << std::endl;
                 queue.push_back(expanded_nodes[i]);
             }
         }
         queue.erase(queue.begin());
     }
     return queue[0];
 }

main.cc:

 #include "../includes/square.h"



 int main(){     
     std::vector<std::vector <int> > square;
     std::vector<int> firstRow;
     std::vector<int> secondRow;
     std::vector<int> thirdRow;
     firstRow.push_back(1);
     firstRow.push_back(4);
     firstRow.push_back(2);
     square.push_back(firstRow);
     secondRow.push_back(0);
     secondRow.push_back(3);
     secondRow.push_back(5);
     square.push_back(secondRow);
     thirdRow.push_back(6);
     thirdRow.push_back(7);
     thirdRow.push_back(8);
     square.push_back(thirdRow);

     Square board(square);
     Square goal = board.bfs();




     return 0;
 }

Source: Windows Questions C++

LEAVE A COMMENT