test/gs/javatest.html

<!DOCTYPE html>
<html>
  <head>
    <title>c2html</title>
    <style type="text/css">
      div.c2html-code {
        white-space: pre;
        font-family: monospace;
      }
      a.c2html-lineno {
        /* as long as user-select isn't widely spread, we throw the bomb */
        -webkit-user-select: none;
        -moz-user-select: none;
        -ms-user-select: none;
        user-select: none;
        display: inline-block;
        font-style: italic;
        text-decoration: none;
        color: grey;
      }
      span.c2html-keyword {
        color: blue;
      }
      span.c2html-macroconst {
        color: cornflowerblue;
      }
      span.c2html-type {
        color: teal;
      }
      span.c2html-directive {
        color: silver;
      }
      span.c2html-string {
        color: darkorange;
      }
      span.c2html-number {
          color: dodgerblue;
      }
      span.c2html-comment {
        color: grey;
      }
      span.c2html-stdinclude, span.c2html-userinclude, a.c2html-userinclude {
      }
    </style>
  </head>
  <body>

<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"> * 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-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>&lt;<span class="c2html-type">Integer</span>&gt;[][] 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 &lt; <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 &lt; <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 &lt; <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>&lt;<span class="c2html-type">Integer</span>&gt;[][] candidates, <span class="c2html-type">List</span>&lt;<span class="c2html-type">Integer</span>&gt;[][] 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 &lt; <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 &lt; <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>&lt;&gt;(<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 &lt; <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 &lt; <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">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 &lt; <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 &lt; <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>&lt;<span class="c2html-type">Integer</span>&gt;[][] candidates, <span class="c2html-type">List</span>&lt;<span class="c2html-type">Integer</span>&gt;[][] 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 &lt; <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 &lt; <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>&lt;<span class="c2html-type">Integer</span>&gt;[][] 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>&lt;<span class="c2html-type">Integer</span>&gt;[][] 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 &lt; <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 &lt; <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) &amp;&amp; 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 &lt; <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 &lt; <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() &gt; <span class="c2html-number">0</span>) {
<a class="c2html-lineno" name="l116" href="#l116">116 </a>                        <span class="c2html-type">List</span>&lt;<span class="c2html-type">Integer</span>&gt;[][] 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>&lt;<span class="c2html-type">Integer</span>&gt;[][] 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 &lt; <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 &lt; <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>&lt;&gt;(<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 &lt;= <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 &lt; <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 &lt; <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 &lt; <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 &lt; <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 &gt;= <span class="c2html-number">0</span>) {
<a class="c2html-lineno" name="l225" href="#l225">225 </a>                <span class="c2html-keyword">if</span> ((++numbers[l]) &gt; <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 &lt; <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>