# 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? – Jonathan M Davis Feb 3 '11 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. – Jonathan M Davis Feb 3 '11 at 5:22
• it seems rules 5 and 6 kinda conflict.... – pseudonym117 Jul 11 '14 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! – nightTrevors Feb 13 '14 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[1])


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[1]) 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. – primo Dec 15 '12 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())


# Answer in D:

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[1].length == 81, new Exception("Invalid argument."));
enforce(!canFind!((a){return !isDigit(to!dchar(a));})
(args[1]),
new Exception("Entire argument must be digits."));

auto sudoku = new Sudoku(args[1]);
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[81] 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, 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


# J, 103

'p n'=:(;#)I.0=a=:("."0)Y
((a p}~3 :'>:?n#9')^:([:(27~:[:+/[:(9=#@~.)"1[:,/(2 2$3),;.3],|:,])9 9$])^:_)a


expected run time: O(gazillion billion years)

• And why is the expected run time "O(gazillion billion years)"? (shouldn't that be just "gazillion billion years" without the O? – Justin Feb 13 '14 at 5:21
• When I saw this question I immediatly knew that J is going to crush this one. There has to be a way to make this shorter than K. – koko Feb 13 '14 at 10:18
• @Quincunx, strictly speaking, it's a wrong use of big-O; the "joke" was supposed to read "constant run time, asymptotically gazillion billion years". – Eelvex Feb 13 '14 at 14:51
• @koko, I couldn't find something better but I'm still working on it. – Eelvex Feb 13 '14 at 14:52

## 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:

$perl -M5.010 golf/sudoku.pl 030001000006000050500000983080006302000050000903800060714000009020000800000400030 832591674496387251571264983185746392267953418943812765714638529329175846658429137  1-liner coffee-script solve = (s, c = 0) -> if c is 81 then s else if s[x = c/9|0][y = c%9] isnt 0 then solve s, c+1 else (([1..9].filter (g) -> ![0...9].some (i) -> g in [s[x][i], s[i][y], s[3*(x/3|0) + i/3|0][3*(y/3|0) + i%3]]).some (g) -> s[x][y] = g; solve s, c+1) or s[x][y] = 0 solve = (sudoku, cell = 0) -> if cell is 9*9 then return sudoku x = cell%9 y = (cell - x)/9 if sudoku[x][y] isnt 0 then return solve sudoku, cell+1 row = (i) -> sudoku[x][i] col = (i) -> sudoku[i][y] box = (i) -> sudoku[x - x%3 + (i - i%3)/3][y - y%3 + i%3] good = (guess) -> [0...9].every (i) -> guess not in [row(i), col(i), box(i)] guesses = [1..9].filter good solves = (guess) -> sudoku[x][y] = guess; solve sudoku, cell+1 (guesses.some solves) or sudoku[x][y] = 0 sudoku = [ [1,0,0,0,0,7,0,9,0], [0,3,0,0,2,0,0,0,8], [0,0,9,6,0,0,5,0,0], [0,0,5,3,0,0,9,0,0], [0,1,0,0,8,0,0,0,2], [6,0,0,0,0,4,0,0,0], [3,0,0,0,0,0,0,1,0], [0,4,0,0,0,0,0,0,7], [0,0,7,0,0,0,3,0,0] ] console.log if solve sudoku then sudoku else 'could not solve'  • Could be shortened by shortening solve, removing lots of whitespace (I know it's significant, but in many places it could be removed), using symbols instead of words (like != instead of isnt), using indentation instead of then keyword, replacing [0...9] with [0..8]. – Konrad Borowski Jan 4 '13 at 11:56 ## 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)))  # 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"
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[1]).write; }  ## 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. – Kyle Kanos Jul 11 '14 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 '14 at 20:27
• Hmm, wasn't aware of that requirement. – Kyle Kanos Jul 11 '14 at 20:28

# 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
`