Skip to content

Instantly share code, notes, and snippets.

Embed
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)))
@jonelf

This comment has been minimized.

Copy link
Owner Author

commented Apr 19, 2011

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.