diff -r 98adda6171d1 -r 2c8514b3891b test/javatest.java
--- 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);
     }
 }