justnull · June 12, 2013 03:55 · Jun 11, 2013
diff --git a/gistfile1.txt b/gistfile1.txt
@@ -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)))
No results found