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.