Thu, 31 Jan 2013 18:44:44 +0100
added solving algorithm
universe@3 | 1 | /* |
universe@3 | 2 | * Copyright 2013 Mike Becker. All rights reserved. |
universe@3 | 3 | * |
universe@3 | 4 | * Redistribution and use in source and binary forms, with or without |
universe@3 | 5 | * modification, are permitted provided that the following conditions are met: |
universe@3 | 6 | * |
universe@3 | 7 | * 1. Redistributions of source code must retain the above copyright |
universe@3 | 8 | * notice, this list of conditions and the following disclaimer. |
universe@3 | 9 | * |
universe@3 | 10 | * 2. Redistributions in binary form must reproduce the above copyright |
universe@3 | 11 | * notice, this list of conditions and the following disclaimer in the |
universe@3 | 12 | * documentation and/or other materials provided with the distribution. |
universe@3 | 13 | * |
universe@3 | 14 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
universe@3 | 15 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
universe@3 | 16 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
universe@3 | 17 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
universe@3 | 18 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
universe@3 | 19 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
universe@3 | 20 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
universe@3 | 21 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
universe@3 | 22 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
universe@3 | 23 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
universe@3 | 24 | * POSSIBILITY OF SUCH DAMAGE. |
universe@3 | 25 | */ |
universe@3 | 26 | |
universe@2 | 27 | package de.uapcore.sudoku; |
universe@2 | 28 | |
universe@7 | 29 | import java.util.ArrayList; |
universe@7 | 30 | import java.util.List; |
universe@7 | 31 | |
universe@2 | 32 | /** |
universe@2 | 33 | * |
universe@2 | 34 | * @author mike |
universe@2 | 35 | */ |
universe@2 | 36 | public final class Solver { |
universe@2 | 37 | |
universe@2 | 38 | public Solver() { |
universe@2 | 39 | } |
universe@2 | 40 | |
universe@7 | 41 | private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) { |
universe@7 | 42 | Integer c = candidates[x][y].remove(0); |
universe@7 | 43 | f.setCellValue(x, y, c); |
universe@7 | 44 | f.setCellModified(x, y, true); |
universe@7 | 45 | for (int i = 0 ; i < 9 ; i++) { |
universe@7 | 46 | candidates[x][i].remove(c); |
universe@7 | 47 | candidates[i][y].remove(c); |
universe@7 | 48 | } |
universe@7 | 49 | for (int i = 0 ; i < 3 ; i++) { |
universe@7 | 50 | for (int j = 0 ; j < 3 ; j++) { |
universe@7 | 51 | candidates[x-x%3+i][y-y%3+j].remove(c); |
universe@7 | 52 | } |
universe@7 | 53 | } |
universe@7 | 54 | return c; |
universe@7 | 55 | } |
universe@7 | 56 | |
universe@7 | 57 | private void makeBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) { |
universe@7 | 58 | for (int x = 0 ; x < 9 ; x++) { |
universe@7 | 59 | for (int y = 0 ; y < 9 ; y++) { |
universe@7 | 60 | candidatesBackup[x][y] = new ArrayList<>(9); |
universe@7 | 61 | candidatesBackup[x][y].addAll(candidates[x][y]); |
universe@7 | 62 | } |
universe@7 | 63 | } |
universe@7 | 64 | } |
universe@7 | 65 | |
universe@7 | 66 | private void makeBackup(Field f, int[][] fieldBackup) { |
universe@7 | 67 | for (int x = 0 ; x < 9 ; x++) { |
universe@7 | 68 | for (int y = 0 ; y < 9 ; y++) { |
universe@7 | 69 | fieldBackup[x][y] = f.getCellValue(x, y); |
universe@7 | 70 | } |
universe@7 | 71 | } |
universe@7 | 72 | } |
universe@7 | 73 | |
universe@7 | 74 | private void restoreBackup(Field f, int[][] fieldBackup) { |
universe@7 | 75 | for (int x = 0 ; x < 9 ; x++) { |
universe@7 | 76 | for (int y = 0 ; y < 9 ; y++) { |
universe@7 | 77 | f.setCellValue(x, y, fieldBackup[x][y]); |
universe@7 | 78 | } |
universe@7 | 79 | } |
universe@7 | 80 | } |
universe@7 | 81 | |
universe@7 | 82 | private void restoreBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) { |
universe@7 | 83 | for (int x = 0 ; x < 9 ; x++) { |
universe@7 | 84 | for (int y = 0 ; y < 9 ; y++) { |
universe@7 | 85 | candidates[x][y].clear(); |
universe@7 | 86 | candidates[x][y].addAll(candidatesBackup[x][y]); |
universe@7 | 87 | } |
universe@7 | 88 | } |
universe@7 | 89 | } |
universe@7 | 90 | |
universe@7 | 91 | private boolean solve(Field f, List<Integer>[][] candidates) { |
universe@7 | 92 | |
universe@7 | 93 | // Make backup |
universe@7 | 94 | List<Integer>[][] candidatesBackup = new List[9][9]; |
universe@7 | 95 | int[][] fieldBackup = new int[9][9]; |
universe@7 | 96 | makeBackup(candidates, candidatesBackup); |
universe@7 | 97 | makeBackup(f, fieldBackup); |
universe@7 | 98 | |
universe@7 | 99 | // Fill in distinct solutions |
universe@7 | 100 | boolean fillDistinct; |
universe@7 | 101 | do { |
universe@7 | 102 | fillDistinct = false; |
universe@7 | 103 | for (int x = 0 ; x < 9 ; x++) { |
universe@7 | 104 | for (int y = 0 ; y < 9 ; y++) { |
universe@7 | 105 | if (f.isCellEmpty(x, y) && candidates[x][y].size() == 1) { |
universe@7 | 106 | fillInCandidate(f, candidates, x, y); |
universe@7 | 107 | fillDistinct = true; |
universe@7 | 108 | } |
universe@7 | 109 | } |
universe@7 | 110 | } |
universe@7 | 111 | } while (fillDistinct); |
universe@7 | 112 | |
universe@7 | 113 | // Try out remaining candidates |
universe@7 | 114 | for (int x = 0 ; x < 9 ; x++) { |
universe@7 | 115 | for (int y = 0 ; y < 9 ; y++) { |
universe@7 | 116 | if (f.isCellEmpty(x, y)) { |
universe@7 | 117 | while (candidates[x][y].size() > 0) { |
universe@7 | 118 | List<Integer>[][] cb = new List[9][9]; |
universe@7 | 119 | makeBackup(candidates, cb); |
universe@7 | 120 | Integer c = fillInCandidate(f, candidates, x, y); |
universe@7 | 121 | if (solve(f, candidates)) { |
universe@7 | 122 | break; |
universe@7 | 123 | } else { |
universe@7 | 124 | f.clearCellValue(x, y); |
universe@7 | 125 | restoreBackup(candidates, cb); |
universe@7 | 126 | // Remove current candidate anyway |
universe@7 | 127 | candidates[x][y].remove(c); |
universe@7 | 128 | } |
universe@7 | 129 | } |
universe@7 | 130 | } |
universe@7 | 131 | if (f.isCellEmpty(x, y)) { |
universe@7 | 132 | restoreBackup(f, fieldBackup); |
universe@7 | 133 | restoreBackup(candidates, candidatesBackup); |
universe@7 | 134 | return false; |
universe@7 | 135 | } |
universe@7 | 136 | } |
universe@7 | 137 | } |
universe@7 | 138 | |
universe@7 | 139 | return true; |
universe@7 | 140 | } |
universe@7 | 141 | |
universe@7 | 142 | public boolean solve(Field f) { |
universe@7 | 143 | |
universe@7 | 144 | // Calculate initial candidates |
universe@7 | 145 | List<Integer> candidates[][] = new List[9][9]; |
universe@7 | 146 | for (int x = 0 ; x < 9 ; x++) { |
universe@7 | 147 | for (int y = 0 ; y < 9 ; y++) { |
universe@7 | 148 | candidates[x][y] = new ArrayList<>(9); |
universe@7 | 149 | if (f.getCellValue(x, y) == 0) { |
universe@7 | 150 | // All numbers are candidates |
universe@7 | 151 | for (int c = 1 ; c <= 9 ; c++) { |
universe@7 | 152 | candidates[x][y].add(c); |
universe@7 | 153 | } |
universe@7 | 154 | // Remove row duplicates |
universe@7 | 155 | int[] line = f.getRow(y); |
universe@7 | 156 | for (Integer c : line) { |
universe@7 | 157 | candidates[x][y].remove(c); |
universe@7 | 158 | } |
universe@7 | 159 | // Remove column duplicates |
universe@7 | 160 | line = f.getColumn(x); |
universe@7 | 161 | for (Integer c : line) { |
universe@7 | 162 | candidates[x][y].remove(c); |
universe@7 | 163 | } |
universe@7 | 164 | // Remove square duplicates |
universe@7 | 165 | int[][] square = f.getSquare(x/3, y/3); |
universe@7 | 166 | for (int[] sq : square) { |
universe@7 | 167 | for (Integer c : sq) { |
universe@7 | 168 | candidates[x][y].remove(c); |
universe@7 | 169 | } |
universe@7 | 170 | } |
universe@7 | 171 | } |
universe@7 | 172 | } |
universe@7 | 173 | } |
universe@7 | 174 | |
universe@7 | 175 | // Backtrack |
universe@7 | 176 | return solve(f, candidates) && complete(f); |
universe@7 | 177 | } |
universe@7 | 178 | |
universe@2 | 179 | public boolean check(Field f) { |
universe@2 | 180 | int line[]; |
universe@2 | 181 | for (int i = 0 ; i < 9 ; i++) { |
universe@5 | 182 | line = f.getRow(i); |
universe@2 | 183 | if (!valid(line)) { |
universe@2 | 184 | return false; |
universe@2 | 185 | } |
universe@5 | 186 | line = f.getColumn(i); |
universe@2 | 187 | if (!valid(line)) { |
universe@2 | 188 | return false; |
universe@2 | 189 | } |
universe@2 | 190 | } |
universe@2 | 191 | |
universe@2 | 192 | int square[][]; |
universe@2 | 193 | for (int x = 0 ; x < 3 ; x++) { |
universe@2 | 194 | for (int y = 0 ; y < 3 ; y++) { |
universe@5 | 195 | square = f.getSquare(x, y); |
universe@2 | 196 | if (!valid(square)) { |
universe@2 | 197 | return false; |
universe@2 | 198 | } |
universe@2 | 199 | } |
universe@2 | 200 | } |
universe@2 | 201 | |
universe@2 | 202 | return true; |
universe@2 | 203 | } |
universe@2 | 204 | |
universe@7 | 205 | private boolean complete(Field f) { |
universe@7 | 206 | for (int i = 0 ; i < 9 ; i++) { |
universe@7 | 207 | if (!complete(f.getRow(i))) { |
universe@7 | 208 | return false; |
universe@7 | 209 | } |
universe@7 | 210 | if (!complete(f.getColumn(i))) { |
universe@7 | 211 | return false; |
universe@7 | 212 | } |
universe@7 | 213 | } |
universe@7 | 214 | for (int x = 0 ; x < 3 ; x++) { |
universe@7 | 215 | for (int y = 0 ; y < 3 ; y++) { |
universe@7 | 216 | if (!complete(f.getSquare(x, y))) { |
universe@7 | 217 | return false; |
universe@7 | 218 | } |
universe@7 | 219 | } |
universe@7 | 220 | } |
universe@7 | 221 | return true; |
universe@7 | 222 | } |
universe@7 | 223 | |
universe@2 | 224 | private boolean complete(int[][] square) { |
universe@2 | 225 | for (int x = 0 ; x < 3 ; x++) { |
universe@2 | 226 | for (int y = 0 ; y < 3 ; y++) { |
universe@2 | 227 | if (square[x][y] == 0) { |
universe@2 | 228 | return false; |
universe@2 | 229 | } |
universe@2 | 230 | } |
universe@2 | 231 | } |
universe@2 | 232 | return true; |
universe@2 | 233 | } |
universe@2 | 234 | |
universe@2 | 235 | private boolean complete(int[] line) { |
universe@2 | 236 | for (int i = 0 ; i < 9 ; i++) { |
universe@2 | 237 | if (line[i] == 0) { |
universe@2 | 238 | return false; |
universe@2 | 239 | } |
universe@2 | 240 | } |
universe@2 | 241 | return true; |
universe@2 | 242 | } |
universe@2 | 243 | |
universe@2 | 244 | private boolean valid(int[] line) { |
universe@5 | 245 | int numbers[]; |
universe@5 | 246 | numbers = new int[9]; |
universe@2 | 247 | for (int i = 0 ; i < 9 ; i++) { |
universe@2 | 248 | int l = line[i]-1; |
universe@2 | 249 | if (l >= 0) { |
universe@5 | 250 | if ((++numbers[l]) > 1) { |
universe@2 | 251 | return false; |
universe@2 | 252 | } |
universe@2 | 253 | } |
universe@2 | 254 | } |
universe@2 | 255 | |
universe@2 | 256 | return true; |
universe@2 | 257 | } |
universe@2 | 258 | |
universe@2 | 259 | private boolean valid(int[][] square) { |
universe@2 | 260 | int[] line = new int[9]; |
universe@2 | 261 | for (int x = 0 ; x < 3 ; x++) { |
universe@5 | 262 | System.arraycopy(square[x], 0, line, 3*x, 3); |
universe@2 | 263 | } |
universe@2 | 264 | return valid(line); |
universe@2 | 265 | } |
universe@2 | 266 | } |