### A exception has been thrown when solving 8-digit problem

As the title, I am going to solve 8-digit problem using breadth first search (BFS), but it has thrown me a exception.

Here is the output:

 ```terminate called after throwing an instance of 'std::length_error' what(): basic_string::_M_create```

Here is the code:

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748`` ``````#include #include #include #include #include using namespace std; struct node { string s; int step; }; string str; // the given string set S; // the set to remember if the string was used queue q; // the queue to search int pos, ax, ay, bpos, bx, by, dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; void bfs() { q.push({str, 0}); S.insert(str); while(true) { node p = q.front(), now; if(p.s == "123804765") return void(cout << p.step << endl); // target string is 123804765 q.pop(); now = {p.s, p.step+1}; pos = p.s.find('0'); // it seems like it is not the fault of the line above, // because there is always a 0 (empty position) in the string ax = pos / 3; ay = pos % 3; for(int i = 0; i < 4; i++) { bx = ax + dx[i]; by = ay + dy[i]; bpos = 3 * bx + by; if(bx >= 0 && bx < 3 && by >= 0 && by < 3 && !S.count(now.s)) { swap(now.s[pos], now.s[bpos]); q.push(now); S.insert(now.s); swap(now.s[pos], now.s[bpos]); } } } } int main() { cin >> str; bfs(); return 0; }``````

I searched and found that this kind of exception may occur when using two iterators to construct a `std::string`, so I think the problem may in relation to the operation on `std::string` and finding `now.s` in the set.

Running the program in Debug mode if you can, preferably step by step one line at a time, would be a first option suggestion. So you know where the code "goes off the rails." Or a reasonably close approximation.

How you do that, running in Debug mode, I can't say. I know how to initiate it in my main compiler/IDE, Visual Studio 2022.
A couple of points:

1) L23. before accessing the queue I would check that the queue is not empty.

2) L27. Yes, I would check pos for std::string::npos. Even if a '0' is expected to be found, I would still check as not finding a '0' when expected would indicate a problem elsewhere.

Anyhow, in cases like this use the debugger to trace through the code watching the values of variables. When the execution path is not as expected or variable value is not as expected, then you have found a problem.

PS What is the code supposed to do?

OK. The problem is that q is empty when .front() is tried to be accessed.
Last edited on
> I am going to solve 8-digit problem
no idea what that is

> but it has thrown me a exception.
consider yourself lucky
run through a debugger and post the backtrace

> cin >> str;
¿example input? if it does reproduce your issue, better.

> bpos = 3 * bx + by;
¿is this always between bounds?

> if(p.s == "123804765") return void(cout << p.step << endl); // target string is 123804765
 ``1234`` ``````if(p.s == target){ // no need for needless comments cout << p.step << endl; return; // or weird hacks }``````

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596`` ``````#include #include #include #include #include #include using namespace std; //-------------------------------------- struct node { string str; int step; }; //-------------------------------------- void drawBoard( const string &str ) { for ( int row = 0; row < 3; row++ ) cout << str.substr( 3 * row, 3 ) << '\n'; } //-------------------------------------- void traceRoute( map &M, string s ) { cout << "Route traced (backwards):\n\n"; for ( ; s != ""; s = M[s] ) { drawBoard( s ); cout << '\n'; } } //-------------------------------------- void bfs( const string &start, const string &target ) { // Input validation if ( start .size() != 9 || target.size() != 9 || start .find_first_not_of( "012345678" ) != string::npos || target.find_first_not_of( "012345678" ) != string::npos ) { cout << "Invalid input\n"; return; } else if ( start == target ) { cout << "Start == target\n"; drawBoard( target ); cout << '\n'; return; } // Main solver int jump[] = { -1, 1, -3, 3 }; // left, right, up, down queue Q; // current search front set S; // set of configurations that have been reached map M; // sequence of predecessors for tracing route Q.push( { start, 0 } ); S.insert( start ); M[start] = ""; while( !Q.empty() ) { // Take next element from FIFO queue and check every configuration accessible from it node p = Q.front(); Q.pop(); int pos = p.str.find( '0' ); // position of blank space in the board for ( int jp : jump ) { string str = p.str; int sop = pos + jp; // position of tile that could be slid into blank space if ( sop < 0 || sop >= 9 || ( pos % 3 == 0 && jp == -1 ) || ( pos % 3 == 2 && jp == +1 ) ) continue; // outside board (top, bottom, left, right), so ignore swap( str[pos], str[sop] ); // slide tile across if ( str == target ) // check for completion { M[str] = p.str; traceRoute( M, str ); // trace back the route to the solution cout << "Solved in " << p.step + 1 << " steps\n"; return; } if ( S.insert( str ).second ) // if not already met, add to new front { Q.push( { str, p.step + 1 } ); // add new element to front, distance one step further M[str] = p.str; } } } cout << "Can't be solved\n"; } //-------------------------------------- int main() { bfs( "134825760", "123804765" ); }``````

 ```Route traced (backwards): 123 804 765 103 824 765 130 824 765 134 820 765 134 825 760 Solved in 4 steps```

See: https://en.wikipedia.org/wiki/Sliding_puzzle
Last edited on
 no idea what that is