comparison: src/main/java/de/uapcore/sudoku/Solver.java
src/main/java/de/uapcore/sudoku/Solver.java
- changeset 10
- 369903afbb29
- parent 9
- 576e7a2861ae
- child 12
- 1c62c6009161
equal
deleted
inserted
replaced
| 9:576e7a2861ae | 10:369903afbb29 |
|---|---|
| 28 | 28 |
| 29 import java.util.ArrayList; | 29 import java.util.ArrayList; |
| 30 import java.util.List; | 30 import java.util.List; |
| 31 | 31 |
| 32 /** | 32 /** |
| 33 * | 33 * Implements the backtracking algorithm for solving the Sudoku. |
| 34 * @author mike | |
| 35 */ | 34 */ |
| 36 public final class Solver { | 35 public final class Solver { |
| 37 | 36 |
| 38 public Solver() { | |
| 39 } | |
| 40 | |
| 41 private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) { | 37 private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) { |
| 42 Integer c = candidates[x][y].remove(0); | 38 Integer c = candidates[x][y].remove(0); |
| 43 f.setCellValue(x, y, c); | 39 f.setCellValue(x, y, c); |
| 44 f.setCellModified(x, y, true); | 40 f.setCellModified(x, y, true); |
| 45 for (int i = 0 ; i < 9 ; i++) { | 41 for (int i = 0 ; i < 9 ; i++) { |
| 136 } | 132 } |
| 137 } | 133 } |
| 138 | 134 |
| 139 return true; | 135 return true; |
| 140 } | 136 } |
| 141 | 137 |
| 138 /** | |
| 139 * Attempts to solve the given Sudoku field. | |
| 140 * | |
| 141 * The solution, if any, is directly entered into the field. | |
| 142 * All solved fields will be in modified state. | |
| 143 * The already given fields are left untouched. | |
| 144 * | |
| 145 * @param f the field to solve | |
| 146 * @return true if a solution could be found, false if the field is unsolvable | |
| 147 */ | |
| 142 public boolean solve(Field f) { | 148 public boolean solve(Field f) { |
| 143 | 149 |
| 144 // Calculate initial candidates | 150 // Calculate initial candidates |
| 145 List<Integer> candidates[][] = new List[9][9]; | 151 List<Integer> candidates[][] = new List[9][9]; |
| 146 for (int x = 0 ; x < 9 ; x++) { | 152 for (int x = 0 ; x < 9 ; x++) { |
| 173 } | 179 } |
| 174 | 180 |
| 175 // Backtrack | 181 // Backtrack |
| 176 return solve(f, candidates); | 182 return solve(f, candidates); |
| 177 } | 183 } |
| 178 | 184 |
| 185 /** | |
| 186 * Performs a fast check whether any field violates the Sudoku rules. | |
| 187 * | |
| 188 * @param f the field to check | |
| 189 * @return true, if the check succeeds, false otherwise | |
| 190 */ | |
| 179 public boolean check(Field f) { | 191 public boolean check(Field f) { |
| 180 int line[]; | 192 int line[]; |
| 181 for (int i = 0 ; i < 9 ; i++) { | 193 for (int i = 0 ; i < 9 ; i++) { |
| 182 line = f.getRow(i); | 194 line = f.getRow(i); |
| 183 if (!valid(line)) { | 195 if (!valid(line)) { |
