Thread: My recursion is "leaking"...

Hi guys, I am quite new to this forum but ive been asking around everywhere and no one can help me solve my problem.
I had a crazy urge to make a sudoku solver that can output the answer to every possible answer to any kind of sudoku it is given, including a blank board.
So pretty well I wanted to make a program that could create every possible answer to a blank sudoku board.
I also wanted to make it super efficient and spent hours upon hours simplifying until I came to a near completed solution in almost 100 lines.
My issue is that the recursion process isn't working, even thought it really seems like it should. Please try and fix it, I commented and formated as best I could to make it simple to solve.
Thank you in advance! ~Raginpirate
P.S. if you scroll to the bottom of the program you can see a detail description of what is causing the error of this program. I however have no idea how to fix it.

class ReSu
{
  // PLEASE HELP ME
 
  public static void main (String [] args)
  {
    recur(input());
  }
  //Gets the input, for now I just want this program to work with a blank board, so I just have it return all 0's in the array.
  public static int[][] input()
  {
    int [][] sudoku = new int [9][9];
    return sudoku;
  }
 
  //The main recursion method. Something about this and startRecursion is causing my issue of leaking values.
  public static void recur(int [][] sudoku)
  {
    //Simple array to hold the return value of checkSolveFill which tells me if the board is solvable / works as a sudoku (checked[0]) and if the board is filled in completely (checked[1])
    boolean [] checked = new boolean [2];
    checked = checkSolveFill(sudoku);
    //If the board is both a valid sudoku and is completely filled in it outputs this board as a final answer
    if (checked[0] && checked[1])
      finalOutput(sudoku);
    // If it is not completely filled in but still a valid (or doesnt have any issues being a sudoku) sudoku it will start the recursion process
    if (checked[0])
      startRecursion(sudoku);
  }
 
  //This checks to see if the sudoku board is valid or filled in. Do not worry this works fine, I have tested this several times
  public static boolean[] checkSolveFill(int [][] sudoku)
  {
    int [][][] rowColumnBoxPossible = new int [3][9][9];
    boolean [] solveFill = new boolean [2];
    solveFill[0] = true;
    solveFill[1] = true;
    for (int x = 0; x<9; x++)
    {
      for (int y = 0; y<9; y++)
      {
        //If the spot on the board is not filled in it will set the later of the two return values to be false
        if (sudoku[x][y]>0)
        {
          //If the spot on the board has a value it will check if the row, column, and box it belongs to contains this value, and if it does the sudoku is not valid and the first of the two return values will be false
          if (rowColumnBoxPossible[0][x][sudoku[x][y]-1]==0 && rowColumnBoxPossible[1][y][sudoku[x][y]-1]==0 && rowColumnBoxPossible[2][boxChecker(x, y)][sudoku[x][y]-1]==0)
          {
            //If it did not have the value in all three, it will then set the section of all three arrays to not be zero. Trust me this works, its hard to think about though.
            rowColumnBoxPossible[0][x][sudoku[x][y]-1]=1;
            rowColumnBoxPossible[1][y][sudoku[x][y]-1]=1;
            rowColumnBoxPossible[2][boxChecker(x, y)][sudoku[x][y]-1]=1;
          }
          else
          {
            solveFill[0] = false;
          }
        }
        else
        {
          solveFill[1] = false;
        }
      }
    }
    return solveFill;
  }
 
  //Simple box check method done by looking at coordinates
  public static int boxChecker(int x, int y)
  {
    if (x<3)
    {
      if (y<3)
        return 0;
      if (y<6)
        return 1;
      return 2;
    }
    if (x<6)
    {
      if (y<3)
        return 3;
      if (y<6)
        return 4;
      return 5;
    }
    if (y<3)
      return 6;
    if (y<6)
      return 7;
    return 8;
  }
 
  //Outputs the sudoku
  public static void finalOutput(int [][] sudoku)
  {
    System.out.println();
    for (int x = 0; x<9; x++)
    {
      for (int y = 0; y<9; y++)
      {
        System.out.print(sudoku[x][y] + " ");
      }
      System.out.println();
    }
  }
 
