Skip to content

My All Sudoku solver

May 6, 2015

I felt really glad that the new PM of Singapore is a (more than) competent programmer!

Just was reminded of my own program, after seeing Norvig’s sudoku solver blog post (did not see his code of course).

Below’s mine in Java (written on Mar 26 2011):-)


public class TrySudoku {

// 1 means can’t write data
public static int[][] sud_ctrl = new int[9][9];
public static int[][] sud_arr = new int[9][9];

public static int cur_i=0;
public static int cur_j=0;

public static void setZeros()
{
for(int i=0; i<9; i++)
for(int j=0; j<9;j++)
{
sud_arr[i][j] = 0;
sud_ctrl[i][j] = 0;
}
}

public static void setCtrlData()
{
for(int i=0; i<9; i++)
for(int j=0; j 0)
sud_ctrl[i][j] = 1;
}
}

public static boolean doesCurrentPlacementBreakRules()
{
//System.out.println(“cur_i: ” + cur_i);
//System.out.println(“cur_j: ” + cur_j);

// check cur_i’s row
for(int j=0; j<9;j++)
{
if(j != cur_j)
if(sud_arr[cur_i][j] == sud_arr[cur_i][cur_j])
return true;
}

// check cur_j's column
for(int i=0; i<9; i++)
{
if(i != cur_i)
if(sud_arr[i][cur_j] == sud_arr[cur_i][cur_j])
return true;
}

// Check in the 3X3 square
int cell_i = 3* (cur_i/3);
int cell_j = 3* (cur_j/3);
//System.out.println("cell_i: " + cell_i);
//System.out.println("cell_j: " + cell_j);
for(int i=cell_i; i< (cell_i + 3); i++)
{
for(int j=cell_j; j< (cell_j+3); j++)
{
if(cur_i != i && cur_j != j)
if(sud_arr[i][j] == sud_arr[cur_i][cur_j])
return true;
}
}
return false;
}

public static void main(String[] args)
{
setZeros();

// sud_arr[0][1] = 1; sud_arr[0][4] = 2; sud_arr[0][7] = 4;
// sud_arr[1][5] = 1; sud_arr[1][8] = 3; // sud_arr[1][7] = 5;
// sud_arr[2][0] = 6; sud_arr[2][5] = 9; sud_arr[2][7] = 1; sud_arr[2][8] = 8;
// sud_arr[3][5] = 7; sud_arr[3][6] = 5; sud_arr[3][7] = 2;
// sud_arr[4][2] = 5; sud_arr[4][6] = 1;
// sud_arr[5][1] = 2; sud_arr[5][2] = 7; sud_arr[5][3] = 4;
// sud_arr[6][0] = 2; sud_arr[6][1] = 4; sud_arr[6][3] = 6; sud_arr[6][8] = 5;
// sud_arr[7][0] = 3; sud_arr[7][3] = 2;
// sud_arr[8][1] = 9; sud_arr[8][4] = 3; sud_arr[8][7] = 8;

// Some hard sudoku problems from http://magictour.free.fr/top95
// String sudokuInput = "4…..8.5.3……….7……2…..6…..8.4……1…….6.3.7.5..2…..1.4……";
// String sudokuInput = "52…6………7.13………..4..8..6……5………..418………3..2…87…..";
// String sudokuInput = "6…..8.3.4.7……………..5.4.7.3..2…..1.6…….2…..5…..8.6……1….";
// String sudokuInput = "48.3…………71.2…….7.5….6….2..8………….1.76…3…..4……5….";
// String sudokuInput = "….14….3….2…7……….9…3.6.1………….8.2…..1.4….5.6…..7.8…";
// String sudokuInput = "……52..8.4……3…9…5.1…6..2..7……..3…..6…1……….7.4…….3.";
// String sudokuInput = "6.2.5………3.4……….43…8….1….2……..7..5..27………..81…6…..";
// String sudokuInput = ".524………7.1…………..8.2…3…..6…9.5…..1.6.3………..897……..";
// String sudokuInput = "6.2.5………4.3……….43…8….1….2……..7..5..27………..81…6…..";
// String sudokuInput = ".923………8.1………..1.7.4………..658………6.5.2…4…..7…..9…..";

// The last two on the page http://magictour.free.fr/top95
// String sudokuInput = "…..2…….7…17..3…9.8..7……2.89.6…13..6….9..5.824…..891……….";
// String sudokuInput = "3…8…….7….51…………..36…2..4….7………..6.13..452………..8..";

// The first & last from http://norvig.com/hardest.txt
// String sudokuInput = "85…24..72……9..4………1.7..23.5…9…4………..8..7..17……….36.4.";
// String sudokuInput = "….7..2.8…….6.1.2.5…9.54….8………3….85.1…3.2.8.4…….9.7..6….";

// A random puzzle generated by Norvig, as the hardest for any program
String sudokuInput = "…..6….59…..82….8….45……..3……..6..3.54…325..6………………";

for(int i=0; i<sudokuInput.length(); i++)
{
int r = i/9;
int c = i%9;

char ch = sudokuInput.charAt(i);
System.out.print(ch + ",");
if(ch != '.')
sud_arr[r][c]= Integer.valueOf((new Character(ch)).toString());
}

System.out.println("Printing the initial mat");
printArr(sud_arr);

setCtrlData();
System.out.println("Printing the ctrl mat");
printArr(sud_ctrl);

if(sud_ctrl[cur_i][cur_j] == 1)
{
advanceIndex();
}

do{
while(true)
{
if(sud_arr[cur_i][cur_j] + 1 <=9)
{
sud_arr[cur_i][cur_j]++;
if(!doesCurrentPlacementBreakRules())
{
advanceIndex();
break;
}
}
else
{
sud_arr[cur_i][cur_j]=0;
moveBackIndex();
break;
}
}

} while(cur_i<9 && cur_j<9);

System.out.println("Printing the result");
printArr(sud_arr);
}

public static void advanceIndex()
{
if(cur_i== 8 && cur_j == 8)
{
// moving the pointer beyond the mat
cur_i=9;
cur_j=0;
return;
}

if(cur_j<8)
{
cur_j++;
if(sud_ctrl[cur_i][cur_j]==1)
advanceIndex();
}
else if(cur_i0)
{
cur_j–;
if(sud_ctrl[cur_i][cur_j]==1)
moveBackIndex();
}
else if(cur_i>0)
{
cur_i–;
cur_j=8;

if(sud_ctrl[cur_i][cur_j]==1)
moveBackIndex();
}
}

private static void printArr(int[][] arr)
{
for(int i=0; i<9; i++)
{
System.out.println("");
for(int j=0; j<9; j++)
{
System.out.print(arr[i][j]);
}
}

System.out.println("");
}

}

Advertisements

From → Uncategorized

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: