Java recursive sudoku solver, recursive function does not return correct value

Question

I am working a sudoku solver and am having trouble returning / ending the solver function correctly. The show() in the moveOn() function gets called and it displays the compleated sudoku fine, however solve returns false. I am trying to have solve return true when the problem is solved and null when it is unsolveable however do not know how to accomplish this.

L is the length of the board (a 9 x 9 sudoku would have L = 9)

getSquare(r,c) returns the value in a 2 dimensional array representing the sudoku board

the different check functions check to see if a value can fit in a specific location. They are not the issue.

the show() function prints out the array in console so it looks like a proper sudoku board.

I also have an isSolved() function that checks the 2D array and if it is a valid solved sudoku returns true, otherweise returns false. I have attempted to implement this as well into the solve() method hoping to use that to return true, though have had no success

//This method's only purpose it to call the findNum function on the next location in the sudoku
public void moveOn(int row, int column) {
    //if the previous location was not the last in the row move to ne next cell in said row.
    //if it was the last location in the row, move to the first column of the next row
    if (column + 1 != L) {solve(row, column + 1);}
    else if (row + 1 != L) {solve(row + 1, 0);}
    else {show();}
}

//This method finds a valid number for a specific location on the sudoku grid\
public boolean solve(int row, int column) {
    if (row >= L) {return true;}
    //pass over any numbers that are not empty
    if (getSquare(row, column) != 0) {moveOn(row, column);}
    else {
        //attempt to find a valid number for the location
        for (int n = 1; n <= L; n++) {
            if (checkRow(row, n) && checkCol(column, n) && checkSquare(row, column, n)) {
                // If a number is allowed at a specific location set that location to the number
                setSquare(row, column, n);
                //Begin checking for a solution based on previous numbers changed           
                moveOn(row, column);
            }               
        }
        //If no number is allowed in this space backtrack to the last successful number 
        //changed and reset all locations that have been changed recursively
        setSquare(row, column, 0);          
    }
    //If the puzzle is unsolveable
    return false;
}

Many thanks to anybody that can help shed some light on the situation. If more of my code / information is needed I will gladly provide

Sample input file: http://pastebin.com/6mSKT3ES

Edit: complete code removed

Daniel Fischer · Accepted Answer · 2012-10-18 23:14:18Z

2

You have only one return statement in the solve function, and that is

return false;

and since that is the last statement in the function, and unconditionally executed, solve will, unless an exception is thrown, always return false.

To get a return value that actually tells you whether you found a solution, you need to make the return value depend on a condition. Also, once you have found a solution, for well-posed puzzles, there is no point in continuing to search.

So you should add a conditional return true; in the searching loop. For that, you need to know when you have found a solution. You wrap the recursion in an intermediate call to moveOn, so the simplest change would be to add a return value to moveOn:

public boolean moveOn(int row, int column) {
    //if the previous location was not the last in the row move to ne next cell in said row.
    //if it was the last location in the row, move to the first column of the next row
    if (column + 1 != L) {return solve(row, column + 1);}
    else if (row + 1 != L) {return solve(row + 1, 0);}
    else {show(); return true;}  // reached end of grid, solved
}

