please do not modify this file it is published at https norvig comsudoku html with only minimal changes to work with modern versions of python if you have improvements please make them in a separate file fmt off fmt on 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 values s digits for s in squares for s d in gridvaluesgrid items if d in digits and not assignvalues s d return false fail if we can t assign d to square s return values def gridvaluesgrid convert grid into a dict of square char with 0 or for empties chars c for c in grid if c in digits or c in 0 assert lenchars 81 return dictzipsquares chars def assignvalues s d eliminate d from valuess propagate when values or places 2 return values except return false if a contradiction is detected if d not in valuess return values already eliminated valuess valuess replaced 1 if a square s is reduced to one value d2 then eliminate d2 from the peers if lenvaluess 0 return false contradiction removed last value elif lenvaluess 1 d2 valuess if not alleliminatevalues s2 d2 for s2 in peerss return false 2 if a unit u is reduced to only one place for a value d then put it there for u in unitss dplaces s for s in u if d in valuess if lendplaces 0 return false contradiction no place for this value elif lendplaces 1 d can only be in one place in unit assign it there if not assignvalues dplaces0 d return false return values def displayvalues display these values as a 2d grid width 1 maxlenvaluess for s in squares line join width 3 3 for r in rows print join valuesr c centerwidth if c in 36 else for c in cols if r in cf printline print def solvegrid return searchparsegridgrid def someseq return some element of seq that is true for e in seq if e return e return false def searchvalues using depthfirst search and propagation try all possible values if values is false return false failed earlier if alllenvaluess 1 for s in squares return values solved chose the unfilled square s with the fewest possibilities n s minlenvaluess s for s in squares if lenvaluess 1 return somesearchassignvalues copy s d for d in valuess def solveallgrids name showif0 0 display puzzles that take long enough 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 s digits for s in squares for s in shuffledsquares if not assignvalues s random choicevaluess break ds valuess for s in squares if lenvaluess 1 if lends assignments and lensetds 8 return joinvaluess if lenvaluess 1 else for s in squares return randompuzzleassignments give up and make a new puzzle def shuffledseq return a randomly shuffled copy of the input sequence seq listseq random shuffleseq return seq 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 solveallfromfileeasy50 txt easy none solveallfromfiletop95 txt hard none solveallfromfilehardest txt hardest none solveallrandompuzzle for in range99 random 100 0 for puzzle in grid1 grid2 hard1 takes 22 sec to solve on my m1 mac displayparsegridpuzzle start time monotonic solvepuzzle t time monotonic start printsolved 5f sec t fmt off fmt on 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 fail if we can t assign d to square s eliminate all the other values except d from values s and propagate return values except return false if a contradiction is detected eliminate d from values s propagate when values or places 2 return values except return false if a contradiction is detected already eliminated 1 if a square s is reduced to one value d2 then eliminate d2 from the peers contradiction removed last value 2 if a unit u is reduced to only one place for a value d then put it there contradiction no place for this value d can only be in one place in unit assign it there failed earlier solved chose the unfilled square s with the fewest possibilities 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 display puzzles that take long enough noqa sim115 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 give up and make a new puzzle solve_all from_file easy50 txt easy none solve_all from_file top95 txt hard none solve_all from_file hardest txt hardest none hard1 takes 22 sec to solve on my m1 mac
import random
import time


def cross(items_a, items_b):
    "Cross product of elements in A and elements in B."
    return [a + b for a in items_a for b in items_b]


digits = "123456789"
rows = "ABCDEFGHI"
cols = digits
squares = cross(rows, cols)
unitlist = (
    [cross(rows, c) for c in cols]
    + [cross(r, cols) for r in rows]
    + [cross(rs, cs) for rs in ("ABC", "DEF", "GHI") for cs in ("123", "456", "789")]
)
units = {s: [u for u in unitlist if s in u] for s in squares}
peers = {s: set(sum(units[s], [])) - {s} for s in squares}


def test():
    "A set of unit tests."
    assert len(squares) == 81
    assert len(unitlist) == 27
    assert all(len(units[s]) == 3 for s in squares)
    assert all(len(peers[s]) == 20 for s in squares)
    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"
    }
    
    print("All tests pass.")


def parse_grid(grid):
    
    
    values = {s: digits for s in squares}
    for s, d in grid_values(grid).items():
        if d in digits and not assign(values, s, d):
            return False  
    return values


def grid_values(grid):
    "Convert grid into a dict of {square: char} with '0' or '.' for empties."
    chars = [c for c in grid if c in digits or c in "0."]
    assert len(chars) == 81
    return dict(zip(squares, chars))


def assign(values, s, d):
    
    other_values = values[s].replace(d, "")
    if all(eliminate(values, s, d2) for d2 in other_values):
        return values
    else:
        return False


def eliminate(values, s, d):
    
    if d not in values[s]:
        return values  
    values[s] = values[s].replace(d, "")
    
    if len(values[s]) == 0:
        return False  
    elif len(values[s]) == 1:
        d2 = values[s]
        if not all(eliminate(values, s2, d2) for s2 in peers[s]):
            return False
    
    for u in units[s]:
        dplaces = [s for s in u if d in values[s]]
        if len(dplaces) == 0:
            return False  
        elif len(dplaces) == 1:
            
            if not assign(values, dplaces[0], d):
                return False
    return values


def display(values):
    "Display these values as a 2-D grid."
    width = 1 + max(len(values[s]) for s in squares)
    line = "+".join(["-" * (width * 3)] * 3)
    for r in rows:
        print(
            "".join(
                values[r + c].center(width) + ("|" if c in "36" else "") for c in cols
            )
        )
        if r in "CF":
            print(line)
    print()


def solve(grid):
    return search(parse_grid(grid))


def some(seq):
    "Return some element of seq that is true."
    for e in seq:
        if e:
            return e
    return False


def search(values):
    "Using depth-first search and propagation, try all possible values."
    if values is False:
        return False  
    if all(len(values[s]) == 1 for s in squares):
        return values  
    
    n, s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
    return some(search(assign(values.copy(), s, d)) for d in values[s])


def solve_all(grids, name="", showif=0.0):
    

    def time_solve(grid):
        start = time.monotonic()
        values = solve(grid)
        t = time.monotonic() - start
        
        if showif is not None and t > showif:
            display(grid_values(grid))
            if values:
                display(values)
            print("(%.5f seconds)\n" % t)
        return (t, solved(values))

    times, results = zip(*[time_solve(grid) for grid in grids])
    if (n := len(grids)) > 1:
        print(
            "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 {values[s] for s in unit} == set(digits)

    return values is not False and all(unitsolved(unit) for unit in unitlist)


def from_file(filename, sep="\n"):
    "Parse a file into a list of strings, separated by sep."
    return open(filename).read().strip().split(sep)  


def random_puzzle(assignments=17):
    
    values = {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) >= assignments and len(set(ds)) >= 8:
            return "".join(values[s] if len(values[s]) == 1 else "." for s in squares)
    return random_puzzle(assignments)  


def shuffled(seq):
    "Return a randomly shuffled copy of the input sequence."
    seq = list(seq)
    random.shuffle(seq)
    return seq


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([random_puzzle() for _ in range(99)], "random", 100.0)
    for puzzle in (grid1, grid2):  
        display(parse_grid(puzzle))
        start = time.monotonic()
        solve(puzzle)
        t = time.monotonic() - start
        print("Solved: %.5f sec" % t)