Skip to content

Instantly share code, notes, and snippets.

@mythz
Last active December 18, 2015 04:09
Show Gist options
  • Save mythz/5723202 to your computer and use it in GitHub Desktop.
Save mythz/5723202 to your computer and use it in GitHub Desktop.
Peter Norvig's Sudoku Solver ported to other languages
#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])
//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))));
}
//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;
}
}
#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
#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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment