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