Peter Norvig's Sudoku Solver ported to other languages

01_sudo.py

#full source: https://github.com/dartist/sudoku_solver/blob/master/benchmarks/sudoku.py

def cross(A, B):
    "Cross product of elements in A and elements in B."
    return [a+b for a in A for b in B]

digits   = '123456789'
rows     = 'ABCDEFGHI'
cols     = digits
squares  = cross(rows, cols)
unitlist = ([cross(rows, c) for c in cols] +
            [cross(r, cols) for r in rows] +
            [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
units = dict((s, [u for u in unitlist if s in u])
             for s in squares)
peers = dict((s, set(sum(units[s],[]))-set([s]))
             for s in squares)

################ Parse a Grid ################

def parse_grid(grid):
    """Convert grid to a dict of possible values, {square: digits}, or
    return False if a contradiction is detected."""
    ## To start, every square can be any digit; then assign values from the grid.
    values = dict((s, digits) for s in squares)
    for s,d in grid_values(grid).items():
        if d in digits and not assign(values, s, d):
            return False ## (Fail if we can't assign d to square s.)
    return values

def grid_values(grid):
    "Convert grid into a dict of {square: char} with '0' or '.' for empties."
    chars = [c for c in grid if c in digits or c in '0.']
    assert len(chars) == 81
    return dict(zip(squares, chars))

################ Constraint Propagation ################

def assign(values, s, d):
    """Eliminate all the other values (except d) from values[s] and propagate.
    Return values, except return False if a contradiction is detected."""
    other_values = values[s].replace(d, '')
    if all(eliminate(values, s, d2) for d2 in other_values):
        return values
    else:
        return False

def eliminate(values, s, d):
    """Eliminate d from values[s]; propagate when values or places <= 2.
    Return values, except return False if a contradiction is detected."""
    if d not in values[s]:
        return values ## Already eliminated
    values[s] = values[s].replace(d,'')
    ## (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
    if len(values[s]) == 0:
        return False ## Contradiction: removed last value
    elif len(values[s]) == 1:
        d2 = values[s]
        if not all(eliminate(values, s2, d2) for s2 in peers[s]):
            return False
    ## (2) If a unit u is reduced to only one place for a value d, then put it there.
    for u in units[s]:
        dplaces = [s for s in u if d in values[s]]
        if len(dplaces) == 0:
            return False ## Contradiction: no place for this value
        elif len(dplaces) == 1:
            # d can only be in one place in unit; assign it there
            if not assign(values, dplaces[0], d):
                return False
    return values

################ Display as 2-D grid ################

def display(values):
    "Display these values as a 2-D grid."
    width = 1+max(len(values[s]) for s in squares)
    line = '+'.join(['-'*(width*3)]*3)
    for r in rows:
        print ''.join(values[r+c].center(width)+('|' if c in '36' else '')
                      for c in cols)
        if r in 'CF': print line
    print

################ Search ################

def solve(grid): return search(parse_grid(grid))

def search(values):
    "Using depth-first search and propagation, try all possible values."
    if values is False:
        return False ## Failed earlier
    if all(len(values[s]) == 1 for s in squares):
        return values ## Solved!
    ## Chose the unfilled square s with the fewest possibilities
    n,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
    return some(search(assign(values.copy(), s, d))
                for d in values[s])

02_sudoku_solver.dart

//full source: https://github.com/dartist/sudoku_solver/blob/master/benchmarks/sudoku.dart

List<List<String>> cross(String A, String B) =>
  A.split('').expand((a) => B.split('')
    .map((b) => a+b)).toList();  

var digits   = '123456789';
var rows     = 'ABCDEFGHI';
var cols     = digits;
var squares = cross(rows, cols);

var unitlist = cols.split('').map((c) => cross(rows, c)).toList()
  ..addAll( rows.split('').map((r) => cross(r, cols)))
  ..addAll( ['ABC','DEF','GHI'].expand((rs) => ['123','456','789'].map((cs) => cross(rs, cs)) ));

var units = dict(squares.map((s) => 
    [s, unitlist.where((u) => u.contains(s)).toList()] ));

var peers = dict(squares.map((s) => 
    [s, units[s].expand((u) => u).toSet()..removeAll([s])]));    

/// Parse a Grid
Map parse_grid(String grid){
  var values = dict(squares.map((s) => [s, digits]));
  var gridValues = grid_values(grid);
  for (var s in gridValues.keys){
    var d = gridValues[s];
    if (digits.contains(d) && assign(values, s, d) == null)
      return null;
  }
  return values;
}

Map grid_values(String grid){
  var chars = grid.split('').where((c) => digits.contains(c) || '0.'.contains(c));
  return dict(zip(squares, chars));
}

/// Constraint Propagation
Map assign(Map values, String s, String d){
  var other_values = values[s].replaceAll(d, '');
  if (all(other_values.split('').map((d2) => eliminate(values, s, d2))))
    return values;
  return null;
}

Map eliminate(Map values, String s, String d){
  if (!values[s].contains(d))
    return values;
  values[s] = values[s].replaceAll(d,'');
  if (values[s].length == 0)
    return null;
  else if (values[s].length == 1){
    var d2 = values[s];
    if (!all(peers[s].map((s2) => eliminate(values, s2, d2))))
      return null;
  }
  for (var u in units[s]){
    var dplaces = u.where((s) => values[s].contains(d)); 
    if (dplaces.length == 0)
      return null;
    else if (dplaces.length == 1)
      if (assign(values, dplaces.elementAt(0), d) == null)
        return null;
  }
  return values;
}

/// Display as 2-D grid
void display(Map values){
  var width = 1 + squares.map((s) => values[s].length).reduce(Math.max);
  var line = repeat('+' + repeat('-', width*3), 3).substring(1);  
  rows.split('').forEach((r){
    print(cols.split('').map((c) => center(values[r+c], width) + ('36'.contains(c) ? '|' : '')).toList()
      .join(''));
    if ('CF'.contains(r))
      print(line);
  });
  print("");
}

/// Search 
Map solve(String grid) => search(parse_grid(grid));

Map search(Map values){
  if (values == null)
    return null;
  if (squares.every((s) => values[s].length == 1))
    return values;
  var s2 = order(squares.where((s) => values[s].length > 1).toList(), on:(s) => values[s].length).first;
  return some(values[s2].split('').map((d) => search(assign(new Map.from(values), s2, d))));
}

03_Solver.cs

//full source: https://github.com/dartist/sudoku_solver/blob/master/benchmarks/sudoku.cs

static class LinqSudokuSolver {

    static string rows = "ABCDEFGHI";
    static string cols = "123456789";
    static string digits = "123456789";
    static string[] squares = cross(rows, cols);
    static Dictionary<string, IEnumerable<string>> peers;
    static Dictionary<string, IGrouping<string, string[]>> units;

    static string[] cross(string A, string B) {
        return (from a in A from b in B select ""+a+b).ToArray();
    }

    static LinqSudokuSolver() {

        var unitlist=((from c in cols select cross(rows, c.ToString()))
                           .Concat(from r in rows select cross(r.ToString(), cols))
                           .Concat(from rs in (new [] { "ABC", "DEF", "GHI" }) from cs in (new [] { "123", "456", "789" }) select cross(rs, cs)));
        
        units = (from s in squares from u in unitlist where u.Contains(s) group u by s into g select g).ToDictionary(g=>g.Key);

        peers = (from s in squares from u in units[s] from s2 in u where s2 != s group s2 by s into g select g).ToDictionary(g=>g.Key, g=>g.Distinct());

    public static Dictionary<string, string> parse_grid(string grid) {
        var grid2 = from c in grid where "0.-123456789".Contains(c) select c;
        var values = squares.ToDictionary(s => s, s => digits); //To start, every square can be any digit

        foreach (var sd in zip(squares, (from s in grid select s.ToString()).ToArray())) {
            var s = sd[0];
            var d = sd[1];

            if (digits.Contains(d) && assign(values, s, d)==null) {
                return null;
            }
        }
        return values;
    }

    public static Dictionary<string, string> search(Dictionary<string, string> values) {
        if (values == null) {
            return null; // Failed earlier
        }
        if (all(from s in squares select values[s].Length == 1?"":null)) {
            return values; // Solved!
        }

        var s2 = (from s in squares where values[s].Length > 1 orderby values[s].Length ascending select s).First();

        return some(from d in values[s2] 
                    select search(assign(new Dictionary<string,string>(values), s2, d.ToString())));
    }
    
    static Dictionary<string, string> assign(Dictionary<string, string> values, string s, string d) {
        if (all(
                from d2 in values[s] 
                where d2.ToString() != d 
                select eliminate(values, s, d2.ToString()))) {
            return values;
        }
        return null;
    }

    static Dictionary<string, string> eliminate(Dictionary<string, string> values, string s, string d) {
        if (!values[s].Contains(d)) {
            return values;
        }
        values[s]=values[s].Replace(d, "");
        if (values[s].Length == 0) {
            return null; //Contradiction: removed last value
        } else if (values[s].Length == 1) {
            var d2 = values[s];
            if (!all(from s2 in peers[s] select eliminate(values, s2, d2))) {
                return null;
            }
        }

        foreach (var u in units[s]) {
            var dplaces = from s2 in u where values[s2].Contains(d) select s2;
            if (dplaces.Count() == 0) {
                return null;
            } else if (dplaces.Count() == 1) {
                if (assign(values, dplaces.First(), d)==null) {
                    return null;
                }
            }
        }
        return values;
    }

    static Dictionary<string, string> print_board(Dictionary<string, string> values) {
        if (values == null) return null;

        var width = 1 + (from s in squares select values[s].Length).Max();
        var line = "\n" + String.Join("+", Enumerable.Repeat(new String('-', width * 3), 3).ToArray());        

        foreach (var r in rows) {
            Console.WriteLine(String.Join("", 
                (from c in cols 
                 select values[""+r+c].Center(width)+("36".Contains(c)?"|":"")).ToArray()) 
                    + ("CF".Contains(r)?line:""));
        }

        Console.WriteLine();
        return values;
    }
}

04_soduku.rb

#full source: https://github.com/dartist/sudoku_solver/blob/master/benchmarks/sudoku.rb

ROWS = ('A'..'I')
COLS = ('1'..'9')
DIGITS = "123456789"

def cross(rows,cols)
  cols.map {|x| rows.map {|y| y + x  }}.flatten
end

@squares =  cross(ROWS, COLS) # total of 81 squares
nine_squares = ROWS.each_slice(3).map {|r| COLS.each_slice(3).map{|c| cross(r,c)}}.flatten(1)
@unitlist = COLS.map{|c| cross(ROWS,[c])} <<
            ROWS.map{|r| cross([r], COLS)} <<
            nine_squares
@units = @squares.inject({}) {|h, s| h[s]=@unitlist.select{|arr| arr.include?(s)};h}

@peers = @squares.inject({}) {|h,s| peers=(cross(ROWS,[s[1]]) << 
                                    cross([s[0]],COLS) << 
                                    nine_squares.select{|sq| sq.include?(s)} ).
                                    flatten; 
                                    peers.delete(s);
                                    h[s]=peers;
                                    h}

def grid_values(grid)
  @squares.zip(grid.each_char.grep(/[0-9\.]/))
end

################ Constraint Propagation ################

def assign(values, s, d)
  other_values = values[s].sub(d,'')
  other_values.each_char do |d2|
    return false unless eliminate(values, s, d2)
  end
  values
end

def eliminate(values, s, d)
  return values unless values[s].include?(d) ## Already eliminated

  values[s] = values[s].sub(d,'')

  if values[s].size== 0
    return false ## Contradiction: removed last value
  elsif values[s].size == 1
    d2 = values[s]
    @peers[s].each do |s2|
      return false unless (eliminate(values, s2, d2))
    end
  end

  sa = [s]
  @units[s].each do |u|
    dplaces = values[s].include?(d) ? sa & u : []
    
    return values if dplaces.size == 0
    if dplaces.size == 1
      return false unless assign(values, dplaces[0], d)
    end
  end
  values
end # def

################ Display Results as 2-D grid ################       

def display(values)
  width = 2 #1 + values.max_by {|a| a.size}[1].size
  puts line = [['-'*width*3]*3].join('+') # 81 square grid
  ROWS.each do |r|
    puts line if "DG".include?(r)    # 3x3 grid
    COLS.each do |c|
      print values["#{r}#{c}"].center(width)
      print '|' if '36'.include?(c)
    end
    puts
  end
  puts line
end

################ Utilities ################

def get_min(d)
  min = d.select{|k,v| v.length>1}.
          min_by{|h| h[1].length}
  return min[0], min[1], min[1].length
end

################ Parse a Grid ################

def parse_grid (grid)
  values = {} # define values dictionary
  @squares.each do |s|
    values[s] = DIGITS
  end

  grid_values(grid).each do |zg|
    s, d = zg
    if DIGITS.include?(d)
      return false unless assign(values, s, d)
    end
  end
  values
end # parse_grid  

################ Search Grid Values ################    

def search(values)
  return false unless values ## Failed earlier
  return values unless @squares.any?{|s| values[s].size != 1}

  k,v,l =  get_min(values)
  v.each_char do |d|
    r = search(assign(values.clone, k, d))
    return r if r
  end
  return false
end # search def

05_soduku.coffee

#full source: https://github.com/dartist/sudoku_solver/blob/master/benchmarks/sudoku.coffee

ROWS = "ABCDEFGHI"
COLS = "123456789"
DIGITS = COLS

cross = (A, B) ->
  results = []
  for a in A
    for b in B
      results.push a + b
  results

copy = (obj) ->
  cl = {};
  for own k, v of obj
    cl[k] = v
  cl

uniq_and_remove = (duparr, ele) ->
  hash = {}
  for sq in duparr
    hash[sq] = 0
  arr = []
  for own key, value of hash
    arr.push(key) if key != ele
  arr

squares = cross(ROWS, COLS)

nine_squares = []
for rs in ['ABC','DEF','GHI']
  for cs in ['123','456','789']
    nine_squares.push cross(rs,cs)

unitlist = (cross(ROWS, c) for c in COLS).concat(cross(r, COLS) for r in ROWS).concat(nine_squares)

units = {}
for s in squares
  units[s] = []
  for u in unitlist
    units[s].push(u) if s in u

peers = {}
for s in squares
  peers[s] = []
  peers[s] = peers[s].concat(cross(ROWS, s[1])).concat(cross(s[0], COLS))
  for ns in nine_squares
    peers[s] = peers[s].concat(ns) if s in ns
  peers[s] = uniq_and_remove(peers[s],s)

parse_grid = (grid) ->
  values = {}
  values[s] = DIGITS for s in squares
  for own s, d of grid_values(grid)
    if d in DIGITS and not assign(values, s, d)
      return false # (Fail if we can't assign d to square s.)
  values

grid_values = (sgrid) ->
  grid = {}
  for i in [0...sgrid.length]
    grid[squares[i]] = if sgrid[i] in DIGITS then sgrid[i] else "."
  grid    

assign = (values, s, d) ->
  other_values = values[s].replace(new RegExp(d, 'g'), '')
  for d2 in other_values
    return false unless eliminate(values, s, d2)
  values

eliminate = (values, s, d) ->
  return values unless values[s].indexOf(d) >= 0
  values[s] = values[s].replace new RegExp(d, 'g'), ''

  if values[s].length == 0
    return false
  else if values[s].length == 1
    d2 = values[s]
    for s2 in peers[s]
      return false unless eliminate(values, s2, d2)

  for u in units[s]
    dplaces = (s for s in u when d in values[s])
    return values if dplaces.length == 0
    if dplaces.length == 1
      return false unless assign(values, dplaces[0], d)
  values

display = (values) ->
  console.log "    " + COLS.replace(/(.)/g, "$1 ")
  line = "  |------+-----+-----|"
  console.log line
  for r in ROWS
    console.log line if r in "DG"
    row = r+" | "
    for c in COLS
      row = row.concat(values[r+c])
      row = row.concat(if c in "369" then "|" else " ")
    console.log row
  console.log line
  console.log ""

orderOn = (seq, fn) ->
  seq.sort (a,b) -> 
    if fn(a) > fn(b) then 1 else -1
  seq

some = (seq) ->
  for e in seq
    return e if e
  false

search = (values) ->
  return false if !values
  if (squares.every (s) -> values[s].length == 1)
    return values
  s2 = (orderOn (s for s in squares when values[s].length > 1), (s) -> values[s].length)[0]
  some values[s2].split('').map (d) -> search assign copy(values), s2, d