<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
    "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<meta http-equiv="Content-Type" content="application/xhtml+xml; charset=UTF-8" />
<meta name="generator" content="AsciiDoc 8.6.9" />
<title>Listing of doc/example-scripts/rosetta-sudoku.tcl</title>
<style type="text/css">
/* Shared CSS for AsciiDoc xhtml11 and html5 backends */

/* Default font. */
body {
  font-family: Georgia,serif;
}

/* Title font. */
h1, h2, h3, h4, h5, h6,
div.title, caption.title,
thead, p.table.header,
#toctitle,
#author, #revnumber, #revdate, #revremark,
#footer {
  font-family: Arial,Helvetica,sans-serif;
}

body {
  margin: 1em 5% 1em 5%;
}

a {
  color: blue;
  text-decoration: underline;
}
a:visited {
  color: fuchsia;
}

em {
  font-style: italic;
  color: navy;
}

strong {
  font-weight: bold;
  color: #083194;
}

h1, h2, h3, h4, h5, h6 {
  color: #527bbd;
  margin-top: 1.2em;
  margin-bottom: 0.5em;
  line-height: 1.3;
}

h1, h2, h3 {
  border-bottom: 2px solid silver;
}
h2 {
  padding-top: 0.5em;
}
h3 {
  float: left;
}
h3 + * {
  clear: left;
}
h5 {
  font-size: 1.0em;
}

div.sectionbody {
  margin-left: 0;
}

hr {
  border: 1px solid silver;
}

p {
  margin-top: 0.5em;
  margin-bottom: 0.5em;
}

ul, ol, li > p {
  margin-top: 0;
}
ul > li     { color: #aaa; }
ul > li > * { color: black; }

.monospaced, code, pre {
  font-family: "Courier New", Courier, monospace;
  font-size: inherit;
  color: navy;
  padding: 0;
  margin: 0;
}
pre {
  white-space: pre-wrap;
}

#author {
  color: #527bbd;
  font-weight: bold;
  font-size: 1.1em;
}
#email {
}
#revnumber, #revdate, #revremark {
}

#footer {
  font-size: small;
  border-top: 2px solid silver;
  padding-top: 0.5em;
  margin-top: 4.0em;
}
#footer-text {
  float: left;
  padding-bottom: 0.5em;
}
#footer-badges {
  float: right;
  padding-bottom: 0.5em;
}

#preamble {
  margin-top: 1.5em;
  margin-bottom: 1.5em;
}
div.imageblock, div.exampleblock, div.verseblock,
div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock,
div.admonitionblock {
  margin-top: 1.0em;
  margin-bottom: 1.5em;
}
div.admonitionblock {
  margin-top: 2.0em;
  margin-bottom: 2.0em;
  margin-right: 10%;
  color: #606060;
}

div.content { /* Block element content. */
  padding: 0;
}

/* Block element titles. */
div.title, caption.title {
  color: #527bbd;
  font-weight: bold;
  text-align: left;
  margin-top: 1.0em;
  margin-bottom: 0.5em;
}
div.title + * {
  margin-top: 0;
}

td div.title:first-child {
  margin-top: 0.0em;
}
div.content div.title:first-child {
  margin-top: 0.0em;
}
div.content + div.title {
  margin-top: 0.0em;
}

div.sidebarblock > div.content {
  background: #ffffee;
  border: 1px solid #dddddd;
  border-left: 4px solid #f0f0f0;
  padding: 0.5em;
}

div.listingblock > div.content {
  border: 1px solid #dddddd;
  border-left: 5px solid #f0f0f0;
  background: #f8f8f8;
  padding: 0.5em;
}

div.quoteblock, div.verseblock {
  padding-left: 1.0em;
  margin-left: 1.0em;
  margin-right: 10%;
  border-left: 5px solid #f0f0f0;
  color: #888;
}

div.quoteblock > div.attribution {
  padding-top: 0.5em;
  text-align: right;
}

div.verseblock > pre.content {
  font-family: inherit;
  font-size: inherit;
}
div.verseblock > div.attribution {
  padding-top: 0.75em;
  text-align: left;
}
/* DEPRECATED: Pre version 8.2.7 verse style literal block. */
div.verseblock + div.attribution {
  text-align: left;
}

div.admonitionblock .icon {
  vertical-align: top;
  font-size: 1.1em;
  font-weight: bold;
  text-decoration: underline;
  color: #527bbd;
  padding-right: 0.5em;
}
div.admonitionblock td.content {
  padding-left: 0.5em;
  border-left: 3px solid #dddddd;
}

div.exampleblock > div.content {
  border-left: 3px solid #dddddd;
  padding-left: 0.5em;
}

div.imageblock div.content { padding-left: 0; }
span.image img { border-style: none; vertical-align: text-bottom; }
a.image:visited { color: white; }

dl {
  margin-top: 0.8em;
  margin-bottom: 0.8em;
}
dt {
  margin-top: 0.5em;
  margin-bottom: 0;
  font-style: normal;
  color: navy;
}
dd > *:first-child {
  margin-top: 0.1em;
}

ul, ol {
    list-style-position: outside;
}
ol.arabic {
  list-style-type: decimal;
}
ol.loweralpha {
  list-style-type: lower-alpha;
}
ol.upperalpha {
  list-style-type: upper-alpha;
}
ol.lowerroman {
  list-style-type: lower-roman;
}
ol.upperroman {
  list-style-type: upper-roman;
}

div.compact ul, div.compact ol,
div.compact p, div.compact p,
div.compact div, div.compact div {
  margin-top: 0.1em;
  margin-bottom: 0.1em;
}

