--- a/test/gs/javatest.html Sun Mar 02 12:47:31 2025 +0100
+++ b/test/gs/javatest.html Sun Mar 02 16:06:24 2025 +0100
@@ -33,6 +33,9 @@
span.c2html-string {
color: darkorange;
}
+ span.c2html-number {
+ color: dodgerblue;
+ }
span.c2html-comment {
color: grey;
}
@@ -44,181 +47,246 @@
<div class="c2html-code">
<a class="c2html-lineno" name="l1" href="#l1"> 1 </a><span class="c2html-comment">/*</span>
-<a class="c2html-lineno" name="l2" href="#l2"> 2 </a><span class="c2html-comment"> * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.</span>
-<a class="c2html-lineno" name="l3" href="#l3"> 3 </a><span class="c2html-comment"> *</span>
-<a class="c2html-lineno" name="l4" href="#l4"> 4 </a><span class="c2html-comment"> * Copyright 2014 Mike Becker. All rights reserved.</span>
-<a class="c2html-lineno" name="l5" href="#l5"> 5 </a><span class="c2html-comment"> *</span>
-<a class="c2html-lineno" name="l6" href="#l6"> 6 </a><span class="c2html-comment"> * Redistribution and use in source and binary forms, with or without</span>
-<a class="c2html-lineno" name="l7" href="#l7"> 7 </a><span class="c2html-comment"> * modification, are permitted provided that the following conditions are met:</span>
-<a class="c2html-lineno" name="l8" href="#l8"> 8 </a><span class="c2html-comment"> *</span>
-<a class="c2html-lineno" name="l9" href="#l9"> 9 </a><span class="c2html-comment"> * 1. Redistributions of source code must retain the above copyright</span>
-<a class="c2html-lineno" name="l10" href="#l10"> 10 </a><span class="c2html-comment"> * notice, this list of conditions and the following disclaimer.</span>
-<a class="c2html-lineno" name="l11" href="#l11"> 11 </a><span class="c2html-comment"> *</span>
-<a class="c2html-lineno" name="l12" href="#l12"> 12 </a><span class="c2html-comment"> * 2. Redistributions in binary form must reproduce the above copyright</span>
-<a class="c2html-lineno" name="l13" href="#l13"> 13 </a><span class="c2html-comment"> * notice, this list of conditions and the following disclaimer in the</span>
-<a class="c2html-lineno" name="l14" href="#l14"> 14 </a><span class="c2html-comment"> * documentation and/or other materials provided with the distribution.</span>
-<a class="c2html-lineno" name="l15" href="#l15"> 15 </a><span class="c2html-comment"> *</span>
-<a class="c2html-lineno" name="l16" href="#l16"> 16 </a><span class="c2html-comment"> * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"</span>
-<a class="c2html-lineno" name="l17" href="#l17"> 17 </a><span class="c2html-comment"> * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE</span>
-<a class="c2html-lineno" name="l18" href="#l18"> 18 </a><span class="c2html-comment"> * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE</span>
-<a class="c2html-lineno" name="l19" href="#l19"> 19 </a><span class="c2html-comment"> * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE</span>
-<a class="c2html-lineno" name="l20" href="#l20"> 20 </a><span class="c2html-comment"> * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR</span>
-<a class="c2html-lineno" name="l21" href="#l21"> 21 </a><span class="c2html-comment"> * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF</span>
-<a class="c2html-lineno" name="l22" href="#l22"> 22 </a><span class="c2html-comment"> * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS</span>
-<a class="c2html-lineno" name="l23" href="#l23"> 23 </a><span class="c2html-comment"> * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN</span>
-<a class="c2html-lineno" name="l24" href="#l24"> 24 </a><span class="c2html-comment"> * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)</span>
-<a class="c2html-lineno" name="l25" href="#l25"> 25 </a><span class="c2html-comment"> * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE</span>
-<a class="c2html-lineno" name="l26" href="#l26"> 26 </a><span class="c2html-comment"> * POSSIBILITY OF SUCH DAMAGE.</span>
-<a class="c2html-lineno" name="l27" href="#l27"> 27 </a><span class="c2html-comment"> *</span>
-<a class="c2html-lineno" name="l28" href="#l28"> 28 </a><span class="c2html-comment"> */</span>
-<a class="c2html-lineno" name="l29" href="#l29"> 29 </a>
-<a class="c2html-lineno" name="l30" href="#l30"> 30 </a><span class="c2html-keyword">package</span> de.uapcore.sigred.doc.base;
+<a class="c2html-lineno" name="l2" href="#l2"> 2 </a><span class="c2html-comment"> * Copyright 2013 Mike Becker. All rights reserved.</span>
+<a class="c2html-lineno" name="l3" href="#l3"> 3 </a><span class="c2html-comment"> * </span>
+<a class="c2html-lineno" name="l4" href="#l4"> 4 </a><span class="c2html-comment"> * Redistribution and use in source and binary forms, with or without</span>
+<a class="c2html-lineno" name="l5" href="#l5"> 5 </a><span class="c2html-comment"> * modification, are permitted provided that the following conditions are met:</span>
+<a class="c2html-lineno" name="l6" href="#l6"> 6 </a><span class="c2html-comment"> * </span>
+<a class="c2html-lineno" name="l7" href="#l7"> 7 </a><span class="c2html-comment"> * 1. Redistributions of source code must retain the above copyright</span>
+<a class="c2html-lineno" name="l8" href="#l8"> 8 </a><span class="c2html-comment"> * notice, this list of conditions and the following disclaimer.</span>
+<a class="c2html-lineno" name="l9" href="#l9"> 9 </a><span class="c2html-comment"> * </span>
+<a class="c2html-lineno" name="l10" href="#l10"> 10 </a><span class="c2html-comment"> * 2. Redistributions in binary form must reproduce the above copyright</span>
+<a class="c2html-lineno" name="l11" href="#l11"> 11 </a><span class="c2html-comment"> * notice, this list of conditions and the following disclaimer in the</span>
+<a class="c2html-lineno" name="l12" href="#l12"> 12 </a><span class="c2html-comment"> * documentation and/or other materials provided with the distribution.</span>
+<a class="c2html-lineno" name="l13" href="#l13"> 13 </a><span class="c2html-comment"> * </span>
+<a class="c2html-lineno" name="l14" href="#l14"> 14 </a><span class="c2html-comment"> * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"</span>
+<a class="c2html-lineno" name="l15" href="#l15"> 15 </a><span class="c2html-comment"> * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE</span>
+<a class="c2html-lineno" name="l16" href="#l16"> 16 </a><span class="c2html-comment"> * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE</span>
+<a class="c2html-lineno" name="l17" href="#l17"> 17 </a><span class="c2html-comment"> * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE</span>
+<a class="c2html-lineno" name="l18" href="#l18"> 18 </a><span class="c2html-comment"> * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR</span>
+<a class="c2html-lineno" name="l19" href="#l19"> 19 </a><span class="c2html-comment"> * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF</span>
+<a class="c2html-lineno" name="l20" href="#l20"> 20 </a><span class="c2html-comment"> * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS</span>
+<a class="c2html-lineno" name="l21" href="#l21"> 21 </a><span class="c2html-comment"> * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN</span>
+<a class="c2html-lineno" name="l22" href="#l22"> 22 </a><span class="c2html-comment"> * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)</span>
+<a class="c2html-lineno" name="l23" href="#l23"> 23 </a><span class="c2html-comment"> * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE</span>
+<a class="c2html-lineno" name="l24" href="#l24"> 24 </a><span class="c2html-comment"> * POSSIBILITY OF SUCH DAMAGE.</span>
+<a class="c2html-lineno" name="l25" href="#l25"> 25 </a><span class="c2html-comment"> */</span>
+<a class="c2html-lineno" name="l26" href="#l26"> 26 </a>
+<a class="c2html-lineno" name="l27" href="#l27"> 27 </a><span class="c2html-keyword">package</span> de.uapcore.sudoku;
+<a class="c2html-lineno" name="l28" href="#l28"> 28 </a>
+<a class="c2html-lineno" name="l29" href="#l29"> 29 </a><span class="c2html-keyword">import</span> java.util.ArrayList;
+<a class="c2html-lineno" name="l30" href="#l30"> 30 </a><span class="c2html-keyword">import</span> java.util.List;
<a class="c2html-lineno" name="l31" href="#l31"> 31 </a>
-<a class="c2html-lineno" name="l32" href="#l32"> 32 </a><span class="c2html-keyword">import</span> de.uapcore.sigred.doc.<span class="c2html-type">Resources</span>;
-<a class="c2html-lineno" name="l33" href="#l33"> 33 </a><span class="c2html-keyword">import</span> de.uapcore.sigrapi.impl.<span class="c2html-type">Digraph</span>;
-<a class="c2html-lineno" name="l34" href="#l34"> 34 </a><span class="c2html-keyword">import</span> de.uapcore.sigrapi.impl.<span class="c2html-type">Graph</span>;
-<a class="c2html-lineno" name="l35" href="#l35"> 35 </a><span class="c2html-keyword">import</span> de.uapcore.sigrapi.<span class="c2html-type">IGraph</span>;
-<a class="c2html-lineno" name="l36" href="#l36"> 36 </a><span class="c2html-keyword">import</span> java.io.<span class="c2html-type">IOException</span>;
-<a class="c2html-lineno" name="l37" href="#l37"> 37 </a><span class="c2html-keyword">import</span> java.io.<span class="c2html-type">InputStream</span>;
-<a class="c2html-lineno" name="l38" href="#l38"> 38 </a><span class="c2html-keyword">import</span> java.io.<span class="c2html-type">OutputStream</span>;
-<a class="c2html-lineno" name="l39" href="#l39"> 39 </a><span class="c2html-keyword">import</span> java.util.concurrent.atomic.<span class="c2html-type">AtomicBoolean</span>;
-<a class="c2html-lineno" name="l40" href="#l40"> 40 </a><span class="c2html-keyword">import</span> java.util.concurrent.atomic.<span class="c2html-type">AtomicReference</span>;
-<a class="c2html-lineno" name="l41" href="#l41"> 41 </a><span class="c2html-keyword">import</span> org.apache.xerces.impl.<span class="c2html-type">Constants</span>;
-<a class="c2html-lineno" name="l42" href="#l42"> 42 </a><span class="c2html-keyword">import</span> org.dom4j.<span class="c2html-type">Document</span>;
-<a class="c2html-lineno" name="l43" href="#l43"> 43 </a><span class="c2html-keyword">import</span> org.dom4j.<span class="c2html-type">DocumentException</span>;
-<a class="c2html-lineno" name="l44" href="#l44"> 44 </a><span class="c2html-keyword">import</span> org.dom4j.<span class="c2html-type">DocumentHelper</span>;
-<a class="c2html-lineno" name="l45" href="#l45"> 45 </a><span class="c2html-keyword">import</span> org.dom4j.<span class="c2html-type">Element</span>;
-<a class="c2html-lineno" name="l46" href="#l46"> 46 </a><span class="c2html-keyword">import</span> org.dom4j.<span class="c2html-type">Namespace</span>;
-<a class="c2html-lineno" name="l47" href="#l47"> 47 </a><span class="c2html-keyword">import</span> org.dom4j.<span class="c2html-type">QName</span>;
-<a class="c2html-lineno" name="l48" href="#l48"> 48 </a><span class="c2html-keyword">import</span> org.dom4j.io.<span class="c2html-type">OutputFormat</span>;
-<a class="c2html-lineno" name="l49" href="#l49"> 49 </a><span class="c2html-keyword">import</span> org.dom4j.io.<span class="c2html-type">SAXReader</span>;
-<a class="c2html-lineno" name="l50" href="#l50"> 50 </a><span class="c2html-keyword">import</span> org.dom4j.io.<span class="c2html-type">XMLWriter</span>;
-<a class="c2html-lineno" name="l51" href="#l51"> 51 </a><span class="c2html-keyword">import</span> org.xml.sax.<span class="c2html-type">ErrorHandler</span>;
-<a class="c2html-lineno" name="l52" href="#l52"> 52 </a><span class="c2html-keyword">import</span> org.xml.sax.<span class="c2html-type">SAXException</span>;
-<a class="c2html-lineno" name="l53" href="#l53"> 53 </a><span class="c2html-keyword">import</span> org.xml.sax.<span class="c2html-type">SAXParseException</span>;
-<a class="c2html-lineno" name="l54" href="#l54"> 54 </a>
-<a class="c2html-lineno" name="l55" href="#l55"> 55 </a><span class="c2html-keyword">public</span> <span class="c2html-keyword">abstract</span> <span class="c2html-keyword">class</span> <span class="c2html-type">AbstractGraphDocument</span><<span class="c2html-type">T</span> <span class="c2html-keyword">extends</span> <span class="c2html-type">IGraph</span>>
-<a class="c2html-lineno" name="l56" href="#l56"> 56 </a> <span class="c2html-keyword">extends</span> <span class="c2html-type">FileBackedDocument</span> {
-<a class="c2html-lineno" name="l57" href="#l57"> 57 </a>
-<a class="c2html-lineno" name="l58" href="#l58"> 58 </a> <span class="c2html-keyword">protected</span> <span class="c2html-keyword">static</span> <span class="c2html-keyword">final</span> <span class="c2html-type">Namespace</span> <span class="c2html-type">NAMESPACE</span> = <span class="c2html-type">Namespace</span>.get(<span class="c2html-string">"sigred"</span>,
-<a class="c2html-lineno" name="l59" href="#l59"> 59 </a> <span class="c2html-string">"http://develop.uap-core.de/sigred/"</span>);
-<a class="c2html-lineno" name="l60" href="#l60"> 60 </a>
-<a class="c2html-lineno" name="l61" href="#l61"> 61 </a> <span class="c2html-keyword">private</span> <span class="c2html-keyword">static</span> <span class="c2html-keyword">final</span>
-<a class="c2html-lineno" name="l62" href="#l62"> 62 </a> <span class="c2html-type">QName</span> <span class="c2html-type">TAG_GRAPHDOC</span> = <span class="c2html-type">QName</span>.get(<span class="c2html-string">"graph-document"</span>, <span class="c2html-type">NAMESPACE</span>);
-<a class="c2html-lineno" name="l63" href="#l63"> 63 </a> <span class="c2html-keyword">private</span> <span class="c2html-keyword">static</span> <span class="c2html-keyword">final</span>
-<a class="c2html-lineno" name="l64" href="#l64"> 64 </a> <span class="c2html-type">QName</span> <span class="c2html-type">TAG_GRAPH</span> = <span class="c2html-type">QName</span>.get(<span class="c2html-string">"graph"</span>, <span class="c2html-type">NAMESPACE</span>);
-<a class="c2html-lineno" name="l65" href="#l65"> 65 </a> <span class="c2html-keyword">private</span> <span class="c2html-keyword">static</span> <span class="c2html-keyword">final</span>
-<a class="c2html-lineno" name="l66" href="#l66"> 66 </a> <span class="c2html-type">QName</span> <span class="c2html-type">TAG_DIGRAPH</span> = <span class="c2html-type">QName</span>.get(<span class="c2html-string">"digraph"</span>, <span class="c2html-type">NAMESPACE</span>);
-<a class="c2html-lineno" name="l67" href="#l67"> 67 </a> <span class="c2html-keyword">private</span> <span class="c2html-keyword">static</span> <span class="c2html-keyword">final</span>
-<a class="c2html-lineno" name="l68" href="#l68"> 68 </a> <span class="c2html-type">QName</span> <span class="c2html-type">TAG_METADATA</span> = <span class="c2html-type">QName</span>.get(<span class="c2html-string">"metadata"</span>, <span class="c2html-type">NAMESPACE</span>);
-<a class="c2html-lineno" name="l69" href="#l69"> 69 </a>
-<a class="c2html-lineno" name="l70" href="#l70"> 70 </a> <span class="c2html-keyword">protected</span> <span class="c2html-keyword">final</span> <span class="c2html-type">T</span> graph;
+<a class="c2html-lineno" name="l32" href="#l32"> 32 </a><span class="c2html-comment">/**</span>
+<a class="c2html-lineno" name="l33" href="#l33"> 33 </a><span class="c2html-comment"> * Implements the backtracking algorithm for solving the Sudoku.</span>
+<a class="c2html-lineno" name="l34" href="#l34"> 34 </a><span class="c2html-comment"> */</span>
+<a class="c2html-lineno" name="l35" href="#l35"> 35 </a><span class="c2html-keyword">public</span> <span class="c2html-keyword">final</span> <span class="c2html-keyword">class</span> <span class="c2html-type">Solver</span> {
+<a class="c2html-lineno" name="l36" href="#l36"> 36 </a>
+<a class="c2html-lineno" name="l37" href="#l37"> 37 </a> <span class="c2html-keyword">public</span> <span class="c2html-keyword">static</span> <span class="c2html-keyword">final</span> <span class="c2html-keyword">int</span> <span class="c2html-type">VERSION</span> = <span class="c2html-number">0x1000</span>;
+<a class="c2html-lineno" name="l38" href="#l38"> 38 </a>
+<a class="c2html-lineno" name="l39" href="#l39"> 39 </a> <span class="c2html-keyword">private</span> <span class="c2html-type">Integer</span> fillInCandidate(<span class="c2html-type">Field</span> f, <span class="c2html-type">List</span><<span class="c2html-type">Integer</span>>[][] candidates, <span class="c2html-keyword">int</span> x, <span class="c2html-keyword">int</span> y) {
+<a class="c2html-lineno" name="l40" href="#l40"> 40 </a> <span class="c2html-type">Integer</span> c = candidates[x][y].remove(<span class="c2html-number">0</span>);
+<a class="c2html-lineno" name="l41" href="#l41"> 41 </a> f.setCellValue(x, y, c);
+<a class="c2html-lineno" name="l42" href="#l42"> 42 </a> f.setCellModified(x, y, true);
+<a class="c2html-lineno" name="l43" href="#l43"> 43 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> i = <span class="c2html-number">0</span> ; i < <span class="c2html-number">9</span> ; i++) {
+<a class="c2html-lineno" name="l44" href="#l44"> 44 </a> candidates[x][i].remove(c);
+<a class="c2html-lineno" name="l45" href="#l45"> 45 </a> candidates[i][y].remove(c);
+<a class="c2html-lineno" name="l46" href="#l46"> 46 </a> }
+<a class="c2html-lineno" name="l47" href="#l47"> 47 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> i = <span class="c2html-number">0</span> ; i < <span class="c2html-number">3</span> ; i++) {
+<a class="c2html-lineno" name="l48" href="#l48"> 48 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> j = <span class="c2html-number">0</span> ; j < <span class="c2html-number">3</span> ; j++) {
+<a class="c2html-lineno" name="l49" href="#l49"> 49 </a> candidates[x-x%<span class="c2html-number">3</span>+i][y-y%<span class="c2html-number">3</span>+j].remove(c);
+<a class="c2html-lineno" name="l50" href="#l50"> 50 </a> }
+<a class="c2html-lineno" name="l51" href="#l51"> 51 </a> }
+<a class="c2html-lineno" name="l52" href="#l52"> 52 </a> <span class="c2html-keyword">return</span> c;
+<a class="c2html-lineno" name="l53" href="#l53"> 53 </a> }
+<a class="c2html-lineno" name="l54" href="#l54"> 54 </a>
+<a class="c2html-lineno" name="l55" href="#l55"> 55 </a> <span class="c2html-keyword">private</span> <span class="c2html-keyword">void</span> makeBackup(<span class="c2html-type">List</span><<span class="c2html-type">Integer</span>>[][] candidates, <span class="c2html-type">List</span><<span class="c2html-type">Integer</span>>[][] candidatesBackup) {
+<a class="c2html-lineno" name="l56" href="#l56"> 56 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> x = <span class="c2html-number">0</span> ; x < <span class="c2html-number">9</span> ; x++) {
+<a class="c2html-lineno" name="l57" href="#l57"> 57 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> y = <span class="c2html-number">0</span> ; y < <span class="c2html-number">9</span> ; y++) {
+<a class="c2html-lineno" name="l58" href="#l58"> 58 </a> candidatesBackup[x][y] = <span class="c2html-keyword">new</span> <span class="c2html-type">ArrayList</span><>(<span class="c2html-number">9</span>);
+<a class="c2html-lineno" name="l59" href="#l59"> 59 </a> candidatesBackup[x][y].addAll(candidates[x][y]);
+<a class="c2html-lineno" name="l60" href="#l60"> 60 </a> }
+<a class="c2html-lineno" name="l61" href="#l61"> 61 </a> }
+<a class="c2html-lineno" name="l62" href="#l62"> 62 </a> }
+<a class="c2html-lineno" name="l63" href="#l63"> 63 </a>
+<a class="c2html-lineno" name="l64" href="#l64"> 64 </a> <span class="c2html-keyword">private</span> <span class="c2html-keyword">void</span> makeBackup(<span class="c2html-type">Field</span> f, <span class="c2html-keyword">int</span>[][] fieldBackup) {
+<a class="c2html-lineno" name="l65" href="#l65"> 65 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> x = <span class="c2html-number">0</span> ; x < <span class="c2html-number">9</span> ; x++) {
+<a class="c2html-lineno" name="l66" href="#l66"> 66 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> y = <span class="c2html-number">0</span> ; y < <span class="c2html-number">9</span> ; y++) {
+<a class="c2html-lineno" name="l67" href="#l67"> 67 </a> fieldBackup[x][y] = f.getCellValue(x, y);
+<a class="c2html-lineno" name="l68" href="#l68"> 68 </a> }
+<a class="c2html-lineno" name="l69" href="#l69"> 69 </a> }
+<a class="c2html-lineno" name="l70" href="#l70"> 70 </a> }
<a class="c2html-lineno" name="l71" href="#l71"> 71 </a>
-<a class="c2html-lineno" name="l72" href="#l72"> 72 </a> <span class="c2html-keyword">private</span> <span class="c2html-keyword">final</span> <span class="c2html-type">GraphDocumentMetadata</span> metadata;
-<a class="c2html-lineno" name="l73" href="#l73"> 73 </a>
-<a class="c2html-lineno" name="l74" href="#l74"> 74 </a> <span class="c2html-keyword">public</span> <span class="c2html-type">AbstractGraphDocument</span>(<span class="c2html-type">Class</span><<span class="c2html-type">T</span>> graphType) {
-<a class="c2html-lineno" name="l75" href="#l75"> 75 </a> <span class="c2html-type">T</span> g;
-<a class="c2html-lineno" name="l76" href="#l76"> 76 </a> <span class="c2html-keyword">try</span> {
-<a class="c2html-lineno" name="l77" href="#l77"> 77 </a> g = graphType.newInstance();
-<a class="c2html-lineno" name="l78" href="#l78"> 78 </a> } <span class="c2html-keyword">catch</span> (<span class="c2html-type">ReflectiveOperationException</span> e) {
-<a class="c2html-lineno" name="l79" href="#l79"> 79 </a> <span class="c2html-keyword">assert</span> false;
-<a class="c2html-lineno" name="l80" href="#l80"> 80 </a> g = null; <span class="c2html-comment">// for the compiler</span>
-<a class="c2html-lineno" name="l81" href="#l81"> 81 </a> }
-<a class="c2html-lineno" name="l82" href="#l82"> 82 </a> graph = g;
-<a class="c2html-lineno" name="l83" href="#l83"> 83 </a> metadata = <span class="c2html-keyword">new</span> <span class="c2html-type">GraphDocumentMetadata</span>();
-<a class="c2html-lineno" name="l84" href="#l84"> 84 </a> }
-<a class="c2html-lineno" name="l85" href="#l85"> 85 </a>
-<a class="c2html-lineno" name="l86" href="#l86"> 86 </a> <span class="c2html-keyword">public</span> <span class="c2html-type">T</span> getGraph() {
-<a class="c2html-lineno" name="l87" href="#l87"> 87 </a> <span class="c2html-keyword">return</span> graph;
-<a class="c2html-lineno" name="l88" href="#l88"> 88 </a> }
-<a class="c2html-lineno" name="l89" href="#l89"> 89 </a>
-<a class="c2html-lineno" name="l90" href="#l90"> 90 </a> <span class="c2html-keyword">public</span> <span class="c2html-type">GraphDocumentMetadata</span> getMetadata() {
-<a class="c2html-lineno" name="l91" href="#l91"> 91 </a> <span class="c2html-keyword">return</span> metadata;
-<a class="c2html-lineno" name="l92" href="#l92"> 92 </a> }
-<a class="c2html-lineno" name="l93" href="#l93"> 93 </a>
-<a class="c2html-lineno" name="l94" href="#l94"> 94 </a> <span class="c2html-keyword">protected</span> <span class="c2html-keyword">abstract</span> <span class="c2html-keyword">void</span> writeGraph(<span class="c2html-type">Element</span> rootNode) <span class="c2html-keyword">throws</span> <span class="c2html-type">IOException</span>;
-<a class="c2html-lineno" name="l95" href="#l95"> 95 </a> <span class="c2html-keyword">protected</span> <span class="c2html-keyword">abstract</span> <span class="c2html-keyword">void</span> readGraph(<span class="c2html-type">Element</span> rootNode) <span class="c2html-keyword">throws</span> <span class="c2html-type">IOException</span>;
-<a class="c2html-lineno" name="l96" href="#l96"> 96 </a>
-<a class="c2html-lineno" name="l97" href="#l97"> 97 </a> <span class="c2html-directive">@Override</span>
-<a class="c2html-lineno" name="l98" href="#l98"> 98 </a> <span class="c2html-keyword">public</span> <span class="c2html-keyword">void</span> writeTo(<span class="c2html-type">OutputStream</span> out) <span class="c2html-keyword">throws</span> <span class="c2html-type">IOException</span> {
-<a class="c2html-lineno" name="l99" href="#l99"> 99 </a> <span class="c2html-type">Document</span> doc = <span class="c2html-type">DocumentHelper</span>.createDocument();
-<a class="c2html-lineno" name="l100" href="#l100">100 </a>
-<a class="c2html-lineno" name="l101" href="#l101">101 </a> <span class="c2html-type">Element</span> rootNode = doc.addElement(<span class="c2html-type">TAG_GRAPHDOC</span>);
-<a class="c2html-lineno" name="l102" href="#l102">102 </a>
-<a class="c2html-lineno" name="l103" href="#l103">103 </a> <span class="c2html-type">Element</span> metadataNode = rootNode.addElement(<span class="c2html-type">TAG_METADATA</span>);
-<a class="c2html-lineno" name="l104" href="#l104">104 </a>
-<a class="c2html-lineno" name="l105" href="#l105">105 </a> metadata.write(metadataNode);
-<a class="c2html-lineno" name="l106" href="#l106">106 </a>
-<a class="c2html-lineno" name="l107" href="#l107">107 </a> <span class="c2html-keyword">if</span> (graph <span class="c2html-keyword">instanceof</span> <span class="c2html-type">Graph</span>) {
-<a class="c2html-lineno" name="l108" href="#l108">108 </a> writeGraph(rootNode.addElement(<span class="c2html-type">TAG_GRAPH</span>));
-<a class="c2html-lineno" name="l109" href="#l109">109 </a> } <span class="c2html-keyword">else</span> <span class="c2html-keyword">if</span> (graph <span class="c2html-keyword">instanceof</span> <span class="c2html-type">Digraph</span>) {
-<a class="c2html-lineno" name="l110" href="#l110">110 </a> writeGraph(rootNode.addElement(<span class="c2html-type">TAG_DIGRAPH</span>));
-<a class="c2html-lineno" name="l111" href="#l111">111 </a> } <span class="c2html-keyword">else</span> {
-<a class="c2html-lineno" name="l112" href="#l112">112 </a> <span class="c2html-keyword">throw</span> <span class="c2html-keyword">new</span> <span class="c2html-type">IOException</span>(<span class="c2html-string">"unsupported graph type"</span>);
-<a class="c2html-lineno" name="l113" href="#l113">113 </a> }
-<a class="c2html-lineno" name="l114" href="#l114">114 </a>
-<a class="c2html-lineno" name="l115" href="#l115">115 </a> <span class="c2html-type">XMLWriter</span> writer = <span class="c2html-keyword">new</span> <span class="c2html-type">XMLWriter</span>(out, <span class="c2html-type">OutputFormat</span>.createPrettyPrint());
-<a class="c2html-lineno" name="l116" href="#l116">116 </a> writer.write(doc);
-<a class="c2html-lineno" name="l117" href="#l117">117 </a> writer.flush();
-<a class="c2html-lineno" name="l118" href="#l118">118 </a> }
-<a class="c2html-lineno" name="l119" href="#l119">119 </a>
-<a class="c2html-lineno" name="l120" href="#l120">120 </a> <span class="c2html-directive">@Override</span>
-<a class="c2html-lineno" name="l121" href="#l121">121 </a> <span class="c2html-keyword">public</span> <span class="c2html-keyword">void</span> readFrom(<span class="c2html-type">InputStream</span> in) <span class="c2html-keyword">throws</span> <span class="c2html-type">IOException</span> {
-<a class="c2html-lineno" name="l122" href="#l122">122 </a> <span class="c2html-keyword">try</span> {
-<a class="c2html-lineno" name="l123" href="#l123">123 </a> <span class="c2html-type">SAXReader</span> reader = <span class="c2html-keyword">new</span> <span class="c2html-type">SAXReader</span>(true);
-<a class="c2html-lineno" name="l124" href="#l124">124 </a> reader.setStripWhitespaceText(true);
-<a class="c2html-lineno" name="l125" href="#l125">125 </a>
-<a class="c2html-lineno" name="l126" href="#l126">126 </a> reader.setFeature(<span class="c2html-type">Constants</span>.<span class="c2html-type">XERCES_FEATURE_PREFIX</span>+
-<a class="c2html-lineno" name="l127" href="#l127">127 </a> <span class="c2html-type">Constants</span>.<span class="c2html-type">SCHEMA_VALIDATION_FEATURE</span>, true);
-<a class="c2html-lineno" name="l128" href="#l128">128 </a> reader.setProperty(<span class="c2html-type">Constants</span>.<span class="c2html-type">XERCES_PROPERTY_PREFIX</span> +
-<a class="c2html-lineno" name="l129" href="#l129">129 </a> <span class="c2html-type">Constants</span>.<span class="c2html-type">SCHEMA_LOCATION</span>, <span class="c2html-type">String</span>.format(<span class="c2html-string">"%s %s"</span>,
-<a class="c2html-lineno" name="l130" href="#l130">130 </a> <span class="c2html-type">NAMESPACE</span>.getURI(), <span class="c2html-type">Resources</span>.<span class="c2html-keyword">class</span>.getResource(
-<a class="c2html-lineno" name="l131" href="#l131">131 </a> <span class="c2html-string">"graph-document.xsd"</span>).toExternalForm()));
-<a class="c2html-lineno" name="l132" href="#l132">132 </a>
-<a class="c2html-lineno" name="l133" href="#l133">133 </a> <span class="c2html-keyword">final</span> <span class="c2html-type">AtomicBoolean</span> passed = <span class="c2html-keyword">new</span> <span class="c2html-type">AtomicBoolean</span>(true);
-<a class="c2html-lineno" name="l134" href="#l134">134 </a> <span class="c2html-keyword">final</span> <span class="c2html-type">AtomicReference</span><<span class="c2html-type">SAXParseException</span>> xmlerror = <span class="c2html-keyword">new</span> <span class="c2html-type">AtomicReference</span><>();
-<a class="c2html-lineno" name="l135" href="#l135">135 </a> <span class="c2html-comment">// TODO: we should do more detailed error handling here</span>
-<a class="c2html-lineno" name="l136" href="#l136">136 </a> reader.setErrorHandler(<span class="c2html-keyword">new</span> <span class="c2html-type">ErrorHandler</span>() {
-<a class="c2html-lineno" name="l137" href="#l137">137 </a> <span class="c2html-directive">@Override</span>
-<a class="c2html-lineno" name="l138" href="#l138">138 </a> <span class="c2html-keyword">public</span> <span class="c2html-keyword">void</span> warning(<span class="c2html-type">SAXParseException</span> exception) <span class="c2html-keyword">throws</span> <span class="c2html-type">SAXException</span> {
-<a class="c2html-lineno" name="l139" href="#l139">139 </a> }
-<a class="c2html-lineno" name="l140" href="#l140">140 </a>
-<a class="c2html-lineno" name="l141" href="#l141">141 </a> <span class="c2html-directive">@Override</span>
-<a class="c2html-lineno" name="l142" href="#l142">142 </a> <span class="c2html-keyword">public</span> <span class="c2html-keyword">void</span> error(<span class="c2html-type">SAXParseException</span> exception) <span class="c2html-keyword">throws</span> <span class="c2html-type">SAXException</span> {
-<a class="c2html-lineno" name="l143" href="#l143">143 </a> xmlerror.set(exception);
-<a class="c2html-lineno" name="l144" href="#l144">144 </a> passed.set(false);
-<a class="c2html-lineno" name="l145" href="#l145">145 </a> }
-<a class="c2html-lineno" name="l146" href="#l146">146 </a>
-<a class="c2html-lineno" name="l147" href="#l147">147 </a> <span class="c2html-directive">@Override</span>
-<a class="c2html-lineno" name="l148" href="#l148">148 </a> <span class="c2html-keyword">public</span> <span class="c2html-keyword">void</span> fatalError(<span class="c2html-type">SAXParseException</span> exception) <span class="c2html-keyword">throws</span> <span class="c2html-type">SAXException</span> {
-<a class="c2html-lineno" name="l149" href="#l149">149 </a> xmlerror.set(exception);
-<a class="c2html-lineno" name="l150" href="#l150">150 </a> passed.set(false);
-<a class="c2html-lineno" name="l151" href="#l151">151 </a> }
-<a class="c2html-lineno" name="l152" href="#l152">152 </a>
-<a class="c2html-lineno" name="l153" href="#l153">153 </a> });
-<a class="c2html-lineno" name="l154" href="#l154">154 </a> <span class="c2html-type">Document</span> doc = reader.read(in);
-<a class="c2html-lineno" name="l155" href="#l155">155 </a> <span class="c2html-keyword">if</span> (!passed.get()) {
-<a class="c2html-lineno" name="l156" href="#l156">156 </a> <span class="c2html-comment">// TODO: provide details (maybe via separate error object?)</span>
-<a class="c2html-lineno" name="l157" href="#l157">157 </a> <span class="c2html-keyword">throw</span> xmlerror.get();
-<a class="c2html-lineno" name="l158" href="#l158">158 </a> }
-<a class="c2html-lineno" name="l159" href="#l159">159 </a>
-<a class="c2html-lineno" name="l160" href="#l160">160 </a> doc.normalize();
-<a class="c2html-lineno" name="l161" href="#l161">161 </a>
-<a class="c2html-lineno" name="l162" href="#l162">162 </a> <span class="c2html-type">Element</span> root = doc.getRootElement();
-<a class="c2html-lineno" name="l163" href="#l163">163 </a> metadata.read(root.element(<span class="c2html-type">TAG_METADATA</span>));
-<a class="c2html-lineno" name="l164" href="#l164">164 </a>
-<a class="c2html-lineno" name="l165" href="#l165">165 </a> <span class="c2html-keyword">if</span> (graph <span class="c2html-keyword">instanceof</span> <span class="c2html-type">Graph</span>) {
-<a class="c2html-lineno" name="l166" href="#l166">166 </a> readGraph(root.element(<span class="c2html-type">TAG_GRAPH</span>));
-<a class="c2html-lineno" name="l167" href="#l167">167 </a> } <span class="c2html-keyword">else</span> <span class="c2html-keyword">if</span> (graph <span class="c2html-keyword">instanceof</span> <span class="c2html-type">Digraph</span>) {
-<a class="c2html-lineno" name="l168" href="#l168">168 </a> readGraph(root.element(<span class="c2html-type">TAG_DIGRAPH</span>));
-<a class="c2html-lineno" name="l169" href="#l169">169 </a> } <span class="c2html-keyword">else</span> {
-<a class="c2html-lineno" name="l170" href="#l170">170 </a> <span class="c2html-keyword">throw</span> <span class="c2html-keyword">new</span> <span class="c2html-type">IOException</span>(<span class="c2html-string">"unsupported graph type"</span>);
-<a class="c2html-lineno" name="l171" href="#l171">171 </a> }
-<a class="c2html-lineno" name="l172" href="#l172">172 </a> } <span class="c2html-keyword">catch</span> (<span class="c2html-type">DocumentException</span> | <span class="c2html-type">SAXException</span> ex) {
-<a class="c2html-lineno" name="l173" href="#l173">173 </a> <span class="c2html-keyword">throw</span> <span class="c2html-keyword">new</span> <span class="c2html-type">IOException</span>(ex);
-<a class="c2html-lineno" name="l174" href="#l174">174 </a> }
-<a class="c2html-lineno" name="l175" href="#l175">175 </a> }
-<a class="c2html-lineno" name="l176" href="#l176">176 </a>}
+<a class="c2html-lineno" name="l72" href="#l72"> 72 </a> <span class="c2html-keyword">private</span> <span class="c2html-keyword">void</span> restoreBackup(<span class="c2html-type">Field</span> f, <span class="c2html-keyword">int</span>[][] fieldBackup) {
+<a class="c2html-lineno" name="l73" href="#l73"> 73 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> x = <span class="c2html-number">0</span> ; x < <span class="c2html-number">9</span> ; x++) {
+<a class="c2html-lineno" name="l74" href="#l74"> 74 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> y = <span class="c2html-number">0</span> ; y < <span class="c2html-number">9</span> ; y++) {
+<a class="c2html-lineno" name="l75" href="#l75"> 75 </a> f.setCellValue(x, y, fieldBackup[x][y]);
+<a class="c2html-lineno" name="l76" href="#l76"> 76 </a> }
+<a class="c2html-lineno" name="l77" href="#l77"> 77 </a> }
+<a class="c2html-lineno" name="l78" href="#l78"> 78 </a> }
+<a class="c2html-lineno" name="l79" href="#l79"> 79 </a>
+<a class="c2html-lineno" name="l80" href="#l80"> 80 </a> <span class="c2html-keyword">private</span> <span class="c2html-keyword">void</span> restoreBackup(<span class="c2html-type">List</span><<span class="c2html-type">Integer</span>>[][] candidates, <span class="c2html-type">List</span><<span class="c2html-type">Integer</span>>[][] candidatesBackup) {
+<a class="c2html-lineno" name="l81" href="#l81"> 81 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> x = <span class="c2html-number">0</span> ; x < <span class="c2html-number">9</span> ; x++) {
+<a class="c2html-lineno" name="l82" href="#l82"> 82 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> y = <span class="c2html-number">0</span> ; y < <span class="c2html-number">9</span> ; y++) {
+<a class="c2html-lineno" name="l83" href="#l83"> 83 </a> candidates[x][y].clear();
+<a class="c2html-lineno" name="l84" href="#l84"> 84 </a> candidates[x][y].addAll(candidatesBackup[x][y]);
+<a class="c2html-lineno" name="l85" href="#l85"> 85 </a> }
+<a class="c2html-lineno" name="l86" href="#l86"> 86 </a> }
+<a class="c2html-lineno" name="l87" href="#l87"> 87 </a> }
+<a class="c2html-lineno" name="l88" href="#l88"> 88 </a>
+<a class="c2html-lineno" name="l89" href="#l89"> 89 </a> <span class="c2html-keyword">private</span> <span class="c2html-keyword">boolean</span> solve(<span class="c2html-type">Field</span> f, <span class="c2html-type">List</span><<span class="c2html-type">Integer</span>>[][] candidates) {
+<a class="c2html-lineno" name="l90" href="#l90"> 90 </a>
+<a class="c2html-lineno" name="l91" href="#l91"> 91 </a> <span class="c2html-comment">// Make backup</span>
+<a class="c2html-lineno" name="l92" href="#l92"> 92 </a> <span class="c2html-type">List</span><<span class="c2html-type">Integer</span>>[][] candidatesBackup = <span class="c2html-keyword">new</span> <span class="c2html-type">List</span>[<span class="c2html-number">9</span>][<span class="c2html-number">9</span>];
+<a class="c2html-lineno" name="l93" href="#l93"> 93 </a> <span class="c2html-keyword">int</span>[][] fieldBackup = <span class="c2html-keyword">new</span> <span class="c2html-keyword">int</span>[<span class="c2html-number">9</span>][<span class="c2html-number">9</span>];
+<a class="c2html-lineno" name="l94" href="#l94"> 94 </a> makeBackup(candidates, candidatesBackup);
+<a class="c2html-lineno" name="l95" href="#l95"> 95 </a> makeBackup(f, fieldBackup);
+<a class="c2html-lineno" name="l96" href="#l96"> 96 </a>
+<a class="c2html-lineno" name="l97" href="#l97"> 97 </a> <span class="c2html-comment">// Fill in distinct solutions</span>
+<a class="c2html-lineno" name="l98" href="#l98"> 98 </a> <span class="c2html-keyword">boolean</span> fillDistinct;
+<a class="c2html-lineno" name="l99" href="#l99"> 99 </a> <span class="c2html-keyword">do</span> {
+<a class="c2html-lineno" name="l100" href="#l100">100 </a> fillDistinct = false;
+<a class="c2html-lineno" name="l101" href="#l101">101 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> x = <span class="c2html-number">0</span> ; x < <span class="c2html-number">9</span> ; x++) {
+<a class="c2html-lineno" name="l102" href="#l102">102 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> y = <span class="c2html-number">0</span> ; y < <span class="c2html-number">9</span> ; y++) {
+<a class="c2html-lineno" name="l103" href="#l103">103 </a> <span class="c2html-keyword">if</span> (f.isCellEmpty(x, y) && candidates[x][y].size() == <span class="c2html-number">1</span>) {
+<a class="c2html-lineno" name="l104" href="#l104">104 </a> fillInCandidate(f, candidates, x, y);
+<a class="c2html-lineno" name="l105" href="#l105">105 </a> fillDistinct = true;
+<a class="c2html-lineno" name="l106" href="#l106">106 </a> }
+<a class="c2html-lineno" name="l107" href="#l107">107 </a> }
+<a class="c2html-lineno" name="l108" href="#l108">108 </a> }
+<a class="c2html-lineno" name="l109" href="#l109">109 </a> } <span class="c2html-keyword">while</span> (fillDistinct);
+<a class="c2html-lineno" name="l110" href="#l110">110 </a>
+<a class="c2html-lineno" name="l111" href="#l111">111 </a> <span class="c2html-comment">// Try out remaining candidates</span>
+<a class="c2html-lineno" name="l112" href="#l112">112 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> x = <span class="c2html-number">0</span> ; x < <span class="c2html-number">9</span> ; x++) {
+<a class="c2html-lineno" name="l113" href="#l113">113 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> y = <span class="c2html-number">0</span> ; y < <span class="c2html-number">9</span> ; y++) {
+<a class="c2html-lineno" name="l114" href="#l114">114 </a> <span class="c2html-keyword">if</span> (f.isCellEmpty(x, y)) {
+<a class="c2html-lineno" name="l115" href="#l115">115 </a> <span class="c2html-keyword">while</span> (candidates[x][y].size() > <span class="c2html-number">0</span>) {
+<a class="c2html-lineno" name="l116" href="#l116">116 </a> <span class="c2html-type">List</span><<span class="c2html-type">Integer</span>>[][] cb = <span class="c2html-keyword">new</span> <span class="c2html-type">List</span>[<span class="c2html-number">9</span>][<span class="c2html-number">9</span>];
+<a class="c2html-lineno" name="l117" href="#l117">117 </a> makeBackup(candidates, cb);
+<a class="c2html-lineno" name="l118" href="#l118">118 </a> <span class="c2html-type">Integer</span> c = fillInCandidate(f, candidates, x, y);
+<a class="c2html-lineno" name="l119" href="#l119">119 </a> <span class="c2html-keyword">if</span> (solve(f, candidates)) {
+<a class="c2html-lineno" name="l120" href="#l120">120 </a> <span class="c2html-keyword">break</span>;
+<a class="c2html-lineno" name="l121" href="#l121">121 </a> } <span class="c2html-keyword">else</span> {
+<a class="c2html-lineno" name="l122" href="#l122">122 </a> f.clearCellValue(x, y);
+<a class="c2html-lineno" name="l123" href="#l123">123 </a> restoreBackup(candidates, cb);
+<a class="c2html-lineno" name="l124" href="#l124">124 </a> <span class="c2html-comment">// Remove current candidate anyway</span>
+<a class="c2html-lineno" name="l125" href="#l125">125 </a> candidates[x][y].remove(c);
+<a class="c2html-lineno" name="l126" href="#l126">126 </a> }
+<a class="c2html-lineno" name="l127" href="#l127">127 </a> }
+<a class="c2html-lineno" name="l128" href="#l128">128 </a> }
+<a class="c2html-lineno" name="l129" href="#l129">129 </a> <span class="c2html-keyword">if</span> (f.isCellEmpty(x, y)) {
+<a class="c2html-lineno" name="l130" href="#l130">130 </a> restoreBackup(f, fieldBackup);
+<a class="c2html-lineno" name="l131" href="#l131">131 </a> restoreBackup(candidates, candidatesBackup);
+<a class="c2html-lineno" name="l132" href="#l132">132 </a> <span class="c2html-keyword">return</span> false;
+<a class="c2html-lineno" name="l133" href="#l133">133 </a> }
+<a class="c2html-lineno" name="l134" href="#l134">134 </a> }
+<a class="c2html-lineno" name="l135" href="#l135">135 </a> }
+<a class="c2html-lineno" name="l136" href="#l136">136 </a>
+<a class="c2html-lineno" name="l137" href="#l137">137 </a> <span class="c2html-keyword">return</span> true;
+<a class="c2html-lineno" name="l138" href="#l138">138 </a> }
+<a class="c2html-lineno" name="l139" href="#l139">139 </a>
+<a class="c2html-lineno" name="l140" href="#l140">140 </a> <span class="c2html-comment">/**</span>
+<a class="c2html-lineno" name="l141" href="#l141">141 </a><span class="c2html-comment"> * Attempts to solve the given Sudoku field.</span>
+<a class="c2html-lineno" name="l142" href="#l142">142 </a><span class="c2html-comment"> *</span>
+<a class="c2html-lineno" name="l143" href="#l143">143 </a><span class="c2html-comment"> * The solution, if any, is directly entered into the field.</span>
+<a class="c2html-lineno" name="l144" href="#l144">144 </a><span class="c2html-comment"> * All solved fields will be in modified state.</span>
+<a class="c2html-lineno" name="l145" href="#l145">145 </a><span class="c2html-comment"> * The already given fields are left untouched.</span>
+<a class="c2html-lineno" name="l146" href="#l146">146 </a><span class="c2html-comment"> *</span>
+<a class="c2html-lineno" name="l147" href="#l147">147 </a><span class="c2html-comment"> * @param f the field to solve</span>
+<a class="c2html-lineno" name="l148" href="#l148">148 </a><span class="c2html-comment"> * @return true if a solution could be found, false if the field is unsolvable</span>
+<a class="c2html-lineno" name="l149" href="#l149">149 </a><span class="c2html-comment"> */</span>
+<a class="c2html-lineno" name="l150" href="#l150">150 </a> <span class="c2html-keyword">public</span> <span class="c2html-keyword">boolean</span> solve(<span class="c2html-type">Field</span> f) {
+<a class="c2html-lineno" name="l151" href="#l151">151 </a>
+<a class="c2html-lineno" name="l152" href="#l152">152 </a> <span class="c2html-comment">// Calculate initial candidates</span>
+<a class="c2html-lineno" name="l153" href="#l153">153 </a> <span class="c2html-type">List</span><<span class="c2html-type">Integer</span>>[][] candidates = <span class="c2html-keyword">new</span> <span class="c2html-type">List</span>[<span class="c2html-number">9</span>][<span class="c2html-number">9</span>];
+<a class="c2html-lineno" name="l154" href="#l154">154 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> x = <span class="c2html-number">0</span> ; x < <span class="c2html-number">9</span> ; x++) {
+<a class="c2html-lineno" name="l155" href="#l155">155 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> y = <span class="c2html-number">0</span> ; y < <span class="c2html-number">9</span> ; y++) {
+<a class="c2html-lineno" name="l156" href="#l156">156 </a> candidates[x][y] = <span class="c2html-keyword">new</span> <span class="c2html-type">ArrayList</span><>(<span class="c2html-number">9</span>);
+<a class="c2html-lineno" name="l157" href="#l157">157 </a> <span class="c2html-keyword">if</span> (f.getCellValue(x, y) == <span class="c2html-number">0</span>) {
+<a class="c2html-lineno" name="l158" href="#l158">158 </a> <span class="c2html-comment">// All numbers are candidates</span>
+<a class="c2html-lineno" name="l159" href="#l159">159 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> c = <span class="c2html-number">1</span> ; c <= <span class="c2html-number">9</span> ; c++) {
+<a class="c2html-lineno" name="l160" href="#l160">160 </a> candidates[x][y].add(c);
+<a class="c2html-lineno" name="l161" href="#l161">161 </a> }
+<a class="c2html-lineno" name="l162" href="#l162">162 </a> <span class="c2html-comment">// Remove row duplicates</span>
+<a class="c2html-lineno" name="l163" href="#l163">163 </a> <span class="c2html-keyword">int</span>[] line = f.getRow(y);
+<a class="c2html-lineno" name="l164" href="#l164">164 </a> <span class="c2html-keyword">for</span> (<span class="c2html-type">Integer</span> c : line) {
+<a class="c2html-lineno" name="l165" href="#l165">165 </a> candidates[x][y].remove(c);
+<a class="c2html-lineno" name="l166" href="#l166">166 </a> }
+<a class="c2html-lineno" name="l167" href="#l167">167 </a> <span class="c2html-comment">// Remove column duplicates</span>
+<a class="c2html-lineno" name="l168" href="#l168">168 </a> line = f.getColumn(x);
+<a class="c2html-lineno" name="l169" href="#l169">169 </a> <span class="c2html-keyword">for</span> (<span class="c2html-type">Integer</span> c : line) {
+<a class="c2html-lineno" name="l170" href="#l170">170 </a> candidates[x][y].remove(c);
+<a class="c2html-lineno" name="l171" href="#l171">171 </a> }
+<a class="c2html-lineno" name="l172" href="#l172">172 </a> <span class="c2html-comment">// Remove square duplicates</span>
+<a class="c2html-lineno" name="l173" href="#l173">173 </a> <span class="c2html-keyword">int</span>[][] square = f.getSquare(x/<span class="c2html-number">3</span>, y/<span class="c2html-number">3</span>);
+<a class="c2html-lineno" name="l174" href="#l174">174 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span>[] sq : square) {
+<a class="c2html-lineno" name="l175" href="#l175">175 </a> <span class="c2html-keyword">for</span> (<span class="c2html-type">Integer</span> c : sq) {
+<a class="c2html-lineno" name="l176" href="#l176">176 </a> candidates[x][y].remove(c);
+<a class="c2html-lineno" name="l177" href="#l177">177 </a> }
+<a class="c2html-lineno" name="l178" href="#l178">178 </a> }
+<a class="c2html-lineno" name="l179" href="#l179">179 </a> }
+<a class="c2html-lineno" name="l180" href="#l180">180 </a> }
+<a class="c2html-lineno" name="l181" href="#l181">181 </a> }
+<a class="c2html-lineno" name="l182" href="#l182">182 </a>
+<a class="c2html-lineno" name="l183" href="#l183">183 </a> <span class="c2html-comment">// Backtrack</span>
+<a class="c2html-lineno" name="l184" href="#l184">184 </a> <span class="c2html-keyword">return</span> solve(f, candidates);
+<a class="c2html-lineno" name="l185" href="#l185">185 </a> }
+<a class="c2html-lineno" name="l186" href="#l186">186 </a>
+<a class="c2html-lineno" name="l187" href="#l187">187 </a> <span class="c2html-comment">/**</span>
+<a class="c2html-lineno" name="l188" href="#l188">188 </a><span class="c2html-comment"> * Performs a fast check whether any field violates the Sudoku rules.</span>
+<a class="c2html-lineno" name="l189" href="#l189">189 </a><span class="c2html-comment"> *</span>
+<a class="c2html-lineno" name="l190" href="#l190">190 </a><span class="c2html-comment"> * @param f the field to check</span>
+<a class="c2html-lineno" name="l191" href="#l191">191 </a><span class="c2html-comment"> * @return true, if the check succeeds, false otherwise</span>
+<a class="c2html-lineno" name="l192" href="#l192">192 </a><span class="c2html-comment"> */</span>
+<a class="c2html-lineno" name="l193" href="#l193">193 </a> <span class="c2html-keyword">public</span> <span class="c2html-keyword">boolean</span> check(<span class="c2html-type">Field</span> f) {
+<a class="c2html-lineno" name="l194" href="#l194">194 </a> <span class="c2html-keyword">int</span>[] line;
+<a class="c2html-lineno" name="l195" href="#l195">195 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> i = <span class="c2html-number">0</span> ; i < <span class="c2html-number">9</span> ; i++) {
+<a class="c2html-lineno" name="l196" href="#l196">196 </a> line = f.getRow(i);
+<a class="c2html-lineno" name="l197" href="#l197">197 </a> <span class="c2html-keyword">if</span> (!valid(line)) {
+<a class="c2html-lineno" name="l198" href="#l198">198 </a> <span class="c2html-keyword">return</span> false;
+<a class="c2html-lineno" name="l199" href="#l199">199 </a> }
+<a class="c2html-lineno" name="l200" href="#l200">200 </a> line = f.getColumn(i);
+<a class="c2html-lineno" name="l201" href="#l201">201 </a> <span class="c2html-keyword">if</span> (!valid(line)) {
+<a class="c2html-lineno" name="l202" href="#l202">202 </a> <span class="c2html-keyword">return</span> false;
+<a class="c2html-lineno" name="l203" href="#l203">203 </a> }
+<a class="c2html-lineno" name="l204" href="#l204">204 </a> }
+<a class="c2html-lineno" name="l205" href="#l205">205 </a>
+<a class="c2html-lineno" name="l206" href="#l206">206 </a> <span class="c2html-keyword">int</span>[][] square;
+<a class="c2html-lineno" name="l207" href="#l207">207 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> x = <span class="c2html-number">0</span> ; x < <span class="c2html-number">3</span> ; x++) {
+<a class="c2html-lineno" name="l208" href="#l208">208 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> y = <span class="c2html-number">0</span> ; y < <span class="c2html-number">3</span> ; y++) {
+<a class="c2html-lineno" name="l209" href="#l209">209 </a> square = f.getSquare(x, y);
+<a class="c2html-lineno" name="l210" href="#l210">210 </a> <span class="c2html-keyword">if</span> (!valid(square)) {
+<a class="c2html-lineno" name="l211" href="#l211">211 </a> <span class="c2html-keyword">return</span> false;
+<a class="c2html-lineno" name="l212" href="#l212">212 </a> }
+<a class="c2html-lineno" name="l213" href="#l213">213 </a> }
+<a class="c2html-lineno" name="l214" href="#l214">214 </a> }
+<a class="c2html-lineno" name="l215" href="#l215">215 </a>
+<a class="c2html-lineno" name="l216" href="#l216">216 </a> <span class="c2html-keyword">return</span> true;
+<a class="c2html-lineno" name="l217" href="#l217">217 </a> }
+<a class="c2html-lineno" name="l218" href="#l218">218 </a>
+<a class="c2html-lineno" name="l219" href="#l219">219 </a> <span class="c2html-keyword">private</span> <span class="c2html-keyword">boolean</span> valid(<span class="c2html-keyword">int</span>[] line) {
+<a class="c2html-lineno" name="l220" href="#l220">220 </a> <span class="c2html-keyword">int</span>[] numbers;
+<a class="c2html-lineno" name="l221" href="#l221">221 </a> numbers = <span class="c2html-keyword">new</span> <span class="c2html-keyword">int</span>[<span class="c2html-number">9</span>];
+<a class="c2html-lineno" name="l222" href="#l222">222 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> i = <span class="c2html-number">0</span> ; i < <span class="c2html-number">9</span> ; i++) {
+<a class="c2html-lineno" name="l223" href="#l223">223 </a> <span class="c2html-keyword">int</span> l = line[i]<span class="c2html-number">-1</span>;
+<a class="c2html-lineno" name="l224" href="#l224">224 </a> <span class="c2html-keyword">if</span> (l >= <span class="c2html-number">0</span>) {
+<a class="c2html-lineno" name="l225" href="#l225">225 </a> <span class="c2html-keyword">if</span> ((++numbers[l]) > <span class="c2html-number">1</span>) {
+<a class="c2html-lineno" name="l226" href="#l226">226 </a> <span class="c2html-keyword">return</span> false;
+<a class="c2html-lineno" name="l227" href="#l227">227 </a> }
+<a class="c2html-lineno" name="l228" href="#l228">228 </a> }
+<a class="c2html-lineno" name="l229" href="#l229">229 </a> }
+<a class="c2html-lineno" name="l230" href="#l230">230 </a>
+<a class="c2html-lineno" name="l231" href="#l231">231 </a> <span class="c2html-keyword">return</span> true;
+<a class="c2html-lineno" name="l232" href="#l232">232 </a> }
+<a class="c2html-lineno" name="l233" href="#l233">233 </a>
+<a class="c2html-lineno" name="l234" href="#l234">234 </a> <span class="c2html-keyword">private</span> <span class="c2html-keyword">boolean</span> valid(<span class="c2html-keyword">int</span>[][] square) {
+<a class="c2html-lineno" name="l235" href="#l235">235 </a> <span class="c2html-keyword">int</span>[] line = <span class="c2html-keyword">new</span> <span class="c2html-keyword">int</span>[<span class="c2html-number">9</span>];
+<a class="c2html-lineno" name="l236" href="#l236">236 </a> <span class="c2html-keyword">for</span> (<span class="c2html-keyword">int</span> x = <span class="c2html-number">0</span> ; x < <span class="c2html-number">3</span> ; x++) {
+<a class="c2html-lineno" name="l237" href="#l237">237 </a> <span class="c2html-type">System</span>.arraycopy(square[x], <span class="c2html-number">0</span>, line, <span class="c2html-number">3</span>*x, <span class="c2html-number">3</span>);
+<a class="c2html-lineno" name="l238" href="#l238">238 </a> }
+<a class="c2html-lineno" name="l239" href="#l239">239 </a> <span class="c2html-keyword">return</span> valid(line);
+<a class="c2html-lineno" name="l240" href="#l240">240 </a> }
+<a class="c2html-lineno" name="l241" href="#l241">241 </a>}
</div>
</body>
</html>