comparison: src/de/uapcore/sudoku/Solver.java
src/de/uapcore/sudoku/Solver.java
- changeset 7
- 2c0a2766461c
- parent 5
- 8ddf4af937d7
- child 8
- e70a0e3555fb
equal
deleted
inserted
replaced
| 6:5bab2e971333 | 7:2c0a2766461c |
|---|---|
| 24 * POSSIBILITY OF SUCH DAMAGE. | 24 * POSSIBILITY OF SUCH DAMAGE. |
| 25 */ | 25 */ |
| 26 | 26 |
| 27 package de.uapcore.sudoku; | 27 package de.uapcore.sudoku; |
| 28 | 28 |
| 29 import java.util.ArrayList; | |
| 30 import java.util.List; | |
| 31 | |
| 29 /** | 32 /** |
| 30 * | 33 * |
| 31 * @author mike | 34 * @author mike |
| 32 */ | 35 */ |
| 33 public final class Solver { | 36 public final class Solver { |
| 34 | 37 |
| 35 public Solver() { | 38 public Solver() { |
| 36 } | 39 } |
| 37 | 40 |
| 41 private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) { | |
| 42 Integer c = candidates[x][y].remove(0); | |
| 43 f.setCellValue(x, y, c); | |
| 44 f.setCellModified(x, y, true); | |
| 45 for (int i = 0 ; i < 9 ; i++) { | |
| 46 candidates[x][i].remove(c); | |
| 47 candidates[i][y].remove(c); | |
| 48 } | |
| 49 for (int i = 0 ; i < 3 ; i++) { | |
| 50 for (int j = 0 ; j < 3 ; j++) { | |
| 51 candidates[x-x%3+i][y-y%3+j].remove(c); | |
| 52 } | |
| 53 } | |
| 54 return c; | |
| 55 } | |
| 56 | |
| 57 private void makeBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) { | |
| 58 for (int x = 0 ; x < 9 ; x++) { | |
| 59 for (int y = 0 ; y < 9 ; y++) { | |
| 60 candidatesBackup[x][y] = new ArrayList<>(9); | |
| 61 candidatesBackup[x][y].addAll(candidates[x][y]); | |
| 62 } | |
| 63 } | |
| 64 } | |
| 65 | |
| 66 private void makeBackup(Field f, int[][] fieldBackup) { | |
| 67 for (int x = 0 ; x < 9 ; x++) { | |
| 68 for (int y = 0 ; y < 9 ; y++) { | |
| 69 fieldBackup[x][y] = f.getCellValue(x, y); | |
| 70 } | |
| 71 } | |
| 72 } | |
| 73 | |
| 74 private void restoreBackup(Field f, int[][] fieldBackup) { | |
| 75 for (int x = 0 ; x < 9 ; x++) { | |
| 76 for (int y = 0 ; y < 9 ; y++) { | |
| 77 f.setCellValue(x, y, fieldBackup[x][y]); | |
| 78 } | |
| 79 } | |
| 80 } | |
| 81 | |
| 82 private void restoreBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) { | |
| 83 for (int x = 0 ; x < 9 ; x++) { | |
| 84 for (int y = 0 ; y < 9 ; y++) { | |
| 85 candidates[x][y].clear(); | |
| 86 candidates[x][y].addAll(candidatesBackup[x][y]); | |
| 87 } | |
| 88 } | |
| 89 } | |
| 90 | |
| 91 private boolean solve(Field f, List<Integer>[][] candidates) { | |
| 92 | |
| 93 // Make backup | |
| 94 List<Integer>[][] candidatesBackup = new List[9][9]; | |
| 95 int[][] fieldBackup = new int[9][9]; | |
| 96 makeBackup(candidates, candidatesBackup); | |
| 97 makeBackup(f, fieldBackup); | |
| 98 | |
| 99 // Fill in distinct solutions | |
| 100 boolean fillDistinct; | |
| 101 do { | |
| 102 fillDistinct = false; | |
| 103 for (int x = 0 ; x < 9 ; x++) { | |
| 104 for (int y = 0 ; y < 9 ; y++) { | |
| 105 if (f.isCellEmpty(x, y) && candidates[x][y].size() == 1) { | |
| 106 fillInCandidate(f, candidates, x, y); | |
| 107 fillDistinct = true; | |
| 108 } | |
| 109 } | |
| 110 } | |
| 111 } while (fillDistinct); | |
| 112 | |
| 113 // Try out remaining candidates | |
| 114 for (int x = 0 ; x < 9 ; x++) { | |
| 115 for (int y = 0 ; y < 9 ; y++) { | |
| 116 if (f.isCellEmpty(x, y)) { | |
| 117 while (candidates[x][y].size() > 0) { | |
| 118 List<Integer>[][] cb = new List[9][9]; | |
| 119 makeBackup(candidates, cb); | |
| 120 Integer c = fillInCandidate(f, candidates, x, y); | |
| 121 if (solve(f, candidates)) { | |
| 122 break; | |
| 123 } else { | |
| 124 f.clearCellValue(x, y); | |
| 125 restoreBackup(candidates, cb); | |
| 126 // Remove current candidate anyway | |
| 127 candidates[x][y].remove(c); | |
| 128 } | |
| 129 } | |
| 130 } | |
| 131 if (f.isCellEmpty(x, y)) { | |
| 132 restoreBackup(f, fieldBackup); | |
| 133 restoreBackup(candidates, candidatesBackup); | |
| 134 return false; | |
| 135 } | |
| 136 } | |
| 137 } | |
| 138 | |
| 139 return true; | |
| 140 } | |
| 141 | |
| 142 public boolean solve(Field f) { | |
| 143 | |
| 144 // Calculate initial candidates | |
| 145 List<Integer> candidates[][] = new List[9][9]; | |
| 146 for (int x = 0 ; x < 9 ; x++) { | |
| 147 for (int y = 0 ; y < 9 ; y++) { | |
| 148 candidates[x][y] = new ArrayList<>(9); | |
| 149 if (f.getCellValue(x, y) == 0) { | |
| 150 // All numbers are candidates | |
| 151 for (int c = 1 ; c <= 9 ; c++) { | |
| 152 candidates[x][y].add(c); | |
| 153 } | |
| 154 // Remove row duplicates | |
| 155 int[] line = f.getRow(y); | |
| 156 for (Integer c : line) { | |
| 157 candidates[x][y].remove(c); | |
| 158 } | |
| 159 // Remove column duplicates | |
| 160 line = f.getColumn(x); | |
| 161 for (Integer c : line) { | |
| 162 candidates[x][y].remove(c); | |
| 163 } | |
| 164 // Remove square duplicates | |
| 165 int[][] square = f.getSquare(x/3, y/3); | |
| 166 for (int[] sq : square) { | |
| 167 for (Integer c : sq) { | |
| 168 candidates[x][y].remove(c); | |
| 169 } | |
| 170 } | |
| 171 } | |
| 172 } | |
| 173 } | |
| 174 | |
| 175 // Backtrack | |
| 176 return solve(f, candidates) && complete(f); | |
| 177 } | |
| 178 | |
| 38 public boolean check(Field f) { | 179 public boolean check(Field f) { |
| 39 int line[]; | 180 int line[]; |
| 40 for (int i = 0 ; i < 9 ; i++) { | 181 for (int i = 0 ; i < 9 ; i++) { |
| 41 line = f.getRow(i); | 182 line = f.getRow(i); |
| 42 if (!valid(line)) { | 183 if (!valid(line)) { |
| 59 } | 200 } |
| 60 | 201 |
| 61 return true; | 202 return true; |
| 62 } | 203 } |
| 63 | 204 |
| 205 private boolean complete(Field f) { | |
| 206 for (int i = 0 ; i < 9 ; i++) { | |
| 207 if (!complete(f.getRow(i))) { | |
| 208 return false; | |
| 209 } | |
| 210 if (!complete(f.getColumn(i))) { | |
| 211 return false; | |
| 212 } | |
| 213 } | |
| 214 for (int x = 0 ; x < 3 ; x++) { | |
| 215 for (int y = 0 ; y < 3 ; y++) { | |
| 216 if (!complete(f.getSquare(x, y))) { | |
| 217 return false; | |
| 218 } | |
| 219 } | |
| 220 } | |
| 221 return true; | |
| 222 } | |
| 223 | |
| 64 private boolean complete(int[][] square) { | 224 private boolean complete(int[][] square) { |
| 65 for (int x = 0 ; x < 3 ; x++) { | 225 for (int x = 0 ; x < 3 ; x++) { |
| 66 for (int y = 0 ; y < 3 ; y++) { | 226 for (int y = 0 ; y < 3 ; y++) { |
| 67 if (square[x][y] == 0) { | 227 if (square[x][y] == 0) { |
| 68 return false; | 228 return false; |
