# Recursion not stopping after return - Sudoku Solver

• ### Question

• I am writing a Sudoku solver in Visual c# using a recursive backtracking algorithm. In my recursive solve method, the base case is checking if the board (an integer double array) is full. If the board is found to be full, it should return. I also made a message box pop up displaying the board as soon as the base case is met. The method works up to this point, because when the message box pops up the puzzle is successfully solved. However, when I dismiss the message box (or comment it out) the method continues to backtrack and turn all of the entries into zero, even after hitting the return statement.

Example:﻿

Result before solve method:

```006    097    004
230    810    006
700    002    080
087    201    040
400    000    002
020    403    610
050    700    009
900    036    078
600    950    300```

Result right after calling solveSudoku(board) and the "Solved" message box pops up:

```816    397    254
234    815    796
795    642    183
387    261    945
461    579    832
529    483    617
153    728    469
942    136    578
678    954    321```

(the solve method correctly solves it at this point)

Result after I dismiss the message box and print the board once again:

```006    097    004
230    810    006
700    002    080
087    201    040
400    000    002
020    403    610
050    700    009
900    036    078
600    950    300```

(it has been changed back to the initial board)

Note: I plan on writing code to actually display the board later.

Code:

```private void solveSudoku(int[,] intBoard)
{
int i = 0;
int j = 0;
List<int> possibilities;

if (checkFull(intBoard))
{
MessageBox.Show("Solved");
MessageBox.Show(printDoubleArray(intBoard));
return;

}
else
{

for (int x = 0; x < 9; x++)
{
for (int y = 0; y < 9; y++)

if (intBoard[x, y] == 0)
{
i = x;
j = y;
break;
}
else
{
continue;
}
}

possibilities = possibleNums(intBoard, i, j); // a list  with the possible entries based
// on the row, column, and 3x3 grid

for (int x = 0; x < possibilities.Count; x++)
{
if (possibilities[x] != 0)
{
intBoard[i, j] = possibilities[x];
solveSudoku(intBoard); //recursion
}
}
intBoard[i, j] = 0;
}
}```

When the message box comes out, that means the base case has been reached. Because of the return, I'm unsure why the method continues to run, but I'm guessing I don't fully understand the recursion. Why is it changing all of the values back to 0, and how do I stop it?

Thursday, December 5, 2019 2:35 AM

### All replies

• Just as a quick suggestion based on general practices - without analyzing your
code at all: Have you considered adding a return - probably a bool - to the
solveSudoku method? Return true if success was found and false if not. Test
that return after each call to see if the program should continue or if it
should end or at least back out of the current nested (recursed) operation.

- Wayne
Thursday, December 5, 2019 2:53 AM
• Greetings Salmon27.

Wayne is right. That's the problem.

Somewhere you call solveSudoku the first time (let's call that CallA), which calls itself (CallB), which calls itself again (CallC) and so on.

Suppose CallC ends up at the MessageBox that signals success. When it returns, it returns to the place in CallB where it left off, and keeps going. When CallB finally finishes, it returns to the point in CallA where it left off, and keeps going. All the returning and keeping going resets the entire board.

The solution is as Wayne explained. Set a flag when the puzzle is solved so that when it returns to where it left off, it doesn't keep going.
Thursday, December 5, 2019 4:11 AM
• Hi salmon27,

Thank you for posting here.

For your question, you want to replace 0 in the array with other numbers based on some rules.

First of all, as Wayne said, you can try to add an end condition.

Secondly, since you want to replace 0 with other numbers,  I suggest that you’d better not use intBoard [i, j] = 0 to reassign the value to 0.

I deleted this line and it should work now.

Here is the code.

```        bool isFull = false;
private void solveSudoku(int[,] intBoard)
{
int i = 0;
int j = 0;
List<int> possibilities;
if (checkFull(intBoard))
{
isFull = true;
}
else
{
for (int x = 0; x < 6; x++)
{
for (int y = 0; y < 3; y++)
{
if (intBoard[x, y] == 0)
{
i = x;
j = y;
break;
}
else
{
continue;
}
}
}
possibilities = possibleNums(intBoard, i, j);

for (int x = 0; x < possibilities.Count; x++)
{
if (possibilities[x] != 0)
{
intBoard[i, j] = possibilities[x];

if (isFull == false)
{
solveSudoku(intBoard);
}
else { break; }

}
}
//intBoard[i, j] = 0;
}
}
```

Hope this could be helpful.

Best Regards,

Timon

MSDN Community Support
Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.

Friday, December 6, 2019 2:56 AM