and use that in `solve':

public boolean solve(int row, int column) {
    //pass over any numbers that are not empty
    if (getSquare(row, column) != 0) {return moveOn(row, column);}
    else {
        //attempt to find a valid number for the location
        for (int n = 1; n <= L; n++) {
            if (checkRow(row, n) && checkCol(column, n) && checkSquare(row, column, n)) {
                // If a number is allowed at a specific location set that location to the number
                setSquare(row, column, n);
                //Begin checking for a solution based on previous numbers changed           
                if (moveOn(row, column)) {
                    return true;       // solved, yay!
                }
            }               
        }
        //If no number is allowed in this space backtrack to the last successful number 
        //changed and reset all locations that have been changed recursively
        setSquare(row, column, 0);          
    }
    //If the puzzle is unsolveable
    return false;
}

answered Oct 18, 2012 at 23:14

Daniel Fischer

185k19 gold badges319 silver badges436 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Nick Delben Over a year ago

I have attempted that change before, and there is a compilation error stating something along the lines of "function moveOn must return type boolean" even thopugh the return statement is there

Daniel Fischer Over a year ago

Did you also add the return to both the if and else if branches? My function does return a boolean in all possible code paths.

Nick Delben Over a year ago

After adding all 3 i am back to the origional issue. I added a debug line System.out.println(Integer.toString(row)+Integer.toString(column)); as the first line of the solve function and noticed that although it does still call the show() and display the board it prints many more debug lines after the board displays and then still returns false. The same as before I made the suggested changes.

Daniel Fischer Over a year ago

That shouldn't happen. Of course I might have overlooked something. Can I get the complete code to check?

Daniel Fischer Over a year ago

Thanks. I have also a return in if (getSquare(row, column) != 0) {moveOn(row, column);}. That's needed to stop it as soon as a solution is found, too.

user2330382 · Accepted Answer · 2013-04-21 14:25:23Z

This code works...

import java.io.*;
import java.util.Arrays;
import java.util.Scanner;


public class Sudoku {

    public static int suRows=9;
    public static int suColumns=9;
    public static int [][] suArray = new int[suRows][suColumns];
    public static int [] dummyRowArray = new int[suRows];
    public static int [] dummyColArray = new int[suColumns];
    public static int [][] dummy3x3Array = new int[3][3];
    public static int [] dummyArray = new int[9];

    //read the contents of the file into a 2 dimensional array
    public static void readSudoku() throws FileNotFoundException, IOException
    {  
        System.out.print("Please enter the full file name containing the Sudoku Puzzle (e.g:X:/sudoku_case1.txt):");
        Scanner scan = new Scanner (System.in);
        String filename = scan.nextLine();
        File file = new File( filename );

       if ( file.exists() )  
       {   
           Scanner inFile = new Scanner( file );
           for(int i=0; i<suRows; i++)
           {
                for(int j=0; j<suColumns; j++)
                {
                    if(inFile.hasNextInt())   suArray[i][j] = inFile.nextInt();
                }
            }   
       inFile.close();
       }    
    }

    public static boolean inOrder(int [] a, int i, int j)
    {
        return a[i]<=a[j];
    }

    public static void swap(int [] a, int i, int j)
    {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }


    public static void exchangeSort(int [] a)
    {
        for(int i=0;i<a.length;i++)
        {
            for(int j=1;j<a.length-i;j++)
            {
                if(!inOrder(a,j-1,j))    swap(a,j-1,j);
            }
        }
    }

    public static void displaySudoku(int [][] suArray)
    {
        for(int i=0; i<suArray.length;i++)
        {
            for(int j=0; j<suArray[i].length;j++)
            {
                System.out.print(suArray[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }    
    }    

    //Check if there are any more zeros
    public static boolean isComplete(int [][]suArray)
    {
        boolean result=true;

        //Check every element for 0
        for(int i=0; i<suArray[0].length; i++)
        {
            for(int j=0 ; j<suRows ; j++)
            {
                if(suArray[i][j]==0) return false;
            }
        }
        System.out.println("There are no zeros in this Sudoku");
        return result;
    }    


    //Check for adjacent duplicates
    public static boolean isAdjacentDup(int [] a)
    {
        for(int i=1; i<a.length; i++)
        {
            if((a[i-1]!=0 || a[i]!=0))
            {
                     if(a[i-1]==a[i]) return true;
            }  
        }
        return false;    
    }

    //Check for 1 through 9
    public static boolean is1to9(int [] a)
    {
        int j=1;
        for(int i=0; i<a.length; i++)
        {
            if(a[i]==j) j++;
            else return false;
        }
        return true;    
    }

    public static boolean isDuplicate(int [][]suArray)
    {
        boolean result=false;

        //Check every row for duplicates
        for(int i=0; i<suArray[0].length; i++)
        {
            for(int j=0 ; j<suRows ; j++)
            {
                dummyRowArray[j]=suArray[i][j];
            }

            //Sort dummyArray so that duplicates can be checked
            exchangeSort(dummyRowArray);


            //Now check Adjacent elements for duplicates
            if(isAdjacentDup(dummyRowArray)==true)
            {
                System.out.println("Duplicates are found in row");
                return true;
            }

        }

        displaySudoku(suArray);

        //Check every column for duplicates 
        for(int j=0; j<suArray[0].length; j++)
        {
            for(int i=0 ; i<suColumns ; i++)
            {
                dummyColArray[i]=suArray[i][j];
            }

            //Sort dummyArray so that duplicates can be checked
            exchangeSort(dummyColArray);


            //Now check Adjacent elements for duplicates
            if(isAdjacentDup(dummyColArray)==true)
            {
                System.out.println("Duplicates are found in columns");
                return true;
            }

        }

        displaySudoku(suArray);

        System.out.println("3X3:");

        //Check every 3X3 matrix for duplicates
        // 1st block 
        if(is3x3Duplicate(suArray,0,3,0,3)==true)
        {
            System.out.println("1st Block has a duplicate");
            return true;
        }
        else System.out.println("1st Block has no duplicate");
        // 2nd block 
        if(is3x3Duplicate(suArray,0,3,3,6)==true)
        {
            System.out.println("2nd Block has a duplicate");
            return true;
        }
        // 3rd block 
        if(is3x3Duplicate(suArray,0,3,6,9)==true)
        {
            System.out.println("3rd Block has a duplicate");
            return true;
        } 
        // 4th block 
        if(is3x3Duplicate(suArray,3,6,0,3)==true)
        {
            System.out.println("4th Block has a duplicate");
            return true;
        } 
        // 5th block 
        if(is3x3Duplicate(suArray,3,6,3,6)==true)
        {
            System.out.println("5th Block has a duplicate");
            return true;
        } 
        // 6th block 
        if(is3x3Duplicate(suArray,3,6,6,9)==true)
        {
            System.out.println("6th Block has a duplicate");
            return true;
        } 
        // 7th block 
        if(is3x3Duplicate(suArray,6,9,0,3)==true)
        {
            System.out.println("7th Block has a duplicate");
            return true;
        } 
        // 8th block 
        if(is3x3Duplicate(suArray,6,9,3,6)==true)
        {
            System.out.println("8th Block has a duplicate");
            return true;
        } 
        // 9th block 
        if(is3x3Duplicate(suArray,6,9,6,9)==true)
        {
            System.out.println("9th Block has a duplicate");
            return true;
        } 

        return result;
    }

    //Check every3X3 grid for duplicates
    public static boolean is3x3Duplicate(int [][]suArray, int x1, int x2, int y1, int y2)
    {
        boolean result=false;
        int k=0, l=0;

        for(int i=x1; i<x2;i++)
        {   
            for(int j=y1;j<y2;j++)
            {

                dummy3x3Array[k][l]=suArray[i][j];
                l++;
            }
            l=0;
            k++;
        }
        displaySudoku(dummy3x3Array);   

        for(int i=0; i<dummy3x3Array.length; i++)
        {
            for(int j=0; j<dummy3x3Array.length; j++)
            {
                dummyArray[(i*dummy3x3Array.length) + j] = dummy3x3Array[i][j];
            }
        }

        System.out.println(Arrays.toString(dummyArray));

        //Sort dummyArray so that duplicates can be checked
        exchangeSort(dummyArray);



        //Now check Adjacent elements for duplicates
        if(isAdjacentDup(dummyArray)==true)
        {
            System.out.println("Duplicates are found in blocks");
            return true;
        }

        return result;
    }

     //Check every3X3 grid for 1 trough 9
    public static boolean is3x3have1to9(int [][]suArray, int x1, int x2, int y1, int y2)
    {
        boolean result=false;
        int k=0, l=0;

        for(int i=x1; i<x2;i++)
        {   

            for(int j=y1;j<y2;j++)
            {

                dummy3x3Array[k][l]=suArray[i][j];
                l++;
            }
            l=0;
            k++;
        }


        for(int i=0; i<dummy3x3Array.length; i++)
        {
            for(int j=0; j<dummy3x3Array.length; j++)
            {
                dummyArray[(i*dummy3x3Array.length) + j] = dummy3x3Array[i][j];
            }
        }



        //Sort dummyArray so that duplicates can be checked
        exchangeSort(dummyArray);



        //Now check Adjacent elements for duplicates
        if(is1to9(dummyArray)==false)
        {
            System.out.println("Block doe snot have 1 through 9");
            return false;
        }

        return result;
    }



    public static boolean isValidSudoku(int [][] suArray)
    {
      //  boolean result=true;

        //All nos should be between 0 and 9 
        for(int i=0; i<suArray.length; i++)
        {
            for(int j=0; j<suArray[i].length; j++)
            {
                    if(suArray[i][j]<0 || suArray[i][j]>9){
                        System.out.println("Nos in the puzzle are out of range");
                        return false;
                    }
            }
        }

        //Call teh isDuplicate function to check for duplicates in the rows
        if( isDuplicate(suArray)==true) return false;

        return true;

    }

    public static boolean isSolvedSudoku(int [][] suArray)
    {
         //Check every row for 1 to 9
        for(int i=0; i<suArray[0].length; i++)
        {

            for(int j=0 ; j<suRows ; j++)
            {
                dummyRowArray[j]=suArray[i][j];
            }


            //Sort dummyArray so that duplicates can be checked
            exchangeSort(dummyRowArray);



            if(is1to9(dummyRowArray)==false)
            {
                System.out.println("1 through 9 not present in rows");
                return false;
            }


        } 
        //Check every column for 1 to 9
        for(int j=0; j<suArray[0].length; j++)
        {

            for(int i=0 ; i<suColumns ; i++)
            {
                dummyColArray[i]=suArray[i][j];
            }


            //Sort dummyArray so that duplicates can be checked
            exchangeSort(dummyColArray);



            //Now check Adjacent elements for duplicates
            if(is1to9(dummyColArray)==false)
            {
                System.out.println("1 through 9 not present in columns");
                return false;
            }

        }

         //Check every 3X3 matrix for 1 through 9
        // 1st block 
        if(is3x3have1to9(suArray,0,3,0,3)==true)
        {
            System.out.println("1st Block does not contain 1 through 9");
            return false;
        }
        // 2nd block 
        if(is3x3have1to9(suArray,0,3,3,6)==true)
        {
            System.out.println("2nd Block does not contain 1 through 9");
            return false;
        }
        // 3rd block 
        if(is3x3have1to9(suArray,0,3,6,9)==true)
        {
            System.out.println("3rd Block does not contain 1 through 9");
            return false;
        } 
        // 4th block 
        if(is3x3have1to9(suArray,3,6,0,3)==true)
        {
            System.out.println("4th Block does not contain 1 through 9");
            return false;
        } 
        // 5th block 
        if(is3x3have1to9(suArray,3,6,3,6)==true)
        {
            System.out.println("5th Block does not contain 1 through 9");
            return false;
        } 
        // 6th block 
        if(is3x3have1to9(suArray,3,6,6,9)==true)
        {
            System.out.println("6th Block does not contain 1 through 9");
            return false;
        } 
        // 7th block 
        if(is3x3have1to9(suArray,6,9,0,3)==true)
        {
            System.out.println("7th Block does not contain 1 through 9");
            return false;
        } 
        // 8th block 
        if(is3x3have1to9(suArray,6,9,3,6)==true)
        {
            System.out.println("8th Block does not contain 1 through 9");
            return false;
        } 
        // 9th block 
        if(is3x3have1to9(suArray,6,9,6,9)==true)
        {
            System.out.println("9th Block does not contain 1 through 9");
            return false;
        } 

        return true;
    }


    public static boolean solveSudoku(int [][] s)
    {
        //Check if Valid
        if(isValidSudoku(suArray)==true) System.out.println("Sudoku is valid");
        else
        {
            System.out.println("Not valid!");
            return false;
        }
        //Check if Complete - No 0's in any place
        if(isComplete(suArray)==true)
        {
            System.out.println("Sudoku is Complete");
            return true;
        }
        else System.out.println("Sudoku is not Complete");

        //Check if solved - 1-9 present in every row, column and 3x3
        if(isSolvedSudoku(suArray)==true) System.out.println("Sudoku is Solved!");
        else System.out.println("Not Solved");   

        //Locate the first 0 in the Sudoko puzzle
        for(int i=0; i<suArray.length; i++)
        {
            for(int j=0 ; j<suArray[i].length ; j++)
            {
                if(suArray[i][j]==0) 
                {
                    System.out.println("0 found in location: " + i +"   " + j );
                    for(int k=1;k<10;k++)
                    {
                        suArray[i][j]=k;
                        System.out.println("New value assigned to Sudoku: " + k);
                        displaySudoku(suArray);
                        if(solveSudoku(suArray))// isValidSudoku(suArray))
                        {
                            displaySudoku(suArray);
                            System.out.println("New value assigned to Sudoku");
                            return true;
                        }
                    }    

                    suArray[i][j]=0; 
                    return false;  // remove this
                }
            }
        }

        return true;
    }



    public static void main(String[] args) throws FileNotFoundException, IOException {


        readSudoku();
        displaySudoku(suArray);

        if( (isValidSudoku(suArray)!=true))
        {
            System.out.println("The given Sudoku Puzzle is not Valid!. Exiting....");
            System.exit(0);
        }

        do
        {
            if(isSolvedSudoku(suArray)==true)
            {
                System.out.println("Sudoku is Completely Solved!");

            }

            if(solveSudoku(suArray)==true) 
            {
                System.out.println("Sudoku is now solved");

            }
            else System.out.println("Not Complete");  


        }while(isSolvedSudoku(suArray)!=true);

        System.out.println("Sudoku is now completely solved:");
        displaySudoku(suArray);


    }
}

Collectives™ on Stack Overflow

Java recursive sudoku solver, recursive function does not return correct value

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related