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: //----------------------------------------------------------------------------- michael@0: var BUGNUMBER = 380237; michael@0: var summary = 'Generator expressions - sudoku'; michael@0: var actual = ''; michael@0: var expect = ''; michael@0: michael@0: michael@0: //----------------------------------------------------------------------------- michael@0: test(); michael@0: //----------------------------------------------------------------------------- michael@0: michael@0: function test() michael@0: { michael@0: enterFunc ('test'); michael@0: printBugNumber(BUGNUMBER); michael@0: printStatus (summary); michael@0: michael@0: if (this.version) version(180); michael@0: michael@0: // XXX should be standard (and named clone, after Java?) michael@0: Object.prototype.copy = function () { michael@0: let o = {} michael@0: for (let i in this) michael@0: o[i] = this[i] michael@0: return o michael@0: } michael@0: michael@0: // Make arrays and strings act more like Python lists by iterating their values, not their keys. michael@0: Array.prototype.__iterator__ = String.prototype.__iterator__ = function () { michael@0: for (let i = 0; i < this.length; i++) michael@0: yield this[i] michael@0: } michael@0: michael@0: // Containment testing for arrays and strings that should be coherent with their __iterator__. michael@0: Array.prototype.contains = String.prototype.contains = function (e) { michael@0: return this.indexOf(e) != -1 michael@0: } michael@0: michael@0: Array.prototype.repeat = String.prototype.repeat = function (n) { michael@0: let s = this.constructor() michael@0: for (let 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: let n = this.length michael@0: if (w <= n) michael@0: return this michael@0: let 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: // XXX thought spurred by the next two functions: array extras should default to identity function michael@0: michael@0: function all(seq) { michael@0: for (let e in 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 (let e in 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 [a+b for (a in A) for (b in B)] michael@0: } michael@0: michael@0: function dict(A) { michael@0: let d = {} michael@0: for (let e in A) michael@0: d[e[0]] = e[1] michael@0: return d michael@0: } michael@0: michael@0: function set(A) { michael@0: let s = [] michael@0: for (let e in 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: let z = [] michael@0: let n = Math.min(A.length, B.length) michael@0: for (let 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 = [cross(rows, c) for (c in cols)] michael@0: .concat([cross(r, cols) for (r in rows)]) michael@0: .concat([cross(rs, cs) for (rs in ['ABC','DEF','GHI']) for (cs in ['123','456','789'])]) michael@0: units = dict([s, [u for (u in unitlist) if (u.contains(s))]] michael@0: for (s in squares)) michael@0: peers = dict([s, set([s2 for (u in units[s]) for (s2 in u) if (s2 != s)])] michael@0: for (s in squares)) 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 = [c for (c in grid) if ('0.-123456789'.contains(c))] michael@0: let values = dict([s, digits] for (s in squares)) michael@0: michael@0: for (let [s, d] in zip(squares, grid)) michael@0: if (digits.contains(d) && !assign(values, s, d)) michael@0: return false 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(eliminate(values, s, d2) for (d2 in values[s]) if (d2 != d))) 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: let d2 = values[s][0] michael@0: if (!all(eliminate(values, s2, d2) for (s2 in peers[s]))) michael@0: return false michael@0: } michael@0: // Now check the places where d appears in the units of s michael@0: for (let u in units[s]) { michael@0: let dplaces = [s for (s in u) if (values[s].contains(d))] 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: let width = 1 + Math.max.apply(Math, [values[s].length for (s in squares)]) michael@0: let line = '\n' + ['-'.repeat(width*3)].repeat(3).join('+') michael@0: for (let r in rows) michael@0: print([values[r+c].center(width) + ('36'.contains(c) && '|' || '') michael@0: for (c in cols)].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(values[s].length == 1 for (s in squares))) 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: let a = [values[s].length + s for (s in squares) if (values[s].length > 1)].sort() michael@0: let s = a[0].slice(-2) michael@0: michael@0: return some(search(assign(values.copy(), s, d)) for (d in values[s])) 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: delete Object.prototype.copy; michael@0: michael@0: reportCompare(expect, actual, summary); michael@0: michael@0: exitFunc ('test'); michael@0: }