Tue, 28 Jul 2020 13:48:59 +0200
adds more tests
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@10 | 33 | * Implements the backtracking algorithm for solving the Sudoku. |
universe@2 | 34 | */ |
universe@2 | 35 | public final class Solver { |
universe@10 | 36 | |
universe@7 | 37 | private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) { |
universe@7 | 38 | Integer c = candidates[x][y].remove(0); |
universe@7 | 39 | f.setCellValue(x, y, c); |
universe@7 | 40 | f.setCellModified(x, y, true); |
universe@7 | 41 | for (int i = 0 ; i < 9 ; i++) { |
universe@7 | 42 | candidates[x][i].remove(c); |
universe@7 | 43 | candidates[i][y].remove(c); |
universe@7 | 44 | } |
universe@7 | 45 | for (int i = 0 ; i < 3 ; i++) { |
universe@7 | 46 | for (int j = 0 ; j < 3 ; j++) { |
universe@7 | 47 | candidates[x-x%3+i][y-y%3+j].remove(c); |
universe@7 | 48 | } |
universe@7 | 49 | } |
universe@7 | 50 | return c; |
universe@7 | 51 | } |
universe@7 | 52 | |
universe@7 | 53 | private void makeBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) { |
universe@7 | 54 | for (int x = 0 ; x < 9 ; x++) { |
universe@7 | 55 | for (int y = 0 ; y < 9 ; y++) { |
universe@7 | 56 | candidatesBackup[x][y] = new ArrayList<>(9); |
universe@7 | 57 | candidatesBackup[x][y].addAll(candidates[x][y]); |
universe@7 | 58 | } |
universe@7 | 59 | } |
universe@7 | 60 | } |
universe@7 | 61 | |
universe@7 | 62 | private void makeBackup(Field f, int[][] fieldBackup) { |
universe@7 | 63 | for (int x = 0 ; x < 9 ; x++) { |
universe@7 | 64 | for (int y = 0 ; y < 9 ; y++) { |
universe@7 | 65 | fieldBackup[x][y] = f.getCellValue(x, y); |
universe@7 | 66 | } |
universe@7 | 67 | } |
universe@7 | 68 | } |
universe@7 | 69 | |
universe@7 | 70 | private void restoreBackup(Field f, int[][] fieldBackup) { |
universe@7 | 71 | for (int x = 0 ; x < 9 ; x++) { |
universe@7 | 72 | for (int y = 0 ; y < 9 ; y++) { |
universe@7 | 73 | f.setCellValue(x, y, fieldBackup[x][y]); |
universe@7 | 74 | } |
universe@7 | 75 | } |
universe@7 | 76 | } |
universe@7 | 77 | |
universe@7 | 78 | private void restoreBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) { |
universe@7 | 79 | for (int x = 0 ; x < 9 ; x++) { |
universe@7 | 80 | for (int y = 0 ; y < 9 ; y++) { |
universe@7 | 81 | candidates[x][y].clear(); |
universe@7 | 82 | candidates[x][y].addAll(candidatesBackup[x][y]); |
universe@7 | 83 | } |
universe@7 | 84 | } |
universe@7 | 85 | } |
universe@7 | 86 | |
universe@7 | 87 | private boolean solve(Field f, List<Integer>[][] candidates) { |
universe@7 | 88 | |
universe@7 | 89 | // Make backup |
universe@7 | 90 | List<Integer>[][] candidatesBackup = new List[9][9]; |
universe@7 | 91 | int[][] fieldBackup = new int[9][9]; |
universe@7 | 92 | makeBackup(candidates, candidatesBackup); |
universe@7 | 93 | makeBackup(f, fieldBackup); |
universe@7 | 94 | |
universe@7 | 95 | // Fill in distinct solutions |
universe@7 | 96 | boolean fillDistinct; |
universe@7 | 97 | do { |
universe@7 | 98 | fillDistinct = false; |
universe@7 | 99 | for (int x = 0 ; x < 9 ; x++) { |
universe@7 | 100 | for (int y = 0 ; y < 9 ; y++) { |
universe@7 | 101 | if (f.isCellEmpty(x, y) && candidates[x][y].size() == 1) { |
universe@7 | 102 | fillInCandidate(f, candidates, x, y); |
universe@7 | 103 | fillDistinct = true; |
universe@7 | 104 | } |
universe@7 | 105 | } |
universe@7 | 106 | } |
universe@7 | 107 | } while (fillDistinct); |
universe@7 | 108 | |
universe@7 | 109 | // Try out remaining candidates |
universe@7 | 110 | for (int x = 0 ; x < 9 ; x++) { |
universe@7 | 111 | for (int y = 0 ; y < 9 ; y++) { |
universe@7 | 112 | if (f.isCellEmpty(x, y)) { |
universe@7 | 113 | while (candidates[x][y].size() > 0) { |
universe@7 | 114 | List<Integer>[][] cb = new List[9][9]; |
universe@7 | 115 | makeBackup(candidates, cb); |
universe@7 | 116 | Integer c = fillInCandidate(f, candidates, x, y); |
universe@7 | 117 | if (solve(f, candidates)) { |
universe@7 | 118 | break; |
universe@7 | 119 | } else { |
universe@7 | 120 | f.clearCellValue(x, y); |
universe@7 | 121 | restoreBackup(candidates, cb); |
universe@7 | 122 | // Remove current candidate anyway |
universe@7 | 123 | candidates[x][y].remove(c); |
universe@7 | 124 | } |
universe@7 | 125 | } |
universe@7 | 126 | } |
universe@7 | 127 | if (f.isCellEmpty(x, y)) { |
universe@7 | 128 | restoreBackup(f, fieldBackup); |
universe@7 | 129 | restoreBackup(candidates, candidatesBackup); |
universe@7 | 130 | return false; |
universe@7 | 131 | } |
universe@7 | 132 | } |
universe@7 | 133 | } |
universe@7 | 134 | |
universe@7 | 135 | return true; |
universe@7 | 136 | } |
universe@10 | 137 | |
universe@10 | 138 | /** |
universe@10 | 139 | * Attempts to solve the given Sudoku field. |
universe@10 | 140 | * |
universe@10 | 141 | * The solution, if any, is directly entered into the field. |
universe@10 | 142 | * All solved fields will be in modified state. |
universe@10 | 143 | * The already given fields are left untouched. |
universe@10 | 144 | * |
universe@10 | 145 | * @param f the field to solve |
universe@10 | 146 | * @return true if a solution could be found, false if the field is unsolvable |
universe@10 | 147 | */ |
universe@7 | 148 | public boolean solve(Field f) { |
universe@7 | 149 | |
universe@7 | 150 | // Calculate initial candidates |
universe@12 | 151 | List<Integer>[][] candidates = new List[9][9]; |
universe@7 | 152 | for (int x = 0 ; x < 9 ; x++) { |
universe@7 | 153 | for (int y = 0 ; y < 9 ; y++) { |
universe@7 | 154 | candidates[x][y] = new ArrayList<>(9); |
universe@7 | 155 | if (f.getCellValue(x, y) == 0) { |
universe@7 | 156 | // All numbers are candidates |
universe@7 | 157 | for (int c = 1 ; c <= 9 ; c++) { |
universe@7 | 158 | candidates[x][y].add(c); |
universe@7 | 159 | } |
universe@7 | 160 | // Remove row duplicates |
universe@7 | 161 | int[] line = f.getRow(y); |
universe@7 | 162 | for (Integer c : line) { |
universe@7 | 163 | candidates[x][y].remove(c); |
universe@7 | 164 | } |
universe@7 | 165 | // Remove column duplicates |
universe@7 | 166 | line = f.getColumn(x); |
universe@7 | 167 | for (Integer c : line) { |
universe@7 | 168 | candidates[x][y].remove(c); |
universe@7 | 169 | } |
universe@7 | 170 | // Remove square duplicates |
universe@7 | 171 | int[][] square = f.getSquare(x/3, y/3); |
universe@7 | 172 | for (int[] sq : square) { |
universe@7 | 173 | for (Integer c : sq) { |
universe@7 | 174 | candidates[x][y].remove(c); |
universe@7 | 175 | } |
universe@7 | 176 | } |
universe@7 | 177 | } |
universe@7 | 178 | } |
universe@7 | 179 | } |
universe@7 | 180 | |
universe@7 | 181 | // Backtrack |
universe@8 | 182 | return solve(f, candidates); |
universe@7 | 183 | } |
universe@10 | 184 | |
universe@10 | 185 | /** |
universe@10 | 186 | * Performs a fast check whether any field violates the Sudoku rules. |
universe@10 | 187 | * |
universe@10 | 188 | * @param f the field to check |
universe@10 | 189 | * @return true, if the check succeeds, false otherwise |
universe@10 | 190 | */ |
universe@2 | 191 | public boolean check(Field f) { |
universe@12 | 192 | int[] line; |
universe@2 | 193 | for (int i = 0 ; i < 9 ; i++) { |
universe@5 | 194 | line = f.getRow(i); |
universe@2 | 195 | if (!valid(line)) { |
universe@2 | 196 | return false; |
universe@2 | 197 | } |
universe@5 | 198 | line = f.getColumn(i); |
universe@2 | 199 | if (!valid(line)) { |
universe@2 | 200 | return false; |
universe@2 | 201 | } |
universe@2 | 202 | } |
universe@2 | 203 | |
universe@12 | 204 | int[][] square; |
universe@2 | 205 | for (int x = 0 ; x < 3 ; x++) { |
universe@2 | 206 | for (int y = 0 ; y < 3 ; y++) { |
universe@5 | 207 | square = f.getSquare(x, y); |
universe@2 | 208 | if (!valid(square)) { |
universe@2 | 209 | return false; |
universe@2 | 210 | } |
universe@2 | 211 | } |
universe@2 | 212 | } |
universe@2 | 213 | |
universe@2 | 214 | return true; |
universe@2 | 215 | } |
universe@2 | 216 | |
universe@2 | 217 | private boolean valid(int[] line) { |
universe@12 | 218 | int[] numbers; |
universe@5 | 219 | numbers = new int[9]; |
universe@2 | 220 | for (int i = 0 ; i < 9 ; i++) { |
universe@2 | 221 | int l = line[i]-1; |
universe@2 | 222 | if (l >= 0) { |
universe@5 | 223 | if ((++numbers[l]) > 1) { |
universe@2 | 224 | return false; |
universe@2 | 225 | } |
universe@2 | 226 | } |
universe@2 | 227 | } |
universe@2 | 228 | |
universe@2 | 229 | return true; |
universe@2 | 230 | } |
universe@2 | 231 | |
universe@2 | 232 | private boolean valid(int[][] square) { |
universe@2 | 233 | int[] line = new int[9]; |
universe@2 | 234 | for (int x = 0 ; x < 3 ; x++) { |
universe@5 | 235 | System.arraycopy(square[x], 0, line, 3*x, 3); |
universe@2 | 236 | } |
universe@2 | 237 | return valid(line); |
universe@2 | 238 | } |
universe@2 | 239 | } |