tfoot {
  font-weight: bold;
}
td > div.verse {
  white-space: pre;
}

div.hdlist {
  margin-top: 0.8em;
  margin-bottom: 0.8em;
}
div.hdlist tr {
  padding-bottom: 15px;
}
dt.hdlist1.strong, td.hdlist1.strong {
  font-weight: bold;
}
td.hdlist1 {
  vertical-align: top;
  font-style: normal;
  padding-right: 0.8em;
  color: navy;
}
td.hdlist2 {
  vertical-align: top;
}
div.hdlist.compact tr {
  margin: 0;
  padding-bottom: 0;
}

.comment {
  background: yellow;
}

.footnote, .footnoteref {
  font-size: 0.8em;
}

span.footnote, span.footnoteref {
  vertical-align: super;
}

#footnotes {
  margin: 20px 0 20px 0;
  padding: 7px 0 0 0;
}

#footnotes div.footnote {
  margin: 0 0 5px 0;
}

#footnotes hr {
  border: none;
  border-top: 1px solid silver;
  height: 1px;
  text-align: left;
  margin-left: 0;
  width: 20%;
  min-width: 100px;
}

div.colist td {
  padding-right: 0.5em;
  padding-bottom: 0.3em;
  vertical-align: top;
}
div.colist td img {
  margin-top: 0.3em;
}

@media print {
  #footer-badges { display: none; }
}

#toc {
  margin-bottom: 2.5em;
}

#toctitle {
  color: #527bbd;
  font-size: 1.1em;
  font-weight: bold;
  margin-top: 1.0em;
  margin-bottom: 0.1em;
}

div.toclevel0, div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 {
  margin-top: 0;
  margin-bottom: 0;
}
div.toclevel2 {
  margin-left: 2em;
  font-size: 0.9em;
}
div.toclevel3 {
  margin-left: 4em;
  font-size: 0.9em;
}
div.toclevel4 {
  margin-left: 6em;
  font-size: 0.9em;
}

span.aqua { color: aqua; }
span.black { color: black; }
span.blue { color: blue; }
span.fuchsia { color: fuchsia; }
span.gray { color: gray; }
span.green { color: green; }
span.lime { color: lime; }
span.maroon { color: maroon; }
span.navy { color: navy; }
span.olive { color: olive; }
span.purple { color: purple; }
span.red { color: red; }
span.silver { color: silver; }
span.teal { color: teal; }
span.white { color: white; }
span.yellow { color: yellow; }

span.aqua-background { background: aqua; }
span.black-background { background: black; }
span.blue-background { background: blue; }
span.fuchsia-background { background: fuchsia; }
span.gray-background { background: gray; }
span.green-background { background: green; }
span.lime-background { background: lime; }
span.maroon-background { background: maroon; }
span.navy-background { background: navy; }
span.olive-background { background: olive; }
span.purple-background { background: purple; }
span.red-background { background: red; }
span.silver-background { background: silver; }
span.teal-background { background: teal; }
span.white-background { background: white; }
span.yellow-background { background: yellow; }

span.big { font-size: 2em; }
span.small { font-size: 0.6em; }

span.underline { text-decoration: underline; }
span.overline { text-decoration: overline; }
span.line-through { text-decoration: line-through; }

div.unbreakable { page-break-inside: avoid; }


/*
 * xhtml11 specific
 *
 * */

div.tableblock {
  margin-top: 1.0em;
  margin-bottom: 1.5em;
}
div.tableblock > table {
  border: 3px solid #527bbd;
}
thead, p.table.header {
  font-weight: bold;
  color: #527bbd;
}
p.table {
  margin-top: 0;
}
/* Because the table frame attribute is overriden by CSS in most browsers. */
div.tableblock > table[frame="void"] {
  border-style: none;
}
div.tableblock > table[frame="hsides"] {
  border-left-style: none;
  border-right-style: none;
}
div.tableblock > table[frame="vsides"] {
  border-top-style: none;
  border-bottom-style: none;
}


/*
 * html5 specific
 *
 * */

table.tableblock {
  margin-top: 1.0em;
  margin-bottom: 1.5em;
}
thead, p.tableblock.header {
  font-weight: bold;
  color: #527bbd;
}
p.tableblock {
  margin-top: 0;
}
table.tableblock {
  border-width: 3px;
  border-spacing: 0px;
  border-style: solid;
  border-color: #527bbd;
  border-collapse: collapse;
}
th.tableblock, td.tableblock {
  border-width: 1px;
  padding: 4px;
  border-style: solid;
  border-color: #527bbd;
}

table.tableblock.frame-topbot {
  border-left-style: hidden;
  border-right-style: hidden;
}
table.tableblock.frame-sides {
  border-top-style: hidden;
  border-bottom-style: hidden;
}
table.tableblock.frame-none {
  border-style: hidden;
}

th.tableblock.halign-left, td.tableblock.halign-left {
  text-align: left;
}
th.tableblock.halign-center, td.tableblock.halign-center {
  text-align: center;
}
th.tableblock.halign-right, td.tableblock.halign-right {
  text-align: right;
}

th.tableblock.valign-top, td.tableblock.valign-top {
  vertical-align: top;
}
th.tableblock.valign-middle, td.tableblock.valign-middle {
  vertical-align: middle;
}
th.tableblock.valign-bottom, td.tableblock.valign-bottom {
  vertical-align: bottom;
}


/*
 * manpage specific
 *
 * */

body.manpage h1 {
  padding-top: 0.5em;
  padding-bottom: 0.5em;
  border-top: 2px solid silver;
  border-bottom: 2px solid silver;
}
body.manpage h2 {
  border-style: none;
}
body.manpage div.sectionbody {
  margin-left: 3em;
}

