Skip to content

Instantly share code, notes, and snippets.

@dherman dherman/sudoku.js
Created Nov 29, 2012

Embed
What would you like to do?
Brendan's Sudoku solver done with left-to-right comprehensions
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
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 [for (a of A) for (b of B) a+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 of 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 = [for (c of cols) cross(rows, c)]
.concat([for (r of rows) cross(r, cols)])
.concat([for (rs of ['ABC','DEF','GHI']) for (cs of ['123','456','789']) cross(rs, cs)])
units = dict(for (s of squares)
[s, [for (u of unitlist) if (u.contains(s)) u]] )
peers = dict(for (s of squares)
[s, set([for (u of units[s]) for (s2 of u) if (s2 != s) s2])])
// Given a string of 81 digits (or . or 0 or -), return a dict of {cell:values}.
function parse_grid(grid) {
grid = [for (c of grid) if ('0.-123456789'.contains(c)) c]
let values = dict(for (s of squares) [s, digits])
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(for (d2 of values[3]) if (d2 != d) eliminate(values, s, d2)))
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(for (s2 of peers[s]) eliminate(values, s2, d2)))
return false
}
// Now check the places where d appears in the units of s
for (let u of units[s]) {
let dplaces = [for (s of u) if (values[s].contains(d)) s]
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, [for (s of squares) values[s].length])
let line = '\n' + ['-'.repeat(width*3)].repeat(3).join('+')
for (let r of rows)
print([for (c of cols)
values[r+c].center(width) + ('36'.contains(c) && '|' || '')]
.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(for (s of squares) values[s].length == 1))
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 = [for (s of squares) if (values[s].length > 1) values[s].length + s].sort()
let s = a[0].slice(-2)
return some(for (d of values[s]) search(assign(values.copy(), s, d)))
}
hard = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
print_board(search(parse_grid(hard)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.