← back to blog.davidsingleton.org

ShortestSudokuSolver

Tweet

Sometime back in 2006, Mark Byers started collecting and tracking the shortest Sudoku solvers in a variety of programming languages on the web. It was a cool page (and one I had a vested interest in since I had a hand in the Java solver) but sadly dropped off the web sometime in 2008. With Mark’s permission, I’m re-instating the content here and declaring it re-open for submissions - if you can improve on the solvers below or contribute a solver in a new language, please let me know. – davidsingleton (at) gmail - David Singleton - August 2011.

Shortest Sudoku Solver

The following 101 bytes K program can solve Sudoku puzzles:

Here is an example of using the solver to solve this puzzle: 

q sudoku.k 200370009009200007001004002050000800008000900006000040900100500800007600400089001 2>/dev/null </dev/null

And the result: 

284375169639218457571964382152496873348752916796831245967143528813527694425689731

See below for more information about this program, and for solvers in other languages.

Short Sudoku Solvers By Language

C

This Sudoku solver in C was written by Oli Charlesworth and reduced by Joel Hockey and is 174 bytes long:

To compile and then run (using GCC for this example): 

gcc -o sudoku sudoku.c && ./sudoku 200370009009200007001004002050000800008000900006000040900100500800007600400089001

The program also compiles and runs successfully in Microsoft Visual Studio.

Oli also pointed out that this program is not strictly legal C, and suggested another slightly longer version (198 bytes) that is legal C.

Contributors:

Groovy

A Groovy Sudoku Solver in 208 bytes.

Contributors:

Haskell

To run: 

ghc --make sudoku.hs && a.out < sudoku.txt

Contributors:

Java

The shortest Java Sudoku solver is 258 bytes.

Here is an example of how to run the program: 

javac S.java; java S 200370009009200007001004002050000800008000900006000040900100500800007600400089001

Contributors:

K

This Sudoku solver written in K is 101 bytes long.

K is a general purpose language produced by kx. It is used mainly in the financial community. Some language documentation is available.

If we allow printing spaces between the characters, the program can be shortened to 95 bytes: 

p:+{(=x)x}'p,,3/:_(p:,/'+:\9#'!9)%3
*{$[&/x;,x;,/.z.s'@[x;i;:;]'&27=x[,/p i:x?0]?!10]}@.:'*.z.x

This program is run as follow: 

$ q sudoku.k 200370009009200007001004002050000800008000900006000040900100500800007600400089001 2>/dev/null </dev/null

And here is the output: 

2 8 4 3 7 5 1 6 9 6 3 9 2 1 8 4 5 7 5 7 1 9 6 4 3 8 2 1 5 2 4 9 6 8 7 3 3 4 8 7 5 2 9 1 6 7 9 6 8 3 1 2 4 5 9 6 7 1 4 3 5 2 8 8 1 3 5 2 7 6 9 4 4 2 5 6 8 9 7 3 1

Contributors:

Objective Caml

The following Object Caml program is 239 bytes.

Example usage: 

echo 000010000301400860900500200700160000020805010000097004003004006048006907000080000 | ocaml sudoku.ml

An Objective Caml interpreter is available for free download.

Contributors:

Perl

The following Perl program that can solve Sudoku is 121 bytes:

Example usage: 

echo 000010000301400860900500200700160000020805010000097004003004006048006907000080000 | perl sudoku.pl

The output is: 

452618379371429865986573241734162598629845713815397624293754186148236957567981432

Notes: 

$_=$`.$_.$'.<>;split//;map{/[@_[map{$i-($i="@-")%9+$_,9*$_+
$i%9,9*$_%26+$i-$i%27+$i%9-$i%3}0..8]]/o||do$0}/0/||print..9

Contributors: 

The difference with the original perl algorithm is that in this version 
I am taking in every iteration a slice @B with the values of the
contiguous cells. The trickiest thing, I think, is the way this slice is
used as a regular expression range in the grep.

Python

The current shortest Python sudoku solver program is 169 bytes long. This program is clean, in that it does not use any unusual features such as outputting to standard error, or crashing instead of terminating properly. It lists all solutions if there are more than one. It requires 6 lines each with no more than 80 characters.

To run the program, use the following syntax: 

echo 000010000301400860900500200700160000020805010000097004003004006048006907000080000 | python sudoku.py

It is also possible to write a program that fits on 3 lines with no line longer than 80 characters, but now 178 bytes are required: 

def r(a):i=a.find('0');~i or exit(a);[m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9
/3^j%9/3)or a[j]for j in range(81)]or r(a[:i]+m+a[i+1:])for m in`14**7*9`]
from sys import*;r(argv[1])

This is the dirtiest version, where we allow ourselves to cheat a little to get the byte count down. It displays what it is thinking so that you can see how the program works. The program terminates with an exception, which must be redirected and the command line required to start the program is slightly more complicated than for the other programs. The solution is displayed on the last line of standard out. This program is 155 bytes. 

def r(a):print a;i=a.index('0');[m
in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for
j in range(81)]or r(a[:i]+m+a[i+1:])for m in`14**7*9`]
r(input())

To run the program, use the following command line: 

echo \'000010000301400860900500200700160000020805010000097004003004006048006907000080000\' | python sudoku.py 2>/dev/null

Contributors:

Ruby

The current shortest Ruby Sudoku solver program is 122 bytes long.

This program prints all the solutions if there are multiple solutions (a real Sudoku should only have one solution).

To run this Ruby program use the following syntax: 

$ ruby sudoku.rb 200370009009200007001004002050000800008000900006000040900100500800007600400089001

The program can be made a further one byte shorter if the 80 character per line restriction is removed, by putting everything on one long line.

The quotes around the result can be removed, but this adds 1 more byte to the length of the program: 

$*.map{|a|(i=a=~/0/)?(v=*?1..?9).fill{|j|v-=[a[j+i-k=i%9],a[
k+j*=9],a[j%26+i-i%3-i%27+k]]}+v.map{|k|$*.<<$`<<k<<$'}:$><<a}

There is also an explanation of how an earlier version of this program works here: ShortestSudokuSolverRuby.

Contributors:

Notes

Programs should not contain lines longer than 80 characters. If the language allows splitting a long line into two shorter lines, using this feature is acceptable.

For compiled languages, source code size is counted, not compiled size.

New line characters are counted as one byte.

A valid program can accept any 9x9 Sudoku from standard input (or else the first command line parameter, if you prefer) and should output the result to standard out. I will also list some of the programs that cheat very slightly (for example, by outputing to standard error instead of standard out).

If command line parameters are required, they are counted as extra bytes using the perlgolf counting rules.

Mark’s original version of this page appeared on the front page of Digg and Reddit! (2006-07-13)

If you enjoyed this page, you might also like Code Golf.

Do you have a shorter program?

Please let me know if you find a shorter Sudoku Solving program.