sudoku.co

# Sudoku solver in Coco based on the Python solution by Peter Norvig
# http://norvig.com/sudoku.html
# 2011-04-19 [email protected]
# 2011-04-21 satyr
# 
# 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) -> a + b for b of B for a of A

uniq_and_remove = (duparr, ele) ->
  dic = {(ele)}
  dic[sq] = sq if sq not in dic for sq of duparr

squares = cross ROWS, COLS

nine_squares = for rs of <[ ABC DEF GHI ]>
               for cs of <[ 123 456 789 ]>
                 cross rs, cs

unitlist =
  ...nine_squares
  ...cross ROWS, c for c of COLS
  ...cross r, COLS for r of ROWS

units = {}
units[s] = (u if s of u for u of unitlist) for s of squares

peers = {}
for s of squares
  arr = cross(ROWS, s.1)concat cross(s.0, COLS)
  arr.push ...ns if s of ns for ns of nine_squares
  peers[s] = uniq_and_remove arr, 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 of squares
  for s, d in grid_values grid
    if +d and not assign values, s, d
      return  # Fail if we can't assign d to square s.)
  values

grid_values = (sgrid) ->
  grid = {}
  grid[squares[i]] = s for s, i of sgrid
  grid

assign = (values, s, d) ->
  return false unless eliminate values, s, d2 for d2 of values[s] - "#{d}"
  values

eliminate = (values, s, d) ->
  return values unless ~values[s]indexOf d

  v = values[s] -= "#{d}"
  return false unless v

  if v.length is 1
    return false unless eliminate values, s2, v for s2 of peers[s]

  for u of units
    dplaces = (s if ~v.indexOf d for s of u)
    return values unless dplaces.length
    return false if dplaces.length is 1 and not assign values, dplaces.0, d

  values

display = (values) ->
  console.log        '    ' + COLS * ' '
  console.log line = '   ------+-----+-----'
  for r of ROWS
    console.log line if r of <[D G]>
    row = r + ' | '
    for c of COLS
      row += values[r+c] + if c of <[3 6 9]> then \| else ' '
    console.log row
  console.log line

search = (values) ->
  return false unless values

  min = pos: -1, length: 10
  max = pos: -1, length: 1
  for key, val in values
    max = {pos: key, val.length} if val.length > max.length
    min = {pos: key, val.length} if min.length > val.length > 1
  return values if max.length is 1  # Solved!

  sq = squares[min.pos]
  for d of values[sq]
    return true unless search assign {...values} sq, values[sq][d]

  false

puzzle = \003020600900305001001806400008102900700000008006708200002609500800203009005010300

display search parse_grid puzzle