sudoku.py

# Sudoku! No solving, just getting started.


def init_board(template):
    """Given a template, returns a list of list of sets. The 2D grid
    represents the board, and the sets represent remaining possible
    values for that square.

    Parameters
    ----------
    template : List[List[int]]
        The board template must be a 9x9 grid of ints. The integer
        0 represents an empty box, and 1-9 represents a hardcoded
        answer.
    """
    board = []
    for row in template:
        new_row = []
        for square in row:
            if square == 0:
                # A blank square has all possible numbers 1-9
                new_row.append(set(range(1, 10)))
            else:
                new_row.append({square})  # only one possibility by definition
        board.append(new_row)
    return board


# Functions that deal with squares in the board

def is_solved(square):
    """Have we solved this square yet?

    Parameters
    ----------
    square : Set[int]
        Represents all the possible numbers that could be placed in the
        square. If there is only one possibility, we have the solution.

    Returns
    -------
    bool
        Whether the square has one definite solution.
    """
    return len(square) == 1


def solution(square):
    """Extract the solution of the square.

    Parameters
    ----------
    square : Set[int]
        Represents all the possible numbers that could be placed in the
        square. If there is only one possibility, we have the solution.

    Returns
    -------
    Union[int, None]
        The solution for this square, or None if not yet solved.
    """
    if is_solved(square):
        return min(square)  # best way to get sole element from a set
    else:
        return None


# Accessor functions -- make getting at rows, columns, and boxes equally easy!

def returns_list(generator):
    """Decorator that makes sure generators return a concrete list,
    instead of a one-use-only executable sequence.
    """
    return lambda *args: list(generator(*args))


@returns_list
def get_row(num, board):
    """Return a row from the board.

    Parameters
    ----------
    num : int
        An index from 0-8 (inclusive).

    board : List[List[Set[int]]]
        Representation of the Sudoku board.

    Returns
    -------
    List[Set[int]]
        A length-9 list of squares from the specified row.
    """
    for square in board[num]:
        yield square


@returns_list
def get_column(num, board):
    """Return a column from the board.

    Parameters
    ----------
    num : int
        An index from 0-8 (inclusive).

    board : List[List[Set[int]]]
        Representation of the Sudoku board.

    Returns
    -------
    List[Set[int]]
        A length-9 list of squares from the specified column.
    """
    for row in board:
        yield(row[num])


@returns_list
def get_box(num, board):
    """Return a box from the board as a list.

    Parameters
    ----------
    num : int
        An index from 0-8 (inclusive).

    board : List[List[Set[int]]]
        Representation of the Sudoku board.

    Returns
    -------
    List[Set[int]]
        A length-9 list of squares from the specified box.
    """
    x_start = (num * 3) % 9
    y_start = (num // 3) * 3
    for xx in range(x_start, x_start + 3):
        for yy in range(y_start, y_start + 3):
            yield board[xx][yy]


def unsolved(squares):
    """Given a collection of squares, returns the numbers not yet solved.

    Parameters
    ----------
    squares : List[Set[int]]
        A length-9 list of squares.

    Returns
    -------
    Set[int]
        Set of numbers which don't have a definite solution yet.
    """
    possibles = set(range(1, 10))
    for square in list(squares):
        if is_solved(square):
            try:
                possibles.remove(solution(square))
            except KeyError:
                print("Is this board valid?")
                raise
    return possibles


# Printing

def print_board(board):
    """Display a board nicely for our viewing.

    Parameters
    ----------
    board : List[List[Set[int]]]
        Representation of the Sudoku board.
    """
    for row in board:
        print('+---' * 9, end='+\n')  # header
        for square in row:
            fill = str(solution(square)) if is_solved(square) else " "
            print("| {} ".format(fill), end='')
        print('|')  # cap end of row
    print('+---' * 9, end='+\n\n')  # footer


def print_group(squares, label="Group"):
    """Display a group of squares... row, column, or box.

    Parameters
    ----------
    squares : List[Set[int]]
        A length-9 list of squares.

    label : str
        Printed in front, so you can see what collection of squares this is.
    """
    print("{} unsolved = {}".format(label, unsolved(squares)))
    print('+---' * 9, end='+\n')  # header
    for square in squares:
        fill = str(solution(square)) if is_solved(square) else " "
        print("| {} ".format(fill), end='')
    print('|')  # cap end of row
    print('+---' * 9, end='+\n\n')  # footer


def print_unsolved(board):
    """Display a group of squares... row, column, or box.

    Parameters
    ----------
    squares : List[Set[int]]
        A length-9 list of squares.
    """
    print('Unsolved components:\n')
    for ii in range(9):
        print_group(
            get_row(ii, board),
            "Row {}".format(ii))

    for ii in range(9):
        print_group(
            get_column(ii, board),
            "Col {}".format(ii))

    for ii in range(9):
        print_group(
            get_box(ii, board),
            "Box {}".format(ii))


# Example usage

my_board = init_board([
    [6, 0, 0, 7, 2, 0, 0, 3, 1],
    [0, 3, 5, 1, 6, 9, 8, 0, 0],
    [9, 0, 0, 0, 8, 0, 0, 0, 0],
    [0, 5, 6, 0, 9, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 7, 0],
    [3, 4, 0, 5, 0, 0, 2, 0, 0],
    [0, 0, 8, 6, 0, 3, 7, 5, 0],
    [0, 7, 0, 0, 5, 0, 0, 0, 3],
    [0, 0, 0, 0, 0, 0, 0, 8, 0]])

print_board(my_board)
print_unsolved(my_board)

print_board() example output:

+---+---+---+---+---+---+---+---+---+
| 6 |   |   | 7 | 2 |   |   | 3 | 1 |
+---+---+---+---+---+---+---+---+---+
|   | 3 | 5 | 1 | 6 | 9 | 8 |   |   |
+---+---+---+---+---+---+---+---+---+
| 9 |   |   |   | 8 |   |   |   |   |
+---+---+---+---+---+---+---+---+---+
|   | 5 | 6 |   | 9 |   |   |   |   |
+---+---+---+---+---+---+---+---+---+
|   |   | 1 |   |   |   |   | 7 |   |
+---+---+---+---+---+---+---+---+---+
| 3 | 4 |   | 5 |   |   | 2 |   |   |
+---+---+---+---+---+---+---+---+---+
|   |   | 8 | 6 |   | 3 | 7 | 5 |   |
+---+---+---+---+---+---+---+---+---+
|   | 7 |   |   | 5 |   |   |   | 3 |
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | 8 |   |
+---+---+---+---+---+---+---+---+---+

print_unsolved() example output (partial, the full output is kinda long):

Row 0 unsolved = {4, 5, 8, 9}
+---+---+---+---+---+---+---+---+---+
| 6 |   |   | 7 | 2 |   |   | 3 | 1 |
+---+---+---+---+---+---+---+---+---+

Col 0 unsolved = {1, 2, 4, 5, 7, 8}
+---+---+---+---+---+---+---+---+---+
| 6 |   | 9 |   |   | 3 |   |   |   |
+---+---+---+---+---+---+---+---+---+

Box 0 unsolved = {1, 2, 4, 7, 8}
+---+---+---+---+---+---+---+---+---+
| 6 |   |   |   | 3 | 5 | 9 |   |   |
+---+---+---+---+---+---+---+---+---+