Recursive Sudoku

[Prasad Pavaluru]

Recursive Sudoku code.. works fine.. just input a Sudoku file of the below format:

0 0 1 7 8 0 3 0 2
6 0 0 0 0 2 0 5 7
0 7 0 9 1 0 0 8 0
0 0 5 0 0 1 7 3 0
0 0 6 0 0 0 4 0 0
0 9 4 2 0 0 8 0 0
0 1 0 0 5 7 0 4 0
5 6 0 8 0 0 0 0 3
3 0 2 0 6 9 5 0 0
-------------------------------

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 (new File("X:/java/PuzzleSolver/sudoku_1.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++)
{
// System.out.println("Calculating row no:" +i);
for(int j=0 ; j<suRows ; j++)
{
dummyRowArray[j]=suArray[i][j];
}
// System.out.println(Arrays.toString(dummyRowArray));

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

// System.out.println(Arrays.toString(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++)
{
// System.out.println("Calculating column no:" +j);
for(int i=0 ; i<suColumns ; i++)
{
dummyColArray[i]=suArray[i][j];
}
// System.out.println(Arrays.toString(dummyColArray));

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

// System.out.println(Arrays.toString(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++)
{
// System.out.println("Va;lue of k:" + k);
for(int j=y1;j<y2;j++)
{
// System.out.println("Va;lue of l:" + l);
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);

// System.out.println(Arrays.toString(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++)
{
// System.out.println("Value of k:" + k);
for(int j=y1;j<y2;j++)
{
// System.out.println("Value of l:" + l);
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);

// System.out.println(Arrays.toString(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++)
{
// System.out.println("Checking row no:" +i);
for(int j=0 ; j<suRows ; j++)
{
dummyRowArray[j]=suArray[i][j];
}
// System.out.println(Arrays.toString(dummyRowArray));

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

// System.out.println(Arrays.toString(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++)
{
// System.out.println("Checking column no:" +j);
for(int i=0 ; i<suColumns ; i++)
{
dummyColArray[i]=suArray[i][j];
}
// System.out.println(Arrays.toString(dummyColArray));

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

// System.out.println(Arrays.toString(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;
}
}
// else
// {
// suArray[i][j]=0;
// continue;
// }

suArray[i][j]=0; //Reset the value back to 0
return false; // remove this
}
}
}

//None of the options worked
//return false;
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);




}
}

[Stuart A. Burkett]

Did you actually have a question or did you just want to show us your code, so that it could be used as an example of how not to write an object oriented program ? Because you didn't UseCodeTags, I didn't look at it in any great detail, but the fact that all your methods are static is a bad sign.

[Prasad Pavaluru]

I just wanted to share this...Last year I searched a lot to find a recursive sudoku code.. but could not find it.. so, just wanted to share it with others..

[Stuart A. Burkett]

Prasad Pavaluru wrote: I just wanted to share this...Last year I searched a lot to find a recursive sudoku code.. but could not find it.. so, just wanted to share it with others..

Okay. Well done. But maybe as an exercise, you could look at applying object oriented principles to your design to improve upon it.

[Prasad Pavaluru]

Thanks .. will remember that..

[Paul Clapham]

I gave it a completely empty grid (zeroes in all 81 places) and it came up with a solution. It should really have said that there was more than one solution -- it's an implicit part of the Sudoku contract that there's going to be only one solution for a puzzle.

[Carey Brown]

Loaded up your program, commented out the println()'s, and ran some boards that I have from a program I wrote many years ago. Note that board 1 causes your program to hang. I didn't analyze it any further. Time shown were for my machine and my program.

static int		board0[][] =
    {
        { 0,0,0,0,0,0,0,0,0 }, // A "blank" board
        { 0,0,0,0,0,0,0,0,0 }, // Comes up with "a" solution
        { 0,0,0,0,0,0,0,0,0 }, // which is not unique
        { 0,0,0,0,0,0,0,0,0 }, // 0.000 seconds
        { 0,0,0,0,0,0,0,0,0 }, // 3,195 iterations
        { 0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0 }
    };
    static int		board1[][] =
    {
        { 0,0,0,0,0,0,0,0,0 }, // "Near worst case"
        { 0,0,0,0,0,3,0,8,5 }, // for brute force solvers
        { 0,0,1,0,2,0,0,0,0 }, // from Wikipedia
        { 0,0,0,5,0,7,0,0,0 }, // 55.625 seconds (storm 15.328 sec)
        { 0,0,4,0,0,0,1,0,0 }, // 622,577,597 iterations
        { 0,9,0,0,0,0,0,0,0 },
        { 5,0,0,0,0,0,0,7,3 },
        { 0,0,2,0,1,0,0,0,0 }, // !!! NEVER SOLVED - PROBABLE INFINITE
        { 0,0,0,0,4,0,0,0,9 }  // !!! LOOP OR RECURSION
    };
    static int		board2[][] =
    {
        { 0,6,0,1,0,4,0,5,0 }, // 0.000 seconds
        { 0,0,8,3,0,5,6,0,0 }, // 14,096 iterations
        { 2,0,0,0,0,0,0,0,1 },
        { 8,0,0,4,0,7,0,0,6 },
        { 0,0,6,0,0,0,3,0,0 },
        { 7,0,0,9,0,1,0,0,4 },
        { 5,0,0,0,0,0,0,0,2 },
        { 0,0,7,2,0,6,9,0,0 },
        { 0,4,0,5,0,8,0,7,0 }
    };
    static int		board3[][] =
    {
        { 0,8,0,0,0,0,0,7,0 }, // 0.000 seconds
        { 3,1,0,2,0,0,0,0,0 }, // 58,534 iterations
        { 0,9,5,6,0,8,0,1,0 },
        { 0,0,0,0,5,0,7,9,0 },
        { 9,0,0,0,0,0,0,0,8 },
        { 0,5,1,0,8,0,0,0,0 },
        { 0,7,0,1,0,4,9,5,0 },
        { 0,0,0,0,0,6,0,8,4 },
        { 0,3,0,0,0,0,0,6,0 }
    };
    static int		board4[][] =
    {
        { 7,0,0,0,0,0,4,0,0 }, // "Top 1465 Number 77"
        { 0,2,0,0,7,0,0,8,0 }, // Exceptionally difficult for
        { 0,0,3,0,0,8,0,0,9 }, // a human to solve
        { 0,0,0,5,0,0,3,0,0 }, // 0.094 seconds (storm: 0.070 sec)
        { 0,6,0,0,2,0,0,9,0 }, // 1,043,099 iterations
        { 0,0,1,0,0,7,0,0,6 },
        { 0,0,0,3,0,0,9,0,0 },
        { 0,3,0,0,4,0,0,6,0 },
        { 0,0,9,0,0,1,0,0,5 }
    };
    static int		board5[][] =
    {
        { 0,0,0,7,0,0,8,0,0 }, // "Qassim Hamza"
        { 0,0,0,0,4,0,0,3,0 }, // Exceptionally difficult for
        { 0,0,0,0,0,9,0,0,1 }, // a human to solve
        { 6,0,0,5,0,0,0,0,0 }, // 0.344 seconds (storm: 0.166 sec)
        { 0,1,0,0,3,0,0,4,0 }, // 3,757,817 iterations
        { 0,0,5,0,0,1,0,0,7 },
        { 5,0,0,2,0,0,6,0,0 },
        { 0,3,0,0,8,0,0,9,0 },
        { 0,0,7,0,0,0,0,0,2 }
    };

[Carey Brown]

--- I take that back. Board 1 in your program just took a VERY long time to solve.