WHY IS THIS HAPPENING?!?!?!?! - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

WHY IS THIS HAPPENING?!?!?!?!

jambeardjambeard Posts: 70Member
I have 2 implementations of a recursive function, one using sets, the other using bitsets. Both functions are EXACTLY the same apart from the fact that one uses a set container, the other a bitset (obviously the set one will use functions such as .insert as opposed to .set but apart from that, the algorithms are exaclty the same).

Now, the function is to solve sudoku problems and it works fine, for all levels of a problem (i.e. for a puzzle with as many missing digits as is possible).

However, the bitset version stops working after 3973 recursions and set implementation stops working after 2017 recursions (that is, it either stops working after that amount of recursions or solves the puzzle, which ever one happens first).

I posted a message on the message board a few days ago and 2 people told me that this was happening because of a stack overflow. I don't think this is true however as a sudoku problem is very small and my computer is very big!

Each time the program crashes in VC++6 I get the following error message:

"Unhandelled exception in "new set investigation.exe" (KERNEL32.DLL): 0xC0000005

NOTE: The above message is for the set implementation, the bitset's one is a little different.

If I click OK in the dialog box that displays this message, VC++6 takes me to some disassembly stuff at line:

7C8024E5 push ebx

I have no idea what this all means but I reall really want to!!!!

I also checked the Windows Task Manager at the recursion just before the program crashes and the amount of memory it was using up was a tiny 5,528K and 00 of the CPU.

Does anyone know why my program is stopping after a certain amount of recursions? It cant be a stack overflow.....

J

PS, I've also tried running the program on different machines and outside the VC++6 environment but the smae thing happens with the same number of recursions.

