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

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

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 :- Find next unsolved cell in the puzzle (cell with more than one possible values)
- We will name this cell as 'X'. Fill cell X with one of the possible value(a trial)
- call solveByElimination()
- If the puzzle is solved, return true
- check for conflict (a puzzle is in conflict state if the elimination process eliminates all possible values of some cells)
- 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

- If the puzzle is not solved, fill cell X with next possible value, then go to step 3

- If all possible values of cell X is tried, return false, this tells the parent that the puzzle cannot be solved

The solution of the sample puzzle presented above is :// 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. }

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 : trueMore 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.
## No comments:

## Post a Comment