Super Sudoku

SuperSudoku.js

/*
 * Solve Every Sudoku Puzzle
 *
 * See http://norvig.com/sudoku.html
 *
 * Throughout this program we have:
 *   r is a row,    e.g. 'A'
 *   c is a column, e.g. '3'
 *   s is a square, e.g. 'A3'
 *   d is a digit,  e.g. '9'
 *   u is a unit,   e.g. ['A1','B1','C1','D1','E1','F1','G1','H1','I1']
 *   grid is a grid,e.g. 81 non-blank chars, e.g. starting with '.18...7...
 *   values is a dict of possible values, e.g. {'A1':'12349', 'A2':'8', ...}
 */

function cross(A, B){
    /*
     * Cross product of elements in A and elements in B.
     */
    var AB = [];
    for (var a in A){
        for (var b in B){
            AB.push(a+b);
        }
    }
    return AB;
}

digits   = '123456789'
rows     = 'ABCDEFGHI'
cols     = digits
squares  = cross(rows, cols)
unitlist = [];
    for (var c in cols){
        unitlist.push(cross(rows,c));
    }
    for (var r in rows){
        unitlist.push(cross(r,cols));
    }
    for (var rs in ['ABC','DEF','GHI']){
        for (var cs in ['123','456','789']){
            unitlist.push(cross(rs, cs));
        }
    }
units = [];
    for (var s in squares){
        var units_of_s = [];
        for (var u in unitlist){
            if (s in u){
                units_of_s.push(u);
            }
        }
        units.push([s,units_of_s]);
    }
    units = dict(units);


peers = [];
    for (var s in squares){
        peers.push( [ s,set_minus(units[s],[s]) ] );
    }
    peers = dict(peers);

//############## Unit Tests ################

function test(){
    /*
     * A set of tests that must pass.
     */
    assert(squares.length === 81);
    assert(unitlist.length === 27);
    for (var s in squares){
        assert(units[s].length === 3);
        assert(peers[s].length === 20);
    }
    assert(units['C2'] === [['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'],
                           ['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'],
                           ['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3']]
            );
    assert(peers['C2'] === ['A2', 'B2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2',
                            'C1', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9',
                            'A1', 'A3', 'B1', 'B3']
            );
    console.log('All tests pass.');
}

//############## Parse a Grid ################

function parse_grid(grid){
    /*
     *Convert grid to a dict of possible values, {square: digits}, or
     *return False if a contradiction is detected.
     */
    // To start, every square can be any digit; then assign values from the grid.
    var values = [];
        for (var s in squares){
            values.push([s,digits]);
        }
    for s,d in grid_values(grid).items(){ //aaaaaah
        if ( d in digits && (!assign(values, s, d)) ){
            return false // (Fail if we can't assign d to square s.)
        }
    }
    return values
}

function grid_values(grid){
    /*
     *Convert grid into a dict of {square: char} with '0' or '.' for empties.
     */
    chars = [];
    for (var c in grid){
        if (c in digits || c === '0' || c === '.'){
            chars.push(c);
        }
    }
    assert(chars.length === 81);
    return dict(zip(squares, chars)) //aaaaaaah
}

//############## Constraint Propagation ################

function assign(values, s, d){
    /*
     *Eliminate all the other values (except d) from values[s] and propagate.
     *Return values, except return False if a contradiction is detected.
     */
    var other_values = values[s].replace(d, '')
    var eliminate_other_values = [];
        for (var d2 in other_values){
            eliminate_other_values.push(eliminate(values,s,d2));
        }
    if all(eliminate_other_values){
        return value;
    }
    else {
        return false
    }
}

function eliminate(values, s, d){
    /*
     *Eliminate d from values[s]; propagate when values or places <= 2.
     *Return values, except return False if a contradiction is detected.
     */
    if (!(d in values[s]) ){
        return values // Already eliminated
    }
    values[s] = values[s].replace(d,'')
    // (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
    if (values[s].length === 0){
        return false // Contradiction: removed last value
    }
    else if (values[s].length === 1){
        var d2 = values[s]
        var eliminate_peers = [];
        for (var s2 in peers[s]){
            eliminate_peers.push(eliminate(values, s2, d2))
        }
        if (! all(eliminate_peers)){
            return false;
        }
    }
    // (2) If a unit u is reduced to only one place for a value d, then put it there.
    for (var u in units[s]){
        var dplaces =[];
            for (var s in u){
                if (d in values[s]){
                    dplaces.push(s);
                }
            }
        if (dplaces.length === 0){
            return false // Contradiction: no place for this value
        }
        else 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
}

//############## Display as 2-D grid ################

function display(values){
    /* 
     * Display these values as a 2-D grid.
     */
    var width = 1+max(len(values[s]) for s in squares) //aaaaaaah
    var line = '+'.join(['-'*(width*3)]*3) //aaaaaaah
    for r in rows:
        console.log( ''.join(values[r+c].center(width)+('|' if c in '36' else '') //aaaaaaah
                      for c in cols)
                    )
        if (r in 'CF'){console.log(line);}
    console.log(" ");
}

//############## Search ################

function solve(grid){ return search(parse_grid(grid)) }

function search(values){
    /*
     *Using depth-first search and propagation, try all possible values.
     */
    if values === False:
        return false // Failed earlier
    var values_length_one = [];
        for (var s in squares){
            values[s].length === 1;
        }
    if all(values_length_one){
        return values // Solved!
    }
    // Chose the unfilled square s with the fewest possibilities
    n,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1) //aaaaaaah
    return some(search(assign(values.copy(), s, d)) //aaaaaaah
                for d in values[s])
}

