a sudoku solver

sudokusolve.py

from PIL import Image
"""
emptygrid = Image.open("sudokugrid.jpg","r")
frame = 1


numberimages = {str(k):Image.open("{}.jpg".format(k),"r") for k in range(1,10)}

rowlabels = "ABCDEFGHI"
columnlabels = "123456789"
"""
class InvalidSudokuError(Exception):
    pass

def eliminate(sudoku, possibilities, edges):
    if not any(possibilities.values()):
        return False
    
    """If there are cells with only one possibility,
    put value there, and set other possibilities correctly.
    """
    # get only one possibilities
    only_possib = [k for k,v in possibilities.items() if len(v) == 1]

    if not only_possib:
        return False # didnt make any changes

    for edge in only_possib:
        put(sudoku, possibilities, edges, edge, possibilities[edge][0])

    # Make remaining eliminations
    while eliminate(sudoku, possibilities, edges):
        pass

    return True # We made some changes


def neighborsof(edge, edges):
    for v1, v2 in edges:
        if v1 == edge:
            yield v2
        elif v2 == edge:
            yield v1
    raise StopIteration

def put(sudoku, possibilities, edges, edge, value):
    global frame
    if value not in possibilities[edge]:
        raise InvalidSudokuError
    assert sudoku[edge] == "0"

    sudoku[edge] = value
    possibilities[edge] = []

    for n in neighborsof(edge, edges):
        try:
            possibilities[n].remove(value)
            if sudoku[n] == "0" and not possibilities[n]:
                # If we put this new value, we get an invalid sudoku
                raise InvalidSudokuError

        except ValueError:
            pass
"""
    row = edge[0]
    col = edge[1]
    rowoffset = "ABCDEFGHI".index(row)
    coloffset = "123456789".index(col)
    imageoffsets = (coloffset * 50 + 2, rowoffset * 50 + 2)
    emptygrid.paste(numberimages[value], imageoffsets)
    emptygrid.save("images/{}.png".format(frame))

    frame += 1"""

def parsesudoku(string,rowlabels, columnlabels):
    sudoku = {}
    for row, rowstring in zip(rowlabels, string.split("\n")):
        for column, value in zip(columnlabels, rowstring.split(" ")):
            sudoku["{}{}".format(row,column)] = value
    return sudoku

def checkrows(sudoku, possibilities, rowlabels, columnlabels, edges, empty, allpossibilities):
    if not any(possibilities):
        return False

    change = False
    for row in rowlabels:
        # Try to find what labels are missing from this row
        remaining = allpossibilities[:]
        for col in columnlabels:
            if sudoku[row+col] != empty:
                assert sudoku[row+col] in remaining
                remaining.remove(sudoku[row+col])

        # Foreach remaining possibility, find places it can be put
        remainingpossibs = {k:[] for k in remaining}
        for col in columnlabels:
            for possib in remainingpossibs.keys():
                if possib in possibilities[row+col]:
                    remainingpossibs[possib].append(col)

        # For each remaining possibility, if there is only one
        # place it can be put, put it there

        for k, v in remainingpossibs.items():
            if not v:
                raise InvalidSudokuError
            if len(v) == 1:
                put(sudoku, possibilities, edges, row+v[0], k)
                change = True
    
    return change

def checkcolumns(sudoku, possibilities, rowlabels, columnlabels, edges, empty, allpossibilities):
    if not any(possibilities.values()):
        return False
    change = False
    for col in columnlabels:
        # Try to find what labels are missing from this row
        remaining = allpossibilities[:]
        for row in rowlabels:
            if sudoku[row+col] != empty:
                assert sudoku[row+col] in remaining
                remaining.remove(sudoku[row+col])

        # Foreach remaining possibility, find places it can be put
        remainingpossibs = {k:[] for k in remaining}
        for row in rowlabels:
            for possib in remainingpossibs.keys():
                if possib in possibilities[row+col]:
                    remainingpossibs[possib].append(row)

        # For each remaining possibility, if there is only one
        # place it can be put, put it there

        for k, v in remainingpossibs.items():
            if not v:
                raise InvalidSudokuError
            if len(v) == 1:
                put(sudoku, possibilities, edges, v[0]+col, k)
                change = True
    
    return change

def checkrowsandcolumns(sudoku, possibilities, rowlabels, columnlabels, edges, empty, allpossibilities):

    if not any(possibilities.values()):
        return False
    
    rows = lambda: checkrows(sudoku, possibilities, rowlabels, columnlabels, edges, empty, allpossibilities)
    columns = lambda: checkcolumns(sudoku, possibilities, rowlabels, columnlabels, edges, empty, allpossibilities)

    change = False
    while rows() or columns():
        # to prevent short circuit of "or"
        change = True
    return change
        
    

def checkgrids(sudoku, possibilities, rowlabels, columnlabels, gridsize, edges, empty, allpossibilities):
    if not any(possibilities.values()):
        return False
    
    change = False
    for rowgroup in (rowlabels[i:i+gridsize] for i in range(0, len(rowlabels), gridsize)):
        for colgroup in (columnlabels[i:i+gridsize] for i in range(0, len(columnlabels), gridsize)):
            remaining = allpossibilities[:]
            # Try to find what labels are missing from this grid
            for row in rowgroup:
                for col in colgroup:
                    if sudoku[row+col] != empty:
                        assert sudoku[row+col] in remaining
                        remaining.remove(sudoku[row+col])

            # Foreach remaining possibility, find places it can be put
            remainingpossibs = {k:[] for k in remaining}
            for row in rowgroup:
                for col in colgroup:
                    for possib in remainingpossibs.keys():
                        if possib in possibilities[row+col]:
                            remainingpossibs[possib].append(row+col)

            # For each remaining possibility, if there is only one
            # place it can be put, put it there

            for k, v in remainingpossibs.items():
                assert len(v) > 0
                if len(v) == 1:
                    put(sudoku, possibilities, edges, v[0], k)
                    change = True

    return change

