Infinite loop seemingly caused by a lack of any output

[SirMount]

Lately I have been working on a Sudoku generator, grader and solver, which has been working fine. I recently made significant speed increases to my program and so decided to remove the now superfluous progress output, but this caused the program to be stuck in the execution of one particular function.

I confirmed that the problem only happened when I was not giving any output, and then tried not outputting anything at all, but still using "fflush(stdout);" just before the main for loop in the function (this line is commented out in the function code included below). With this flush, the program would run fine; without it, it gets stuck in an infinite loop.

Before I explain any more about the problem I just want to clarify that, as I am not calling this function many times and performance is not critical, I can just leave the flush of stdout in there, but I would like to understand this problem regardless.

Interestingly, the fflush statement can be anywhere before the for loop or inside it (but not after it) in order for the function to finish its execution. However, if the fflush is inside another function called by the function in question, the program still gets stuck in its infinite loop. It also does not work if the fflush is just before the function is called.

Here's the function code in question:

void blankSomeBits(Cell sudoku[81]) {
	unsigned short order[81];
	randomOrder(order);
	
	Cell backup[81];
	//fflush(stdout);
	
	for (unsigned i = 0; i < 81; ++i) {
		/* backup and clear cell */
		backupCells(backup, sudoku);
		sudoku[order[i]].clear();
		
		/* check for uniqueness */
		logicsolve(sudoku);	// NB: this line can be commented out; it just makes it alot slower
					// also, its presence/absence does not affect the glitch at all
		if (checkUnique(sudoku)) {
			/* re-clear cell after sudoku has been solved */
			backupCells(sudoku, backup);
			sudoku[order[i]].clear();
			continue;
		}
		
		/* not a unique solution so rollback */
		backupCells(sudoku, backup);
	}
	
	return;
}

This function basically just picks a random order in which to blank the cells of the sudoku passed to it. After each cell is blanked, the puzzle is checked for the uniqueness of its solution in checkUnique(), and if it fails this check the puzzle is reverted to its previous state and the next cell is tried.

It is quite difficult to debug as using any form of output (including files) fixes the problem. I have tried using a couple of debuggers which I have but haven't gained much from it other than confirming that the function checkUnique() is successfully executed all the time (as is backupCells and as stated in the code, logicsolve can be omitted). Thus the problem is in the for loop of the above function which does not finish executing.

I am on Fedora 16, compiling with gcc, and program is single-threaded.

I have tried searching a number of places and have asked several people who have some experience in C/C++, but haven't found any suggestion of what could be the cause.

Thanks for your time.

[dhayden]

It sounds to me like you're corrupting memory somewhere and backup or order are getting trashed. Try adding some code to check the value of order[i] inside the loop to see if it's within 0-81

[cire]

I'm with dhayden. Sounds like stack corruption, where adding a function call with a parameter modifies the stack enough to mask the problem.

[SirMount]

Thanks for your help guys!

I've fixed the problem now, though I still am not sure why it would only have occurred when I was not outputting anything.

The bug was actually in the checkUnique() function, in which the value of i was being incremented twice (when its value was already 80) and then being compared with (i == 81). Like I said, this doesn't account for why the problem only happened without the output flush though it does explain the infinite loop. Perhaps the invalid value of i led to a something else corrupting sudoku...


Thanks once again!