limit on recursion?

Hey guys

I have programmed a brute force sudoku solver. However, whilst it is fine for some of the easier puzzles, it seems to randomly stop half way through for the hard ones.

Im not sure, but could this be because I am using a lot of recursion? If i understand correctly, everytime you call recursion it eats away at memory. Could my program be stopping itself automatically due to some sort of overflow?

If so, is there any way around this?

Many thanks

There is no explicit limit to the number of recursions you can make, but there is a limit to the amount of stack-space you can use up - that's about 2MB on Windows (by default - , but can be smaller or larger in other systems. Using microsoft tools, you can change the stack-size by giving a larger size with the /STACK option - but there's a limit somewhere to how far you can go.

Edit: But the way around it is to either avoid deep recursion, or "don't store big things on the stack while recursing" [for example, don't make another copy of the Sudoku board every recursion, or if you have to do that, make it using "new" rather than as a local variable.

--
Mats

Ok nice. I think i will change the stack sizes and check how far the brute force solver will go.

Just to give an idea, I am recursing the function 'force' very many times

Code:

---

void force(int puzzle_grid[9][9],nodeptr pointer_array[9][9],coordptr coords_array[9][9],int xcoord, int ycoord,coordptr searchptr,int value)

---

So it has the puzzle board, two arrays of list pointers, three integers and a pointer);
is this considered excessive? I havn't had much programming experience.

Well, each [9][9] array will only take up 4 bytes, as it turns into a pointer, so with 7 arguments, the total of your arguments is 28 bytes + whatever the compiler needs for internal use, so say 48 bytes to be on the safe side - that would allow you several thousand recursions - about 40000 if you haven't got any huge local variables.

But you also have to add any local variables in the function itself, for example local copies of the board.

--
Mats

Instead of using function recursion and the program stack, implement the algorithm using a common loop and std::stack with push_back/pop_back etc...

Oh dear. I did some debugging on visual c++ and when the program ends earlier than it should its either due to a memory violation or stack overflow.

There must be quite a serious fault in my code. When inputting a completely blank sudoku, it gets a stack overflow after finding 3 solutions. A blank sudoku should have billions of solutions >.< my computer should be finding them all day long!

Whenever the program stops it is always at the same place.

Code:

---

coordptr searchptr = coords_array[xcoord][ycoord];
while (searchptr->next !=NULL){
        xcoord = searchptr->xcoord;
        ycoord = searchptr->ycoord;
                for(int number=1 ;number<10; number++){
                                nodeptr newnode = new node;
                                newnode->number = number;
                                newnode->next = pointer_array[xcoord][ycoord];
                                pointer_array[xcoord][ycoord] = newnode;
                                }
                searchptr = searchptr->next;
}

---

It is always on the line

Code:

---

nodeptr newnode = new node;

---

This piece of code is from a function which is called every time the program effectively does a backtrack.
I call a function which deletes every node from an array of pointers and then i remake the lists using the function above.

Is it very wrong to make lists within lots of recursion.

It is not wrong to make lists within recursion, but if you run out of memory, or overwrite the end of your buffer, then you will get the problems you are describing.

It sounds like you are running out of memory to me.

Running out of stack due to too much recursion will also lead to INSTANT death of the application. If you have a look at the register view, and check ESP, see what it is in main, then whenever it's crashed, check if it's about 0x200000 lower - that's out of stack in default stack-size.

Almost all recursive algorithms can be written using linear iteration.

--
Mats

I think you're right, I took a bit of time replacing my recursion needs with while loops. No longer get stack overflows! I guess recursion was just in my head from just having done it on my course hehe

However, still can't solve every sudoku - have found what appears to be a bug ;)

Thanks for all the help!