Mercurial > hg > c2html / file comparison

comparison: test/javatest.java

test/javatest.java

changeset 91
2c8514b3891b
parent 65
7dd4fd1e7071
equal deleted inserted replaced
90:98adda6171d1 91:2c8514b3891b
1 /* 1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 2 * Copyright 2013 Mike Becker. All rights reserved.
3 * 3 *
4 * Copyright 2014 Mike Becker. All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without 4 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met: 5 * modification, are permitted provided that the following conditions are met:
8 * 6 *
9 * 1. Redistributions of source code must retain the above copyright 7 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer. 8 * notice, this list of conditions and the following disclaimer.
11 * 9 *
12 * 2. Redistributions in binary form must reproduce the above copyright 10 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the 11 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution. 12 * documentation and/or other materials provided with the distribution.
15 * 13 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 18 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 20 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 21 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 22 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE. 24 * POSSIBILITY OF SUCH DAMAGE.
27 *
28 */ 25 */
29 26
30 package de.uapcore.sigred.doc.base; 27 package de.uapcore.sudoku;
31 28
32 import de.uapcore.sigred.doc.Resources; 29 import java.util.ArrayList;
33 import de.uapcore.sigrapi.impl.Digraph; 30 import java.util.List;
34 import de.uapcore.sigrapi.impl.Graph; 31
35 import de.uapcore.sigrapi.IGraph; 32 /**
36 import java.io.IOException; 33 * Implements the backtracking algorithm for solving the Sudoku.
37 import java.io.InputStream; 34 */
38 import java.io.OutputStream; 35 public final class Solver {
39 import java.util.concurrent.atomic.AtomicBoolean; 36
40 import java.util.concurrent.atomic.AtomicReference; 37 public static final int VERSION = 0x1000;
41 import org.apache.xerces.impl.Constants; 38
42 import org.dom4j.Document; 39 private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) {
43 import org.dom4j.DocumentException; 40 Integer c = candidates[x][y].remove(0);
44 import org.dom4j.DocumentHelper; 41 f.setCellValue(x, y, c);
45 import org.dom4j.Element; 42 f.setCellModified(x, y, true);
46 import org.dom4j.Namespace; 43 for (int i = 0 ; i < 9 ; i++) {
47 import org.dom4j.QName; 44 candidates[x][i].remove(c);
48 import org.dom4j.io.OutputFormat; 45 candidates[i][y].remove(c);
49 import org.dom4j.io.SAXReader; 46 }
50 import org.dom4j.io.XMLWriter; 47 for (int i = 0 ; i < 3 ; i++) {
51 import org.xml.sax.ErrorHandler; 48 for (int j = 0 ; j < 3 ; j++) {
52 import org.xml.sax.SAXException; 49 candidates[x-x%3+i][y-y%3+j].remove(c);
53 import org.xml.sax.SAXParseException; 50 }
54 51 }
55 public abstract class AbstractGraphDocument<T extends IGraph> 52 return c;
56 extends FileBackedDocument { 53 }
57 54
58 protected static final Namespace NAMESPACE = Namespace.get("sigred", 55 private void makeBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
59 "http://develop.uap-core.de/sigred/"); 56 for (int x = 0 ; x < 9 ; x++) {
60 57 for (int y = 0 ; y < 9 ; y++) {
61 private static final 58 candidatesBackup[x][y] = new ArrayList<>(9);
62 QName TAG_GRAPHDOC = QName.get("graph-document", NAMESPACE); 59 candidatesBackup[x][y].addAll(candidates[x][y]);
63 private static final 60 }
64 QName TAG_GRAPH = QName.get("graph", NAMESPACE); 61 }
65 private static final 62 }
66 QName TAG_DIGRAPH = QName.get("digraph", NAMESPACE); 63
67 private static final 64 private void makeBackup(Field f, int[][] fieldBackup) {
68 QName TAG_METADATA = QName.get("metadata", NAMESPACE); 65 for (int x = 0 ; x < 9 ; x++) {
69 66 for (int y = 0 ; y < 9 ; y++) {
70 protected final T graph; 67 fieldBackup[x][y] = f.getCellValue(x, y);
71 68 }
72 private final GraphDocumentMetadata metadata; 69 }
73 70 }
74 public AbstractGraphDocument(Class<T> graphType) { 71
75 T g; 72 private void restoreBackup(Field f, int[][] fieldBackup) {
76 try { 73 for (int x = 0 ; x < 9 ; x++) {
77 g = graphType.newInstance(); 74 for (int y = 0 ; y < 9 ; y++) {
78 } catch (ReflectiveOperationException e) { 75 f.setCellValue(x, y, fieldBackup[x][y]);
79 assert false; 76 }
80 g = null; // for the compiler 77 }
81 } 78 }
82 graph = g; 79
83 metadata = new GraphDocumentMetadata(); 80 private void restoreBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
84 } 81 for (int x = 0 ; x < 9 ; x++) {
85 82 for (int y = 0 ; y < 9 ; y++) {
86 public T getGraph() { 83 candidates[x][y].clear();
87 return graph; 84 candidates[x][y].addAll(candidatesBackup[x][y]);
88 } 85 }
89 86 }
90 public GraphDocumentMetadata getMetadata() { 87 }
91 return metadata; 88
92 } 89 private boolean solve(Field f, List<Integer>[][] candidates) {
93 90
94 protected abstract void writeGraph(Element rootNode) throws IOException; 91 // Make backup
95 protected abstract void readGraph(Element rootNode) throws IOException; 92 List<Integer>[][] candidatesBackup = new List[9][9];
96 93 int[][] fieldBackup = new int[9][9];
97 @Override 94 makeBackup(candidates, candidatesBackup);
98 public void writeTo(OutputStream out) throws IOException { 95 makeBackup(f, fieldBackup);
99 Document doc = DocumentHelper.createDocument(); 96
100 97 // Fill in distinct solutions
101 Element rootNode = doc.addElement(TAG_GRAPHDOC); 98 boolean fillDistinct;
102 99 do {
103 Element metadataNode = rootNode.addElement(TAG_METADATA); 100 fillDistinct = false;
104 101 for (int x = 0 ; x < 9 ; x++) {
105 metadata.write(metadataNode); 102 for (int y = 0 ; y < 9 ; y++) {
106 103 if (f.isCellEmpty(x, y) && candidates[x][y].size() == 1) {
107 if (graph instanceof Graph) { 104 fillInCandidate(f, candidates, x, y);
108 writeGraph(rootNode.addElement(TAG_GRAPH)); 105 fillDistinct = true;
109 } else if (graph instanceof Digraph) { 106 }
110 writeGraph(rootNode.addElement(TAG_DIGRAPH)); 107 }
111 } else { 108 }
112 throw new IOException("unsupported graph type"); 109 } while (fillDistinct);
113 } 110
114 111 // Try out remaining candidates
115 XMLWriter writer = new XMLWriter(out, OutputFormat.createPrettyPrint()); 112 for (int x = 0 ; x < 9 ; x++) {
116 writer.write(doc); 113 for (int y = 0 ; y < 9 ; y++) {
117 writer.flush(); 114 if (f.isCellEmpty(x, y)) {
118 } 115 while (candidates[x][y].size() > 0) {
119 116 List<Integer>[][] cb = new List[9][9];
120 @Override 117 makeBackup(candidates, cb);
121 public void readFrom(InputStream in) throws IOException { 118 Integer c = fillInCandidate(f, candidates, x, y);
122 try { 119 if (solve(f, candidates)) {
123 SAXReader reader = new SAXReader(true); 120 break;
124 reader.setStripWhitespaceText(true); 121 } else {
125 122 f.clearCellValue(x, y);
126 reader.setFeature(Constants.XERCES_FEATURE_PREFIX+ 123 restoreBackup(candidates, cb);
127 Constants.SCHEMA_VALIDATION_FEATURE, true); 124 // Remove current candidate anyway
128 reader.setProperty(Constants.XERCES_PROPERTY_PREFIX + 125 candidates[x][y].remove(c);
129 Constants.SCHEMA_LOCATION, String.format("%s %s", 126 }
130 NAMESPACE.getURI(), Resources.class.getResource( 127 }
131 "graph-document.xsd").toExternalForm())); 128 }
132 129 if (f.isCellEmpty(x, y)) {
133 final AtomicBoolean passed = new AtomicBoolean(true); 130 restoreBackup(f, fieldBackup);
134 final AtomicReference<SAXParseException> xmlerror = new AtomicReference<>(); 131 restoreBackup(candidates, candidatesBackup);
135 // TODO: we should do more detailed error handling here 132 return false;
136 reader.setErrorHandler(new ErrorHandler() { 133 }
137 @Override 134 }
138 public void warning(SAXParseException exception) throws SAXException { 135 }
139 } 136
140 137 return true;
141 @Override 138 }
142 public void error(SAXParseException exception) throws SAXException { 139
143 xmlerror.set(exception); 140 /**
144 passed.set(false); 141 * Attempts to solve the given Sudoku field.
145 } 142 *
146 143 * The solution, if any, is directly entered into the field.
147 @Override 144 * All solved fields will be in modified state.
148 public void fatalError(SAXParseException exception) throws SAXException { 145 * The already given fields are left untouched.
149 xmlerror.set(exception); 146 *
150 passed.set(false); 147 * @param f the field to solve
151 } 148 * @return true if a solution could be found, false if the field is unsolvable
152 149 */
153 }); 150 public boolean solve(Field f) {
154 Document doc = reader.read(in); 151
155 if (!passed.get()) { 152 // Calculate initial candidates
156 // TODO: provide details (maybe via separate error object?) 153 List<Integer>[][] candidates = new List[9][9];
157 throw xmlerror.get(); 154 for (int x = 0 ; x < 9 ; x++) {
158 } 155 for (int y = 0 ; y < 9 ; y++) {
159 156 candidates[x][y] = new ArrayList<>(9);
160 doc.normalize(); 157 if (f.getCellValue(x, y) == 0) {
161 158 // All numbers are candidates
162 Element root = doc.getRootElement(); 159 for (int c = 1 ; c <= 9 ; c++) {
163 metadata.read(root.element(TAG_METADATA)); 160 candidates[x][y].add(c);
164 161 }
165 if (graph instanceof Graph) { 162 // Remove row duplicates
166 readGraph(root.element(TAG_GRAPH)); 163 int[] line = f.getRow(y);
167 } else if (graph instanceof Digraph) { 164 for (Integer c : line) {
168 readGraph(root.element(TAG_DIGRAPH)); 165 candidates[x][y].remove(c);
169 } else { 166 }
170 throw new IOException("unsupported graph type"); 167 // Remove column duplicates
171 } 168 line = f.getColumn(x);
172 } catch (DocumentException | SAXException ex) { 169 for (Integer c : line) {
173 throw new IOException(ex); 170 candidates[x][y].remove(c);
174 } 171 }
172 // Remove square duplicates
173 int[][] square = f.getSquare(x/3, y/3);
174 for (int[] sq : square) {
175 for (Integer c : sq) {
176 candidates[x][y].remove(c);
177 }
178 }
179 }
180 }
181 }
182
183 // Backtrack
184 return solve(f, candidates);
185 }
186
187 /**
188 * Performs a fast check whether any field violates the Sudoku rules.
189 *
190 * @param f the field to check
191 * @return true, if the check succeeds, false otherwise
192 */
193 public boolean check(Field f) {
194 int[] line;
195 for (int i = 0 ; i < 9 ; i++) {
196 line = f.getRow(i);
197 if (!valid(line)) {
198 return false;
199 }
200 line = f.getColumn(i);
201 if (!valid(line)) {
202 return false;
203 }
204 }
205
206 int[][] square;
207 for (int x = 0 ; x < 3 ; x++) {
208 for (int y = 0 ; y < 3 ; y++) {
209 square = f.getSquare(x, y);
210 if (!valid(square)) {
211 return false;
212 }
213 }
214 }
215
216 return true;
217 }
218
219 private boolean valid(int[] line) {
220 int[] numbers;
221 numbers = new int[9];
222 for (int i = 0 ; i < 9 ; i++) {
223 int l = line[i]-1;
224 if (l >= 0) {
225 if ((++numbers[l]) > 1) {
226 return false;
227 }
228 }
229 }
230
231 return true;
232 }
233
234 private boolean valid(int[][] square) {
235 int[] line = new int[9];
236 for (int x = 0 ; x < 3 ; x++) {
237 System.arraycopy(square[x], 0, line, 3*x, 3);
238 }
239 return valid(line);
175 } 240 }
176 } 241 }

Mercurial Repository: c2html

mercurial