# Implement a Brute Force Sudoku Solver

Implement the shortest Sudoku solver using guessing. Since I have received a few request I have added this as an alternative question for those wishing to implement a brute force sudoku solver.

Sudoku Puzzle:

 | 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A|   3   |     1 |
B|     6 |       |   5
C| 5     |       | 9 8 3
-+-----------------------
D|   8   |     6 | 3   2
E|       |   5   |
F| 9   3 | 8     |   6
-+-----------------------
G| 7 1 4 |       |     9
H|   2   |       | 8
I|       | 4     |   3


 | 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A| 8 3 2 | 5 9 1 | 6 7 4
B| 4 9 6 | 3 8 7 | 2 5 1
C| 5 7 1 | 2 6 4 | 9 8 3
-+-----------------------
D| 1 8 5 | 7 4 6 | 3 9 2
E| 2 6 7 | 9 5 3 | 4 1 8
F| 9 4 3 | 8 1 2 | 7 6 5
-+-----------------------
G| 7 1 4 | 6 3 8 | 5 2 9
H| 3 2 9 | 1 7 5 | 8 4 6
I| 6 5 8 | 4 2 9 | 1 3 7


Rules:

1. Assume all mazes are solvable by logic only.
2. All input will be 81 characters long. Missing characters will be 0.
3. Output the solution as a single string.
4. The "grid" may be stored internally however you wish.
5. The solution must using a brute force guessing solution.
6. Solutions should solve within a reasonable time limit.

Example I/O:

>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137

• How can the input be 27 characters long? It needs to be 81 characters long - 9 rows x 9 columns. That's what your example does too. Also, I assume that "missing characters will be 0" means that if the number of characters is less than 81, then the zeroes go on the end? Feb 3, 2011 at 5:15
• Oh, wait. I get the missing characters will be 0 bit. Duh. Those are the ones that need to be guessed. In any case, the number of characters does need to be 81, not 27. Feb 3, 2011 at 5:22
• it seems rules 5 and 6 kinda conflict.... Jul 11, 2014 at 13:36

# k (72 bytes)

Credit for this goes to Arthur Whitney, creator of the k language.

