Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Sudoku solver in CoffeScript based on the Python solution by Peter Norvig
# Sudoku solver in CoffeeScript based on the Python solution by Peter Norvig
# http://norvig.com/sudoku.html
# 2011-04-19 jonelf@gmail.com
#
# Throughout this program we have:
# r is a row, e.g. 'A'
# c is a column, e.g. '3'
# s is a square, e.g. 'A3'
# d is a digit, e.g. '9'
# u is a unit, e.g. ['A1','B1','C1','D1','E1','F1','G1','H1','I1']
# grid is a grid,e.g. 81 non-blank chars, e.g. starting with '.18...7...
# values is a dict/hash of possible values, e.g. {'A1':'12349', 'A2':'8', ...}
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)
# "Tests"
# console.log squares.length
# console.log nine_squares
# console.log nine_squares.length
# console.log unitlist
# console.log unitlist.length
# console.log units
# console.log units["C2"]
# console.log peers["C2"]
parse_grid = (grid) ->
# To start, every square can be any digit; then assign values from the 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(d, '')
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(d, '')
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
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
search = (values) ->
return false if !values
min = {pos: -1, length: 10}
max = {pos: -1, length: 1}
for own key, value of values
if value.length > max.length then max = {pos: key, length: value.length}
if min.length > value.length > 1 then min= {pos: key, length: value.length}
return values if max.length==1 # Solved!
sq = squares[min.pos]
for d in values[sq]
return true unless search(assign(copy(values), sq, values[sq][d]))
return false
puzzle = '003020600900305001001806400008102900700000008006708200002609500800203009005010300'
display(search(parse_grid(puzzle)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment