| /* -*- tab-width: 2; indent-tabs-mode: nil; js-indent-level: 2 -*- */ |
| /* This Source Code Form is subject to the terms of the Mozilla Public |
| * License, v. 2.0. If a copy of the MPL was not distributed with this |
| * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ |
| |
| |
| //----------------------------------------------------------------------------- |
| var BUGNUMBER = 380237; |
| var summary = 'Generator expressions - sudoku'; |
| var actual = ''; |
| var expect = ''; |
| |
| |
| //----------------------------------------------------------------------------- |
| test(); |
| //----------------------------------------------------------------------------- |
| |
| function test() |
| { |
| enterFunc ('test'); |
| printBugNumber(BUGNUMBER); |
| printStatus (summary); |
| |
| if (this.version) version(180); |
| |
| // 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 |
| } |
| |
| // Make arrays and strings act more like Python lists by iterating their values, not their keys. |
| Array.prototype.__iterator__ = String.prototype.__iterator__ = function () { |
| for (let i = 0; i < this.length; i++) |
| yield this[i] |
| } |
| |
| // 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 in seq) |
| if (!e) |
| return false |
| return true |
| } |
| |
| function some(seq) { |
| for (let e in seq) |
| if (e) |
| return e |
| return false |
| } |
| |
| function cross(A, B) { |
| return [a+b for (a in A) for (b in B)] |
| } |
| |
| function dict(A) { |
| let d = {} |
| for (let e in 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 in unitlist) if (u.contains(s))]] |
| for (s in squares)) |
| peers = dict([s, set([s2 for (u in units[s]) for (s2 in u) if (s2 != s)])] |
| for (s in 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] in 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('\n') |
| } |
| |
| 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))) |
| |
| delete Object.prototype.copy; |
| |
| reportCompare(expect, actual, summary); |
| |
| exitFunc ('test'); |
| } |