# Find a solution to a sudoku puzzle

## Implementations

### Erlang

It changes an input list into the tuple. To do a data display easily, it changes into the period except 1 - 9 characters.

```-module(sudoku).
-export([solver/1]).

solver(List) when length(List) =:= 81 ->
L = re:replace(List, "[^1-9]", ".", [global, {return, list}]),
Tuple = list_to_tuple(L),
print(Tuple),
try solve(Tuple)
catch
{ok, Result} ->
print(Result),
tuple_to_list(Result);
Throw -> Throw
end.

print(T) ->
F = fun(I) ->
if (I rem 27) =:= 0 -> io:format("+-----+-----+-----+~n"); true -> ok end,
X = element(I+1, T),
if (I rem 3) =:= 0 -> io:format("|~c", [X]);
true           -> io:format(" ~c", [X])
end,
if (I rem 9) =:= 8 -> io:format("|~n"); true -> ok end
end,
lists:foreach(F, lists:seq(0, 80)),
io:format("+-----+-----+-----+~n").

solve(T) ->
F = fun(X, Res) when element(X+1, T) =/= \$. -> Res;
(X, Res) ->
case validity(T, X) of
[] -> throw(impossible);
V  -> [{length(V), X, V} | Res]
end
end,
case lists:foldl(F, [], lists:seq(0, 80)) of
[] -> throw({ok, T});                           % solution
Possible -> trial_and_error(T, Possible)
end.

trial_and_error(T, Possible) ->
{_Len, I, V} = lists:min(Possible),
F = fun(X) ->
try solve(setelement(I+1, T, X))
catch
{ok, Res} -> throw({ok, Res});
_ -> ng
end
end,
lists:foreach(F, V),
throw(impossible).

validity(T, N) ->
I = N div 9,
J = N rem 9,
F = fun(X, A) -> [element(I*9+X+1 ,T), element(X*9+J+1, T) | A] end,
A1 = lists:foldl(F, [], lists:seq(0, 8)),
Block = [1,2,3,10,11,12,19,20,21],
B = (I div 3) * 27 + (J div 3) * 3,
A2 = lists:foldl(fun(X, A) -> [element(B+X, T) | A] end, A1, Block),
"123456789" -- A2.
```

For example(Eshell):

```1> c(sudoku).
{ok,sudoku}
2> sudoku:solver("000000060007300900008900000071000000000000008800050604010200090200004000069000070"
).
```

The output is the same as Ruby.

### OCaml

```let m = Array.init 9 (fun _ -> read_line())
let print() = Array.iter print_endline m
let rec invalid ?(i=0) x y n =
i<9 && (m.(y).[i] = n || m.(i).[x] = n ||
m.(y/3*3 + i/3).[x/3*3 + i mod 3] = n || invalid ~i:(i+1) x y n)
let rec fold f accu l u = if l=u then accu else fold f (f accu l) (l+1) u
let rec search ?(x=0) ?(y=0) f accu = match x, y with
9, y -> search ~x:0 ~y:(y+1) f accu (* Next row *)
| 0, 9 -> f accu                      (* Found a solution *)
| x, y ->
if m.(y).[x] <> '0' then search ~x:(x+1) ~y f accu else
fold (fun accu n ->
let n = Char.chr (n + 48) in
if invalid x y n then accu else
(m.(y).[x] <- n;
let accu = search ~x:(x+1) ~y f accu in
m.(y).[x] <- '0';
accu)) accu 1 10
let () = Printf.printf "%d solutions\n" (search (fun i -> print(); i+1) 0)
```

### Perl

The following Perl program that can solve Sudoku is only 185 bytes:

```use integer;sub R{for\$i(grep!\$A[\$_],@x=0..80){%t=map{\$_/27-\$i/27|\$_%9/3-\$i%9/3&&\$_
/9-\$i/9&&(\$_-\$i)%9?0:\$A[\$_]=>1}@x;R(\$A[\$i]=\$_)for grep!\$t{\$_},1..9;return\$A[\$i]=0}
die@A}@A=split//,<>;R
```

This program is a slightly modified version of another three line Sudoku Solver (page includes a description of how it works).

The initial board must be supplied as a row of 81 digits with no formatting, created by appending the rows one after another on one line. Use the characters 1-9 to represent the givens, and 0 for an unknown. The output is given in the same form.

Example usage, with an initially empty grid:

```\$ echo 000000000000000000000000000000000000000000000000000000000000000000000000000000000 |
perl sudoku.pl
```

The output is:

```123456789456789123789123456214365897365897214897214365531642978642978531978531642
```

Which corresponds to the following Sudoku:

```-------------
|123|456|789|
|456|789|123|
|789|123|456|
|---+---+---|
|214|365|897|
|365|897|214|
|897|214|365|
|---+---+---|
|531|642|978|
|642|978|531|
|978|531|642|
-------------
```

The program is very fast for most inputs, but there are valid sudoku puzzles that this program takes a very long time to solve (over an hour), for example:

