Created
June 11, 2013 00:36
Revisions
-
BrendanEich created this gist
Jun 11, 2013 .There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,163 @@ // XXX should be standard (and named clone, after Java?) Object.prototype.copy = function () { let o = {} for (let i in this) o[i] = this[i] return o } // Containment testing for arrays and strings that should be coherent with their iterator. Array.prototype.contains = String.prototype.contains = function (e) { return this.indexOf(e) != -1 } Array.prototype.repeat = String.prototype.repeat = function (n) { let s = this.constructor() for (let i = 0; i < n; i++) s = s.concat(this) return s } String.prototype.center = function (w) { let n = this.length if (w <= n) return this let m = Math.floor((w - n) / 2) return ' '.repeat(m) + this + ' '.repeat(w - n - m) } Array.prototype.toString = Array.prototype.toSource Object.prototype.toString = Object.prototype.toSource // XXX thought spurred by the next two functions: array extras should default to identity function function all(seq) { for (let e of seq) if (!e) return false return true } function some(seq) { for (let e of seq) if (e) return e return false } function cross(A, B) { return [a+b for (a of A) for (b of B)] } function dict(A) { let d = {} for (let e of A) d[e[0]] = e[1] return d } function set(A) { let s = [] for (let e in A) if (!s.contains(e)) s.push(e) return s } function zip(A, B) { let z = [] let n = Math.min(A.length, B.length) for (let i = 0; i < n; i++) z.push([A[i], B[i]]) return z } rows = 'ABCDEFGHI' cols = '123456789' digits = '123456789' squares = cross(rows, cols) unitlist = [cross(rows, c) for (c in cols)] .concat([cross(r, cols) for (r in rows)]) .concat([cross(rs, cs) for (rs in ['ABC','DEF','GHI']) for (cs in ['123','456','789'])]) units = dict([s, [u for (u of unitlist) if (u.contains(s))]] for (s of squares)) peers = dict([s, set([s2 for (u of units[s]) for (s2 of u) if (s2 != s)])] for (s of squares)) // Given a string of 81 digits (or . or 0 or -), return a dict of {cell:values}. function parse_grid(grid) { grid = [c for (c in grid) if ('0.-123456789'.contains(c))] let values = dict([s, digits] for (s in squares)) for (let [s, d] of zip(squares, grid)) if (digits.contains(d) && !assign(values, s, d)) return false return values } // Eliminate all the other values (except d) from values[s] and propagate. function assign(values, s, d) { if (all(eliminate(values, s, d2) for (d2 in values[s]) if (d2 != d))) return values return false } // Eliminate d from values[s]; propagate when values or places <= 2. function eliminate(values, s, d) { if (!values[s].contains(d)) return values // Already eliminated values[s] = values[s].replace(d, '') if (values[s].length == 0) return false // Contradiction: removed last value if (values[s].length == 1) { // If there is only one value (d2) left in square, remove it from peers let d2 = values[s][0] if (!all(eliminate(values, s2, d2) for (s2 in peers[s]))) return false } // Now check the places where d appears in the units of s for (let u in units[s]) { let dplaces = [s for (s in u) if (values[s].contains(d))] if (dplaces.length == 0) return false if (dplaces.length == 1) // d can only be in one place in unit; assign it there if (!assign(values, dplaces[0], d)) return false } return values } // Used for debugging. function print_board(values) { let width = 1 + Math.max.apply(Math, [values[s].length for (s in squares)]) let line = '\n' + ['-'.repeat(width*3)].repeat(3).join('+') for (let r in rows) print([values[r+c].center(width) + ('36'.contains(c) && '|' || '') for (c in cols)].join('') + ('CF'.contains(r) && line || '')) print() } easy = "..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3.." print_board(parse_grid(easy)) // Using depth-first search and constraint propagation, try all possible values. function search(values) { if (!values) return false // Failed earlier if (all(values[s].length == 1 for (s in squares))) return values // Solved! // Choose the unfilled square s with the fewest possibilities // XXX Math.min etc. should work with generator expressions and other iterators // XXX Math.min etc. should work on arrays (lists or tuples in Python) as well as numbers let a = [values[s].length + s for (s in squares) if (values[s].length > 1)].sort() let s = a[0].slice(-2) return some(search(assign(values.copy(), s, d)) for (d in values[s])) } hard = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......' print_board(search(parse_grid(hard)))