c2html: comparison test/javatest.java

-:98adda6171d1
+:2c8514b3891b
 /*
-* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
+* Copyright 2013 Mike Becker. All rights reserved.
 *
-* Copyright 2014 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
+* 1. Redistributions of source code must retain the above copyright
-*      notice, this list of conditions and the following disclaimer.
+*    notice, this list of conditions and the following disclaimer.
 *
-*   2. Redistributions in binary form must reproduce the above copyright
+* 2. Redistributions in binary form must reproduce the above copyright
-*      notice, this list of conditions and the following disclaimer in the
+*    notice, this list of conditions and the following disclaimer in the
-*      documentation and/or other materials provided with the distribution.
+*    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
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * 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 de.uapcore.sigred.doc.Resources;
+import java.util.ArrayList;
-import de.uapcore.sigrapi.impl.Digraph;
+import java.util.List;
-import de.uapcore.sigrapi.impl.Graph;
-import de.uapcore.sigrapi.IGraph;
+/**
-import java.io.IOException;
+* Implements the backtracking algorithm for solving the Sudoku.
-import java.io.InputStream;
+*/
-import java.io.OutputStream;
+public final class Solver {
-import java.util.concurrent.atomic.AtomicBoolean;
-import java.util.concurrent.atomic.AtomicReference;
+public static final int VERSION = 0x1000;
-import org.apache.xerces.impl.Constants;
-import org.dom4j.Document;
+private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) {
-import org.dom4j.DocumentException;
+Integer c = candidates[x][y].remove(0);
-import org.dom4j.DocumentHelper;
+f.setCellValue(x, y, c);
-import org.dom4j.Element;
+f.setCellModified(x, y, true);
-import org.dom4j.Namespace;
+for (int i = 0 ; i < 9 ; i++) {
-import org.dom4j.QName;
+candidates[x][i].remove(c);
-import org.dom4j.io.OutputFormat;
+candidates[i][y].remove(c);
-import org.dom4j.io.SAXReader;
+}
-import org.dom4j.io.XMLWriter;
+for (int i = 0 ; i < 3 ; i++) {
-import org.xml.sax.ErrorHandler;
+for (int j = 0 ; j < 3 ; j++) {
-import org.xml.sax.SAXException;
+candidates[x-x%3+i][y-y%3+j].remove(c);
-import org.xml.sax.SAXParseException;
+}
+}
-public abstract class AbstractGraphDocument<T extends IGraph>
+return c;
-extends FileBackedDocument {
+}
-protected static final Namespace NAMESPACE = Namespace.get("sigred",
+private void makeBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
-"http://develop.uap-core.de/sigred/");
+for (int x = 0 ; x < 9 ; x++) {
+for (int y = 0 ; y < 9 ; y++) {
-private static final
+candidatesBackup[x][y] = new ArrayList<>(9);
-QName TAG_GRAPHDOC = QName.get("graph-document", NAMESPACE);
+candidatesBackup[x][y].addAll(candidates[x][y]);
-private static final
+}
-QName TAG_GRAPH = QName.get("graph", NAMESPACE);
+}
-private static final
+}
-QName TAG_DIGRAPH = QName.get("digraph", NAMESPACE);
-private static final
+private void makeBackup(Field f, int[][] fieldBackup) {
-QName TAG_METADATA = QName.get("metadata", NAMESPACE);
+for (int x = 0 ; x < 9 ; x++) {
+for (int y = 0 ; y < 9 ; y++) {
-protected final T graph;
+fieldBackup[x][y] = f.getCellValue(x, y);
+}
-private final GraphDocumentMetadata metadata;
+}
+}
-public AbstractGraphDocument(Class<T> graphType) {
-T g;
+private void restoreBackup(Field f, int[][] fieldBackup) {
-try {
+for (int x = 0 ; x < 9 ; x++) {
-g = graphType.newInstance();
+for (int y = 0 ; y < 9 ; y++) {
-} catch (ReflectiveOperationException e) {
+f.setCellValue(x, y, fieldBackup[x][y]);
-assert false;
+}
-g = null; // for the compiler
+}
 }
-graph = g;
-metadata = new GraphDocumentMetadata();
+private void restoreBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
-}
+for (int x = 0 ; x < 9 ; x++) {
+for (int y = 0 ; y < 9 ; y++) {
-public T getGraph() {
+candidates[x][y].clear();
-return graph;
+candidates[x][y].addAll(candidatesBackup[x][y]);
 }
+}
-public GraphDocumentMetadata getMetadata() {
+}
-return metadata;
-}
+private boolean solve(Field f, List<Integer>[][] candidates) {
-protected abstract void writeGraph(Element rootNode) throws IOException;
+// Make backup
-protected abstract void readGraph(Element rootNode) throws IOException;
+List<Integer>[][] candidatesBackup = new List[9][9];
+int[][] fieldBackup = new int[9][9];
-@Override
+makeBackup(candidates, candidatesBackup);
-public void writeTo(OutputStream out) throws IOException {
+makeBackup(f, fieldBackup);
-Document doc = DocumentHelper.createDocument();
+// Fill in distinct solutions
-Element rootNode = doc.addElement(TAG_GRAPHDOC);
+boolean fillDistinct;
+do {
-Element metadataNode = rootNode.addElement(TAG_METADATA);
+fillDistinct = false;
+for (int x = 0 ; x < 9 ; x++) {
-metadata.write(metadataNode);
+for (int y = 0 ; y < 9 ; y++) {
+if (f.isCellEmpty(x, y) && candidates[x][y].size() == 1) {
-if (graph instanceof Graph) {
+fillInCandidate(f, candidates, x, y);
-writeGraph(rootNode.addElement(TAG_GRAPH));
+fillDistinct = true;
-} else if (graph instanceof Digraph) {
+}
-writeGraph(rootNode.addElement(TAG_DIGRAPH));
+}
-} else {
+}
-throw new IOException("unsupported graph type");
+} while (fillDistinct);
-}
+// Try out remaining candidates
-XMLWriter writer = new XMLWriter(out, OutputFormat.createPrettyPrint());
+for (int x = 0 ; x < 9 ; x++) {
-writer.write(doc);
+for (int y = 0 ; y < 9 ; y++) {
-writer.flush();
+if (f.isCellEmpty(x, y)) {
-}
+while (candidates[x][y].size() > 0) {
+List<Integer>[][] cb = new List[9][9];
-@Override
+makeBackup(candidates, cb);
-public void readFrom(InputStream in) throws IOException {
+Integer c = fillInCandidate(f, candidates, x, y);
-try {
+if (solve(f, candidates)) {
-SAXReader reader = new SAXReader(true);
+break;
-reader.setStripWhitespaceText(true);
+} else {
+f.clearCellValue(x, y);
-reader.setFeature(Constants.XERCES_FEATURE_PREFIX+
+restoreBackup(candidates, cb);
-Constants.SCHEMA_VALIDATION_FEATURE, true);
+// Remove current candidate anyway
-reader.setProperty(Constants.XERCES_PROPERTY_PREFIX +
+candidates[x][y].remove(c);
-Constants.SCHEMA_LOCATION, String.format("%s %s",
+}
-NAMESPACE.getURI(), Resources.class.getResource(
+}
-"graph-document.xsd").toExternalForm()));
+}
+if (f.isCellEmpty(x, y)) {
-final AtomicBoolean passed = new AtomicBoolean(true);
+restoreBackup(f, fieldBackup);
-final AtomicReference<SAXParseException> xmlerror = new AtomicReference<>();
+restoreBackup(candidates, candidatesBackup);
-// TODO: we should do more detailed error handling here
+return false;
-reader.setErrorHandler(new ErrorHandler() {
+}
-@Override
+}
-public void warning(SAXParseException exception) throws SAXException {
+}
-}
+return true;
-@Override
+}
-public void error(SAXParseException exception) throws SAXException {
-xmlerror.set(exception);
+/**
-passed.set(false);
+* Attempts to solve the given Sudoku field.
-}
+*
+* The solution, if any, is directly entered into the field.
-@Override
+* All solved fields will be in modified state.
-public void fatalError(SAXParseException exception) throws SAXException {
+* The already given fields are left untouched.
-xmlerror.set(exception);
+*
-passed.set(false);
+* @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) {
-Document doc = reader.read(in);
-if (!passed.get()) {
+// Calculate initial candidates
-// TODO: provide details (maybe via separate error object?)
+List<Integer>[][] candidates = new List[9][9];
-throw xmlerror.get();
+for (int x = 0 ; x < 9 ; x++) {
-}
+for (int y = 0 ; y < 9 ; y++) {
+candidates[x][y] = new ArrayList<>(9);
-doc.normalize();
+if (f.getCellValue(x, y) == 0) {
+// All numbers are candidates
-Element root = doc.getRootElement();
+for (int c = 1 ; c <= 9 ; c++) {
-metadata.read(root.element(TAG_METADATA));
+candidates[x][y].add(c);
+}
-if (graph instanceof Graph) {
+// Remove row duplicates
-readGraph(root.element(TAG_GRAPH));
+int[] line = f.getRow(y);
-} else if (graph instanceof Digraph) {
+for (Integer c : line) {
-readGraph(root.element(TAG_DIGRAPH));
+candidates[x][y].remove(c);
-} else {
+}
-throw new IOException("unsupported graph type");
+// Remove column duplicates
-}
+line = f.getColumn(x);
-} catch (DocumentException | SAXException ex) {
+for (Integer c : line) {
-throw new IOException(ex);
+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);
+}
+}
+}
+}
+}
+// Backtrack
+return solve(f, candidates);
+}
+/**
+* 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;
+}
+}
+}
+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;
+}
+}
+}
+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);
 }
 }

Mercurial > hg > c2html / file comparison

comparison: test/javatest.java

test/javatest.java