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