{{ message }}

Instantly share code, notes, and snippets.

# jonelf/gist:927782

Created Apr 19, 2011
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 commented Apr 19, 2011

 The generated JavaScript http://alicebobandmallory.com/sudoku.js.html and a small blog post http://alicebobandmallory.com/articles/2011/04/19/sudoku-solver-in-coffeescript