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