p,:3/:_(p:9\:!81)%3
s:{*(,x)(,/{@[x;y;:;]'&21=x[&|/p[;y]=p]?!10}')/&~x}

• classic! I was going to post this too! Feb 13, 2014 at 13:41

# Python, 188 bytes

This is a further shortened version of my winning submission for CodeSprint Sudoku, modified for command line input instead of stdin (as per the OP):

def f(s):
x=s.find('0')
if x<0:print s;exit()
[c in[(x-y)%9*(x/9^y/9)*(x/27^y/27|x%9/3^y%9/3)or s[y]for y in range(81)]or f(s[:x]+c+s[x+1:])for c in'%d'%5**18]
import sys
f(sys.argv)


If you're using Python 2, '%d'%5**18 can be replaced with 5**18 to save 3 bytes.

To make it run faster, you can replace '%d'%5**18 with any permutation of '123456789' at a cost of 1 byte.

If you want it to accept the input on stdin instead, you can replace import sys;f(sys.argv) with f(raw_input()), bringing it down to 177 bytes.

def f(s):
x=s.find('0')
if x<0:print s;exit()
[c in[(x-y)%9*(x/9^y/9)*(x/27^y/27|x%9/3^y%9/3)or s[y]for y in range(81)]or f(s[:x]+c+s[x+1:])for c in'%d'%5**18]
f(raw_input())

• Very nice solution. Dec 15, 2012 at 15:49

## Python, 197 characters

def S(s):
i=s.find('0')
if i<0:print s;return
for v in'123456789':
if sum(v==s[j]and(i/9==j/9or i%9==j%9or(i%9/3==j%9/3and i/27==j/27))for j in range(81))==0:S(s[:i]+v+s[i+1:])
S(raw_input())


# Perl, 120 bytes

Oh, I remember golfing that back in 2008... And it in fact stopped working in perl 5.12 since implicit setting of @_ by split was removed then. So only try this on a sufficiently old perl.

Run with the input on STDIN:

sudoku.pl <<< "030001000006000050500000983080006302000050000903800060714000009020000800000400030"


sudoku.pl:

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

• It's Clarke's third law, but in reverse! Mar 17, 2016 at 12:36

import std.algorithm;
import std.conv;
import std.ascii;
import std.exception;
import std.stdio;

void main(string[] args)
{
enforce(args.length == 2, new Exception("Missing argument."));
enforce(args.length == 81, new Exception("Invalid argument."));
enforce(!canFind!((a){return !isDigit(to!dchar(a));})
(args),
new Exception("Entire argument must be digits."));

auto sudoku = new Sudoku(args);
sudoku.fillIn();

writeln(sudoku);
}

class Sudoku
{
public:

this(string str) nothrow
{
normal = new int[][](9, 9);

for(size_t i = 0, k =0; i < 9; ++i)
{
for(size_t j = 0; j < 9; ++j)
normal[i][j] = to!int(str[k++]) - '0';
}

reversed = new int*[][](9, 9);

for(size_t i = 0; i < 9; ++i)
{
for(size_t j = 0; j < 9; ++j)
reversed[j][i] = &normal[i][j];
}

boxes = new int*[][](9, 9);
indexedBoxes = new int*[][][](9, 9);

for(size_t boxRow = 0, boxNum = 0; boxRow < 3; ++boxRow)
{
for(size_t boxCol = 0; boxCol < 3; ++boxCol, ++boxNum)
{
for(size_t i = 3 * boxRow, square = 0; i < 3 * (boxRow + 1); ++i)
{
for(size_t j = 3 * boxCol; j < 3 * (boxCol + 1); ++j)
{
boxes[boxNum][square++] = &normal[i][j];
indexedBoxes[i][j] = boxes[boxNum];
}
}
}
}
}

void fillIn()
{
fillIn(0, 0);
}

@property bool valid()
{
assert(full);

for(size_t i = 0; i < 9; ++i)
{
for(int n = 1; n < 10; ++n)
{
if(!canFind(normal[i], n) ||
!canFind!"*a == b"(reversed[i], n) ||
!canFind!"*a == b"(boxes[i], n))
{
return false;
}
}
}

return true;
}

override string toString() const
{
char retval;

for(size_t i = 0, k =0; i < 9; ++i)
{
for(size_t j = 0; j < 9; ++j)
retval[k++] = to!char(normal[i][j] + '0');
}

}

private:

@property bool full()
{
for(size_t i = 0; i < 9; ++i)
{
if(canFind(normal[i], 0))
return false;
}

return true;
}

bool fillIn(size_t row, size_t col)
{
if(row == 9)
return valid;

size_t nextRow = row;
size_t nextCol = col + 1;

if(nextCol == 9)
{
nextRow = row + 1;
nextCol = 0;
}

if(normal[row][col] == 0)
{
for(int n = 1; n < 10; ++n)
{
if(canFind(normal[row], n) ||
canFind!"*a == b"(reversed[col], n) ||
canFind!"*a == b"(indexedBoxes[row][col], n))
{
continue;
}

normal[row][col] = n;

if(fillIn(nextRow, nextCol))
return true;
}

normal[row][col] = 0;

return false;
}
else
return fillIn(nextRow, nextCol);
}

int[][] normal;
int*[][] reversed;
int*[][] boxes;
int*[][][] indexedBoxes;
}


With the sample input, it takes .033s on my Phenom II X6 1090T when compiled with dmd -w (i.e. without optimizations), and it takes .011s when compiled with dmd -w -O -inline -release (i.e. with optimizations).

## Perl, 235 chars

$_=$s=<>;$r=join$/,map{$n=$_;'.*(?!'.(join'|',map+($_%9==$n%9||int($_/9)==int($n/9)||int($_/27)==int($n/27)&&int($_/3%3)==int($n/3%3)and$_<$n?'\\'.($_+1):$_>$n&&substr$s,$_,1)||X,@a).')(.).*'}@a=0..80;s!.!($&||123456789).$/!eg;say/^$r/


This is a golfed version of something I posted many years ago to the Fun With Perl mailing list: a sudoku-solving regexp.

Basically, it mangles the input into 81 lines, each containing all the numbers that could occur in the corresponding square. It then constructs a regexp to match one number from each line, using backreferences and negative lookahead assertions to reject solutions that violate the row, column or region constraints. Then it matches the string against the regexp, letting Perl's regexp engine do the hard work of trial and backtracking.

Astonishingly, it's possible to create a single regexp that works for any input, like my original program does. Unfortunately, it's quite slow, so I based the golfed code here on the hardcoded-givens version (found later in the FWP thread), which tweaks the regexp to reject early any solutions that it knows will later violate a constraint. This makes it reasonably fast for easy to moderate level sudokus, although particularly hard ones can still take a rather long time to solve.

Run the code with perl -M5.010 to enable the Perl 5.10+ say feature. The input should be given on standard input, and the solution will be printed to standard output; example:

p[i/27*27+i%9/3*3..$][0..21].chunks(3).stride(3).joiner ).array.sort)) { c = o&63; if (s(p)) return p; } c=48; return []; } return p; } s(args).write; }  ## Clojure - 480 bytes The size exploded, but atleast it's a pretty number. I think it could be improved a lot by using just 1D-vector. Anyways, the test case takes a little under four seconds on my laptop. I thought it would be fitting to define a function, as it is a functional language after all. (defn f[o &[x y]](if x(if(> y 8)(apply str(map #(apply str %)o))(first(for[q[(o y)]v(if(=(q x)0)(range 1 10)[(q x)])d[(assoc o y(assoc(o y)x v))]s[(and(every? true?(concat(for[i(range 9)](and(or(not=((d y)i)v)(= i x))(or(not=((d i)x)v)(= i y))))(for[m[#(+ %2(- %(mod % 3)))]r[(range 3)]a r b r c[(m y b)]e[(m x a)]](or(and(= e x)(= c y))(not=((d y)x)((d c)e))))))(f d(mod(+ x 1)9)(if(= x 8)(+ 1 y)y)))]:when s]s)))(f(vec(for[a(partition 9 o)](vec(map #(Integer.(str %))a))))0 0)))  Examples: (f "030001000006000050500000983080006302000050000903800060714000009020000800000400030") => "832591674496387251571264983185746392267953418943812765714638529329175846658429137" (f "004720900039008005001506004040010520028050170016030090400901300100300840007085600") => "654723981239148765871596234743819526928654173516237498482961357165372849397485612"  A slightly ungolfed (and prettier) version: (defn check-place [o x y v] (and (every? true? (for [i (range 9)] (and (or (not= ((o y) i) v) (= i x)) (or (not= ((o i) x) v) (= i y))))) (every? true? (for [r [(range 3)] a r b r c [(+ b (- y (mod y 3)))] d [(+ a (- x (mod x 3)))]] (or (and (= d x) (= c y)) (not= ((o y) x) ((o c) d))))))) (defn solve-sudoku [board & [x y]] (if x (if (> y 8) (apply str (map #(apply str %) board)) (first (for [v (if (= ((board y) x) 0) (range 1 10) [((board y) x)]) :let [a (mod (+ x 1) 9) b (if (= x 8) (+ 1 y) y) d (assoc board y (assoc (board y) x v)) s (and (check-place d x y v) (solve-sudoku d a b))] :when s] s))) (solve-sudoku (vec (for [a (partition 9 board)] (vec (map #(Integer. (str %)) a)))) 0 0)))  # J, 94 bytes Works in exactly the same way as the K version, namely with a BFS (so it shall output all solutions). It prints spaces between output digits, but so does the K program. I’m not counting “s=:” as this is just naming the function (just like I wouldn’t count the filename in another language).  s=: [:<@((]i.0:)}"0 _~(>:i.9)-.{&((+./ .=|:)3(],.[,@#.<.@%~)9 9#:i.81)@i.&0#])"1^:(0 e.,)@;^:_"."0 s'030001000006000050500000983080006302000050000903800060714000009020000800000400030' 8 3 2 5 9 1 6 7 4 4 9 6 3 8 7 2 5 1 5 7 1 2 6 4 9 8 3 1 8 5 7 4 6 3 9 2 2 6 7 9 5 3 4 1 8 9 4 3 8 1 2 7 6 5 7 1 4 6 3 8 5 2 9 3 2 9 1 7 5 8 4 6 6 5 8 4 2 9 1 3 7  # PowerShell, 244242218 215 bytes $a=(24,24,6)*3|%{,(0..8|%{($r++)});,(0..8|%{$c%81;$c+=9});$c++;,((1,1,7)*3|%{+$q;$q+=$_});$q-=$_}$f={param($s)$l,$r=$s-split0,2;if($p=$a|?{$l.length-in$_}){1..9|?{"$_"-notin($p|%{$s[$_]})}|%{&$f "$l$_$r"}}else{$s}}  Try it online! The script finds all solutions for a sudoku. Unrolled: $a=(24,24,6)*3|%{                       # array of indexes for a sudoku...
,(0..8|%{($r++)}) # rows ,(0..8|%{$c%81;$c+=9});$c++         # columns
,((1,1,7)*3|%{+$q;$q+=$_});$q-=$_ # and squares }$f = {
param($s) # optional log. remove this statement in a release version. if($script:iter++ -lt 100 -or ($script:iter%100)-eq0){ Write-Information ('{0}: {1,6}: {2}'-f (get-Date),$script:iter, ($s-replace0,' ')) -InformationAction Continue }$left,$right=$s-split0,2                # split by a first 0; $left.length is a position of this 0 if$s contains the 0
if( $parts=$a|?{$left.length-in$_} ){   # get sudoku parts (rows, columns, squares) contain the position
1..9|?{                             # try a digit
"$_"-notin($parts|%{$s[$_]})    # all digits in these parts will be unique if parts do not contain the digit
}|%{
&$f "$left$_$right"             # recursive call with the digit
} #|select -f 1                     # uncomment this to get a first result only
}
else{
$s } }  Test cases: @( # 5 iterations, my notebook: 00:00:00, all # 5 iterations, my notebook: 00:00:00, first only , ( "832591674496387251571264983185746392267953418943812765714638529329175846658400030", "832591674496387251571264983185746392267953418943812765714638529329175846658429137" ) # ~29600 iterations, my notebook: 00:01:27, all # ~2100 iterations, my notebook: 00:00:10, first only # , ( "830001000006000050500000983080006302000050000903800060714000009020000800000400030", # "832591674496387251571264983185746392267953418943812765714638529329175846658429137" ) # ~49900 iterations, my notebook: 00:02:39, all # ~22400 iterations, my notebook: 00:01:20, first only # , ( "030001000006000050500000983080006302000050000903800060714000009020000800000400030", # "832591674496387251571264983185746392267953418943812765714638529329175846658429137" ) ) | % {$sudoku, $expected =$_
$time = Measure-Command {$result = &$f$sudoku
}
"$($result-contains$expected):$time"
$result }  ## Perl (195 chars) use integer;@A=split//,<>;sub R{for$i(0..80){next if$A[$i];my%t=map{$_/9==$/9||$_%9==$i%9||$_/27==$i/27&&$_%9/3==$i%9/3?$A[$_]:0=>1}0..80;R($A[$i]=$_)for grep{!$t{$_}}1..9;return$A[\$i]=0}die@A}R
`

All credit goes to the creator here, and the explanation can be found there as well.

• If you didn't write it yourself, then you should check the "Community Wiki" button. Jul 11, 2014 at 14:04
• After some research as to what that is, it doesn't look possible for me. Apparently 100 rep is needed for me to see the checkbox (see the addendum section under #2 of this post)
– Qwix
Jul 11, 2014 at 20:27
• Hmm, wasn't aware of that requirement. Jul 11, 2014 at 20:28