C++

Forum

 
 
A exception has been thrown when solving 8-digit problem

oddy (15)
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
#include <iostream>
#include <string>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

struct node {
    string s;
    int step;
};

string str; // the given string
set<string> S; // the set to remember if the string was used
queue<node> 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.

Could you please give me some hints about this?

Thanks in advance.
deleted account xyzzy (5768)
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.
seeplus (6589)
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
ne555 (10692)
> 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
1
2
3
4
 
if(p.s == target){ // no need for needless comments
  cout << p.step << endl;
  return; // or weird hacks
}

lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
#include <iostream>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
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<string,string> &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<node> Q;                                     // current search front
   set<string> S;                                     // set of configurations that have been reached
   map<string,string> 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
MikeyBoy (5631)
no idea what that is

Using your fingers to type, but not your thumbs?

;)
Topic archived. No new replies allowed.