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.

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.

: 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

This message was edited by stober at 2006-2-3 4:42:10

---

: : 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.

: : 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.

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:

#pragma warning(disable: 4786)

#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <bitset>
#include <windows.h>
#include <map>

using namespace std;
using std::bitset;


vector< bitset<9> > H(9), V(9), S(9);
vector<short> 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;
//	
//	
}

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.

: 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

: 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?

: :
:
: Did you happen to see how large the stack frame was when the function stopped?
:


No -- didn't look that hard at the program.