<!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> < 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><1 || <span class='nx-variable'>$value</span>>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> < <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> < <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> < 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> < 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> && <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> < 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> && <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> < <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> < <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>) && <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>