Sudoku

sudoku.py

#!/usr/bin/python3

import sys
import itertools
import time

N = 9
S = 3

def process(f):
    def printBoard(board,level=0):
        for i in range(N):
            row = ' '.join([('_' if x == 0 else str(x)) for x in board[i]])
            print('{}{}'.format('  '*level,row))

    # Find positions on the board that are unfilled.
    def findEmpties(board):
        for i in range(N):
            for j in range(N):
                if board[i][j] is 0:
                    yield (i,j)

    # Compute the set of all valid values that can be placed in the empty position at (r,c).
    def possibleOpenings(board, r, c):
        # Collect the values for every batch that contains this position.
        row = board[r]
        column = [board[i][c] for i in range(N)]
        subsquare = [board[i + (r // S)*S][j + (c // S)*S] for i in range(S) for j in range(S)]

        # Return the complement of the values in those batches.
        return set(range(1,10)).difference(set(row + column + subsquare))
 
    # If any of the empty positions has an unambiguous solution then use that solution.
    def setUniques(board):
        for (r,c) in findEmpties(board):
            # This position has an unambigous move if and only if there is only one possible opening.
            openings = list(possibleOpenings(board, r, c))
            if len(openings) == 1:
                board[r][c] = openings[0]

    # Determine if a (possibly incomplete) board lacks conflicting positions.
    def consistent(board):
        for i in range(N):
            for j in range(N):
                # Temporarily vacate the position in order to find possible openings.
                t = board[i][j]
                board[i][j] = 0
                openings = possibleOpenings(board,i,j)
                board[i][j] = t
                # The board is inconsistent if there are no openings or a filled value is not in the openings (the value is in an associated batch).
                if len(openings) == 0 or (t != 0 and t not in openings):
                    return False
        return True

    # Compile the unfilled positions for every batch on the board. The result is a tuple consisting of an indicator for the
    # batch type, the index of the batch, and the indexes inside the batch of the unfilled positions.
    def findBatchEmpty(board):
        results = []

        # These are the rows. The batch index is just the row index. The intra-batch indexes are the column indexes.
        for r in range(N):
            row = board[r]
            indexes = [i for (i,x) in zip(range(N),row) if x is 0]

            if len(indexes) > 0:
                results += [('row',r,indexes)]

        # These are the columns. The batch index is just the column index. The intra-batch indexes are the row indexes.
        for c in range(N):
            column = [board[r][c] for r in range(N)]
            indexes = [i for (i,x) in zip(range(N),column) if x is 0]

            if len(indexes) > 0:
                results += [('column',c,indexes)]

        # These are the nine subsquares. The subsquares use a row major ordering. The intra-batch indexes are also row major.
        for sr in range(S):
            for sc in range(S):
                subsquare = [board[sr * S + r][sc * S + c] for r in range(S) for c in range(S)]
                indexes = [i for (i,x) in zip(range(N),subsquare) if x is 0]
                if len(indexes) > 0:
                    results += [('subsquare',sr*S+sc,indexes)]

        # Return the results sorted by the number of empty slots.
        return sorted(results,key=lambda x: len(x[2]))


    def solve(board):
        # Reject this board if it is not consistent. There can be no possible solutions.
        if not consistent(board):
            return

        # This is a special case of the permutation visitations. We visit the trivial
        # permutations in one go to avoid unnecessary recursion. This is merely an optimization.
        setUniques(board)

        # Find the unfilled positions and their associated batches.
        batchEmpties = findBatchEmpty(board)

        # Yield and return this board as a solution if there are no empty positions.
        if len(batchEmpties) == 0:
            yield board
            return

        # We want to enumerate the smallest permutation.
        (task,index,indexes) = batchEmpties[0]

        # Get the missing values for the batch. First get the elemnts from the batch.
        if task == 'row':
            batch = board[index]
        elif task == 'column':
            batch = [board[i][index] for i in range(N)]
        elif task == 'subsquare':
            r = index // S
            c = index % S
            batch = [board[i + r*S][j + c*S] for i in range(S) for j in range(S)]
        # Now complement the set of batch elements.
        missing = list(set(range(1,10)).difference(set(batch)))

        # Visit the permutations of the unfilled positions in the batch.
        for pindexes in itertools.permutations(indexes):
            # We want to give the subsequent recursive calls a new board and
            # fill the empty batch positions with permutations of the missing values.
            newboard = [[board[i][j] for j in range(N)] for i in range(N)]

            # Get the board positions of all of the batch elements.
            if task == 'row':
                positions = [(index,i) for i in range(N)]
            elif task == 'column':
                positions = [(i,index )for i in range(N)]
            elif task == 'subsquare':
                r = index // S
                c = index % S
                positions = [(i + r*S, j + c*S) for i in range(S) for j in range(S)]

            # Fill the new board with the permuted missing values.
            for i,j in zip(range(N),pindexes):
                (r,c) = positions[j]
                newboard[r][c] = missing[i]
            yield from solve(newboard)

    # Load the board. Filled values are represented by the digits from 1 to 9. Other characters indicate
    # unfilled positions. Columns are separated by spaces and rows are separated into lines. 
    inboard = []
    for _ in range(N):
        line = f.readline()
        items = map(lambda x: int(x) if x in "123456789" else 0,line.split())
        inboard += [list(items)]

    print('Board:')
    printBoard(inboard)

    if not consistent(inboard):
        print('The board is not consistent!')
        return

    print('\nThese are the only solutions:\n')

    # Start the timer. There is no need to time the parsing and sanity checking. 
    startTime = time.clock()

    for solution in solve(inboard):
        printBoard(solution)
        print('(This solution was found within {} seconds.)\n'.format(time.clock() - startTime))

    print('(The exhaustive search took {} seconds.)\n'.format(time.clock() - startTime))

def main():
    if len(sys.argv) > 1:
        filename = sys.argv[1]
        with open(filename,'r') as f:
           process(f)
    else:
        process(sys.stdin)



if __name__ == "__main__":
    main()


# This is a hard Sudoku puzzle as well as the format for input files.
# http://www.telegraph.co.uk/news/science/science-news/9359579/Worlds-hardest-sudoku-can-you-crack-it.html
"""
8 _ _ _ _ _ _ _ _
_ _ 3 6 _ _ _ _ _
_ 7 _ _ 9 _ 2 _ _
_ 5 _ _ _ 7 _ _ _
_ _ _ _ 4 5 7 _ _
_ _ _ 1 _ _ _ 3 _
_ _ 1 _ _ _ _ 6 8
_ _ 8 5 _ _ _ 1 _
_ 9 _ _ _ _ 4 _ _
"""