src/main/java/de/uapcore/sudoku/Solver.java

Mon, 27 Jul 2020 12:08:23 +0200

author
Mike Becker <universe@uap-core.de>
date
Mon, 27 Jul 2020 12:08:23 +0200
changeset 15
fea6eaa0d520
parent 12
1c62c6009161
permissions
-rw-r--r--

fix: window cannot get smaller than the field

3
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
1 /*
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
2 * Copyright 2013 Mike Becker. All rights reserved.
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
3 *
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
4 * Redistribution and use in source and binary forms, with or without
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
5 * modification, are permitted provided that the following conditions are met:
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
6 *
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
7 * 1. Redistributions of source code must retain the above copyright
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
8 * notice, this list of conditions and the following disclaimer.
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
9 *
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
10 * 2. Redistributions in binary form must reproduce the above copyright
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
11 * notice, this list of conditions and the following disclaimer in the
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
12 * documentation and/or other materials provided with the distribution.
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
13 *
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
15 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
18 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
19 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
20 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
21 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
22 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
24 * POSSIBILITY OF SUCH DAMAGE.
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
25 */
ed931970b4ac added license and main menu
Mike Becker <universe@uap-core.de>
parents: 2
diff changeset
26
2
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
27 package de.uapcore.sudoku;
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
28
7
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
29 import java.util.ArrayList;
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
30 import java.util.List;
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
31
2
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
32 /**
10
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
33 * Implements the backtracking algorithm for solving the Sudoku.
2
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
34 */
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
35 public final class Solver {
10
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
36
7
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
37 private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
38 Integer c = candidates[x][y].remove(0);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
39 f.setCellValue(x, y, c);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
40 f.setCellModified(x, y, true);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
41 for (int i = 0 ; i < 9 ; i++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
42 candidates[x][i].remove(c);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
43 candidates[i][y].remove(c);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
44 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
45 for (int i = 0 ; i < 3 ; i++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
46 for (int j = 0 ; j < 3 ; j++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
47 candidates[x-x%3+i][y-y%3+j].remove(c);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
48 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
49 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
50 return c;
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
51 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
52
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
53 private void makeBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
54 for (int x = 0 ; x < 9 ; x++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
55 for (int y = 0 ; y < 9 ; y++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
56 candidatesBackup[x][y] = new ArrayList<>(9);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
57 candidatesBackup[x][y].addAll(candidates[x][y]);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
58 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
59 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
60 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
61
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
62 private void makeBackup(Field f, int[][] fieldBackup) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
63 for (int x = 0 ; x < 9 ; x++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
64 for (int y = 0 ; y < 9 ; y++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
65 fieldBackup[x][y] = f.getCellValue(x, y);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
66 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
67 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
68 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
69
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
70 private void restoreBackup(Field f, int[][] fieldBackup) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
71 for (int x = 0 ; x < 9 ; x++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
72 for (int y = 0 ; y < 9 ; y++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
73 f.setCellValue(x, y, fieldBackup[x][y]);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
74 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
75 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
76 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
77
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
78 private void restoreBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
79 for (int x = 0 ; x < 9 ; x++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
80 for (int y = 0 ; y < 9 ; y++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
81 candidates[x][y].clear();
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
82 candidates[x][y].addAll(candidatesBackup[x][y]);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
83 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
84 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
85 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
86
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
87 private boolean solve(Field f, List<Integer>[][] candidates) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
88
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
89 // Make backup
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
90 List<Integer>[][] candidatesBackup = new List[9][9];
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
91 int[][] fieldBackup = new int[9][9];
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
92 makeBackup(candidates, candidatesBackup);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
93 makeBackup(f, fieldBackup);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
94
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
95 // Fill in distinct solutions
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
96 boolean fillDistinct;
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
97 do {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
98 fillDistinct = false;
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
99 for (int x = 0 ; x < 9 ; x++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
100 for (int y = 0 ; y < 9 ; y++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
101 if (f.isCellEmpty(x, y) && candidates[x][y].size() == 1) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
102 fillInCandidate(f, candidates, x, y);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
103 fillDistinct = true;
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
104 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
105 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
106 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
107 } while (fillDistinct);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
108
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
109 // Try out remaining candidates
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
110 for (int x = 0 ; x < 9 ; x++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
111 for (int y = 0 ; y < 9 ; y++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
112 if (f.isCellEmpty(x, y)) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
113 while (candidates[x][y].size() > 0) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
114 List<Integer>[][] cb = new List[9][9];
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
115 makeBackup(candidates, cb);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
116 Integer c = fillInCandidate(f, candidates, x, y);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
117 if (solve(f, candidates)) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
118 break;
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
119 } else {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
120 f.clearCellValue(x, y);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
121 restoreBackup(candidates, cb);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
122 // Remove current candidate anyway
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
123 candidates[x][y].remove(c);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
124 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
125 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
126 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
127 if (f.isCellEmpty(x, y)) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
128 restoreBackup(f, fieldBackup);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
129 restoreBackup(candidates, candidatesBackup);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
130 return false;
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
131 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
132 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
133 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
134
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
135 return true;
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
136 }
10
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
137
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
138 /**
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
139 * Attempts to solve the given Sudoku field.
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
140 *
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
141 * The solution, if any, is directly entered into the field.
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
142 * All solved fields will be in modified state.
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
143 * The already given fields are left untouched.
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
144 *
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
145 * @param f the field to solve
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
146 * @return true if a solution could be found, false if the field is unsolvable
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
147 */
7
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
148 public boolean solve(Field f) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
149
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
150 // Calculate initial candidates
12
1c62c6009161 fixes some code inspection issues
Mike Becker <universe@uap-core.de>
parents: 10
diff changeset
151 List<Integer>[][] candidates = new List[9][9];
7
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
152 for (int x = 0 ; x < 9 ; x++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
153 for (int y = 0 ; y < 9 ; y++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
154 candidates[x][y] = new ArrayList<>(9);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
155 if (f.getCellValue(x, y) == 0) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
156 // All numbers are candidates
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
157 for (int c = 1 ; c <= 9 ; c++) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
158 candidates[x][y].add(c);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
159 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
160 // Remove row duplicates
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
161 int[] line = f.getRow(y);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
162 for (Integer c : line) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
163 candidates[x][y].remove(c);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
164 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
165 // Remove column duplicates
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
166 line = f.getColumn(x);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
167 for (Integer c : line) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
168 candidates[x][y].remove(c);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
169 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
170 // Remove square duplicates
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
171 int[][] square = f.getSquare(x/3, y/3);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
172 for (int[] sq : square) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
173 for (Integer c : sq) {
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
174 candidates[x][y].remove(c);
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
175 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
176 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
177 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
178 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
179 }
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
180
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
181 // Backtrack
8
e70a0e3555fb removed completeness test - the solver automatically returns false when the field is incomplete
Mike Becker <universe@uap-core.de>
parents: 7
diff changeset
182 return solve(f, candidates);
7
2c0a2766461c added solving algorithm
Mike Becker <universe@uap-core.de>
parents: 5
diff changeset
183 }
10
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
184
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
185 /**
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
186 * Performs a fast check whether any field violates the Sudoku rules.
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
187 *
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
188 * @param f the field to check
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
189 * @return true, if the check succeeds, false otherwise
369903afbb29 adds more javadoc
Mike Becker <universe@uap-core.de>
parents: 9
diff changeset
190 */
2
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
191 public boolean check(Field f) {
12
1c62c6009161 fixes some code inspection issues
Mike Becker <universe@uap-core.de>
parents: 10
diff changeset
192 int[] line;
2
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
193 for (int i = 0 ; i < 9 ; i++) {
5
8ddf4af937d7 moved field methods to field class + added (parts of the) document handler
Mike Becker <universe@uap-core.de>
parents: 3
diff changeset
194 line = f.getRow(i);
2
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
195 if (!valid(line)) {
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
196 return false;
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
197 }
5
8ddf4af937d7 moved field methods to field class + added (parts of the) document handler
Mike Becker <universe@uap-core.de>
parents: 3
diff changeset
198 line = f.getColumn(i);
2
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
199 if (!valid(line)) {
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
200 return false;
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
201 }
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
202 }
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
203
12
1c62c6009161 fixes some code inspection issues
Mike Becker <universe@uap-core.de>
parents: 10
diff changeset
204 int[][] square;
2
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
205 for (int x = 0 ; x < 3 ; x++) {
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
206 for (int y = 0 ; y < 3 ; y++) {
5
8ddf4af937d7 moved field methods to field class + added (parts of the) document handler
Mike Becker <universe@uap-core.de>
parents: 3
diff changeset
207 square = f.getSquare(x, y);
2
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
208 if (!valid(square)) {
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
209 return false;
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
210 }
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
211 }
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
212 }
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
213
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
214 return true;
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
215 }
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
216
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
217 private boolean valid(int[] line) {
12
1c62c6009161 fixes some code inspection issues
Mike Becker <universe@uap-core.de>
parents: 10
diff changeset
218 int[] numbers;
5
8ddf4af937d7 moved field methods to field class + added (parts of the) document handler
Mike Becker <universe@uap-core.de>
parents: 3
diff changeset
219 numbers = new int[9];
2
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
220 for (int i = 0 ; i < 9 ; i++) {
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
221 int l = line[i]-1;
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
222 if (l >= 0) {
5
8ddf4af937d7 moved field methods to field class + added (parts of the) document handler
Mike Becker <universe@uap-core.de>
parents: 3
diff changeset
223 if ((++numbers[l]) > 1) {
2
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
224 return false;
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
225 }
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
226 }
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
227 }
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
228
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
229 return true;
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
230 }
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
231
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
232 private boolean valid(int[][] square) {
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
233 int[] line = new int[9];
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
234 for (int x = 0 ; x < 3 ; x++) {
5
8ddf4af937d7 moved field methods to field class + added (parts of the) document handler
Mike Becker <universe@uap-core.de>
parents: 3
diff changeset
235 System.arraycopy(square[x], 0, line, 3*x, 3);
2
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
236 }
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
237 return valid(line);
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
238 }
5179eff8a9b6 check functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
239 }

mercurial