backtracking constraint solver applied to sudoku

constraint.ts

//   ___________________________
// _| generic constraint solver |__________________________________________________

type Assignments<V> = {[K: string]: V}
type Constraint<V> = (assignments: Assignments<V>) => boolean
type KProperties<V> = {
    domain: V[]
    constraints: Constraint<V>[]
}
type Problem<V> = {
    map: {[K: string]: KProperties<V>}
    addVariable: (k: string, domain: V[]) => void
    addConstraint: (k: string, constraint: Constraint<V>) => void
    satisfiesConstraints: (k: string, assignments: Assignments<V>) => boolean
}
export const problem = <V>(): Problem<V> =>  {
    const map: {[K: string]: KProperties<V>} = {}
    return {
        map,
        addVariable: (k, domain) => {map[k] = ({domain, constraints: []})},
        addConstraint: (k, constraint) => {map[k].constraints.push(constraint)},
        satisfiesConstraints: (k, assignments) => map[k].constraints.every(
            constraint => constraint(assignments)
        ),
    }
}
const unassigned = <V>(problem: Problem<V>, assignments: Assignments<V>): string[] =>
    Object.keys(problem.map).filter(k => assignments[k] === undefined)
export function* yieldSolutions<V>(problem: Problem<V>): Iterable<Assignments<V>>{
    let q: Assignments<V>[] = [{}]
    while (q.length){
        const assignments = q.pop() as Assignments<V>
        for (const local of next(problem, assignments)){
            if (unassigned(problem, local).length) q.push(local)
            else yield local
        }
    }
}
const next = <V>(problem: Problem<V>, assignments: Assignments<V>): Assignments<V>[] => {
    // pick k with the smallest domain, return all potential assignments
    const len = (k: string) => problem.map[k].domain.length
    const k = unassigned(problem, assignments)
        .sort((a, b) => len(a) < len(b) ? -1 : len(a) > len(b) ? 1 : 0)[0]
    return k === undefined ? [] : problem.map[k].domain
        .map(v => ({...assignments, [k]: v}))
        .filter(local => problem.satisfiesConstraints(k, local))
}

//   _______________________________
// _| application to sudoku problem |______________________________________________

type Coordinate = [number, number]
type Value = number
type Game = Value[][]

const toKey = (coordinate: Coordinate) => `${coordinate[0]}, ${coordinate[1]}`

const allDifferent = (ks: string[], assignments: Assignments<Value>): boolean => {
    const seen: {[V: number]: true} = {}
    const values = ks.map(k => assignments[k]).filter(v => v !== undefined)
    for (const v of values){
        if (seen[v]) return false
        seen[v] = true
    }
    return true
}

const range9 = [...Array(9).keys()]
const range3 = [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]
const rows: Coordinate[][] = range9.map(i => range9.map(j => [i, j]))
const cols: Coordinate[][] = range9.map(j => range9.map(i => [i, j]))
const boxes: Coordinate[][] = range3.map(([k, l]) => range3.map(([i, j]) => [i + k * 3, j + l * 3]))

function* solutions(game: Game): Iterable<Game> {
    const sudoku = problem<Value>()

    for (const i of range9){
        for (const j of range9){
            const domain = game[i][j]
                ? [game[i][j]]
                : [1, 2, 3, 4, 5, 6, 7, 8, 9]
            sudoku.addVariable(toKey([i, j]), domain)
        }
    }
    for (const group of [...rows, ...cols, ...boxes]){
        const ks = group.map(toKey)
        for (const k of ks){
            sudoku.addConstraint(k, assignments => allDifferent(ks, assignments))
        }
    }
    for (const s of yieldSolutions(sudoku)){
        yield range9.map(i => range9.map(j => s[toKey([i, j])]))
    }
}

let game = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]
for (const solution of solutions(game)){
    console.log(solution.map(row => row.join('')).join('\n'))
}