Comments

  • stoberstober Posts: 9,765Member ✭✭✭
    most recursive functions crash due to stack overflow, which may be caused by coding infinit recursion. Check your code for infinite loops -- when does the recursion stop? Also check for large number of variables allocated on the stack inside the function.
  • jambeardjambeard Posts: 70Member
    : most recursive functions crash due to stack overflow, which may be caused by coding infinit recursion. Check your code for infinite loops -- when does the recursion stop? Also check for large number of variables allocated on the stack inside the function.
    :


    There are deffinately no infinite loops. it works fine up untill it reaches the, (in the bitset function), 3974th recursion call. Up to this point nothing unusual happens. how can I check the stack properly?

    J
  • stoberstober Posts: 9,765Member ✭✭✭
    [b][red]This message was edited by stober at 2006-2-3 4:42:10[/red][/b][hr]
    : : most recursive functions crash due to stack overflow, which may be caused by coding infinit recursion. Check your code for infinite loops -- when does the recursion stop? Also check for large number of variables allocated on the stack inside the function.
    : :
    :
    :
    : There are deffinately no infinite loops. it works fine up untill it reaches the, (in the bitset function), 3974th recursion call. Up to this point nothing unusual happens. how can I check the stack properly?
    :
    : J
    :

    post the function -- or at least the first few lines that who the parameters and auto variables. 3,974 recursive calls is a lot of recursion! Every recursive call takes 4 bytes just to store the return address. Then add the size of the parameters and the size of any auto variables inside the function.




  • stephlstephl Posts: 422Member
    : : most recursive functions crash due to stack overflow, which may be caused by coding infinit recursion. Check your code for infinite loops -- when does the recursion stop? Also check for large number of variables allocated on the stack inside the function.
    : :
    :
    :
    : There are deffinately no infinite loops. it works fine up untill it reaches the, (in the bitset function), 3974th recursion call. Up to this point nothing unusual happens. how can I check the stack properly?
    :
    : J
    :
    You should follow Stober's advices. You can also check whether your compiler provides a "Check stack overflow" option (exists in Turbo C).

    Steph.
  • jambeardjambeard Posts: 70Member
    The function is pretty ineffiecient, I just couldn't understand why it was stopping at exaclty the same point on all the computers I tried it on, not just mine.

    Here's the entire code used for the bitset function, its set up to cause an error like i've been describing so if you have time copy / paste it and see for yourselves:

    [code]

    #pragma warning(disable: 4786)

    #include
    #include
    #include
    #include
    #include
    #include
    #include


    using namespace std;
    using std::bitset;


    vector< bitset<9> > H(9), V(9), S(9);
    vector row(81), col(81), sq(81);

    vector< pair< int, bitset< 9 > > > tryValues; //int to represent the position in the string (x)
    //bitset for the numbers to try

    int poo = 0;

    void init()
    {
    int x;

    string st = "000111222000111222000111222333444555333444555333444555666777888666777888666777888";

    for (x=0; x<81; x++)
    {
    row[x] = x / 9;
    col[x] = x % 9;
    sq[x] = st[x]-'0';
    }
    }


    bool check(const string & st)
    {
    short digit;
    bool okay = true;

    for (int x=0; x<81; x++)
    {
    digit=st[x] -'0';
    digit--;
    H[row[x]].set(digit);
    V[col[x]].set(digit);
    S[sq[x]].set(digit);
    }

    x=0;

    while( okay && (x<9) )
    {
    if( (H[x++].count() != 9) || (V[x++].count() != 9) || (S[x++].count() != 9) )
    {
    okay = false;
    }
    }

    return okay;
    }


    void setUpBitsetsCheck()
    {
    for( int x = 0; x < 9; x++ )
    {
    H[x].reset();
    V[x].reset();
    S[x].reset();
    }
    }

    string setUpBitsetsInfer(const string &st)
    {
    string result = st;
    short digit;

    for( int x = 0; x < 9; x++ )
    {
    H[x].set();
    V[x].set();
    S[x].set();
    }

    x=0;

    for( x = 0; x < 81; x++ )
    {
    digit = result[x] - '0';
    if( digit != 0 )
    {
    digit--;
    H[row[x]].reset(digit);
    V[col[x]].reset(digit);
    S[sq[x]].reset(digit);
    }
    }

    return result;
    }

    bool checkIncomplete( const string &st)
    {
    bool okay = true;
    int x = 0;
    short digit;

    while( okay && (x < 81) )
    {
    digit = st[x] - '0';

    if( digit != 0 )
    {

    digit--;
    if( H[row[x]].test(digit) )
    {
    okay = false;
    }
    else
    {
    H[row[x]].set(digit);
    }

    if( V[col[x]].test(digit) )
    {
    okay = false;
    }
    else
    {
    V[col[x]].set(digit);
    }

    if( S[sq[x]].test(digit) )
    {
    okay = false;
    }
    else
    {
    S[sq[x]].set(digit);
    }
    }

    x++;
    }

    return okay;
    }

    string infer(const string &st)
    {
    cout << poo++ << endl;
    string result = setUpBitsetsInfer(st);


    int x = 0; // counter
    int digit = 0; //digit from string
    int allDoneCount = 0;
    bool allDone = false; //terminates recursion if true


    bitset<9> possibleValues, tempBitset;

    for( x = 0; x < 9; x++ )
    {
    if( (H[x].none()) && (V[x].none()) && (S[x].none()) )
    {
    allDoneCount++;
    }
    if( allDoneCount == 9 )
    {
    allDone = true;
    }
    }

    x = 0;

    //////////////////////////////////////////////
    //MAIN LOOP //
    //////////////////////////////////////////////

    if( !allDone )
    {

    if( !checkIncomplete(result) )
    {
    result = setUpBitsetsInfer(st);

    //dead end - need to go back a state

    //get the last element in tryValues
    vector< pair< int, bitset< 9 > > >::iterator it = (tryValues.end()-1);

    //get bitset from pair
    possibleValues.reset();
    possibleValues = it->second;

    //see if there are any numbers in it
    while( possibleValues.none() )
    {
    x = it->first;
    result[x] = 0 + '0';

    tryValues.pop_back();

    it = (tryValues.end()-1);
    possibleValues = it->second;
    }

    //set x to previous x and then..
    x = it->first;

    //get next number from bitset and update bitset (so you remove the next bit)
    for( int j = 0; j < 9; j++ )
    {
    if( possibleValues.test(j) )
    {
    tempBitset.reset();
    possibleValues.reset(j);
    tempBitset.set(j);
    break;
    }
    }

    it->second = possibleValues;

    //set the new digit in result...
    for( int i = 0; i < 9; i++ )
    {
    if( tempBitset.test(i) )
    {
    result[x] = (i+1) + '0';
    }
    }

    return infer(result);
    }

    else
    {
    result = setUpBitsetsInfer(st);

    for( x = 0; x < 81; x++ )
    {
    digit = result[x] - '0';
    if( digit == 0 )
    {

    ////////////////////////////////////////////////
    //TRY INTERSECTING ROW COL SQ TO FIND DIGIT //
    ////////////////////////////////////////////////

    possibleValues = H[row[x]] & V[col[x]];
    possibleValues = possibleValues & S[sq[x]];

    if( possibleValues.count() == 0 )
    {
    //dead end - need to go back a state

    //get the last element in tryValues
    vector< pair< int, bitset< 9 > > >::iterator it = (tryValues.end()-1);

    //get bitset from pair
    possibleValues.reset();
    possibleValues = it->second;

    //see if there are any numbers in it
    while( possibleValues.none() )
    {
    x = it->first;
    result[x] = 0 + '0';

    tryValues.pop_back();

    it = (tryValues.end()-1);
    possibleValues = it->second;
    }

    //set x to previous x and then..
    x = it->first;

    //get next number from bitset and update bitset (so you remove the next bit)
    for( int j = 0; j < 9; j++ )
    {
    if( possibleValues.test(j) )
    {
    tempBitset.reset();
    possibleValues.reset(j);
    tempBitset.set(j);
    break;
    }
    }

    it->second = possibleValues;

    //set the new digit in result...
    for( int i = 0; i < 9; i++ )
    {
    if( tempBitset.test(i) )
    {
    result[x] = (i+1) + '0';
    }
    }
    }
    else if( possibleValues.count() == 1 )
    {
    for( int i = 0; i < 9; i++ )
    {
    if( possibleValues.test(i) )
    {
    result[x] = (i+1) + '0';
    possibleValues.reset(i);
    break;
    }
    }

    tryValues.push_back( make_pair( x, possibleValues) );
    }
    else if( possibleValues.count() > 1 )
    {
    //extract first digit and alter the bitset accordingly
    for( int j = 0; j < 9; j++ )
    {
    if( possibleValues.test(j) )
    {
    tempBitset.reset();
    possibleValues.reset(j);
    tempBitset.set(j);
    break;
    }
    }

    //add this value in this position to solution
    for( int i = 0; i < 9; i++ )
    {
    if( tempBitset.test(i) )
    {
    result[x] = (i+1) + '0';
    }
    }

    //add possibleValues and x to end of vector (push back)

    tryValues.push_back( make_pair( x, possibleValues) );
    }

    break;
    }

    }

    return infer(result);

    }

    }

    return result;
    }

    void main(void)
    {
    double m_LastCount, m_CurCount;


    init();
    // cout << (check("963174258178325649254689731821437596496852317735961824589713462317246985642598173")?"Yes":"no") << endl;

    // string s = infer("903174258178325640204080701821407590400802000735961824589710402310240985642500073");
    // cout << s << endl;
    // cout << (check(s)?"yes":"no") << endl;


    ///* cout << "GENTLE" << endl;
    // cout << infer("060000500039064010400050000200900005100702004900006003000090006040180970008000400") << endl;
    // cout << infer("400090080000500700623700040049000073000000000760000920030002415002006000010050007") << endl;
    // QueryPerformanceCounter( (LARGE_INTEGER*)&m_LastCount);
    // cout << infer("704003000308001000500060100000034000940102035000690000005080007000500309000400508") << endl;
    // QueryPerformanceCounter( (LARGE_INTEGER*)&m_CurCount);
    // cout << (m_CurCount - m_LastCount) << endl;
    // cout << infer("000902000054000730600000002007503100030000020009201400900000004076000310000706000") << endl << endl;

    cout << "MODERATE" << endl;
    cout << infer("009600023406100000080000406001000070700000004050000900605000010000005209320007500") << endl;
    // cout << infer("040108050058000740702000308000201000300000006000805000501000903037000160090306080") << endl << endl;

    // cout << "TOUGH" << endl;
    // cout << infer("060940008003006000800001060950000400206000109001000076020800004000700500400019020") << endl << endl;

    // cout << "DIABOLICALE" << endl;
    //
    // cout << infer("010000080005010300040803005900260004030000050200034007100602090006080700020000060") << endl;
    //
    //
    }

    [/code]
  • stoberstober Posts: 9,765Member ✭✭✭
    after adding a little debug code, I'm pretty convinced the problem is stack overflow. It runs 7655 (or so) recursions on my computer (XP Pro) using Dev-C++ compiler.

    you might have to redesign to use iteration instead of recursion.
  • jambeardjambeard Posts: 70Member
    : after adding a little debug code, I'm pretty convinced the problem is stack overflow. It runs 7655 (or so) recursions on my computer (XP Pro) using Dev-C++ compiler.
    :
    : you might have to redesign to use iteration instead of recursion.
    :

    Ok, thanks a lot for taking a look at it.

    J
  • jambeardjambeard Posts: 70Member
    : after adding a little debug code, I'm pretty convinced the problem is stack overflow. It runs 7655 (or so) recursions on my computer (XP Pro) using Dev-C++ compiler.
    :
    : you might have to redesign to use iteration instead of recursion.
    :

    Did you happen to see how large the stack frame was when the function stopped?
  • stoberstober Posts: 9,765Member ✭✭✭
    : :
    :
    : Did you happen to see how large the stack frame was when the function stopped?
    :


    No -- didn't look that hard at the program.
Sign In or Register to comment.