1.1 --- a/src/de/uapcore/sudoku/Solver.java Fri Feb 01 10:18:47 2013 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,227 +0,0 @@
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 -}
