Copy Page

You are not logged in. Any changes you make will be marked as anonymous. You may want to Log In if you already have an account. You can also Sign Up for a new account.

<p>This page describes a Groovy solution for <a href="http://markbyers.com/moinmoin/moin.cgi/ShortestSudokuSolver">ShortestSudokuSolver</a>. Check the link for all the details, but basically the puzzle state is fed in as a String. Each line of the script must be no more than 80 characters in length.</p>

<p>The solution (184 characters plus 2 newlines):</p>
<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
def r(a){def i=a.indexOf(48);if(i&lt;0)print a else(('1'..'9')-(0..80).collect{j->
g={(int)it(i)==(int)it(j)};g{it/9}|g{it%9}|g{it/27}&amp;g{it%9/3}?a[j]:'0'}).each{
r(a[0..&lt;i]+it+a[i+1..-1])}}
</pre></td></tr></table>
<p>Notes:</p>
<ul>
	<li>The script could be 25 characters shorter if Groovy supported integer division.</li>
	<li>The script executes more efficiently if you use logical operators '&amp;&amp;' and '||' instead of '&amp;' and '|' because short-circuiting kicks in at the expense of 3 characters.</li>
	<li>The script would be 1 character longer if for clarity you wanted to use '0' instead of the first 48.</li>
	<li>The script would be 2 characters longer if you want to use <code>println</code> rather than <code>print</code> if you are fussy about the formatting</li>
	<li>To make the function stop as soon as it finds the first solution (proper puzzles will only have one solution), the part before the <code>else</code> becomes {<code>print a;System.exit(1)</code>}</li>
</ul>

<p>Add the following line to the script to solve a partially complete puzzle (should take just a few seconds):</p>
<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
r '200375169639218457571964382152496873348752916796831245900100500800007600400089001'
</pre></td></tr></table>
<p>Alternatively, add the following line to the script to solve a puzzle from scratch (may take 30-60 minutes or more):</p>
<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
r '200370009009200007001004002050000800008000900006000040900100500800007600400089001'
</pre></td></tr></table>
<p>The expected output is:</p>
<table class="wysiwyg-macro" data-macro-name="code" data-macro-default-parameter="none" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGU6bm9uZX0&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
284375169639218457571964382152496873348752916796831245967143528813527694425689731
</pre></td></tr></table>

<p>Here is the more usual representation of the puzzle:</p>

<p><img class="confluence-embedded-image" src="/download/attachments/231079964/suduko.jpg?version=1&amp;modificationDate=1369168734319" data-image-src="/download/attachments/231079964/suduko.jpg?version=1&amp;modificationDate=1369168734319" data-linked-resource-id="231374891" data-linked-resource-type="attachment" data-linked-resource-default-alias="suduko.jpg" data-base-url="http://docs.codehaus.org" data-linked-resource-container-id="231079964" title="null > suduko.jpg"></p>

<p>You can run it from the command-line by adding <code>;r args[0]</code> to the end of the script (saved in a file called <code>sudoku.groovy</code>) and then invoking:</p>
<table class="wysiwyg-macro" data-macro-name="code" data-macro-default-parameter="none" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGU6bm9uZX0&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
> groovy sudoku.groovy 200370009009200007001004002050000800008000900006000040900100500800007600400089001
</pre></td></tr></table>
<p>If you use '.groovy' as your script file extension, you can even leave off the extension as follows:</p>
<table class="wysiwyg-macro" data-macro-name="code" data-macro-default-parameter="none" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGU6bm9uZX0&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
> groovy sudoku 200370009009200007001004002050000800008000900006000040900100500800007600400089001
</pre></td></tr></table>

<p>A slightly longer version using a matcher and no inner closure (209 characters plus 2 newlines):</p>
<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
def r(a){def m=a=~'0';if(m.find()){int i=m.start();(('1'..'9')-(0..80).collect{
j->int q=j/9,r=i/9,u=q/3,v=r/3,w=j%9/3,x=i%9/3;q==r||j%9==i%9||u==v&amp;&amp;w==x?
a[j]:'0'}).each{r(a[0..&lt;i]+it+a[i+1..-1])}}else print a}
</pre></td></tr></table>

<p>Or without the matcher (193 characters plus two newlines):</p>

<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
def r(a){int i=a.indexOf(48);if(i&lt;0)print a else(('1'..'9')-(0..80).collect{j->
int q=j/9,r=i/9,u=q/3,v=r/3,w=j%9/3,x=i%9/3;q==r||i%9==j%9||u==v&amp;&amp;w==x?a[j]:'0'
}).each{r(a[0..&lt;i]+it+a[i+1..-1])}}
</pre></td></tr></table>

<p>Also see <a href="http://www.bytemycode.com/snippets/snippet/474/">another version</a> for a more understandable (though much longer) algorithm - but it also does a lot more.</p>