  //My main problem. This method should work, but my understanding of recursion might be lacking.
  public static void startRecursion(int [][] sudoku)
  {
    int lastCoord=0;
    //First it finds all blank spots on the board and remebers the last one it found.
    for (int x = 0; x<9; x++)
    {
      for (int y = 0; y<9; y++)
      {
        if (sudoku[x][y] == 0)
          lastCoord = x*10+y;
      }
    }
    //It then reruns the whole program with this spot in the sudoku being all the values between 1-9.
    for (int z = 1; z<10; z++)
    {
      sudoku[lastCoord/10][lastCoord%10] = z;
      recur(sudoku);
    }
  }
}
/*If you try running this program however it will do nothing.
 * I have no idea how to fix this issue, because my recursion is kind of "leaking over"
 * the program works like this:
 * It finds a spot on the board which is blank and guesses 1-9 on it
 * it then checks to see if the sudoku is still solvable and if it is does the same guessing method again
 * if it is not solvable that pathway should end, and it should try the previous recursion pathway with its next number
 * for example:
 * bottom row of a blank sudoku 000000021
 * it would then guess 000000121
 * it would then realise this cant work and try 000000221
 * it would then realise this cant work and try 000000321
 * it would then continue on to guess 000001321 because this pathway worked and so on...
 * but here is where the program no longer works
 * when we reach this: (as it is the simplist pathway for the program to reach)
 * 009321654
 * 987654321
 * The program should revert to the last possible pathway and become:
 * 000421654
 * 987654321
 * however it "leaks" the value 9 into the last pathway and instead does this:
 * 009421654
 * 987654321
 * the program realises this cant work and clocks from 4-9 and then repeats the same issue with the next step and so on
 * until the program finally ends when it becomes
 * 009999999
 * 999999999
 * Instead of reseting when it moves back one pathway it carrys the previous recursive pathway backwards and I cannot
 * figure out why. Please help me and I hope I did the best I could to explain why it doesnt work!

Great post!

I don't quite understand your objective, because there isn't a Sudoku puzzle I've seen that starts with 81 empty squares. So instead of trying to find all possible solutions, I think you are trying to find all possible completed puzzles, which is kind of the same but definitely different. Do you have any idea how many possible 81-square puzzles there are? I'm not sure.

I think you shouldn't focus on the 9 "leaking" into the solution (I don't quite see it as leaking, but it's okay that you do), I think you should wonder why this result:

* 000421654
* 987654321

isn't recognized as incorrect. Why are 2 4s allowed on the same line and in the same group of 9? There's something fundamentally wrong with your "solver" algorithm to allow that to happen. Work on that for a bit and come back when you're ready to discuss it some more.

You might also consider starting with a solver that can solve the standard Easy/Medium/Hard puzzle flawlessly. You may not be able to go directly from there to a creator that can then create all possible completed puzzles, but the knowledge gained will make that next step much easier.

But about why I want it to move on to the next line with two fours in it isn't because that is a correct line it is because that is what the program should do, and if it did it would be able to figure out it is incorrect.

Then I don't understand what you're trying to do.

I suppose im not explaining myself properly, sorry for causing any confusion.
The program SHOULD react like this to my understanding:
it would go from
009321654
987654321
to trying this:
000421654
987654321
However it would "try" this, not actually output anything or keep these numbers because my checkSolveFill method would say it cannot work and end that branch of recursion.
The next step it should do would be
000521654
987654321
and then count that spot up until 7 (because 6 would be an incorrect sudoku aswell), where it would work and then do
001721654
987654321
and then it would repeat the same as before, revert and try 8 there, revert try 9...
and the process would backtrack itself counting upward and moving forward whenever the sudoku cannot have a number there.
It is kind of hard to think about, but (no offense) I don't really expect people to understand the logic behind this, I just really want someone to point out my issue with why certain branches of my recursion are affecting others.

Okay. Your additional explanation verified that you were trying to do what I thought you were.

It helps to build a program that can be scaled and provides feedback instead of ending with no results that leave you wondering what the h*&% happened. To be scalable, you also have to avoid the use of magic numbers, like '9' in for loops. Use generalized expressions whenever/wherever possible. To that end, I've modified your original code to do just that. The results are significantly different than you've described, so I'm not sure where you are on this quest.

class ReSu
{
    // an array for use throughout the program
    public static int[][] sudoku;
 
    // row and column constants to scale the program
    public static final int ROWS = 2;
    public static final int COLUMNS = 9;
 
    public static void main ( String [] args )
    {
        // initialize the array with the number of specified rows and columns
        sudoku = input( ROWS, COLUMNS );
 
        // fill the puzzle rows and columns
        recur( sudoku );
 
        // test output: present the output no matter what the results
        finalOutput( sudoku );
    }
    // Gets the input, for now I just want this program to work with a blank
    // board, so I just have it return all 0's in the array.
    public static int[][] input( int rows, int columns )
    {
        int [][] sudoku = new int [rows][columns];
        return sudoku;
    }
 
    // The main recursion method. Something about this and startRecursion is
    // causing my issue of leaking values.
    public static void recur( int[][] sudoku )
    {
        // Simple array to hold the return value of checkSolveFill which tells
        // me if the board is solvable / works as a sudoku (checked[0]) and if
        // the board is filled in completely (checked[1])
        boolean [] checked = new boolean [2];
        checked = checkSolveFill( sudoku );
 
        // If the board is both a valid sudoku and is completely filled in it
        // outputs this board as a final answer
        if ( checked[0] && checked[1] )
        {
            finalOutput( sudoku );
        }
 
        // If it is not completely filled in but still a valid (or doesnt have
        // any issues being a sudoku) sudoku it will start the recursion process
        if ( checked[0] )
        {
            startRecursion( sudoku );
        }
    }
 
    // This checks to see if the sudoku board is valid or filled in. Do not
    // worry this works fine, I have tested this several times
    public static boolean[] checkSolveFill( int [][] sudoku )
    {
        int [][][] rowColumnBoxPossible = new int [3][9][9];
        boolean [] solveFill = new boolean [2];
        solveFill[0] = true;
        solveFill[1] = true;
 
        for ( int x = 0; x < sudoku.length ; x++ )
        {
            for ( int y = 0; y < sudoku[x].length ; y++ )
            {
                // If the spot on the board is not filled in it will set the
                // later of the two return values to be false
                if ( sudoku[x][y] > 0 )
                {
                    // If the spot on the board has a value it will check if the
                    // row, column, and box it belongs to contains this value,
                    // and if it does the sudoku is not valid and the first of
                    // the two return values will be false
                    if ( rowColumnBoxPossible[0][x][sudoku[x][y] - 1] == 0
                         && rowColumnBoxPossible[1][y][sudoku[x][y] - 1] == 0
                         && rowColumnBoxPossible[2][boxChecker( x, y )][sudoku[x][y] - 1] == 0 )
                    {
                        // If it did not have the value in all three, it will
                        // then set the section of all three arrays to not be
                        // zero. Trust me this works, its hard to think about
                        // though.
                        rowColumnBoxPossible[0][x][sudoku[x][y] - 1] = 1;
                        rowColumnBoxPossible[1][y][sudoku[x][y] - 1] = 1;
                        rowColumnBoxPossible[2][boxChecker( x, y )][sudoku[x][y] - 1] = 1;
                    }
                    else
                    {
                        solveFill[0] = false;
                    }
                }
                else
                {
                    solveFill[1] = false;
                }
            }
        }
 
        return solveFill;
    }
 
    //Simple box check method done by looking at coordinates
    public static int boxChecker( int x, int y )
    {
        if ( x < 3 )
        {
            if ( y < 3 )
            {
                return 0;
            }
 
            if ( y < 6 )
            {
                return 1;
            }
 
            return 2;
        }
 
        if ( x < 6 )
        {
            if ( y < 3 )
            {
                return 3;
            }
 
            if ( y < 6 )
            {
                return 4;
            }
 
            return 5;
        }
 
        if ( y < 3 )
        {
            return 6;
        }
 
        if ( y < 6 )
        {
            return 7;
        }
 
        return 8;
    }
 
    //Outputs the sudoku
    public static void finalOutput( int [][] sudoku )
    {
        System.out.println();
 
        for ( int x = 0; x < sudoku.length ; x++ )
        {
            for ( int y = 0; y < sudoku[x].length ; y++ )
            {
                System.out.print( sudoku[x][y] + " " );
            }
 
            System.out.println();
        }
    }
 
    // My main problem. This method should work, but my understanding of
    // recursion might be lacking.
    public static void startRecursion( int [][] sudoku )
    {
        int lastCoord = 0;
 
        // First it finds all blank spots on the board and remebers the last
        // one it found.
        for ( int x = 0; x < sudoku.length ; x++ )
        {
            for ( int y = 0; y < sudoku[x].length ; y++ )
            {
                if ( sudoku[x][y] == 0 )
                {
                    lastCoord = x * 10 + y;
                }
            }
        }
 
        // It then reruns the whole program with this spot in the sudoku being
        // all the values between 1-9.
        for ( int z = 1; z < 10; z++ )
        {
            sudoku[lastCoord / 10][lastCoord % 10] = z;
            recur( sudoku );
        }
    }
}

Thank you very much for improving my commenting in the code and adding the final output :3 I have only started looking into proper formatting with java XD
About the output however, it is exactly what I stated in my first program, it clocks all the values up until 9 and then ends the program because the recursion is error.
So in the end, we haven't really learned anything about how to fix it
P.S. I do blame myself for this though, I feel if I were better at explaining my thoughts and conveying my understandings about how I am trying to make this program work we would be much further ahead than we are now with this problem : /
P.P.S. The only issue I have with your re-written program is the length of the rows, because if it is two and someone does get around to fixing my leaking error they wont really know unless the blank sudoku board given is of proper length to see if it produces a proper output.

The number of rows can be increased to 9 with a keystroke or two. I limited it (scaled it) to 2 to simplify the problem and in case the recursion was getting lost as the problem became more complicated.

As for being no further, yes, you may be no further, but I've come along quite a bit. You could have improved everyone else's starting point and therefore the input you'd get from others - especially the slow ones like me - if you'd explained from the start the current state of the problem, that the output was all 9s, what troubleshooting you'd done and how you'd done it, and what conclusions you'd come to from those results. I'm still not sure how you've captured the intermediate results that you've shown. Asking for help to solve difficult problems is not a simple thing, and like everything else, gets better with practice. No worries.

Let me play with it a while to catch up to where you are.

--- Update ---

Adding my print statements to monitor what is going on, here's an excerpt of my results:

Printing the result at the start of recure() (I added the comments after pasting):
 
0 0 9 3 2 1 6 5 4 
9 8 7 6 5 4 3 2 1 
 
Printing the result at the start of recure():
 
0 0 9 4 2 1 6 5 4   // backtracking begins here - this is the first time EVER
9 8 7 6 5 4 3 2 1   // and the '9' in the second row should be '0'
 
Printing the result at the start of recure():
 
0 0 9 5 2 1 6 5 4   // backtracking continues . . .
9 8 7 6 5 4 3 2 1 
 
Printing the result at the start of recure():
 
0 0 9 6 2 1 6 5 4   //. . . and backtracking continues . . . 
9 8 7 6 5 4 3 2 1

Eventually, the code increments each element to 9 and then moves back to the preceding element, increments it to 9, etc., until all elements are changed to 9 and then the program exits. So, the backtracking algorithm is broken.

When backtracking begins, the value that caused the invalid state and triggered the backtracking should be returned to the default value, 0. There may be other logic errors with your backtracking algorithm, but that's a start.

Ok, I don't mean to be rude in any way possible, and its probably because I am very bad at explaining myself, but I stated this already**... My issue is that I cannot figure out why this number does not return to 0 because the pathway in my recursion that contained that 9 should have ended... : / I am probably making a mistake somewhere or making assumptions about recursion that I am incorrect about since I self taught myself recursion and therefor do not understand it aswell as others might. I have spent hours upon end trying to find this mistake but I just don't see it, and even in other attempts to reset this value it just wont work... I am hoping someone else could spot the issue for me because I seriously cannot find one.

Also, let me make one thing clear:
I know there are no issues in this program besides the one number being carried over due to my EXTENSIVE testing. So if this situation with the 9 being carried over didn't occur it would work perfectly.

**If your wondering where I stated this, its at the bottom of the program I pasted at the beginning in comments.

Backtracking would typically be a break from the normal recursive solver method, a reset of the recursive solver. Your backtracking implementation has nothing to do with your understanding of recursion or how you've implemented recursion. The basic recursion concept - a method calling itself - is kind of hard to mess up, harder to stop when appropriate.

When your solver comes to a dead end, the solver algorithm should pause and backtrack to the last known valid state advanced to the next valid state. The next valid state should be stored in the current state, and the recursive solver should resume from there.

The recursive solve doesn't backtrack by itself. Backtracking is a pause in the recursive solver to allow the current state to be altered from which the recursion then continues. You need to add backtracking to your current code.

Yeh, you either don't understand much about arrays (like me before today) or you didn't read this code properly...
Took my teacher 1 minute to find the problem:
I did not understand that java array parameters carry values across because they share the same point in memory... therefor I had to make the most simple fix to cause my program to work:
In my last method I had to loop for the length of the array to copy it over to a new array and use that one to recur.

Thanks for trying... I guess.

Glad you fixed it. Sounds like you have a good teacher.