1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/main/java/de/uapcore/sudoku/Solver.java Sat Jul 25 14:01:28 2020 +0200 1.3 @@ -0,0 +1,227 @@ 1.4 +/* 1.5 + * Copyright 2013 Mike Becker. All rights reserved. 1.6 + * 1.7 + * Redistribution and use in source and binary forms, with or without 1.8 + * modification, are permitted provided that the following conditions are met: 1.9 + * 1.10 + * 1. Redistributions of source code must retain the above copyright 1.11 + * notice, this list of conditions and the following disclaimer. 1.12 + * 1.13 + * 2. Redistributions in binary form must reproduce the above copyright 1.14 + * notice, this list of conditions and the following disclaimer in the 1.15 + * documentation and/or other materials provided with the distribution. 1.16 + * 1.17 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 1.18 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1.19 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1.20 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 1.21 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 1.22 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 1.23 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 1.24 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 1.25 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 1.26 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 1.27 + * POSSIBILITY OF SUCH DAMAGE. 1.28 + */ 1.29 + 1.30 +package de.uapcore.sudoku; 1.31 + 1.32 +import java.util.ArrayList; 1.33 +import java.util.List; 1.34 + 1.35 +/** 1.36 + * 1.37 + * @author mike 1.38 + */ 1.39 +public final class Solver { 1.40 + 1.41 + public Solver() { 1.42 + } 1.43 + 1.44 + private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) { 1.45 + Integer c = candidates[x][y].remove(0); 1.46 + f.setCellValue(x, y, c); 1.47 + f.setCellModified(x, y, true); 1.48 + for (int i = 0 ; i < 9 ; i++) { 1.49 + candidates[x][i].remove(c); 1.50 + candidates[i][y].remove(c); 1.51 + } 1.52 + for (int i = 0 ; i < 3 ; i++) { 1.53 + for (int j = 0 ; j < 3 ; j++) { 1.54 + candidates[x-x%3+i][y-y%3+j].remove(c); 1.55 + } 1.56 + } 1.57 + return c; 1.58 + } 1.59 + 1.60 + private void makeBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) { 1.61 + for (int x = 0 ; x < 9 ; x++) { 1.62 + for (int y = 0 ; y < 9 ; y++) { 1.63 + candidatesBackup[x][y] = new ArrayList<>(9); 1.64 + candidatesBackup[x][y].addAll(candidates[x][y]); 1.65 + } 1.66 + } 1.67 + } 1.68 + 1.69 + private void makeBackup(Field f, int[][] fieldBackup) { 1.70 + for (int x = 0 ; x < 9 ; x++) { 1.71 + for (int y = 0 ; y < 9 ; y++) { 1.72 + fieldBackup[x][y] = f.getCellValue(x, y); 1.73 + } 1.74 + } 1.75 + } 1.76 + 1.77 + private void restoreBackup(Field f, int[][] fieldBackup) { 1.78 + for (int x = 0 ; x < 9 ; x++) { 1.79 + for (int y = 0 ; y < 9 ; y++) { 1.80 + f.setCellValue(x, y, fieldBackup[x][y]); 1.81 + } 1.82 + } 1.83 + } 1.84 + 1.85 + private void restoreBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) { 1.86 + for (int x = 0 ; x < 9 ; x++) { 1.87 + for (int y = 0 ; y < 9 ; y++) { 1.88 + candidates[x][y].clear(); 1.89 + candidates[x][y].addAll(candidatesBackup[x][y]); 1.90 + } 1.91 + } 1.92 + } 1.93 + 1.94 + private boolean solve(Field f, List<Integer>[][] candidates) { 1.95 + 1.96 + // Make backup 1.97 + List<Integer>[][] candidatesBackup = new List[9][9]; 1.98 + int[][] fieldBackup = new int[9][9]; 1.99 + makeBackup(candidates, candidatesBackup); 1.100 + makeBackup(f, fieldBackup); 1.101 + 1.102 + // Fill in distinct solutions 1.103 + boolean fillDistinct; 1.104 + do { 1.105 + fillDistinct = false; 1.106 + for (int x = 0 ; x < 9 ; x++) { 1.107 + for (int y = 0 ; y < 9 ; y++) { 1.108 + if (f.isCellEmpty(x, y) && candidates[x][y].size() == 1) { 1.109 + fillInCandidate(f, candidates, x, y); 1.110 + fillDistinct = true; 1.111 + } 1.112 + } 1.113 + } 1.114 + } while (fillDistinct); 1.115 + 1.116 + // Try out remaining candidates 1.117 + for (int x = 0 ; x < 9 ; x++) { 1.118 + for (int y = 0 ; y < 9 ; y++) { 1.119 + if (f.isCellEmpty(x, y)) { 1.120 + while (candidates[x][y].size() > 0) { 1.121 + List<Integer>[][] cb = new List[9][9]; 1.122 + makeBackup(candidates, cb); 1.123 + Integer c = fillInCandidate(f, candidates, x, y); 1.124 + if (solve(f, candidates)) { 1.125 + break; 1.126 + } else { 1.127 + f.clearCellValue(x, y); 1.128 + restoreBackup(candidates, cb); 1.129 + // Remove current candidate anyway 1.130 + candidates[x][y].remove(c); 1.131 + } 1.132 + } 1.133 + } 1.134 + if (f.isCellEmpty(x, y)) { 1.135 + restoreBackup(f, fieldBackup); 1.136 + restoreBackup(candidates, candidatesBackup); 1.137 + return false; 1.138 + } 1.139 + } 1.140 + } 1.141 + 1.142 + return true; 1.143 + } 1.144 + 1.145 + public boolean solve(Field f) { 1.146 + 1.147 + // Calculate initial candidates 1.148 + List<Integer> candidates[][] = new List[9][9]; 1.149 + for (int x = 0 ; x < 9 ; x++) { 1.150 + for (int y = 0 ; y < 9 ; y++) { 1.151 + candidates[x][y] = new ArrayList<>(9); 1.152 + if (f.getCellValue(x, y) == 0) { 1.153 + // All numbers are candidates 1.154 + for (int c = 1 ; c <= 9 ; c++) { 1.155 + candidates[x][y].add(c); 1.156 + } 1.157 + // Remove row duplicates 1.158 + int[] line = f.getRow(y); 1.159 + for (Integer c : line) { 1.160 + candidates[x][y].remove(c); 1.161 + } 1.162 + // Remove column duplicates 1.163 + line = f.getColumn(x); 1.164 + for (Integer c : line) { 1.165 + candidates[x][y].remove(c); 1.166 + } 1.167 + // Remove square duplicates 1.168 + int[][] square = f.getSquare(x/3, y/3); 1.169 + for (int[] sq : square) { 1.170 + for (Integer c : sq) { 1.171 + candidates[x][y].remove(c); 1.172 + } 1.173 + } 1.174 + } 1.175 + } 1.176 + } 1.177 + 1.178 + // Backtrack 1.179 + return solve(f, candidates); 1.180 + } 1.181 + 1.182 + public boolean check(Field f) { 1.183 + int line[]; 1.184 + for (int i = 0 ; i < 9 ; i++) { 1.185 + line = f.getRow(i); 1.186 + if (!valid(line)) { 1.187 + return false; 1.188 + } 1.189 + line = f.getColumn(i); 1.190 + if (!valid(line)) { 1.191 + return false; 1.192 + } 1.193 + } 1.194 + 1.195 + int square[][]; 1.196 + for (int x = 0 ; x < 3 ; x++) { 1.197 + for (int y = 0 ; y < 3 ; y++) { 1.198 + square = f.getSquare(x, y); 1.199 + if (!valid(square)) { 1.200 + return false; 1.201 + } 1.202 + } 1.203 + } 1.204 + 1.205 + return true; 1.206 + } 1.207 + 1.208 + private boolean valid(int[] line) { 1.209 + int numbers[]; 1.210 + numbers = new int[9]; 1.211 + for (int i = 0 ; i < 9 ; i++) { 1.212 + int l = line[i]-1; 1.213 + if (l >= 0) { 1.214 + if ((++numbers[l]) > 1) { 1.215 + return false; 1.216 + } 1.217 + } 1.218 + } 1.219 + 1.220 + return true; 1.221 + } 1.222 + 1.223 + private boolean valid(int[][] square) { 1.224 + int[] line = new int[9]; 1.225 + for (int x = 0 ; x < 3 ; x++) { 1.226 + System.arraycopy(square[x], 0, line, 3*x, 3); 1.227 + } 1.228 + return valid(line); 1.229 + } 1.230 +}