src/de/uapcore/sudoku/Solver.java@2c0a2766461c
src/de/uapcore/sudoku/Solver.java
Thu, 31 Jan 2013 18:44:44 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Thu, 31 Jan 2013 18:44:44 +0100
- changeset 7
- 2c0a2766461c
- parent 5
- 8ddf4af937d7
- child 8
- e70a0e3555fb
- permissions
- -rw-r--r--
added solving algorithm
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 */
27 package de.uapcore.sudoku;
29 import java.util.ArrayList;
30 import java.util.List;
32 /**
33 *
34 * @author mike
35 */
36 public final class Solver {
38 public Solver() {
39 }
41 private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) {
42 Integer c = candidates[x][y].remove(0);
43 f.setCellValue(x, y, c);
44 f.setCellModified(x, y, true);
45 for (int i = 0 ; i < 9 ; i++) {
46 candidates[x][i].remove(c);
47 candidates[i][y].remove(c);
48 }
49 for (int i = 0 ; i < 3 ; i++) {
50 for (int j = 0 ; j < 3 ; j++) {
51 candidates[x-x%3+i][y-y%3+j].remove(c);
52 }
53 }
54 return c;
55 }
57 private void makeBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
58 for (int x = 0 ; x < 9 ; x++) {
59 for (int y = 0 ; y < 9 ; y++) {
60 candidatesBackup[x][y] = new ArrayList<>(9);
61 candidatesBackup[x][y].addAll(candidates[x][y]);
62 }
63 }
64 }
66 private void makeBackup(Field f, int[][] fieldBackup) {
67 for (int x = 0 ; x < 9 ; x++) {
68 for (int y = 0 ; y < 9 ; y++) {
69 fieldBackup[x][y] = f.getCellValue(x, y);
70 }
71 }
72 }
74 private void restoreBackup(Field f, int[][] fieldBackup) {
75 for (int x = 0 ; x < 9 ; x++) {
76 for (int y = 0 ; y < 9 ; y++) {
77 f.setCellValue(x, y, fieldBackup[x][y]);
78 }
79 }
80 }
82 private void restoreBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
83 for (int x = 0 ; x < 9 ; x++) {
84 for (int y = 0 ; y < 9 ; y++) {
85 candidates[x][y].clear();
86 candidates[x][y].addAll(candidatesBackup[x][y]);
87 }
88 }
89 }
91 private boolean solve(Field f, List<Integer>[][] candidates) {
93 // Make backup
94 List<Integer>[][] candidatesBackup = new List[9][9];
95 int[][] fieldBackup = new int[9][9];
96 makeBackup(candidates, candidatesBackup);
97 makeBackup(f, fieldBackup);
99 // Fill in distinct solutions
100 boolean fillDistinct;
101 do {
102 fillDistinct = false;
103 for (int x = 0 ; x < 9 ; x++) {
104 for (int y = 0 ; y < 9 ; y++) {
105 if (f.isCellEmpty(x, y) && candidates[x][y].size() == 1) {
106 fillInCandidate(f, candidates, x, y);
107 fillDistinct = true;
108 }
109 }
110 }
111 } while (fillDistinct);
113 // Try out remaining candidates
114 for (int x = 0 ; x < 9 ; x++) {
115 for (int y = 0 ; y < 9 ; y++) {
116 if (f.isCellEmpty(x, y)) {
117 while (candidates[x][y].size() > 0) {
118 List<Integer>[][] cb = new List[9][9];
119 makeBackup(candidates, cb);
120 Integer c = fillInCandidate(f, candidates, x, y);
121 if (solve(f, candidates)) {
122 break;
123 } else {
124 f.clearCellValue(x, y);
125 restoreBackup(candidates, cb);
126 // Remove current candidate anyway
127 candidates[x][y].remove(c);
128 }
129 }
130 }
131 if (f.isCellEmpty(x, y)) {
132 restoreBackup(f, fieldBackup);
133 restoreBackup(candidates, candidatesBackup);
134 return false;
135 }
136 }
137 }
139 return true;
140 }
142 public boolean solve(Field f) {
144 // Calculate initial candidates
145 List<Integer> candidates[][] = new List[9][9];
146 for (int x = 0 ; x < 9 ; x++) {
147 for (int y = 0 ; y < 9 ; y++) {
148 candidates[x][y] = new ArrayList<>(9);
149 if (f.getCellValue(x, y) == 0) {
150 // All numbers are candidates
151 for (int c = 1 ; c <= 9 ; c++) {
152 candidates[x][y].add(c);
153 }
154 // Remove row duplicates
155 int[] line = f.getRow(y);
156 for (Integer c : line) {
157 candidates[x][y].remove(c);
158 }
159 // Remove column duplicates
160 line = f.getColumn(x);
161 for (Integer c : line) {
162 candidates[x][y].remove(c);
163 }
164 // Remove square duplicates
165 int[][] square = f.getSquare(x/3, y/3);
166 for (int[] sq : square) {
167 for (Integer c : sq) {
168 candidates[x][y].remove(c);
169 }
170 }
171 }
172 }
173 }
175 // Backtrack
176 return solve(f, candidates) && complete(f);
177 }
179 public boolean check(Field f) {
180 int line[];
181 for (int i = 0 ; i < 9 ; i++) {
182 line = f.getRow(i);
183 if (!valid(line)) {
184 return false;
185 }
186 line = f.getColumn(i);
187 if (!valid(line)) {
188 return false;
189 }
190 }
192 int square[][];
193 for (int x = 0 ; x < 3 ; x++) {
194 for (int y = 0 ; y < 3 ; y++) {
195 square = f.getSquare(x, y);
196 if (!valid(square)) {
197 return false;
198 }
199 }
200 }
202 return true;
203 }
205 private boolean complete(Field f) {
206 for (int i = 0 ; i < 9 ; i++) {
207 if (!complete(f.getRow(i))) {
208 return false;
209 }
210 if (!complete(f.getColumn(i))) {
211 return false;
212 }
213 }
214 for (int x = 0 ; x < 3 ; x++) {
215 for (int y = 0 ; y < 3 ; y++) {
216 if (!complete(f.getSquare(x, y))) {
217 return false;
218 }
219 }
220 }
221 return true;
222 }
224 private boolean complete(int[][] square) {
225 for (int x = 0 ; x < 3 ; x++) {
226 for (int y = 0 ; y < 3 ; y++) {
227 if (square[x][y] == 0) {
228 return false;
229 }
230 }
231 }
232 return true;
233 }
235 private boolean complete(int[] line) {
236 for (int i = 0 ; i < 9 ; i++) {
237 if (line[i] == 0) {
238 return false;
239 }
240 }
241 return true;
242 }
244 private boolean valid(int[] line) {
245 int numbers[];
246 numbers = new int[9];
247 for (int i = 0 ; i < 9 ; i++) {
248 int l = line[i]-1;
249 if (l >= 0) {
250 if ((++numbers[l]) > 1) {
251 return false;
252 }
253 }
254 }
256 return true;
257 }
259 private boolean valid(int[][] square) {
260 int[] line = new int[9];
261 for (int x = 0 ; x < 3 ; x++) {
262 System.arraycopy(square[x], 0, line, 3*x, 3);
263 }
264 return valid(line);
265 }
266 }