//############## Utilities ################

function some(seq){
    /*
     *Return some element of seq that is true.
     */
    for e in seq{
        if e{return e}
        }
    return False
}

function from_file(filename, sep='\n'):
    /* 
     *Parse a file into a list of strings, separated by sep.
     */
    return file(filename).read().strip().split(sep) //aaaaaaah

function shuffled(seq):
    /*
     *Return a randomly shuffled copy of the input sequence.
     */
    var seq = list(seq) //aaaaaaah
    random.shuffle(seq) //aaaaaaah
    return seq

function dict(items){
    /*
     * Takes a list of lists of length two, and outputs a dictionary of item[0] -> item[1]
     * Note1: if there are multiple item[0]s it will just overwrite.
     * Note2: if there is a problem (i.e. not a list of lists of length two, will break)
     */
     new_dict = {}
     for (var item in items){
        new_dict[item[0]] = item[1];
     }
     return new_dict;
}

function set_minus(A, B=[]){
    /*
     * takes two lists and returns A-B, with no repeat entries
     */
    AB=[]
    for (var a in A){
        if ( (!(a in B)) && (!(a in AB)) ){
            AB.push(a);
        }
    }
    return AB
}

function all(A){
    /*
     * Takes a list of Boolean values and returns true if every element is true, else false
     */
     for (var a in A){
        if (!a){
            return false
        }
     }
     return true
}

//############## System test ################

import time, random

def solve_all(grids, name='', showif=0.0):
    /*
     * Attempt to solve a sequence of grids. Report results.
     * When showif is a number of seconds, display puzzles that take longer.
     * When showif is None, don't display any puzzles.
     */
    def time_solve(grid):
        start = time.clock()
        values = solve(grid)
        t = time.clock()-start
        // Display puzzles that take long enough
        if showif is not None and t > showif:
            display(grid_values(grid))
            if values: display(values)
            console.log('(%.2f seconds)\n' % t)
        return (t, solved(values))
    times, results = zip(*[time_solve(grid) for grid in grids])
    N = grids.length;
    if (N > 1){
        console.log("Solved %d of %d %s puzzles (avg %.2f secs (%d Hz), max %.2f secs)." % (
            sum(results), N, name, sum(times)/N, N/sum(times), max(times)) );
    }

def solved(values):
    /*
     * A puzzle is solved if each unit is a permutation of the digits 1 to 9.
     */
    def unitsolved(unit): return set(values[s] for s in unit) == set(digits)
    return values is not False and all(unitsolved(unit) for unit in unitlist)

def random_puzzle(N=17):
    /*
     * Make a random puzzle with N or more assignments. Restart on contradictions.
     * Note the resulting puzzle is not guaranteed to be solvable, but empirically
     * about 99.8% of them are solvable. Some have multiple solutions.
     */
    values = dict((s, digits) for s in squares)
    for s in shuffled(squares):
        if not assign(values, s, random.choice(values[s])):
            break
        ds = [values[s] for s in squares if len(values[s]) == 1]
        if len(ds) >= N and len(set(ds)) >= 8:
            return ''.join(values[s] if len(values[s])==1 else '.' for s in squares)
    return random_puzzle(N) ## Give up and make a new puzzle

grid1  = '003020600900305001001806400008102900700000008006708200002609500800203009005010300'
grid2  = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
hard1  = '.....6....59.....82....8....45........3........6..3.54...325..6..................'
    
if __name__ == '__main__':
    test()
    solve_all(from_file("easy50.txt", '========'), "easy", None)
    solve_all(from_file("top95.txt"), "hard", None)
    solve_all(from_file("hardest.txt"), "hardest", None)
    solve_all([random_puzzle() for _ in range(99)], "random", 100.0)

// References used:
// http://www.scanraid.com/BasicStrategies.htm
// http://www.sudokudragon.com/sudokustrategy.htm
// http://www.krazydad.com/blog/2005/09/29/an-index-of-sudoku-strategies/
// http://www2.warwick.ac.uk/fac/sci/moac/currentstudents/peter_cock/python/sudoku/