How to write a sudoku generator ?

The idea is to start with an empty grid. Then repeatedly fill a random digit to a random cell, until a valid puzzle is produced. A puzzle is valid if it has a unique solution. The number of solution can be found using a modified version of SudokuSolver.java described in the previous article.

To compile :

javac SudokuGenerator.java

To run, you must supply an integer seed :

java SudokuGenerator 0

The file out.txt will be generated :

Puzzle in plain text format :
.....2...
1.6....39
....6.5.1
....9....
.........
..9.2....
.9...4...
.....5...
...6.8...

Puzzle in Java String format :
    String puzzle = ".....2..."+
                    "1.6....39"+
                    "....6.5.1"+
                    "....9...."+
                    "........."+
                    "..9.2...."+
                    ".9...4..."+
                    ".....5..."+
                    "...6.8...";

Supplying a different seed will generate a different puzzle.

Full source can be found here : SudokuGenerator.java

Thanks for reading. Comments are welcome.

Patching

A reader's comment pointed out that there are two issues.
The fix is now available at :
Sudoku Generator - A Bug Fixing Patch

Sudoku Solver Part 2

The previous article presents how to solve a sudoku puzzle by the method of elimination.

The method of elimination is derived directly from the rule of sudoku :

1. Row Elimination : No cells in the same row are allowed to contain duplicate digits
2. Column Elimination : No cells in the same column are allowed to contain duplicate digits
3. Region Elimination : No cells in a region are allowed to contain duplicate digits

The above elimination process can solve some simple sudoku puzzles. Some complex puzzles cannot be solved, but would be simplified by the elimination process.

For simple puzzle solvable by the method of elimination, the sudoku solver can quit immediately.
The following is a puzzle solvable by elimination only :

//
    String puzzle= ".4.61..9."+
                   ".7..5...."+
                   "1.3948..."+
                   "961.....2"+
                   "..58261.."+
                   "8.....365"+
                   "...3792.4"+
                   "....8..5."+
                   ".8..65.3.";

And the solution is :

After all eliminations:
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       |7

The following is a puzzle not solvable by elimination alone :

//
    String puzzle= "9.1..4..."+
                   "......296"+
                   ".8....4.7"+
                   "21...6..."+
                   "..6.23..4"+
                   ".5.94...."+
                   ".....8.4."+
                   "....7..3."+
                   "....316.5";

The result after all eliminations is :

After all eliminations:
9       |2367    |1       |23678   |68      |4       |358     |58      |38

347     |347     |347     |1378    |18      |5       |2       |9       |6

356     |8       |235     |1236    |169     |29      |4       |15      |7

2       |1       |34789   |58      |58      |6       |35789   |578     |389

78      |79      |6       |158     |2       |3       |15789   |1578    |4

38      |5       |38      |9       |4       |7       |138     |1268    |1238

13567   |23679   |23579   |256     |569     |8       |179     |4       |129

14568   |2469    |24589   |2456    |7       |29      |189     |3       |1289

478     |2479    |24789   |24      |3       |1       |6       |278     |5

Puzzle solvable by method of eliminations : false

Checking puzzle states

For the above simplified puzzle, it can be solved by a recursive "trial and error" algorithm.
Before entering the recursive search routine, we need to check whether the puzzle had already been solved by the method of eliminations.

A straight forward way is just to count the number of possible values in every cell, if all of them have only one possible value, then all cells are solved cells.

// check whether the puzzle is solved
  public boolean isSolved()
  {
    boolean solved=true;
    for (int i=0;i<81;i++)
    {
      if (cells[i].size()!=1) { solved=false; break; }
    }
    return solved;
  }

Method of Recursion

This method is based on trial an error. The algorithm of the Recursive Solver is :

1. Find next unsolved cell in the puzzle (cell with more than one possible values)
2. We will name this cell as 'X'. Fill cell X with one of the possible value(a trial)
3. call solveByElimination()
4. If the puzzle is solved, return true
5. check for conflict (a puzzle is in conflict state if the elimination process eliminates all possible values of some cells)
6. If the puzzle is not solved and not in conflict state, call the recursive solver to do a trial and error on the next unsolved cell
   
7. If the puzzle is not solved, fill cell X with next possible value, then go to step 3
   
8. If all possible values of cell X is tried, return false, this tells the parent that the puzzle cannot be solved
   

The actual java code follows :

//
  public boolean solveByRecursion()
  {
    // before doing anything, backup the puzzle first
    ArrayList<Integer>[] backupCells=new ArrayList[81];
    for (int i=0;i<81;i++) // allocate back structure
    {
      backupCells[i]=new ArrayList();
    }
 
    cellCopy(cells, backupCells);  // backup
    
    // get next unsolved cell
    int unsolvedCellIndex=-1;
    for (int i=0;i<81;i++)
    {
      if (cells[i].size()>1) { unsolvedCellIndex=i; break; }
    }

    // no unsolved cell, the puzzle is solved
    if (unsolvedCellIndex==-1) return true;

    for (int j=0;j<cells[unsolvedCellIndex].size();j++) // try all possible digits
    {       
      Integer digit = cells[unsolvedCellIndex].get(j); 
      cells[unsolvedCellIndex].clear();  // clear all values
      cells[unsolvedCellIndex].add(digit);  // then fill it with only one value         
      solveByElimination();
      if (isSolved()) return true;  // solved
      if (!isConflict()) 
      {
        // The unsolved cell is filled with a trial value, but the puzzle is not solved,
        // call myself recursively to do a trial and error on another unsolved cell.
        if (solveByRecursion()) return true; // solved        
      }
      // the trial digit cannot solve the puzzle
      cellCopy(backupCells,cells); // restore from backup, try next digit
    }
    // all values of a cell have been tried 
    return false;   // cannot solve this way.
  }

The solution of the sample puzzle presented above is :

9       |2       |1       |7       |6       |4       |3       |5       |8       
4       |3       |7       |8       |1       |5       |2       |9       |6       
6       |8       |5       |3       |9       |2       |4       |1       |7       
2       |1       |4       |5       |8       |6       |9       |7       |3       
7       |9       |6       |1       |2       |3       |5       |8       |4       
3       |5       |8       |9       |4       |7       |1       |6       |2       
1       |6       |3       |2       |5       |8       |7       |4       |9       
5       |4       |2       |6       |7       |9       |8       |3       |1       
8       |7       |9       |4       |3       |1       |6       |2       |5       
Puzzle solvable by method of recursion : true

More sample puzzles here :

// sample puzzle 1
    String puzzle= ".9..76.1."+
                   ".374....."+
                   ".......57"+
                   ".2..54..."+
                   "....6.9.5"+
                   ".1.9.3..."+
                   ".5.31..4."+
                   "..4..2..."+
                   "1.9....8.";

// sample puzzle 2
   String puzzle= "........."+
                  ".13.94..8"+
                  "8..5.2..."+
                  ".498..2.7"+
                  ".....1.83"+
                  "13......5"+
                  "2...7...6"+
                  ".6......."+
                  "..72.53..";

The full source code can be view here : SudokuSolver.java

Thanks for reading. Comments are welcome.

How to write a sudoku solver ?

Sudoku is a number-placement puzzle.

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       |12479

The 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.

int rowNumber = cellIndex / 9;    // which row does the current cell belong to ?        
int columnNumber=cellIndex % 9;   // which column does the current cell belong to ?        

Actually, the region number can be found from rowNumber and columnNumber :

int regionNumber=3*(rowNumber/3) + columnNumber/3;

Think carefully and make sure you understand the above formula. Source code for region elimination :

// 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       |7

Summary

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.