[Question]
  [
Implement the shortest Sudoku solver using guessing. Since I have received a few request I have added this as an alternative [question](https://codegolf.stackexchange.com/questions/355/implement-a-non-guessing-sudoku-solver) 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
```
**Answer:**
```
 | 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
```
  
[Answer]
# 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}
```
[Answer]
# Python, 188 bytes
This is a further shortened version of my winning submission for [CodeSprint Sudoku](https://sudoku.interviewstreet.com/), 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())
```
**EDIT:** [Here's a link to a more detailed walkthrough.](http://blog.cyphase.com/2012/12/07/playing-sudoku-beach/)
[Answer]
## 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]
# 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
```
[Answer]
# 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');
        }
        return to!string(retval);
    }
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).
[Answer]
## 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](http://www.nntp.perl.org/group/perl.fwp/2006/04/msg3836.html): 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](http://www.nntp.perl.org/group/perl.fwp/2006/04/msg3838.html)), 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
```
[Answer]
# 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)*
[Answer]
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`
[Here is the bigger version with sample usage](https://gist.github.com/3863614):
```
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'
```
[Answer]
## D (322 chars)
For each unsolved square it builds an array of available options and then loops over it.
```
import std.algorithm,std.range,std.stdio;void main(char[][]args){T s(T)(T p){foreach(i,ref c;p)if(c<49){foreach(o;"123456789".setDifference(chain(p[i/9*9..i/9*9+9],p[i%9..$].stride(9),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;}
```
with whitespace:
```
import std.algorithm, std.range, std.stdio;
void main(char[][] args) {
    T s(T)(T p) {
        foreach (i, ref c; p) if (c < 49) {
            foreach (o; "123456789".setDifference(chain(
                    p[i/9*9..i/9*9+9],
                    p[i%9..$].stride(9),
                    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;
}
```
[Answer]
## 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)))
```
[Answer]
# 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
```
[Answer]
# [PowerShell](https://github.com/TryItOnline/TioSetup/wiki/Powershell), ~~244~~ ~~242~~ ~~218~~ 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!](https://tio.run/##1VLbrpswEHznKyzOpoJykS9g7EaolfrcL6gqhBLnHFQCBBO1EuHb0zWkR@17VeksaFnPjGf2gaH/YUb7Ytr2foe6DHgW4yvD9@K2m@OApqnCIYAxisIl3L8icNgptodDVGqE8RshF7CYxcV2N4LLHi5RCZXjL4kbPDiV81CP9TkAG0Ibw1iCTezQNhON@b45BTCUUN8@ztCmremep5ek6ZzFzNJUI@5D5SddPzUdSt0e9itU35ZwwfkdnIgPLVQw@stiWmuQXpb7p8AjWDEJiK8EzzWTRZZpKVTBc5YXjMtMK8FUXmRSaM5loXORMaUzoRgvJEqQUDnXgmtW5CqTEhulVFA/Xs1d/VNznEXhk9Bb7Z9@b4@ZjLqSruX4uMIAqhwoKN9wB1KxYhQDNtVGqvXw1/ZP/2l/@hb3D8mN7Mi8BoG9Hvvv15iA@TmYw2SOpCRQbdzUnA0ev5jaXkeTfO7P57o7Pm6uitHYazuhxv2qD6@VXdbuQ/CQJIe@m@qms6854YctwPf@cPKW@y8 "PowerShell – 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
}
```
[Answer]
## 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](http://www.ecclestoad.co.uk/2005/06/sudoku-solver-in-three-lines-explained), and the explanation can be found there as well.
]