If you don't know what is sudoku, try googling for "sudoku wiki".
First we define the data structures for holding the puzzle.
A sudoku puzzle contains a grid of 81 cells, we may label it in a row major order :
0
1
2
9
10
11
18
19
20
3
4
5
12
13
14
21
22
23
6
7
8
15
16
17
24
25
26
27
28
29
36
37
38
45
46
47
30
31
32
39
40
41
48
49
50
33
34
35
42
43
44
51
52
53
54
55
56
63
64
65
72
73
74
57
58
59
66
67
68
75
76
77
60
61
62
69
70
71
78
79
80
That is naturally implemented by a one-dimensional array.
// structure for holding sudoku grid int[] cells=new int[81];
Normally a cell would contains one digit only, but that is true for a solved puzzle only.
Before the puzzle is completely solved, some cells may contains more than one possible values, it is desirable to store all the possible values of a cell. Hence each cell should hold a integer list.
For this reason, we change the simple integer array implementation.
// structure for holding sudoku grid ArrayList<Integer>[] cells=new ArrayList[81];
Roughly speaking, there are three constraints for filling the cells.
1. No duplicate digits allowed in the same row
2. No duplicate digits allowed in the same column
3. No duplicate digits allowed in the same region.
It is obvious that we need some data structures to represent the row, column and region.
We may group the cell label to form a row. A row is actually a list of indices to the cell array.
For example, the first row would be :
{ 0, 1, 2, 3, 4, 5, 6, 7, 8}
The second row would be :
{ 9,10,11,12,13,14,15,16,17}
A column can be defined in a similar way.
The first column is :
{0,9,18,27,36,45,54,63,72}
and the last column would be :
{8,17,26,35,44,53,62,71,80}
Region can be defined in a similar way.
The upperleft region contains 9 cells :
{0,1,2 ,9,10,11, 18,19,20}
The full data structure would be :
// structure for holding sudoku grid
ArrayList<Integer>[] cells=new ArrayList[81];
private int[][] row=new int[][] {
{ 0, 1, 2, 3, 4, 5, 6, 7, 8}, // row 0
{ 9,10,11,12,13,14,15,16,17}, // row 1
{18,19,20,21,22,23,24,25,26}, // row 2
{27,28,29,30,31,32,33,34,35}, // row 3
{36,37,38,39,40,41,42,43,44}, // row 4
{45,46,47,48,49,50,51,52,53}, // row 5
{54,55,56,57,58,59,60,61,62}, // row 6
{63,64,65,66,67,68,69,70,71}, // row 7
{72,73,74,75,76,77,78,79,80} // row 8
};
private int[][] column=new int[][] {
{ 0, 9,18,27,36,45,54,63,72}, // column 0
{ 1,10,19,28,37,46,55,64,73}, // column 1
{ 2,11,20,29,38,47,56,65,74}, // column 2
{ 3,12,21,30,39,48,57,66,75}, // column 3
{ 4,13,22,31,40,49,58,67,76}, // column 4
{ 5,14,23,32,41,50,59,68,77}, // column 5
{ 6,15,24,33,42,51,60,69,78}, // column 6
{ 7,16,25,34,43,52,61,70,79}, // column 7
{ 8,17,26,35,44,53,62,71,80} // column 8
};
private int[][] region=new int[][] {
{ 0, 1, 2, 9,10,11,18,19,20}, // region 0, upper left region (North West)
{ 3, 4, 5,12,13,14,21,22,23}, // region 1, top region (North)
{ 6, 7, 8,15,16,17,24,25,26}, // region 2, upper right region (North East)
{27,28,29,36,37,38,45,46,47}, // region 3, left region (west)
{30,31,32,39,40,41,48,49,50}, // region 4, middle region
{33,34,35,42,43,44,51,52,53}, // region 5, right region (east)
{54,55,56,63,64,65,72,73,74}, // region 6, lower left region (South West)
{57,58,59,66,67,68,75,76,77}, // region 7, bottom region (south)
{60,61,62,69,70,71,78,79,80} // region 8, lower right right (South East)
};
Next we define a problem, suppose we want to solve the following puzzle :
4
7
1
3
6
1
5
9
4
8
9
9
6
1
5
8
8
2
6
2
1
3
6
5
8
3
7
9
8
6
5
2
4
5
3
The puzzle can be represented by a String :
String puzzle = ".4.61..9."+
".7..5...."+
"1.3948..."+
"961.....2"+
"..58261.."+
"8.....365"+
"...3792.4"+
"....8..5."+
".8..65.3.";
To solve another puzzle, just change the content of the puzzle String.
It is not difficult to read the puzzle through command line parameter or read it from a file.
For simplicity purpose, I am not going to mess up the source code and just hard code the puzzle string.
Next, initialize all possible values of each cell, according to the puzzle.
//
public void init(String puzzle)
{
for (int i=0;i<81;i++)
{
cells[i]=new ArrayList<Integer>();
String s=puzzle.substring(i,i+1);
if (s.equals(".")) // unsolved cells, all values are possible
for (int digit=1;digit<=9;digit++) cells[i].add(digit);
else // solved cells, only one possible value
cells[i].add(Integer.parseInt(s));
}
}
Then print the grid :
// display all possible of the grid
public void printGrid()
{
String delimiter="";
for (int i=0;i<81;i++)
{
String s="";
for (int j=0;j<cells[i].size();j++)
{
s+=cells[i].get(j);
}
// make sure each cell contains exactly 8 character
for (int j=0;j<8-cells[i].size();j++) s+=" ";
if (s.length()>8) s="ALL "; // overflow
s=delimiter+s;
delimiter="|";
System.out.print(s);
if ((i+1)%9==0) { System.out.println(); delimiter=""; }
}
}
Here is our first version of sudoku solver, it only display the problem grid :
/******************************************************************************
* File : SudokuSolver.java (Version 1)
* Author : http://java.macteki.com/
* Description :
* A sudoku solver. (just display the puzzle grid)
* Tested with : JDK 1.6
******************************************************************************/
import java.util.ArrayList;
import java.lang.reflect.Array;
public class SudokuSolver
{
// structure for holding sudoku grid
ArrayList<Integer>[] cells=new ArrayList[81];
private int[][] row=new int[][] {
{ 0, 1, 2, 3, 4, 5, 6, 7, 8}, // row 0
{ 9,10,11,12,13,14,15,16,17}, // row 1
{18,19,20,21,22,23,24,25,26}, // row 2
{27,28,29,30,31,32,33,34,35}, // row 3
{36,37,38,39,40,41,42,43,44}, // row 4
{45,46,47,48,49,50,51,52,53}, // row 5
{54,55,56,57,58,59,60,61,62}, // row 6
{63,64,65,66,67,68,69,70,71}, // row 7
{72,73,74,75,76,77,78,79,80} // row 8
};
private int[][] column=new int[][] {
{ 0, 9,18,27,36,45,54,63,72}, // column 0
{ 1,10,19,28,37,46,55,64,73}, // column 1
{ 2,11,20,29,38,47,56,65,74}, // column 2
{ 3,12,21,30,39,48,57,66,75}, // column 3
{ 4,13,22,31,40,49,58,67,76}, // column 4
{ 5,14,23,32,41,50,59,68,77}, // column 5
{ 6,15,24,33,42,51,60,69,78}, // column 6
{ 7,16,25,34,43,52,61,70,79}, // column 7
{ 8,17,26,35,44,53,62,71,80} // column 8
};
private int[][] region=new int[][] {
{ 0, 1, 2, 9,10,11,18,19,20}, // region 0, upper left region (North West)
{ 3, 4, 5,12,13,14,21,22,23}, // region 1, top region (North)
{ 6, 7, 8,15,16,17,24,25,26}, // region 2, upper right region (North East)
{27,28,29,36,37,38,45,46,47}, // region 3, left region (west)
{30,31,32,39,40,41,48,49,50}, // region 4, middle region
{33,34,35,42,43,44,51,52,53}, // region 5, right region (east)
{54,55,56,63,64,65,72,73,74}, // region 6, lower left region (South West)
{57,58,59,66,67,68,75,76,77}, // region 7, bottom region (south)
{60,61,62,69,70,71,78,79,80} // region 8, lower right right (South East)
};
public void init(String puzzle)
{
for (int i=0;i<81;i++)
{
cells[i]=new ArrayList<Integer>();
String s=puzzle.substring(i,i+1);
if (s.equals(".")) // unsolved cells, all values are possible
for (int digit=1;digit<=9;digit++) cells[i].add(digit);
else // solved cells, only one possible value
cells[i].add(Integer.parseInt(s));
}
}
// display all possible of the grid
public void printGrid()
{
String delimiter="";
for (int i=0;i<81;i++)
{
String s="";
for (int j=0;j<cells[i].size();j++)
{
s+=cells[i].get(j);
}
// make sure each cell contains exactly 8 character
for (int j=0;j<8-cells[i].size();j++) s+=" ";
if (s.length()>8) s="ALL "; // overflow
s=delimiter+s;
delimiter="|";
System.out.print(s);
if ((i+1)%9==0) { System.out.println(); delimiter=""; }
}
}
public static void main(String[] args) throws Exception
{
// change this String for another puzzle
String puzzle= ".4.61..9."+
".7..5...."+
"1.3948..."+
"961.....2"+
"..58261.."+
"8.....365"+
"...3792.4"+
"....8..5."+
".8..65.3.";
SudokuSolver solver=new SudokuSolver();
solver.init(puzzle);
solver.printGrid();
}
}
Row Elimination
The next step is to make sure all rows cannot have duplicate digits. If a cell contains only one possible digit, it is a solved cell. For each solved cell, check which row it belongs to, then remove the solved digit from every cells in the row.
// eliminate duplicate digit of the same rows
public void rowElimination()
{
for (int i=0;i<81;i++) // loop over all cells
{
int n=cells[i].size(); // get number of possible values of current cell
if (n==1) // this is a solved cell
{
int solvedDigit=cells[i].get(0);
int rowNumber=i/9; // which row does the current cell belong to ?
for (int j=0;j<9;j++) // loop over all cells in the affected row
{
int cellNum=row[rowNumber][j];
// all other cells in the row cannot contain the solved digit
if (cellNum!=i) cells[cellNum].remove(new Integer(solvedDigit));
}
}
}
}
Look at the first row of the puzzle, the digit "4","6","1" and "9" are solved, hence all unsolved cells in the row cannot have the possible value of "4","6","1","9", that means the unsolved cells must be "2","3","5","7" or "8". After row elimination, the puzzle should be simplified as follows (every cell shows the possible digits):
23578 |4 |23578 |6 |1 |23578 |23578 |9 |23578 1234689 |7 |1234689 |1234689 |5 |1234689 |1234689 |1234689 |1234689 1 |2567 |3 |9 |4 |8 |2567 |2567 |2567 9 |6 |1 |34578 |34578 |34578 |34578 |34578 |2 3479 |3479 |5 |8 |2 |6 |1 |3479 |3479 8 |12479 |12479 |12479 |12479 |12479 |3 |6 |5 1568 |1568 |1568 |3 |7 |9 |2 |1568 |4 1234679 |1234679 |1234679 |1234679 |8 |1234679 |1234679 |5 |1234679 12479 |8 |12479 |12479 |6 |5 |12479 |3 |12479The following is the program that produce the above row eliminated output :
/******************************************************************************
* File : SudokuSolver.java
* Author : http://java.macteki.com/
* Description :
* A sudoku solver.
* Tested with : JDK 1.6
******************************************************************************/
import java.util.ArrayList;
import java.lang.reflect.Array;
public class SudokuSolver
{
// structure for holding sudoku grid
ArrayList<Integer>[] cells=new ArrayList[81];
private int[][] row=new int[][] {
{ 0, 1, 2, 3, 4, 5, 6, 7, 8}, // row 0
{ 9,10,11,12,13,14,15,16,17}, // row 1
{18,19,20,21,22,23,24,25,26}, // row 2
{27,28,29,30,31,32,33,34,35}, // row 3
{36,37,38,39,40,41,42,43,44}, // row 4
{45,46,47,48,49,50,51,52,53}, // row 5
{54,55,56,57,58,59,60,61,62}, // row 6
{63,64,65,66,67,68,69,70,71}, // row 7
{72,73,74,75,76,77,78,79,80} // row 8
};
private int[][] column=new int[][] {
{ 0, 9,18,27,36,45,54,63,72}, // column 0
{ 1,10,19,28,37,46,55,64,73}, // column 1
{ 2,11,20,29,38,47,56,65,74}, // column 2
{ 3,12,21,30,39,48,57,66,75}, // column 3
{ 4,13,22,31,40,49,58,67,76}, // column 4
{ 5,14,23,32,41,50,59,68,77}, // column 5
{ 6,15,24,33,42,51,60,69,78}, // column 6
{ 7,16,25,34,43,52,61,70,79}, // column 7
{ 8,17,26,35,44,53,62,71,80} // column 8
};
private int[][] region=new int[][] {
{ 0, 1, 2, 9,10,11,18,19,20}, // region 0, upper left region (North West)
{ 3, 4, 5,12,13,14,21,22,23}, // region 1, top region (North)
{ 6, 7, 8,15,16,17,24,25,26}, // region 2, upper right region (North East)
{27,28,29,36,37,38,45,46,47}, // region 3, left region (west)
{30,31,32,39,40,41,48,49,50}, // region 4, middle region
{33,34,35,42,43,44,51,52,53}, // region 5, right region (east)
{54,55,56,63,64,65,72,73,74}, // region 6, lower left region (South West)
{57,58,59,66,67,68,75,76,77}, // region 7, bottom region (south)
{60,61,62,69,70,71,78,79,80} // region 8, lower right right (South East)
};
public void init(String puzzle)
{
for (int i=0;i<81;i++)
{
cells[i]=new ArrayList<Integer>();
String s=puzzle.substring(i,i+1);
if (s.equals(".")) // unsolved cells, all values are possible
for (int digit=1;digit<=9;digit++) cells[i].add(digit);
else // solved cells, only one possible value
cells[i].add(Integer.parseInt(s));
}
}
// display all possible of the grid
public void printGrid()
{
String delimiter="";
for (int i=0;i<81;i++)
{
String s="";
for (int j=0;j<cells[i].size();j++)
{
s+=cells[i].get(j);
}
// make sure each cell contains exactly 8 character
for (int j=0;j<8-cells[i].size();j++) s+=" ";
if (s.length()>8) s="ALL "; // overflow
s=delimiter+s;
delimiter="|";
System.out.print(s);
if ((i+1)%9==0) { System.out.println(); delimiter=""; }
}
}
// eliminate duplicate digit of the same rows
public void rowElimination()
{
for (int i=0;i<81;i++) // loop over all cells
{
int n=cells[i].size(); // get number of possible values of current cell
if (n==1) // this is a solved cell
{
int solvedDigit=cells[i].get(0);
int rowNumber=i/9; // which row does the current cell belong to ?
for (int j=0;j<9;j++) // loop over all cells in the affected row
{
int cellNum=row[rowNumber][j];
// all other cells in the row cannot contain the solved digit
if (cellNum!=i) cells[cellNum].remove(new Integer(solvedDigit));
}
}
}
}
public static void main(String[] args) throws Exception
{
// change this String for another puzzle
String puzzle= ".4.61..9."+
".7..5...."+
"1.3948..."+
"961.....2"+
"..58261.."+
"8.....365"+
"...3792.4"+
"....8..5."+
".8..65.3.";
SudokuSolver solver=new SudokuSolver();
solver.init(puzzle);
solver.printGrid();
solver.rowElimination();
System.out.println("After row elimination:");
solver.printGrid();
}
}
Column Elimination
This is very similar to the row elimination, if a cell is solved, just remove the solved digit from the possible values of all cells in the same column.
// eliminate duplicate digit of the same column
public void columnElimination()
{
for (int i=0;i<81;i++) // loop over all cells
{
int n=cells[i].size(); // get number of possible values of current cell
if (n==1) // this is a solved cell
{
int solvedDigit=cells[i].get(0);
int columnNumber=i % 9; // which column does the current cell belong to ?
for (int j=0;j<9;j++) // loop over all cells in the affected column
{
int cellNum=column[columnNumber][j];
// all other cells in the column cannot contain the solved digit
if (cellNum!=i) cells[cellNum].remove(new Integer(solvedDigit));
}
}
}
}
The problem is further simplified after column elimination :
2357 |4 |278 |6 |1 |237 |578 |9 |378 2346 |7 |24689 |124 |5 |1234 |4689 |1248 |13689 1 |25 |3 |9 |4 |8 |567 |27 |67 9 |6 |1 |457 |3 |347 |4578 |478 |2 347 |39 |5 |8 |2 |6 |1 |47 |379 8 |129 |2479 |1247 |9 |1247 |3 |6 |5 56 |15 |68 |3 |7 |9 |2 |18 |4 23467 |1239 |24679 |1247 |8 |12347 |4679 |5 |13679 247 |8 |2479 |1247 |6 |5 |479 |3 |179
Region Elimination
Each region cannot contains duplicate digit. It is a little bit tricky to find which region a cell belongs to. For example, cell number 0 belongs to region 0 (upper left) cell number 80 belongs to region 8 (lower right) Finding the row number and column number are relatively easy.
Actually, the region number can be found from rowNumber and columnNumber :int rowNumber = cellIndex / 9; // which row does the current cell belong to ? int columnNumber=cellIndex % 9; // which column does the current cell belong to ?
Think carefully and make sure you understand the above formula. Source code for region elimination :int regionNumber=3*(rowNumber/3) + columnNumber/3;
// eliminate duplicate digit of the same region
public void regionElimination()
{
for (int i=0;i<81;i++) // loop over all cells
{
int n=cells[i].size(); // get number of possible values of current cell
if (n==1) // this is a solved cell
{
int solvedDigit=cells[i].get(0);
int rowNumber = i / 9; // which row does the current cell belong to ?
int columnNumber=i % 9; // which column does the current cell belong to ?
int regionNumber=3*(rowNumber/3) + columnNumber/3;
for (int j=0;j<9;j++) // loop over all cells in the affected region
{
int cellNum=region[regionNumber][j];
// all other cells in the region cannot contain the solved digit
if (cellNum!=i) cells[cellNum].remove(new Integer(solvedDigit));
}
}
}
}
After region elimination, the problem is further simplifed to :
25 |4 |28 |6 |1 |237 |578 |9 |378 26 |7 |2689 |2 |5 |23 |468 |1248 |1368 1 |25 |3 |9 |4 |8 |567 |27 |67 9 |6 |1 |457 |3 |47 |478 |478 |2 47 |3 |5 |8 |2 |6 |1 |47 |79 8 |2 |47 |147 |9 |147 |3 |6 |5 56 |15 |6 |3 |7 |9 |2 |18 |4 23467 |1239 |24679 |124 |8 |124 |679 |5 |1679 247 |8 |2479 |124 |6 |5 |79 |3 |179
Note that newly solved cells are generated after the three eliminations. Repeat the process until no more newly solved cells are found. Some problems can be solved by eliminations only, some cannot. For those puzzles which cannot be solved by eliminations only, we would still simplify the problem by elimination, then solve them by a trial and error algorithm. Full source code and solution of the puzzles follows :
/******************************************************************************
* File : SudokuSolver.java
* Author : http://java.macteki.com/
* Description :
* A sudoku solver.
* Tested with : JDK 1.6
******************************************************************************/
import java.util.ArrayList;
import java.lang.reflect.Array;
public class SudokuSolver
{
// structure for holding sudoku grid
ArrayList<Integer>[] cells=new ArrayList[81];
private int[][] row=new int[][] {
{ 0, 1, 2, 3, 4, 5, 6, 7, 8}, // row 0
{ 9,10,11,12,13,14,15,16,17}, // row 1
{18,19,20,21,22,23,24,25,26}, // row 2
{27,28,29,30,31,32,33,34,35}, // row 3
{36,37,38,39,40,41,42,43,44}, // row 4
{45,46,47,48,49,50,51,52,53}, // row 5
{54,55,56,57,58,59,60,61,62}, // row 6
{63,64,65,66,67,68,69,70,71}, // row 7
{72,73,74,75,76,77,78,79,80} // row 8
};
private int[][] column=new int[][] {
{ 0, 9,18,27,36,45,54,63,72}, // column 0
{ 1,10,19,28,37,46,55,64,73}, // column 1
{ 2,11,20,29,38,47,56,65,74}, // column 2
{ 3,12,21,30,39,48,57,66,75}, // column 3
{ 4,13,22,31,40,49,58,67,76}, // column 4
{ 5,14,23,32,41,50,59,68,77}, // column 5
{ 6,15,24,33,42,51,60,69,78}, // column 6
{ 7,16,25,34,43,52,61,70,79}, // column 7
{ 8,17,26,35,44,53,62,71,80} // column 8
};
private int[][] region=new int[][] {
{ 0, 1, 2, 9,10,11,18,19,20}, // region 0, upper left region (North West)
{ 3, 4, 5,12,13,14,21,22,23}, // region 1, top region (North)
{ 6, 7, 8,15,16,17,24,25,26}, // region 2, upper right region (North East)
{27,28,29,36,37,38,45,46,47}, // region 3, left region (west)
{30,31,32,39,40,41,48,49,50}, // region 4, middle region
{33,34,35,42,43,44,51,52,53}, // region 5, right region (east)
{54,55,56,63,64,65,72,73,74}, // region 6, lower left region (South West)
{57,58,59,66,67,68,75,76,77}, // region 7, bottom region (south)
{60,61,62,69,70,71,78,79,80} // region 8, lower right right (South East)
};
public void init(String puzzle)
{
for (int i=0;i<81;i++)
{
cells[i]=new ArrayList<Integer>();
String s=puzzle.substring(i,i+1);
if (s.equals(".")) // unsolved cells, all values are possible
for (int digit=1;digit<=9;digit++) cells[i].add(digit);
else // solved cells, only one possible value
cells[i].add(Integer.parseInt(s));
}
}
// display all possible of the grid
public void printGrid()
{
String delimiter="";
for (int i=0;i<81;i++)
{
String s="";
for (int j=0;j<cells[i].size();j++)
{
s+=cells[i].get(j);
}
// make sure each cell contains exactly 8 character
for (int j=0;j<8-cells[i].size();j++) s+=" ";
if (s.length()>8) s="ALL "; // overflow
s=delimiter+s;
delimiter="|";
System.out.print(s);
if ((i+1)%9==0) { System.out.println(); delimiter=""; }
}
}
// eliminate duplicate digit of the same row
public boolean rowElimination()
{
boolean newSolved=false;
for (int i=0;i<81;i++) // loop over all cells
{
int n=cells[i].size(); // get number of possible values of current cell
if (n==1) // this is a solved cell
{
Integer solvedDigit=cells[i].get(0);
int rowNumber=i/9; // which row does the current cell belong to ?
for (int j=0;j<9;j++) // loop over all cells in the affected row
{
int cellNum=row[rowNumber][j];
// all other cells in the row cannot contain the solved digit
if (cellNum!=i && cells[cellNum].contains(solvedDigit))
{
cells[cellNum].remove(solvedDigit);
if (cells[cellNum].size()==1) newSolved=true; // newly solved cell found
}
}
}
}
return newSolved;
}
// eliminate duplicate digit of the same column
public boolean columnElimination()
{
boolean newSolved=false;
for (int i=0;i<81;i++) // loop over all cells
{
int n=cells[i].size(); // get number of possible values of current cell
if (n==1) // this is a solved cell
{
Integer solvedDigit=cells[i].get(0);
int columnNumber=i % 9; // which column does the current cell belong to ?
for (int j=0;j<9;j++) // loop over all cells in the affected column
{
int cellNum=column[columnNumber][j];
// all other cells in the column cannot contain the solved digit
if (cellNum!=i && cells[cellNum].contains(solvedDigit))
{
cells[cellNum].remove(solvedDigit);
if (cells[cellNum].size()==1) newSolved=true; // newly solved cell found
}
}
}
}
return newSolved;
}
// eliminate duplicate digit of the same region
public boolean regionElimination()
{
boolean newSolved=false;
for (int i=0;i<81;i++) // loop over all cells
{
int n=cells[i].size(); // get number of possible values of current cell
if (n==1) // this is a solved cell
{
Integer solvedDigit=cells[i].get(0);
int rowNumber = i / 9; // which row does the current cell belong to ?
int columnNumber=i % 9; // which column does the current cell belong to ?
int regionNumber=3*(rowNumber/3) + columnNumber/3;
for (int j=0;j<9;j++) // loop over all cells in the affected region
{
int cellNum=region[regionNumber][j];
// all other cells in the region cannot contain the solved digit
if (cellNum!=i && cells[cellNum].contains(solvedDigit))
{
cells[cellNum].remove(solvedDigit);
if (cells[cellNum].size()==1) newSolved=true; // newly solved cell found
}
}
}
}
return newSolved;
}
public void solveByElimination()
{
boolean newCellSolved=false;
while (true)
{
newCellSolved=false;
if (rowElimination()) newCellSolved=true;
if (columnElimination()) newCellSolved=true;
if (regionElimination()) newCellSolved=true;
if (!newCellSolved) break; // no newly solved cell generated, quit
}
}
public static void main(String[] args) throws Exception
{
// change this String for another puzzle
String puzzle= ".4.61..9."+
".7..5...."+
"1.3948..."+
"961.....2"+
"..58261.."+
"8.....365"+
"...3792.4"+
"....8..5."+
".8..65.3.";
SudokuSolver solver=new SudokuSolver();
solver.init(puzzle);
solver.printGrid();
solver.solveByElimination();
System.out.println("After all eliminations:");
solver.printGrid();
}
}
Solution of the problems :
2 |4 |8 |6 |1 |7 |5 |9 |3 6 |7 |9 |2 |5 |3 |4 |1 |8 1 |5 |3 |9 |4 |8 |7 |2 |6 9 |6 |1 |5 |3 |4 |8 |7 |2 7 |3 |5 |8 |2 |6 |1 |4 |9 8 |2 |4 |7 |9 |1 |3 |6 |5 5 |1 |6 |3 |7 |9 |2 |8 |4 3 |9 |7 |4 |8 |2 |6 |5 |1 4 |8 |2 |1 |6 |5 |9 |3 |7Summary
This article presents a java sample for solving sudoku by method of elimination.
Note that some complex puzzle cannot be solved by this sample. However, those puzzle would be highly simplified by the program and it is not difficult to solve it by a trial and error method, which will be presented in the next article.
Thanks for reading. Comments are welcome.
How do you write java code in html, do you use some software like mathjax for code?
ReplyDeleteI am using syntax highlighter by Alex Gorbatchev
Deletehttp://alexgorbatchev.com/SyntaxHighlighter/manual/brushes/java.html