--- a/test/javatest.java Sun Mar 02 12:47:31 2025 +0100
+++ b/test/javatest.java Sun Mar 02 16:06:24 2025 +0100
@@ -1,18 +1,16 @@
/*
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
- *
- * Copyright 2014 Mike Becker. All rights reserved.
- *
+ * Copyright 2013 Mike Becker. All rights reserved.
+ *
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
- *
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- *
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
@@ -24,153 +22,220 @@
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
- *
*/
-package de.uapcore.sigred.doc.base;
+package de.uapcore.sudoku;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Implements the backtracking algorithm for solving the Sudoku.
+ */
+public final class Solver {
+
+ public static final int VERSION = 0x1000;
-import de.uapcore.sigred.doc.Resources;
-import de.uapcore.sigrapi.impl.Digraph;
-import de.uapcore.sigrapi.impl.Graph;
-import de.uapcore.sigrapi.IGraph;
-import java.io.IOException;
-import java.io.InputStream;
-import java.io.OutputStream;
-import java.util.concurrent.atomic.AtomicBoolean;
-import java.util.concurrent.atomic.AtomicReference;
-import org.apache.xerces.impl.Constants;
-import org.dom4j.Document;
-import org.dom4j.DocumentException;
-import org.dom4j.DocumentHelper;
-import org.dom4j.Element;
-import org.dom4j.Namespace;
-import org.dom4j.QName;
-import org.dom4j.io.OutputFormat;
-import org.dom4j.io.SAXReader;
-import org.dom4j.io.XMLWriter;
-import org.xml.sax.ErrorHandler;
-import org.xml.sax.SAXException;
-import org.xml.sax.SAXParseException;
-
-public abstract class AbstractGraphDocument<T extends IGraph>
- extends FileBackedDocument {
+ private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) {
+ Integer c = candidates[x][y].remove(0);
+ f.setCellValue(x, y, c);
+ f.setCellModified(x, y, true);
+ for (int i = 0 ; i < 9 ; i++) {
+ candidates[x][i].remove(c);
+ candidates[i][y].remove(c);
+ }
+ for (int i = 0 ; i < 3 ; i++) {
+ for (int j = 0 ; j < 3 ; j++) {
+ candidates[x-x%3+i][y-y%3+j].remove(c);
+ }
+ }
+ return c;
+ }
- protected static final Namespace NAMESPACE = Namespace.get("sigred",
- "http://develop.uap-core.de/sigred/");
-
- private static final
- QName TAG_GRAPHDOC = QName.get("graph-document", NAMESPACE);
- private static final
- QName TAG_GRAPH = QName.get("graph", NAMESPACE);
- private static final
- QName TAG_DIGRAPH = QName.get("digraph", NAMESPACE);
- private static final
- QName TAG_METADATA = QName.get("metadata", NAMESPACE);
-
- protected final T graph;
+ private void makeBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
+ for (int x = 0 ; x < 9 ; x++) {
+ for (int y = 0 ; y < 9 ; y++) {
+ candidatesBackup[x][y] = new ArrayList<>(9);
+ candidatesBackup[x][y].addAll(candidates[x][y]);
+ }
+ }
+ }
- private final GraphDocumentMetadata metadata;
+ private void makeBackup(Field f, int[][] fieldBackup) {
+ for (int x = 0 ; x < 9 ; x++) {
+ for (int y = 0 ; y < 9 ; y++) {
+ fieldBackup[x][y] = f.getCellValue(x, y);
+ }
+ }
+ }
- public AbstractGraphDocument(Class<T> graphType) {
- T g;
- try {
- g = graphType.newInstance();
- } catch (ReflectiveOperationException e) {
- assert false;
- g = null; // for the compiler
+ private void restoreBackup(Field f, int[][] fieldBackup) {
+ for (int x = 0 ; x < 9 ; x++) {
+ for (int y = 0 ; y < 9 ; y++) {
+ f.setCellValue(x, y, fieldBackup[x][y]);
+ }
}
- graph = g;
- metadata = new GraphDocumentMetadata();
- }
-
- public T getGraph() {
- return graph;
}
- public GraphDocumentMetadata getMetadata() {
- return metadata;
+ private void restoreBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
+ for (int x = 0 ; x < 9 ; x++) {
+ for (int y = 0 ; y < 9 ; y++) {
+ candidates[x][y].clear();
+ candidates[x][y].addAll(candidatesBackup[x][y]);
+ }
+ }
+ }
+
+ private boolean solve(Field f, List<Integer>[][] candidates) {
+
+ // Make backup
+ List<Integer>[][] candidatesBackup = new List[9][9];
+ int[][] fieldBackup = new int[9][9];
+ makeBackup(candidates, candidatesBackup);
+ makeBackup(f, fieldBackup);
+
+ // Fill in distinct solutions
+ boolean fillDistinct;
+ do {
+ fillDistinct = false;
+ for (int x = 0 ; x < 9 ; x++) {
+ for (int y = 0 ; y < 9 ; y++) {
+ if (f.isCellEmpty(x, y) && candidates[x][y].size() == 1) {
+ fillInCandidate(f, candidates, x, y);
+ fillDistinct = true;
+ }
+ }
+ }
+ } while (fillDistinct);
+
+ // Try out remaining candidates
+ for (int x = 0 ; x < 9 ; x++) {
+ for (int y = 0 ; y < 9 ; y++) {
+ if (f.isCellEmpty(x, y)) {
+ while (candidates[x][y].size() > 0) {
+ List<Integer>[][] cb = new List[9][9];
+ makeBackup(candidates, cb);
+ Integer c = fillInCandidate(f, candidates, x, y);
+ if (solve(f, candidates)) {
+ break;
+ } else {
+ f.clearCellValue(x, y);
+ restoreBackup(candidates, cb);
+ // Remove current candidate anyway
+ candidates[x][y].remove(c);
+ }
+ }
+ }
+ if (f.isCellEmpty(x, y)) {
+ restoreBackup(f, fieldBackup);
+ restoreBackup(candidates, candidatesBackup);
+ return false;
+ }
+ }
+ }
+
+ return true;
}
- protected abstract void writeGraph(Element rootNode) throws IOException;
- protected abstract void readGraph(Element rootNode) throws IOException;
-
- @Override
- public void writeTo(OutputStream out) throws IOException {
- Document doc = DocumentHelper.createDocument();
-
- Element rootNode = doc.addElement(TAG_GRAPHDOC);
-
- Element metadataNode = rootNode.addElement(TAG_METADATA);
-
- metadata.write(metadataNode);
-
- if (graph instanceof Graph) {
- writeGraph(rootNode.addElement(TAG_GRAPH));
- } else if (graph instanceof Digraph) {
- writeGraph(rootNode.addElement(TAG_DIGRAPH));
- } else {
- throw new IOException("unsupported graph type");
+ /**
+ * Attempts to solve the given Sudoku field.
+ *
+ * The solution, if any, is directly entered into the field.
+ * All solved fields will be in modified state.
+ * The already given fields are left untouched.
+ *
+ * @param f the field to solve
+ * @return true if a solution could be found, false if the field is unsolvable
+ */
+ public boolean solve(Field f) {
+
+ // Calculate initial candidates
+ List<Integer>[][] candidates = new List[9][9];
+ for (int x = 0 ; x < 9 ; x++) {
+ for (int y = 0 ; y < 9 ; y++) {
+ candidates[x][y] = new ArrayList<>(9);
+ if (f.getCellValue(x, y) == 0) {
+ // All numbers are candidates
+ for (int c = 1 ; c <= 9 ; c++) {
+ candidates[x][y].add(c);
+ }
+ // Remove row duplicates
+ int[] line = f.getRow(y);
+ for (Integer c : line) {
+ candidates[x][y].remove(c);
+ }
+ // Remove column duplicates
+ line = f.getColumn(x);
+ for (Integer c : line) {
+ candidates[x][y].remove(c);
+ }
+ // Remove square duplicates
+ int[][] square = f.getSquare(x/3, y/3);
+ for (int[] sq : square) {
+ for (Integer c : sq) {
+ candidates[x][y].remove(c);
+ }
+ }
+ }
+ }
}
-
- XMLWriter writer = new XMLWriter(out, OutputFormat.createPrettyPrint());
- writer.write(doc);
- writer.flush();
+
+ // Backtrack
+ return solve(f, candidates);
}
- @Override
- public void readFrom(InputStream in) throws IOException {
- try {
- SAXReader reader = new SAXReader(true);
- reader.setStripWhitespaceText(true);
-
- reader.setFeature(Constants.XERCES_FEATURE_PREFIX+
- Constants.SCHEMA_VALIDATION_FEATURE, true);
- reader.setProperty(Constants.XERCES_PROPERTY_PREFIX +
- Constants.SCHEMA_LOCATION, String.format("%s %s",
- NAMESPACE.getURI(), Resources.class.getResource(
- "graph-document.xsd").toExternalForm()));
-
- final AtomicBoolean passed = new AtomicBoolean(true);
- final AtomicReference<SAXParseException> xmlerror = new AtomicReference<>();
- // TODO: we should do more detailed error handling here
- reader.setErrorHandler(new ErrorHandler() {
- @Override
- public void warning(SAXParseException exception) throws SAXException {
- }
-
- @Override
- public void error(SAXParseException exception) throws SAXException {
- xmlerror.set(exception);
- passed.set(false);
+ /**
+ * Performs a fast check whether any field violates the Sudoku rules.
+ *
+ * @param f the field to check
+ * @return true, if the check succeeds, false otherwise
+ */
+ public boolean check(Field f) {
+ int[] line;
+ for (int i = 0 ; i < 9 ; i++) {
+ line = f.getRow(i);
+ if (!valid(line)) {
+ return false;
+ }
+ line = f.getColumn(i);
+ if (!valid(line)) {
+ return false;
+ }
+ }
+
+ int[][] square;
+ for (int x = 0 ; x < 3 ; x++) {
+ for (int y = 0 ; y < 3 ; y++) {
+ square = f.getSquare(x, y);
+ if (!valid(square)) {
+ return false;
}
-
- @Override
- public void fatalError(SAXParseException exception) throws SAXException {
- xmlerror.set(exception);
- passed.set(false);
- }
-
- });
- Document doc = reader.read(in);
- if (!passed.get()) {
- // TODO: provide details (maybe via separate error object?)
- throw xmlerror.get();
}
-
- doc.normalize();
-
- Element root = doc.getRootElement();
- metadata.read(root.element(TAG_METADATA));
-
- if (graph instanceof Graph) {
- readGraph(root.element(TAG_GRAPH));
- } else if (graph instanceof Digraph) {
- readGraph(root.element(TAG_DIGRAPH));
- } else {
- throw new IOException("unsupported graph type");
+ }
+
+ return true;
+ }
+
+ private boolean valid(int[] line) {
+ int[] numbers;
+ numbers = new int[9];
+ for (int i = 0 ; i < 9 ; i++) {
+ int l = line[i]-1;
+ if (l >= 0) {
+ if ((++numbers[l]) > 1) {
+ return false;
+ }
}
- } catch (DocumentException | SAXException ex) {
- throw new IOException(ex);
}
+
+ return true;
+ }
+
+ private boolean valid(int[][] square) {
+ int[] line = new int[9];
+ for (int x = 0 ; x < 3 ; x++) {
+ System.arraycopy(square[x], 0, line, 3*x, 3);
+ }
+ return valid(line);
}
}