Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Comment: Migrated to Confluence 5.3

This page describes a Groovy solution for ShortestSudokuSolver. 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.

The solution (184 characters plus 2 newlines):

Code Block
def r(a){def i=a.indexOf(48);if(i<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}&g{it%9/3}?a[j]:'0'}).each{
r(a[0..<i]+it+a[i+1..-1])}}

Notes:

  • The script could be 25 characters shorter if Groovy supported integer division.
  • The script executes more efficiently if you use logical operators '&&' and '||' instead of '&' and '|' because short-circuiting kicks in at the expense of 3 characters.
  • The script would be 1 character longer if for clarity you wanted to use '0' instead of the first 48.
  • The script would be 2 characters longer if you want to use println rather than print if you are fussy about the formatting
  • To make the function stop as soon as it finds the first solution (proper puzzles will only have one solution), the part before the else becomes {print a;System.exit(1)}

Add the following line to the script to solve a partially complete puzzle (should take just a few seconds):

Code Block
r '200375169639218457571964382152496873348752916796831245900100500800007600400089001'

Alternatively, add the following line to the script to solve a puzzle from scratch (may take 30-60 minutes or more):

Code Block
r '200370009009200007001004002050000800008000900006000040900100500800007600400089001'

The expected output is:

Code Block
none
none
284375169639218457571964382152496873348752916796831245967143528813527694425689731

Here is the more usual representation of the puzzle:

You can run it from the command-line by adding ;r args[0] to the end of the script (saved in a file called sudoku.groovy) and then invoking:

Code Block
none
none
> groovy sudoku.groovy 200370009009200007001004002050000800008000900006000040900100500800007600400089001

If you use '.groovy' as your script file extension, you can even leave off the extension as follows:

Code Block
none
none
> groovy sudoku 200370009009200007001004002050000800008000900006000040900100500800007600400089001

A slightly longer version using a matcher and no inner closure (209 characters plus 2 newlines):

Code Block
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&&w==x?
a[j]:'0'}).each{r(a[0..<i]+it+a[i+1..-1])}}else print a}

Or without the matcher (193 characters plus two newlines):

Code Block
def r(a){int i=a.indexOf(48);if(i<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&&w==x?a[j]:'0'
}).each{r(a[0..<i]+it+a[i+1..-1])}}

Also see another version for a more understandable (though much longer) algorithm - but it also does a lot more.