Головоломка из 8 плиток через BFS

Я искал глубины Интернета, и я еще не нашел решение моей проблемы. Я реализовал (я думаю) BFS для игры с раздвижными плитками. Однако он не может решить проблему, если состояние не находится в нескольких шагах, иначе это просто приведет к ошибкам нехватки памяти. Итак, мой вопрос к вам, где я ошибаюсь? Насколько я знаю, мой код следует псевдокоду BFS.

РЕДАКТИРОВАТЬ/ПРИМЕЧАНИЕ. Я прошел через отладчик и еще не нашел ничего необычного на мой взгляд, но я сравнительно начинающий программист.

#include <ctime>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <deque>
#include <vector>

using namespace std;

///////////////////////////////////////////////////////////////////////////////////////////
//
// Search Algorithm:  Breadth-First Search 
//
// Move Generator:  
//
////////////////////////////////////////////////////////////////////////////////////////////
class State{
public:
    int state[9];

    State(){
        for (int i = 0; i < 9; i++){
            state[i] = i;
        }
    }

    State(string st){
        for (int i = 0; i < st.length(); i++){
            state[i] = st.at(i) - '0';
        }
    }

    State(const State &st){
        for (int i = 0; i < 9; i++){
            state[i] = st.state[i];
        }
    }

    bool operator==(const State& other) {

        for (int i = 0; i < 9; i++){
            if (this->state[i] != other.state[i]){return false;}
        }
        return true;
    }

    bool operator!=(const State& other) {
        return !(*this == other);
    }

    void swap(int x, int y){
        // State b; // blank state
        // for (int i = 0; i < 9; i++) // fill blank state with current state
        //  b.state[i] = state[i];

        int t = this->state[x]; // saves value of the value in position x of the state

        this->state[x] = this->state[y]; // swaps value of position x with position y in the state
        this->state[y] = t; // swaps value of position y with saved position x in the state
    }

    int findBlank(){ // finds position in 3x3 of blank tile
        for (int i=0; i<9; i++){
            if (state[i]==0) return i;
        }
    }

    vector<State> blankExpand(){
        int pos = this->findBlank();
        vector<State> vecStates;


        if (pos != 0 && pos != 1 && pos != 2){ // swaps the tile above it
            State newState = State(*this);
            newState.swap(pos,pos - 3);
            vecStates.push_back(newState);
        }

        if (pos != 6 && pos != 7 && pos != 8){ // swaps the tile above it
            State newState = State(*this);
            newState.swap(pos,pos + 3);
            vecStates.push_back(newState);
        }

        if (pos != 0 && pos != 3 && pos != 6){ // swaps the tile above it
            State newState = State(*this);
            newState.swap(pos,pos - 1);
            vecStates.push_back(newState);
        }

        if (pos != 2 && pos != 5 && pos != 8){ // swaps the tile above it
            State newState = State(*this);
            newState.swap(pos,pos + 1);
            vecStates.push_back(newState);
        }

        return vecStates;
    }
};

string breadthFirstSearch_with_VisitedList(string const initialState, string const goalState){
    string path;

  clock_t startTime;
  startTime = clock();

  deque<State> nodesToVisit;
  vector<State> visitedList;
  int maxQLength = 0;


  //Init
    State init(initialState);
    State goal(goalState);
    nodesToVisit.push_back(init);

    int count = 0;
    int numOfStateExpansions = 0 ;
//
    while (!nodesToVisit.empty()){
        if(maxQLength < nodesToVisit.size()){maxQLength = nodesToVisit.size();}

        State cur = nodesToVisit.front();
        nodesToVisit.pop_front();
         //remove front

        if (cur == goal){
            //solution found
            cout << "solved!";
            break;
        }

        //Get children
        vector<State> children = cur.blankExpand();

        numOfStateExpansions += children.size();        

        //For each child
        for (State& child : children) {
            for (int i = 0 ; i < 9;i++){
                cout << child.state[i];
            }
            cout << " child" << endl;

          //If already visited ignore
          if (std::find(visitedList.begin(), visitedList.end(), child) != visitedList.end()) {
            // cout << "duplicate" << endl;
            continue;
          }

          //If not in nodes to Visit
          else if (std::find(nodesToVisit.begin(), nodesToVisit.end(), child) == nodesToVisit.end()) {
            //Add child
            nodesToVisit.push_back(child);
          }
        }
        visitedList.push_back(cur);

    }



//***********************************************************************************************************
    clock_t actualRunningTime = ((float)(clock() - startTime)/CLOCKS_PER_SEC);  
    return path;    

}

int main(){
    breadthFirstSearch_with_VisitedList("042158367", "123804765");
    //042158367
}

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