comparison: src/de/uapcore/sudoku/Solver.java
src/de/uapcore/sudoku/Solver.java
- changeset 9
- 576e7a2861ae
- parent 7
- 2c0a2766461c
equal
deleted
inserted
replaced
| 8:e70a0e3555fb | 9:576e7a2861ae |
|---|---|
| 1 /* | |
| 2 * Copyright 2013 Mike Becker. All rights reserved. | |
| 3 * | |
| 4 * Redistribution and use in source and binary forms, with or without | |
| 5 * modification, are permitted provided that the following conditions are met: | |
| 6 * | |
| 7 * 1. Redistributions of source code must retain the above copyright | |
| 8 * notice, this list of conditions and the following disclaimer. | |
| 9 * | |
| 10 * 2. Redistributions in binary form must reproduce the above copyright | |
| 11 * notice, this list of conditions and the following disclaimer in the | |
| 12 * documentation and/or other materials provided with the distribution. | |
| 13 * | |
| 14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | |
| 15 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
| 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
| 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE | |
| 18 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | |
| 19 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | |
| 20 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | |
| 21 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | |
| 22 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
| 23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | |
| 24 * POSSIBILITY OF SUCH DAMAGE. | |
| 25 */ | |
| 26 | |
| 27 package de.uapcore.sudoku; | |
| 28 | |
| 29 import java.util.ArrayList; | |
| 30 import java.util.List; | |
| 31 | |
| 32 /** | |
| 33 * | |
| 34 * @author mike | |
| 35 */ | |
| 36 public final class Solver { | |
| 37 | |
| 38 public Solver() { | |
| 39 } | |
| 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); | |
| 177 } | |
| 178 | |
| 179 public boolean check(Field f) { | |
| 180 int line[]; | |
| 181 for (int i = 0 ; i < 9 ; i++) { | |
| 182 line = f.getRow(i); | |
| 183 if (!valid(line)) { | |
| 184 return false; | |
| 185 } | |
| 186 line = f.getColumn(i); | |
| 187 if (!valid(line)) { | |
| 188 return false; | |
| 189 } | |
| 190 } | |
| 191 | |
| 192 int square[][]; | |
| 193 for (int x = 0 ; x < 3 ; x++) { | |
| 194 for (int y = 0 ; y < 3 ; y++) { | |
| 195 square = f.getSquare(x, y); | |
| 196 if (!valid(square)) { | |
| 197 return false; | |
| 198 } | |
| 199 } | |
| 200 } | |
| 201 | |
| 202 return true; | |
| 203 } | |
| 204 | |
| 205 private boolean valid(int[] line) { | |
| 206 int numbers[]; | |
| 207 numbers = new int[9]; | |
| 208 for (int i = 0 ; i < 9 ; i++) { | |
| 209 int l = line[i]-1; | |
| 210 if (l >= 0) { | |
| 211 if ((++numbers[l]) > 1) { | |
| 212 return false; | |
| 213 } | |
| 214 } | |
| 215 } | |
| 216 | |
| 217 return true; | |
| 218 } | |
| 219 | |
| 220 private boolean valid(int[][] square) { | |
| 221 int[] line = new int[9]; | |
| 222 for (int x = 0 ; x < 3 ; x++) { | |
| 223 System.arraycopy(square[x], 0, line, 3*x, 3); | |
| 224 } | |
| 225 return valid(line); | |
| 226 } | |
| 227 } |