def findpossibilities(sudoku,edges, allpossibilities):

    possibilities = {k:allpossibilities[:] for k in sudoku.keys()}

    for k, v in sudoku.items():
        if v != '0':
            possibilities[k] = []

    for v1, v2 in edges:
        if sudoku[v1] != "0":
            try:
                possibilities[v2].remove(sudoku[v1])
            except ValueError:
                pass
        if sudoku[v2] != "0":
            try:
                possibilities[v1].remove(sudoku[v2])
            except ValueError:
                pass

    return possibilities

def printsudoku(sudoku, rowlabels, columnlabels):
    "Doesn't actually print it, but returns printable string"
    parts = ["   "]
    parts.extend([" {} ".format(c) for c in columnlabels])
    parts.append("\n")
    parts.append("-" * 3 * (len(columnlabels) + 1))
    parts.append("\n")
    for row in rowlabels:
        parts.append(" {}|".format(row))
        for col in columnlabels:
            parts.append(" {} ".format(sudoku[row+col]))
        parts.append("\n")
    return "".join(parts)

def putdeterministic(sudoku, possibilities, edges, rowlabels, columnlabels, empty, gridsize, labelspace):
    changed = False
    while eliminate(sudoku, possibilities, edges) or checkrowsandcolumns(
        sudoku,
        possibilities,
        rowlabels,
        columnlabels,
        edges,
        empty,
        labelspace) or checkgrids(sudoku, possibs, rowlabels, columnlabels, gridsize, edges, empty, labelspace):
            changed = True

    return changed

def hashsudoku(sudoku):
    return "".join("{}:{};".format(k,v) for k,v in sorted(sudoku.items(), key=lambda x: x[0]))

def groupby(listlike, key):
    groups = []
    currentgroup = [listlike[0]]
    currentvalue = listlike[0]
    for a in listlike[1:]:
        if a == currentvalue:
            currentgroup.append(a)
        else:
            groups.append(currentgroup)
            currentgroup = [a]
            currentvalue = a
    return groups

def getheuristics(sudoku, possibilities, edges, empty, labelspace):

    # Ordering
    # 1) cells with least possibilities
    # // 2) cells with most undecided neighbors
    # 3) Values that are used the most

    cellpossibs = sorted([(k,len(v)) for k,v in possibilities.items()], key=lambda x: x[1])
    # print "cell possibs", cellpossibs
    sortedcells = [k[0] for k in cellpossibs]

    labelusage = {k:0 for k in labelspace}
    # print labelusage
    for v in sudoku.values():
        if v != empty:
            labelusage[v] += 1

    heuristics = []

    for cell in sortedcells:
        sortedpossibs = sorted(possibilities[cell], key=lambda x: labelusage[x], reverse=True)
        heuristics.extend([(cell, num) for num in sortedpossibs])
    # print "heuristics", heuristics
    return heuristics
        

def solve(sudoku, possibilities, edges, rowlabels, columnlabels, empty, gridsize, labelspace, visited = []):

    myhash = hashsudoku(sudoku)
    # print(myhash)
    if myhash in visited:
        return sudoku

    visited.append(myhash)

    putdeterministic(sudoku, possibilities, edges, rowlabels, columnlabels, empty, gridsize, labelspace)

    if not any(possibilities.values()): # possibility space consumed, sudoku is finished
        return sudoku
    
    # print(printsudoku(sudoku, "ABCDEFGHI","123456789"))
    for edge, value in getheuristics(sudoku, possibilities, edges, empty, labelspace):
            # print("Trying to put {} on {}".format(num,k))
            copysudoku = {k:v for k,v in sudoku.items()}
            #print(copysudoku)
            copypossibilities = {k:v[:] for k,v in possibilities.items()}
            #print(copypossibilities)
            #return
            put(copysudoku, copypossibilities, edges, edge, value)
            try:
                solve(copysudoku, copypossibilities, edges, rowlabels, columnlabels, empty, gridsize, labelspace)
            except InvalidSudokuError:
                continue

            if not any(copypossibilities.values()):
                return copysudoku

    return sudoku

if __name__ == "__main__":

    sdk="""2 7 6 1 5 8 9 3 4
8 0 9 0 0 6 0 0 7
0 0 0 0 0 0 6 8 2
1 0 3 4 0 2 0 0 8
0 0 0 0 3 0 0 0 0
9 0 0 5 0 1 4 0 3
5 6 1 0 0 0 0 0 0
7 0 0 6 0 0 5 0 0
0 9 4 0 1 0 0 0 0"""
    sudoku = parsesudoku(sdk, "ABCDEFGHI", "123456789")

    with open("edges") as e:
        edges = [k.strip().split(" ") for k in e.readlines()]
        
    possibs = findpossibilities(sudoku, edges, list("123456789"))
    solved = solve(sudoku, possibs, edges, "ABCDEFGHI", "123456789", "0", 3, list("123456789"))
    print(printsudoku(solved, "ABCDEFGHI","123456789"))