michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: 
michael@0: function copy(obj) {
michael@0:   var o = {};
michael@0:   for (var i in obj)
michael@0:     o[i] = obj[i];
michael@0:   return o;
michael@0: }
michael@0: 
michael@0: Array.prototype.contains = String.prototype.contains = function (e) {
michael@0:   for (var elt of this)
michael@0:     if (elt == e)
michael@0:       return true;
michael@0:   return false;
michael@0: }
michael@0: 
michael@0: Array.prototype.repeat = String.prototype.repeat = function (n) {
michael@0:   var s = this.constructor();
michael@0:   for (var i = 0; i < n; i++)
michael@0:     s = s.concat(this);
michael@0:   return s;
michael@0: }
michael@0: 
michael@0: String.prototype.center = function (w) {
michael@0:   var n = this.length;
michael@0:   if (w <= n)
michael@0:     return this;
michael@0:   var m = Math.floor((w - n) / 2);
michael@0:   return ' '.repeat(m) + this + ' '.repeat(w - n - m);
michael@0: }
michael@0: 
michael@0: Array.prototype.toString = Array.prototype.toSource
michael@0: Object.prototype.toString = Object.prototype.toSource
michael@0: 
michael@0: function all(seq) {
michael@0:   for (var e of seq)
michael@0:     if (!e)
michael@0:       return false;
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: function some(seq) {
michael@0:   for (var e of seq)
michael@0:     if (e)
michael@0:       return e;
michael@0:   return false;
michael@0: }
michael@0: 
michael@0: function cross(A, B) {
michael@0:   return [for (a of A) for (b of B) a+b];
michael@0: }
michael@0: 
michael@0: function dict(A) {
michael@0:   var d = {};
michael@0:   for (var e of A)
michael@0:     d[e[0]] = e[1];
michael@0:   return d;
michael@0: }
michael@0: 
michael@0: function set(A) {
michael@0:   var s = [];
michael@0:   for (var e of A)
michael@0:     if (!s.contains(e))
michael@0:       s.push(e);
michael@0:   return s;
michael@0: }
michael@0: 
michael@0: function zip(A, B) {
michael@0:   var z = [];
michael@0:   var n = Math.min(A.length, B.length);
michael@0:   for (var i = 0; i < n; i++)
michael@0:     z.push([A[i], B[i]]);
michael@0:   return z;
michael@0: }
michael@0: 
michael@0: rows = 'ABCDEFGHI';
michael@0: cols = '123456789';
michael@0: digits   = '123456789';
michael@0: squares  = cross(rows, cols);
michael@0: unitlist = [for (c of cols) cross(rows, c)]
michael@0:   .concat([for (r of rows) cross(r, cols)])
michael@0:   .concat([for (rs of ['ABC','DEF','GHI']) for (cs of ['123','456','789']) cross(rs, cs)]);
michael@0: units = dict((for (s of squares)
michael@0:                 [s, [for (u of unitlist) if (u.contains(s)) u]]));
michael@0: 
michael@0: peers = dict((for (s of squares)
michael@0:                 [s, set([for (u of units[s]) for (s2 of u) if (s2 != s) s2])]));
michael@0: 
michael@0: // Given a string of 81 digits (or . or 0 or -), return a dict of {cell:values}.
michael@0: function parse_grid(grid) {
michael@0:   grid = [for (c of grid) if ('0.-123456789'.contains(c)) c];
michael@0:   var values = dict((for (s of squares) [s, digits]));
michael@0: 
michael@0:   for (var pair of zip(squares, grid)) {
michael@0:     var s = pair[0], d = pair[1];
michael@0:     if (digits.contains(d) && !assign(values, s, d))
michael@0:       return false;
michael@0:   }
michael@0:   return values;
michael@0: }
michael@0: 
michael@0: // Eliminate all the other values (except d) from values[s] and propagate.
michael@0: function assign(values, s, d) {
michael@0:   if (all((for (d2 of values[s]) if (d2 != d) eliminate(values, s, d2))))
michael@0:     return values;
michael@0:   return false;
michael@0: }
michael@0: 
michael@0: // Eliminate d from values[s]; propagate when values or places <= 2.
michael@0: function eliminate(values, s, d) {
michael@0:   if (!values[s].contains(d))
michael@0:     return values; // Already eliminated
michael@0:   values[s] = values[s].replace(d, '');
michael@0:   if (values[s].length == 0)
michael@0:     return false;  // Contradiction: removed last value
michael@0:   if (values[s].length == 1) {
michael@0:     // If there is only one value (d2) left in square, remove it from peers
michael@0:     var d2 = values[s][0];
michael@0:     if (!all((for (s2 of peers[s]) eliminate(values, s2, d2))))
michael@0:       return false;
michael@0:   }
michael@0:   // Now check the places where d appears in the units of s
michael@0:   for (var u of units[s]) {
michael@0:     var dplaces = [for (s of u) if (values[s].contains(d)) s];
michael@0:     if (dplaces.length == 0)
michael@0:       return false;
michael@0:     if (dplaces.length == 1)
michael@0: 	    // d can only be in one place in unit; assign it there
michael@0:       if (!assign(values, dplaces[0], d))
michael@0:         return false;
michael@0:   }
michael@0:   return values;
michael@0: }
michael@0: 
michael@0: // Used for debugging.
michael@0: function print_board(values) {
michael@0:   var width = 1 + Math.max.apply(Math, [for (s of squares) values[s].length]);
michael@0:   var line = '\n' + ['-'.repeat(width*3)].repeat(3).join('+');
michael@0:   for (var r of rows)
michael@0:     print([for (c of cols)
michael@0:               values[r+c].center(width) + ('36'.contains(c) && '|' || '')]
michael@0:           .join('') + ('CF'.contains(r) && line || ''));
michael@0:   print('\n');
michael@0: }
michael@0: 
michael@0: 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..";
michael@0: 
michael@0: print_board(parse_grid(easy));
michael@0: 
michael@0: // Using depth-first search and constraint propagation, try all possible values.
michael@0: function search(values) {
michael@0:   if (!values)
michael@0:     return false;    // Failed earlier
michael@0:   if (all((for (s of squares) values[s].length == 1)))
michael@0:     return values;   // Solved!
michael@0: 
michael@0:   // Choose the unfilled square s with the fewest possibilities
michael@0:   // XXX Math.min etc. should work with generator expressions and other iterators
michael@0:   // XXX Math.min etc. should work on arrays (lists or tuples in Python) as well as numbers
michael@0:   var a = [for (s of squares) if (values[s].length > 1) values[s].length + s].sort();
michael@0:   var s = a[0].slice(-2);
michael@0: 
michael@0:   return some((for (d of values[s]) search(assign(copy(values), s, d))));
michael@0: }
michael@0: 
michael@0: hard = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......';
michael@0: 
michael@0: print_board(search(parse_grid(hard)))
michael@0: 
michael@0: if (typeof reportCompare === "function")
michael@0:   reportCompare(true, true);