Find a solution to a sudoku puzzle

From CodeCodex

Implementations[edit]

Erlang[edit]

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[edit]

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[edit]

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[edit]

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[1])

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[1])

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[1])

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[edit]

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|
+-----+-----+-----+

Related Sudoku Sites[edit]

tips for sudoku

sudoku puzzle solver

sudoku tips and tricks

sudoku hints

solving sudoku

daily sudoku

suduko