josephkulandai.com

Sudoku is a logic-based placement puzzle or also we can designate it as an classical assignment problem. The object is to fill the grid so that every column, every row and every 3×3 box contains the digits 1 to 9. The puzzle setter provides a partially completed grid and the unfilled cells has to be filled.
For more information on Sudoku, visit the website: http://en.wikipedia.org/wiki/Sudoku

Following is a java program (source code) to solve the Sudoku puzzle. I need your comments to improve the efficiency of the algorithm. Source code is free for use, any body can dowload and use it for any purpose free of cost and no licence issues. Test it yourself for the correctness of the program.

To use, you need Java JDK to compile and run the program. Type the sudoku puzzle to be solved in the main method, then compile and run the program.

Output of the program:

Source code starts:

/**
* To solve the Sudoku puzzle
* @author Joseph Kulandai
*/
public class Sudoku {
/**
* To check if the array is completely filled
*/
public static boolean isArrayComplete(int arr[][]) {
boolean flag = true;
int currentRow = 0;
do {
int colCount = 0;
int currentColumn = 0;
// calculates the sum of the current row
do {
colCount += arr[currentRow][currentColumn];
currentColumn++;
} while (currentColumn < 9);
if (colCount < 45)
flag = false;
else
currentRow++;
} while (currentRow < 9 & flag == true);
return flag;
}   

/**
* To get the common elements in two arrays.
*/
public static int[] getCommonElements(int[] arr1,int[] arr2){
int k = 0;
int[] commonArr = new int[10];
for (int i = 0; i < arr1.length; i++)
for (int j = 0; j < arr2.length; j++) {
if (arr1[i] == arr2[j] & arr1[i] != 0) {
commonArr[k] = arr1[i];
k++;
}
}
return commonArr;
}   

 /**
* This method is used to get the missing elements
*/
public static int[] getMissingElements(int[] sequence) {
int[] missingElementsArr = new int[10];
boolean set[] = new boolean[10];
for (int i = 0; i < sequence.length; i++)
set[sequence[i]] = true;
for (int i = 1, k = 0; i < set.length; i++) {
if (set[i] == false) {
missingElementsArr[k] = i;
k++;
}
}
return missingElementsArr;
}

/**
* to get the possible elements
*/
public static int[] getPossibleElements(
int currentRow, int currentColumn,int[][] arr){
int[] tempArr1 = new int[10];
int[] tempArr2 = new int[10];
  // retrieving the elements that are in the corresponding
// row and column for that cell
  for (int i = 0; i < 9; i++) {
tempArr1[i] = arr[currentRow][i];
tempArr2[i] = arr[i][currentColumn];
}
int[] rowMissingArr = new int[10];
int[] colMissingArr = new int[10];
rowMissingArr = getMissingElements(tempArr1);
colMissingArr = getMissingElements(tempArr2);
  // finding the row,col index for the first cell for the
// block for which the current cell belongs to
  int blockRow=(((currentRow+1)%3>0)?((currentRow+1)/3)
:((currentRow+1)/3-1))*3;
int blockCol=(((currentColumn+1)%3>0)?((currentColumn+1)/3)
:((currentColumn+1)/3-1))*3;
  // retrieving the elements from in the corresponding block
  int k = 0;
int[] tempArr3 = new int[10];
for (int i = 0; i < 3; blockRow++, i++)
for(int j=0,colIndex=blockCol; j<3; colIndex++,j++,k++)
tempArr3[k] = arr[blockRow][colIndex];
int[] blockMissingArr = new int[10];
blockMissingArr = getMissingElements(tempArr3);
int[] tempArr4 = new int[10];
tempArr4 = getCommonElements(rowMissingArr, colMissingArr);
int[] possibleElementArr = new int[10];
possibleElementArr =
getCommonElements(tempArr4, blockMissingArr);
return possibleElementArr;
}   

 /**
* to fill the elements
*/
 public static int[][] fillElements(int[][] arr) {
for(int currentRow = 0; currentRow < 9; currentRow++) {
for(int currentColumn=0;currentColumn<9;currentColumn++) {
int[] tempArr = new int[10];
if (arr[currentRow][currentColumn] == 0) {
tempArr = getPossibleElements(currentRow, currentColumn,
 arr);
if (tempArr[1] == 0) {
arr[currentRow][currentColumn] = tempArr[0];
}
}
}
}
return arr;
}   

 /**
* the main method
*/
 public static void main(String args[]) {
  // type the sudoku to be solved here,
// put 0 (zero) for the not filled cells
  int[][] arr = {
{ 4, 1, 0, 0, 0, 3, 0, 7, 8 },
{ 2, 3, 7, 1, 0, 8, 5, 0, 0 },
{ 5, 8, 9, 6, 0, 0, 1, 4, 0 },
{ 7, 4, 0, 5, 0, 2, 0, 0, 0 },
{ 8, 2, 1, 0, 7, 0, 0, 0, 9 },
{ 0, 9, 0, 0, 3, 1, 7, 2, 0 },
{ 0, 0, 0, 7, 1, 0, 0, 0, 2 },
{ 1, 0, 0, 3, 8, 4, 0, 6, 5 },
{ 3, 5, 4, 0, 6, 9, 0, 0, 0 } };
// printing the problem
System.out.println(”The problem: “);
printSudoku(arr);
int i = 0;
do {
arr = fillElements(arr);
} while (!isArrayComplete(arr));
  // printing the final solved sudoku puzzle - solution
  System.out.println(”nThe solution: “);
printSudoku(arr);
}   

 /**
* to print the sudoku
*/
public static void printSudoku(int[][] arr) {
for (int m = 0; m < 9; m++) {
if(m%3==0) System.out.println();
for (int n = 0; n < 9; n++) {
  if(n%3==0) System.out.print(” “);
  System.out.print(” ” + arr[m][n]);
}
System.out.println();
}
}
}

This entry was posted on Tuesday, October 24th, 2006 at 9:06 pm and is filed under Software. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.