@media print {
  body.manpage div#toc { display: none; }
}


</style>
<script type="text/javascript">
/*<![CDATA[*/
var asciidoc = {  // Namespace.

/////////////////////////////////////////////////////////////////////
// Table Of Contents generator
/////////////////////////////////////////////////////////////////////

/* Author: Mihai Bazon, September 2002
 * http://students.infoiasi.ro/~mishoo
 *
 * Table Of Content generator
 * Version: 0.4
 *
 * Feel free to use this script under the terms of the GNU General Public
 * License, as long as you do not remove or alter this notice.
 */

 /* modified by Troy D. Hanson, September 2006. License: GPL */
 /* modified by Stuart Rackham, 2006, 2009. License: GPL */

// toclevels = 1..4.
toc: function (toclevels) {

  function getText(el) {
    var text = "";
    for (var i = el.firstChild; i != null; i = i.nextSibling) {
      if (i.nodeType == 3 /* Node.TEXT_NODE */) // IE doesn't speak constants.
        text += i.data;
      else if (i.firstChild != null)
        text += getText(i);
    }
    return text;
  }

  function TocEntry(el, text, toclevel) {
    this.element = el;
    this.text = text;
    this.toclevel = toclevel;
  }

  function tocEntries(el, toclevels) {
    var result = new Array;
    var re = new RegExp('[hH]([1-'+(toclevels+1)+'])');
    // Function that scans the DOM tree for header elements (the DOM2
    // nodeIterator API would be a better technique but not supported by all
    // browsers).
    var iterate = function (el) {
      for (var i = el.firstChild; i != null; i = i.nextSibling) {
        if (i.nodeType == 1 /* Node.ELEMENT_NODE */) {
          var mo = re.exec(i.tagName);
          if (mo && (i.getAttribute("class") || i.getAttribute("className")) != "float") {
            result[result.length] = new TocEntry(i, getText(i), mo[1]-1);
          }
          iterate(i);
        }
      }
    }
    iterate(el);
    return result;
  }

  var toc = document.getElementById("toc");
  if (!toc) {
    return;
  }

  // Delete existing TOC entries in case we're reloading the TOC.
  var tocEntriesToRemove = [];
  var i;
  for (i = 0; i < toc.childNodes.length; i++) {
    var entry = toc.childNodes[i];
    if (entry.nodeName.toLowerCase() == 'div'
     && entry.getAttribute("class")
     && entry.getAttribute("class").match(/^toclevel/))
      tocEntriesToRemove.push(entry);
  }
  for (i = 0; i < tocEntriesToRemove.length; i++) {
    toc.removeChild(tocEntriesToRemove[i]);
  }

  // Rebuild TOC entries.
  var entries = tocEntries(document.getElementById("content"), toclevels);
  for (var i = 0; i < entries.length; ++i) {
    var entry = entries[i];
    if (entry.element.id == "")
      entry.element.id = "_toc_" + i;
    var a = document.createElement("a");
    a.href = "#" + entry.element.id;
    a.appendChild(document.createTextNode(entry.text));
    var div = document.createElement("div");
    div.appendChild(a);
    div.className = "toclevel" + entry.toclevel;
    toc.appendChild(div);
  }
  if (entries.length == 0)
    toc.parentNode.removeChild(toc);
},


/////////////////////////////////////////////////////////////////////
// Footnotes generator
/////////////////////////////////////////////////////////////////////

/* Based on footnote generation code from:
 * http://www.brandspankingnew.net/archive/2005/07/format_footnote.html
 */

footnotes: function () {
  // Delete existing footnote entries in case we're reloading the footnodes.
  var i;
  var noteholder = document.getElementById("footnotes");
  if (!noteholder) {
    return;
  }
  var entriesToRemove = [];
  for (i = 0; i < noteholder.childNodes.length; i++) {
    var entry = noteholder.childNodes[i];
    if (entry.nodeName.toLowerCase() == 'div' && entry.getAttribute("class") == "footnote")
      entriesToRemove.push(entry);
  }
  for (i = 0; i < entriesToRemove.length; i++) {
    noteholder.removeChild(entriesToRemove[i]);
  }

  // Rebuild footnote entries.
  var cont = document.getElementById("content");
  var spans = cont.getElementsByTagName("span");
  var refs = {};
  var n = 0;
  for (i=0; i<spans.length; i++) {
    if (spans[i].className == "footnote") {
      n++;
      var note = spans[i].getAttribute("data-note");
      if (!note) {
        // Use [\s\S] in place of . so multi-line matches work.
        // Because JavaScript has no s (dotall) regex flag.
        note = spans[i].innerHTML.match(/\s*\[([\s\S]*)]\s*/)[1];
        spans[i].innerHTML =
          "[<a id='_footnoteref_" + n + "' href='#_footnote_" + n +
          "' title='View footnote' class='footnote'>" + n + "</a>]";
        spans[i].setAttribute("data-note", note);
      }
      noteholder.innerHTML +=
        "<div class='footnote' id='_footnote_" + n + "'>" +
        "<a href='#_footnoteref_" + n + "' title='Return to text'>" +
        n + "</a>. " + note + "</div>";
      var id =spans[i].getAttribute("id");
      if (id != null) refs["#"+id] = n;
    }
  }
  if (n == 0)
    noteholder.parentNode.removeChild(noteholder);
  else {
    // Process footnoterefs.
    for (i=0; i<spans.length; i++) {
      if (spans[i].className == "footnoteref") {
        var href = spans[i].getElementsByTagName("a")[0].getAttribute("href");
        href = href.match(/#.*/)[0];  // Because IE return full URL.
        n = refs[href];
        spans[i].innerHTML =
          "[<a href='#_footnote_" + n +
          "' title='View footnote' class='footnote'>" + n + "</a>]";
      }
    }
  }
},

install: function(toclevels) {
  var timerId;

  function reinstall() {
    asciidoc.footnotes();
    if (toclevels) {
      asciidoc.toc(toclevels);
    }
  }

  function reinstallAndRemoveTimer() {
    clearInterval(timerId);
    reinstall();
  }

  timerId = setInterval(reinstall, 500);
  if (document.addEventListener)
    document.addEventListener("DOMContentLoaded", reinstallAndRemoveTimer, false);
  else
    window.onload = reinstallAndRemoveTimer;
}

}
asciidoc.install();
/*]]>*/
</script>
</head>
<body class="article">
<div id="header">
<h1>Listing of doc/example-scripts/rosetta-sudoku.tcl</h1>
</div>
<div id="content">
<div class="sect1">
<h2 id="_rosetta_example_sudoku">Rosetta Example: Sudoku</h2>
<div class="sectionbody">
<div class="paragraph"><p>Solve a partially filled-in 9x9 Sudoku grid and display the result
in a human-readable format.  For detailed description of this
example, see <a href="http://rosettacode.org/wiki/Sudoku_Solver">http://rosettacode.org/wiki/Sudoku_Solver</a></p></div>
<div class="paragraph"><p>This implementation is based on <a href="http://wiki.tcl.tk/19934">http://wiki.tcl.tk/19934</a></p></div>
<div class="listingblock">
<div class="content"><style type='text/css'>
.nx             {color: #000000; font-weight: normal; font-style: normal; padding-left: 10px}
table.nx        {border-collapse: collapse; border-spacing: 3px;}
.nx-linenr      {border-right: 1px solid #DDDDDD;padding-right: 5px; color: #2B547D;font-style: italic;}
.nx-string      {color: #779977; font-weight: normal; font-style: italic;}
.nx-comment     {color: #717ab3; font-weight: normal; font-style: italic;}
.nx-keyword     {color: #7f0055; font-weight: normal; font-style: normal;}
.nx-placeholder {color: #AF663F; font-weight: normal; font-style: italic;}
.nx-variable    {color: #AF663F; font-weight: normal; font-style: normal;}
</style>
<pre class='nx'><span class='nx-keyword'>package</span> <span class='nx-keyword'>require</span> nx</pre></div></div>
<div class="paragraph"><p>The class <code>Sudoku</code> implements the basic interface to a sudoku 9x9
board to load/dump data and to set/access cells, rows, columns and
regions.</p></div>
<div class="listingblock">
<div class="content"><style type='text/css'>
.nx             {color: #000000; font-weight: normal; font-style: normal; padding-left: 10px}
table.nx        {border-collapse: collapse; border-spacing: 3px;}
.nx-linenr      {border-right: 1px solid #DDDDDD;padding-right: 5px; color: #2B547D;font-style: italic;}
.nx-string      {color: #779977; font-weight: normal; font-style: italic;}
.nx-comment     {color: #717ab3; font-weight: normal; font-style: italic;}
.nx-keyword     {color: #7f0055; font-weight: normal; font-style: normal;}
.nx-placeholder {color: #AF663F; font-weight: normal; font-style: italic;}
.nx-variable    {color: #AF663F; font-weight: normal; font-style: normal;}
</style>
<pre class='nx'><span class='nx-keyword'>nx::Class</span> <span class='nx-keyword'>create</span> Sudoku {

    <span class='nx-keyword'>:variable</span> board

    <span class='nx-comment'># Setup an array from 0..9 to ease iterations over the cells of
</span>    <span class='nx-comment'># lines and columns.
</span>    <span class='nx-keyword'>for</span> {<span class='nx-keyword'>set</span> i 0} {<span class='nx-variable'>$i</span> &lt; 9} {<span class='nx-keyword'>incr</span> i} {<span class='nx-keyword'>lappend</span> positions <span class='nx-variable'>$i</span>}
    <span class='nx-keyword'>:variable</span> positions <span class='nx-variable'>$positions</span>

    <span class='nx-keyword'>:public</span> <span class='nx-keyword'>method</span> <span class='nx-keyword'>load</span> {data} {
        <span class='nx-comment'>#
</span>        <span class='nx-comment'># Load a 9x9 partially solved sudoku. The unsolved cells are
</span>        <span class='nx-comment'># represented by a@ symbols.
</span>        <span class='nx-comment'>#
</span>        <span class='nx-keyword'>set</span> <span class='nx-keyword'>error</span> <span class='nx-string'>"data must be a 9-element list, each element also being a\
                list of 9 numbers from 1 to 9 or blank or an @ symbol."</span>
        <span class='nx-keyword'>if</span> {[<span class='nx-keyword'>llength</span> <span class='nx-variable'>$data</span>] != 9} {
            <span class='nx-keyword'>error</span> <span class='nx-variable'>$error</span>
        }
        <span class='nx-keyword'>foreach</span> y <span class='nx-variable'>${</span><span class='nx-variable'>:positions}</span> {
            <span class='nx-keyword'>set</span> row [<span class='nx-keyword'>lindex</span> <span class='nx-variable'>$data</span> <span class='nx-variable'>$y</span>]
            <span class='nx-keyword'>if</span> {[<span class='nx-keyword'>llength</span> <span class='nx-variable'>$row</span>] != 9} {
                <span class='nx-keyword'>error</span> <span class='nx-variable'>$error</span>
            }
            <span class='nx-keyword'>foreach</span> x <span class='nx-variable'>${</span><span class='nx-variable'>:positions}</span> {
                <span class='nx-keyword'>set</span> cell [<span class='nx-keyword'>lindex</span> <span class='nx-variable'>$row</span> <span class='nx-variable'>$x</span>]
                <span class='nx-keyword'>if</span> {![<span class='nx-keyword'>regexp</span> {^[@1-9]?<span class='nx-variable'>$</span>} <span class='nx-variable'>$cell</span>]} {
                    <span class='nx-keyword'>error</span> <span class='nx-variable'>$cell</span>-<span class='nx-variable'>$error</span>
                }
                <span class='nx-keyword'>if</span> {<span class='nx-variable'>$cell</span> eq <span class='nx-string'>"@"</span>} {<span class='nx-keyword'>set</span> cell <span class='nx-string'>""</span>}
                <span class='nx-keyword'>:set</span> <span class='nx-variable'>$x</span> <span class='nx-variable'>$y</span> <span class='nx-variable'>$cell</span>
            }
        }
    }

    <span class='nx-keyword'>:public</span> <span class='nx-keyword'>method</span> dump {-pretty-print<span class='nx-keyword'>:switch</span>} {
        <span class='nx-comment'>#
</span>        <span class='nx-comment'># Output the current state of the sudoku either as list or in
</span>        <span class='nx-comment'># a pretty-print style.
</span>        <span class='nx-comment'>#
</span>        <span class='nx-keyword'>set</span> rows [lmap y <span class='nx-variable'>${</span><span class='nx-variable'>:positions}</span> {:getRow 0 <span class='nx-variable'>$y</span>}]
        <span class='nx-keyword'>if</span> {<span class='nx-variable'>${</span><span class='nx-variable'>pretty-print}</span>} {
            <span class='nx-keyword'>set</span> result +-----+-----+-----+\n
            <span class='nx-keyword'>foreach</span> line <span class='nx-variable'>$rows</span> postline {0 0 1 0 0 1 0 0 1} {
                <span class='nx-keyword'>append</span> result |[<span class='nx-keyword'>lrange</span> <span class='nx-variable'>$line</span> 0 2]|[<span class='nx-keyword'>lrange</span> <span class='nx-variable'>$line</span> 3 5]|[<span class='nx-keyword'>lrange</span> <span class='nx-variable'>$line</span> 6 8]|\n
                <span class='nx-keyword'>if</span> {<span class='nx-variable'>$postline</span>} {
                    <span class='nx-keyword'>append</span> result +-----+-----+-----+\n
                }
            }
            <span class='nx-keyword'>return</span> <span class='nx-variable'>$result</span>
        } <span class='nx-keyword'>else</span> {
            <span class='nx-keyword'>return</span> <span class='nx-variable'>$rows</span>
        }
    }

    <span class='nx-keyword'>:method</span> log {msg} {
        <span class='nx-comment'>#puts "log: $msg"
</span>    }

    <span class='nx-keyword'>:method</span> <span class='nx-keyword'>set</span> {x y value:integer,0..1} {
        <span class='nx-comment'>#
</span>        <span class='nx-comment'># Set cell at position x,y to the given value or empty.
</span>        <span class='nx-comment'>#
</span>        <span class='nx-keyword'>if</span> {<span class='nx-variable'>$value</span>&lt;1 || <span class='nx-variable'>$value</span>&gt;9} {
            <span class='nx-keyword'>set</span> :board(<span class='nx-variable'>$x</span>,<span class='nx-variable'>$y</span>) {}
        } <span class='nx-keyword'>else</span> {
            <span class='nx-keyword'>set</span> :board(<span class='nx-variable'>$x</span>,<span class='nx-variable'>$y</span>) <span class='nx-variable'>$value</span>
        }
    }
    <span class='nx-keyword'>:method</span> get {x y} {
        <span class='nx-comment'>#
</span>        <span class='nx-comment'># Get value of cell at position x, y.
</span>        <span class='nx-comment'>#
</span>        <span class='nx-keyword'>return</span> [<span class='nx-keyword'>set</span> :board(<span class='nx-variable'>$x</span>,<span class='nx-variable'>$y</span>)]
    }

    <span class='nx-keyword'>:method</span> getRow {x y} {
        <span class='nx-comment'>#
</span>        <span class='nx-comment'># Return a row at constant position y.
</span>        <span class='nx-comment'>#
</span>        <span class='nx-keyword'>return</span> [lmap x <span class='nx-variable'>${</span><span class='nx-variable'>:positions}</span> {:get <span class='nx-variable'>$x</span> <span class='nx-variable'>$y</span>}]
    }
    <span class='nx-keyword'>:method</span> getCol {x y} {
        <span class='nx-comment'>#
</span>        <span class='nx-comment'># Return a column at constant position x.
</span>        <span class='nx-comment'>#
</span>        <span class='nx-keyword'>return</span> [lmap y <span class='nx-variable'>${</span><span class='nx-variable'>:positions}</span> {:get <span class='nx-variable'>$x</span> <span class='nx-variable'>$y</span>}]
    }

    <span class='nx-keyword'>:method</span> getRegion {x y} {
        <span class='nx-comment'>#
</span>        <span class='nx-comment'># Return a 3x3 region
</span>        <span class='nx-comment'>#
</span>        <span class='nx-keyword'>set</span> xR [<span class='nx-keyword'>expr</span> {(<span class='nx-variable'>$x</span>/3)*3}]
        <span class='nx-keyword'>set</span> yR [<span class='nx-keyword'>expr</span> {(<span class='nx-variable'>$y</span>/3)*3}]
        <span class='nx-keyword'>set</span> regn {}
        <span class='nx-keyword'>for</span> {<span class='nx-keyword'>set</span> x <span class='nx-variable'>$xR</span>} {<span class='nx-variable'>$x</span> &lt; <span class='nx-variable'>$xR</span>+3} {<span class='nx-keyword'>incr</span> x} {
            <span class='nx-keyword'>for</span> {<span class='nx-keyword'>set</span> y <span class='nx-variable'>$yR</span>} {<span class='nx-variable'>$y</span> &lt; <span class='nx-variable'>$yR</span>+3} {<span class='nx-keyword'>incr</span> y} {
                <span class='nx-keyword'>lappend</span> regn [:get <span class='nx-variable'>$x</span> <span class='nx-variable'>$y</span>]
            }
        }
        <span class='nx-keyword'>return</span> <span class='nx-variable'>$regn</span>
    }
}
</pre></div></div>
<div class="paragraph"><p>The class <code>SudokuSolver</code> inherits from <code>Sudoku</code>, and adds the
ability to solve a given Sudoku game. The method <em>solve</em> applies all
rules for each unsolved cell until it finds a safe solution.</p></div>
<div class="listingblock">
<div class="content"><style type='text/css'>
.nx             {color: #000000; font-weight: normal; font-style: normal; padding-left: 10px}
table.nx        {border-collapse: collapse; border-spacing: 3px;}
.nx-linenr      {border-right: 1px solid #DDDDDD;padding-right: 5px; color: #2B547D;font-style: italic;}
.nx-string      {color: #779977; font-weight: normal; font-style: italic;}
.nx-comment     {color: #717ab3; font-weight: normal; font-style: italic;}
.nx-keyword     {color: #7f0055; font-weight: normal; font-style: normal;}
.nx-placeholder {color: #AF663F; font-weight: normal; font-style: italic;}
.nx-variable    {color: #AF663F; font-weight: normal; font-style: normal;}
</style>
<pre class='nx'>
<span class='nx-keyword'>nx::Class</span> <span class='nx-keyword'>create</span> SudokuSolver -superclass Sudoku {

    <span class='nx-keyword'>:public</span> <span class='nx-keyword'>method</span> validchoices {x y} {
        <span class='nx-keyword'>set</span> v [:get <span class='nx-variable'>$x</span> <span class='nx-variable'>$y</span>]
        <span class='nx-keyword'>if</span> {<span class='nx-variable'>$v</span> ne {}} {
            <span class='nx-keyword'>return</span> <span class='nx-variable'>$v</span>
        }

        <span class='nx-keyword'>set</span> row [:getRow <span class='nx-variable'>$x</span> <span class='nx-variable'>$y</span>]
        <span class='nx-keyword'>set</span> col [:getCol <span class='nx-variable'>$x</span> <span class='nx-variable'>$y</span>]
        <span class='nx-keyword'>set</span> regn [:getRegion <span class='nx-variable'>$x</span> <span class='nx-variable'>$y</span>]
        <span class='nx-keyword'>set</span> eliminate [<span class='nx-keyword'>list</span> {*}<span class='nx-variable'>$row</span> {*}<span class='nx-variable'>$col</span> {*}<span class='nx-variable'>$regn</span>]
        <span class='nx-keyword'>set</span> eliminate [<span class='nx-keyword'>lsearch</span> -all -inline -not <span class='nx-variable'>$eliminate</span> {}]
        <span class='nx-keyword'>set</span> eliminate [<span class='nx-keyword'>lsort</span> -unique <span class='nx-variable'>$eliminate</span>]

        <span class='nx-keyword'>set</span> choices {}
        <span class='nx-keyword'>for</span> {<span class='nx-keyword'>set</span> c 1} {<span class='nx-variable'>$c</span> &lt; 10} {<span class='nx-keyword'>incr</span> c} {
            <span class='nx-keyword'>if</span> {<span class='nx-variable'>$c</span> ni <span class='nx-variable'>$eliminate</span>} {
                <span class='nx-keyword'>lappend</span> choices <span class='nx-variable'>$c</span>
            }
        }
        <span class='nx-keyword'>if</span> {[<span class='nx-keyword'>llength</span> <span class='nx-variable'>$choices</span>]==0} {
            <span class='nx-keyword'>error</span> <span class='nx-string'>"No choices left for square $x,$y"</span>
        }
        <span class='nx-keyword'>return</span> <span class='nx-variable'>$choices</span>
    }

    <span class='nx-keyword'>:method</span> completion {} {
        <span class='nx-comment'>#
</span>        <span class='nx-comment'># Return the number of already solved items.
</span>        <span class='nx-comment'>#
</span>        <span class='nx-keyword'>return</span> [<span class='nx-keyword'>expr</span> {81-[<span class='nx-keyword'>llength</span> [<span class='nx-keyword'>lsearch</span> -all -inline [<span class='nx-keyword'>join</span> [:dump]] {}]]}]
    }

    <span class='nx-keyword'>:public</span> <span class='nx-keyword'>method</span> solve {} {
        <span class='nx-comment'>#
</span>        <span class='nx-comment'># Try to solve the sudoku by applying the provided rules.
</span>        <span class='nx-comment'>#
</span>        <span class='nx-keyword'>while</span> {1} {
            <span class='nx-keyword'>set</span> begin [:completion]
            <span class='nx-keyword'>foreach</span> y <span class='nx-variable'>${</span><span class='nx-variable'>:positions}</span> {
                <span class='nx-keyword'>foreach</span> x <span class='nx-variable'>${</span><span class='nx-variable'>:positions}</span> {
                    <span class='nx-keyword'>if</span> {[:get <span class='nx-variable'>$x</span> <span class='nx-variable'>$y</span>] eq <span class='nx-string'>""</span>} {
                        <span class='nx-keyword'>foreach</span> rule [Rule <span class='nx-keyword'>info</span> instances] {
                            <span class='nx-keyword'>set</span> c [<span class='nx-variable'>$rule</span> solve [<span class='nx-keyword'>self</span>] <span class='nx-variable'>$x</span> <span class='nx-variable'>$y</span>]
                            <span class='nx-keyword'>if</span> {<span class='nx-variable'>$c</span>} {
                                <span class='nx-keyword'>:set</span> <span class='nx-variable'>$x</span> <span class='nx-variable'>$y</span> <span class='nx-variable'>$c</span>
                                :log <span class='nx-string'>"[$rule info class] solved [self] at $x,$y for $c"</span>
                                <span class='nx-keyword'>break</span>
                            }
                        }
                    }
                }
            }
            <span class='nx-keyword'>set</span> end [:completion]
            <span class='nx-keyword'>if</span> {<span class='nx-variable'>$end</span> == 81} {
                :log <span class='nx-string'>"Finished solving!"</span>
                <span class='nx-keyword'>break</span>
            } elseif {<span class='nx-variable'>$begin</span> == <span class='nx-variable'>$end</span>} {
                :log <span class='nx-string'>"A round finished without solving any squares, giving up."</span>
                <span class='nx-keyword'>break</span>
            }
        }
    }
}
</pre></div></div>
<div class="paragraph"><p>The class rule provides "solve" as public interface for all rule
objects. The rule objects apply their logic to the values
passed in and return either <em>0</em> or a number to allocate to the
requested square.</p></div>
<div class="listingblock">
<div class="content"><style type='text/css'>
.nx             {color: #000000; font-weight: normal; font-style: normal; padding-left: 10px}
table.nx        {border-collapse: collapse; border-spacing: 3px;}
.nx-linenr      {border-right: 1px solid #DDDDDD;padding-right: 5px; color: #2B547D;font-style: italic;}
.nx-string      {color: #779977; font-weight: normal; font-style: italic;}
.nx-comment     {color: #717ab3; font-weight: normal; font-style: italic;}
.nx-keyword     {color: #7f0055; font-weight: normal; font-style: normal;}
.nx-placeholder {color: #AF663F; font-weight: normal; font-style: italic;}
.nx-variable    {color: #AF663F; font-weight: normal; font-style: normal;}
</style>
<pre class='nx'><span class='nx-keyword'>nx::Class</span> <span class='nx-keyword'>create</span> Rule {

    <span class='nx-keyword'>:public</span> <span class='nx-keyword'>method</span> solve {hSudoku<span class='nx-keyword'>:object</span>,type=::SudokuSolver x y} {
        :Solve <span class='nx-variable'>$hSudoku</span> <span class='nx-variable'>$x</span> <span class='nx-variable'>$y</span> [<span class='nx-variable'>$hSudoku</span> validchoices <span class='nx-variable'>$x</span> <span class='nx-variable'>$y</span>]
    }

    <span class='nx-comment'># Get all the allocated numbers for each square in the the row, column, and
</span>    <span class='nx-comment'># region containing $x,$y. If there is only one unallocated number among all
</span>    <span class='nx-comment'># three groups, it must be allocated at $x,$y
</span>    <span class='nx-keyword'>:create</span> ruleOnlyChoice {
        <span class='nx-keyword'>:object</span> <span class='nx-keyword'>method</span> Solve {hSudoku x y choices} {
            <span class='nx-keyword'>if</span> {[<span class='nx-keyword'>llength</span> <span class='nx-variable'>$choices</span>] == 1} {
                <span class='nx-keyword'>return</span> <span class='nx-variable'>$choices</span>
            } <span class='nx-keyword'>else</span> {
                <span class='nx-keyword'>return</span> 0
            }
        }
    }

    <span class='nx-comment'># Test each column to determine if $choice is an invalid choice for all other
</span>    <span class='nx-comment'># columns in row $X. If it is, it must only go in square $x,$y.
</span>    <span class='nx-keyword'>:create</span> RuleColumnChoice {
        <span class='nx-keyword'>:object</span> <span class='nx-keyword'>method</span> Solve {hSudoku x y choices} {
            <span class='nx-keyword'>foreach</span> choice <span class='nx-variable'>$choices</span> {
                <span class='nx-keyword'>set</span> failed 0
                <span class='nx-keyword'>for</span> {<span class='nx-keyword'>set</span> x2 0} {<span class='nx-variable'>$x2</span> &lt; 9} {<span class='nx-keyword'>incr</span> x2} {
                    <span class='nx-keyword'>if</span> {<span class='nx-variable'>$x2</span> != <span class='nx-variable'>$x</span> &amp;&amp; <span class='nx-variable'>$choice</span> in [<span class='nx-variable'>$hSudoku</span> validchoices <span class='nx-variable'>$x2</span> <span class='nx-variable'>$y</span>]} {
                        <span class='nx-keyword'>set</span> failed 1
                        <span class='nx-keyword'>break</span>
                    }
                }
                <span class='nx-keyword'>if</span> {!<span class='nx-variable'>$failed</span>} {<span class='nx-keyword'>return</span> <span class='nx-variable'>$choice</span>}
            }
            <span class='nx-keyword'>return</span> 0
        }
    }

    <span class='nx-comment'># Test each row to determine if $choice is an invalid choice for all other
</span>    <span class='nx-comment'># rows in column $y. If it is, it must only go in square $x,$y.
</span>    <span class='nx-keyword'>:create</span> RuleRowChoice {
        <span class='nx-keyword'>:object</span> <span class='nx-keyword'>method</span> Solve {hSudoku x y choices} {
            <span class='nx-keyword'>foreach</span> choice <span class='nx-variable'>$choices</span> {
                <span class='nx-keyword'>set</span> failed 0
                <span class='nx-keyword'>for</span> {<span class='nx-keyword'>set</span> y2 0} {<span class='nx-variable'>$y2</span> &lt; 9} {<span class='nx-keyword'>incr</span> y2} {
                    <span class='nx-keyword'>if</span> {<span class='nx-variable'>$y2</span> != <span class='nx-variable'>$y</span> &amp;&amp; <span class='nx-variable'>$choice</span> in [<span class='nx-variable'>$hSudoku</span> validchoices <span class='nx-variable'>$x</span> <span class='nx-variable'>$y2</span>]} {
                        <span class='nx-keyword'>set</span> failed 1
                        <span class='nx-keyword'>break</span>
                    }
                }
                <span class='nx-keyword'>if</span> {!<span class='nx-variable'>$failed</span>} {<span class='nx-keyword'>return</span> <span class='nx-variable'>$choice</span>}
            }
            <span class='nx-keyword'>return</span> 0
        }
    }

    <span class='nx-comment'># Test each square in the region occupied by $x,$y to determine if $choice is
</span>    <span class='nx-comment'># an invalid choice for all other squares in that region. If it is, it must
</span>    <span class='nx-comment'># only go in square $x,$y.
</span>    <span class='nx-keyword'>:create</span> RuleRegionChoice {
        <span class='nx-keyword'>:object</span> <span class='nx-keyword'>method</span> Solve {hSudoku x y choices} {
            <span class='nx-keyword'>foreach</span> choice <span class='nx-variable'>$choices</span> {
                <span class='nx-keyword'>set</span> failed 0
                <span class='nx-keyword'>set</span> regnX [<span class='nx-keyword'>expr</span> {(<span class='nx-variable'>$x</span>/3)*3}]
                <span class='nx-keyword'>set</span> regnY [<span class='nx-keyword'>expr</span> {(<span class='nx-variable'>$y</span>/3)*3}]
                <span class='nx-keyword'>for</span> {<span class='nx-keyword'>set</span> y2 <span class='nx-variable'>$regnY</span>} {<span class='nx-variable'>$y2</span> &lt; <span class='nx-variable'>$regnY</span>+3} {<span class='nx-keyword'>incr</span> y2} {
                    <span class='nx-keyword'>for</span> {<span class='nx-keyword'>set</span> x2 <span class='nx-variable'>$regnX</span>} {<span class='nx-variable'>$x2</span> &lt; <span class='nx-variable'>$regnX</span>+3} {<span class='nx-keyword'>incr</span> x2} {
                        <span class='nx-keyword'>if</span> {
                            (<span class='nx-variable'>$x2</span>!=<span class='nx-variable'>$x</span> || <span class='nx-variable'>$y2</span>!=<span class='nx-variable'>$y</span>)
                            &amp;&amp; <span class='nx-variable'>$choice</span> in [<span class='nx-variable'>$hSudoku</span> validchoices <span class='nx-variable'>$x2</span> <span class='nx-variable'>$y2</span>]
                        } then {
                            <span class='nx-keyword'>set</span> failed 1
                            <span class='nx-keyword'>break</span>
                        }
                    }
                }
                <span class='nx-keyword'>if</span> {!<span class='nx-variable'>$failed</span>} {<span class='nx-keyword'>return</span> <span class='nx-variable'>$choice</span>}
            }
            <span class='nx-keyword'>return</span> 0
        }
    }
}

SudokuSolver <span class='nx-keyword'>create</span> sudoku {

    <span class='nx-keyword'>:load</span> {
        {3 9 4    @ @ 2    6 7 @}
        {@ @ @    3 @ @    4 @ @}
        {5 @ @    6 9 @    @ 2 @}

        {@ 4 5    @ @ @    9 @ @}
        {6 @ @    @ @ @    @ @ 7}
        {@ @ 7    @ @ @    5 8 @}

        {@ 1 @    @ 6 7    @ @ 8}
        {@ @ 9    @ @ 8    @ @ @}
        {@ 2 6    4 @ @    7 3 5}
    }
    :solve

    <span class='nx-keyword'>puts</span> [:dump -pretty-print]
}</pre></div></div>
<div class="paragraph"><p>The dump method outputs the solved Sudoku:</p></div>
<div class="literalblock">
<div class="content">
<pre><code>+-----+-----+-----+
|3 9 4|8 5 2|6 7 1|
|2 6 8|3 7 1|4 5 9|
|5 7 1|6 9 4|8 2 3|
+-----+-----+-----+
|1 4 5|7 8 3|9 6 2|
|6 8 2|9 4 5|3 1 7|
|9 3 7|1 2 6|5 8 4|
+-----+-----+-----+
|4 1 3|5 6 7|2 9 8|
|7 5 9|2 3 8|1 4 6|
|8 2 6|4 1 9|7 3 5|
+-----+-----+-----+</code></pre>
</div></div>
</div>
</div>
</div>
<div id="footnotes"><hr /></div>
<div id="footer">
<div id="footer-text">
Last updated 2014-12-13 12:07:44 CET
</div>
</div>
</body>
</html>