none
Recursion not stopping after return - Sudoku Solver RRS feed

  • 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