gistfile1.coffee

# Sudoku solver in CoffeeScript based on the Python solution by Peter Norvig
# http://norvig.com/sudoku.html
# 2011-04-19 [email protected]
# 
# 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)))