```-------------
|...|...|.6.|
|..7|3..|9..|
|..8|9..|...|
|---+---+---|
|.71|...|...|
|...|...|..8|
|8..|.5.|6.4|
|---+---+---|
|.1.|2..|.9.|
|2..|..4|...|
|.69|...|.7.|
-------------
```

There is also a slightly longer version which can solve a Super Sudoku (a Sudoku with a 16 by 16 grid). This time the input must consist of the characters 0-9,a-f and a space for unknown.

```use integer;@A=split//,<>;sub R{for\$i(grep\$A[\$_]=~' ',@x=0..255){%t=map{\$_/16==\$i/
16||\$_%16==\$i%16||\$_/64==\$i/64&&\$_%16/4==\$i%16/4?\$A[\$_]:''=>1}@x;R(\$A[\$i]=\$_)for
grep!\$t{\$_},0..9,'a'..'f';return\$A[\$i]=' '}die@A}R
```

### Python

The current shortest Python sudoku solver program is 178 bytes long and fits on four lines with no line longer than 80 chars. It prints the first solution only. To run, the intial layout must be given as command line argument containing 81 characters from 0-9 (0 = unknown), and the solution is returned in the same format to standard error. The input must have a valid solution.

```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'%d'%5**18]
from sys import*;r(argv)
```

To run, on a blank board:

```python sudoku.py 000000000000000000000000000000000000000000000000000000000000000000000000000000000
```

The program can be adjusted to fit on 3 lines with no line longer than 80 characters, but now 179 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'%d'%5**18]
from sys import*;r(argv)
```

This is the cleanest version which does not use any unusual features such as outputting to standard error, or crashing instead of terminating properly. This program is 190 bytes:

```def r(a):
i=a.find('0')
if i<0:print a;exit()
[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'%d'%5**18]
from sys import*;r(argv)
```

This is the dirtiest version, where byte count is all that matters. It reads the initial board layout from a file. 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. The solution is displayed on the last line of standard out. This program is 165 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'%d'%5**18]
r(open('f').read())
```

To run the program, first write the board to a file called f, then run the script from the same directory, as shown here:

```echo -n 000000000000000000000000000000000000000000000000000000000000000000000000000000000 > f
python sudoku.py 2>/dev/null
```

### Ruby

```def input_data(f)
board = []
while line=f.gets do board << line.chomp.split(//).map{|c|c.to_i} end
board.flatten
end

def print_board(board)
frame = "+-----+-----+-----+"
board.each_with_index do |x,i|
puts frame  if i%27 == 0
print (i%3 == 0) ? "|" : " "
print x == 0 ? "." : x
puts "|\n"  if i%9 == 8
end
puts frame
end

def valid_value(board, index)
i, j = index.divmod(9)
value = [nil] + (1..9).to_a
9.times {|x| value[board[x*9+j]] = nil; value[board[i*9+x]] = nil}
b = (i / 3) * 27 + (j / 3) * 3
[0,1,2,9,10,11,18,19,20].each {|x| value[board[b+x]] = nil}
value.compact
end

def sudoku_solver(board)
loop do
possible = []
board.each_with_index do |x,i|
next  if x > 0
v = valid_value(board, i)
return  if v.empty?                       # Impossible
possible << [i, v]
end
return board  if possible.empty?            # solution
i, v = possible.min_by {|x| x.last.size}
if v.size == 1
board[i] = v.first
else
v.each do |value|
work = board.dup
work[i] = value
result = sudoku_solver(work)
return result  if result
end
return                                    # Impossible
end
end
end

board = input_data(DATA)
print_board(board)

if result = sudoku_solver(board)
print_board(result)
else
puts "Impossible"
end

__END__
.......6.
..73..9..
..89.....
.71......
........8
8...5.6.4
.1.2...9.
2....4...
.69....7.
```

output:

```+-----+-----+-----+
|. . .|. . .|. 6 .|
|. . 7|3 . .|9 . .|
|. . 8|9 . .|. . .|
+-----+-----+-----+
|. 7 1|. . .|. . .|
|. . .|. . .|. . 8|
|8 . .|. 5 .|6 . 4|
+-----+-----+-----+
|. 1 .|2 . .|. 9 .|
|2 . .|. . 4|. . .|
|. 6 9|. . .|. 7 .|
+-----+-----+-----+
+-----+-----+-----+
|9 3 2|8 4 1|5 6 7|
|6 4 7|3 2 5|9 8 1|
|1 5 8|9 7 6|2 4 3|
+-----+-----+-----+
|4 7 1|6 8 2|3 5 9|
|5 2 6|4 3 9|7 1 8|
|8 9 3|1 5 7|6 2 4|
+-----+-----+-----+
|7 1 4|2 6 3|8 9 5|
|2 8 5|7 9 4|1 3 6|
|3 6 9|5 1 8|4 7 2|
+-----+-----+-----+
```