sudoku.py

# coding=utf-8
"""Sudoku solver using constraint propogation + search"""
from collections import defaultdict
from itertools import chain, product
from pprint import pprint
from typing import List

CELLS = None
UNITS = None
PEERS = None


def build_index_maps():
    """Generate cells, units, and peers.

    Following peter norvig's idea to avoid index math later.

    cells: list of all cell indices
    units: mapping of a cell index to its associated units
    peers: mapping of a cell index to its associated peers

    Returns:
        (cells, units, peers)
    """
    rows = range(9)
    cols = range(9)
    # pnorvig's units + peer idea to avoid index math later.
    celllist = list(product(rows, cols))  # list of all cell indices
    unitlist = []  # list of all units (list of cells representing rows, cols, and subboards)
    for col in cols:
        unitlist.append(list(product(rows, (col,))))
    for row in rows:
        unitlist.append(list(product((row,), cols)))
    for i, j in product(((0, 1, 2), (3, 4, 5), (6, 7, 8)), repeat=2):
        unitlist.append(list(product(i, j)))
    units = defaultdict(list)  # cell -> list of associated units
    for cell in celllist:
        for unit in unitlist:
            if cell in unit:
                units[cell].append(unit)
    peers = {}  # cell -> set of associated cells
    for cell, unit in units.items():
        cells = set(chain.from_iterable(unit))
        cells.remove(cell)  # remove self from set
        peers[cell] = cells
    return celllist, units, peers


def assign(values, cell_idx, val):
    """Assign a value to a cell and eliminate the value from cell's peers"""
    values[cell_idx] = set(val)
    for cell in PEERS[cell_idx]:
        eliminate(values, cell, val)


def eliminate(values, cell_idx, val):
    """Eliminate a potential value form a cell.

    Raises ValueError if the potential value list is empty"""
    if val not in values[cell_idx]:
        return
    values[cell_idx].remove(val)
    if len(values[cell_idx]) == 1:  # if only 1 possible val for this cell, eliminate val from cell's peers
        assign(values, cell_idx, next(iter(values[cell_idx])))
    if not values[cell_idx]:  # if no possible vals, raise exception
        display(values)
        raise ValueError('Invalid sudoku board. No possible value for cell {}'.format(cell_idx))


def solve(board):
    """Solve a sudoku board"""
    global CELLS, UNITS, PEERS
    if not all((CELLS, UNITS, PEERS)):
        CELLS, UNITS, PEERS = build_index_maps()
    values = {cell: set('123456789') for cell in CELLS}  # all cells can be any value
    for cell in CELLS:
        val = board[cell[0]][cell[1]]
        if val is '.':
            continue
        assign(values, cell, val)  # assign value to cell
    # search through values for any solution:
    search(board)
    display(values)
    return values


def search(values):
    if all(len(v) == 1 for v in values.values()):  # board is already solved
        return values
    num, idx = min((len(values[idx]), idx) for idx in CELLS if len(values[idx]) > 1)


def display(values):
    """Display these values as a 2-D grid."""
    board = [[None for _ in range(9)] for _ in range(9)]
    for cell_idx, val in values.items():
        board[cell_idx[0]][cell_idx[1]] = val
    pprint(board)


def is_solvable(board: List[List[str]]) -> bool:
    """Return whether a given sudoku board is solvable

    Args:
        board: 9x9 sudoku board

    Returns:
        True if board is solvable, False otherwise
    """
    try:
        solve(board)
        return True
    except ValueError as e:
        print(e)
        return False


if __name__ == '__main__':
    easy_board = [["5", "3", ".", ".", "7", ".", ".", ".", "."],
                  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
                  [".", "9", "8", ".", ".", ".", ".", "6", "."],
                  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
                  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
                  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
                  [".", "6", ".", ".", ".", ".", "2", "8", "."],
                  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
                  [".", ".", ".", ".", "8", ".", ".", "7", "9"]]
    print(is_solvable(easy_board))
    hard_board = [['4', '.', '.', '.', '.', '.', '8', '.', '5'],
                  ['.', '3', '.', '.', '.', '.', '.', '.', '.'],
                  ['.', '.', '.', '7', '.', '.', '.', '.', '.'],
                  ['.', '2', '.', '.', '.', '.', '.', '6', '.'],
                  ['.', '.', '.', '.', '8', '.', '4', '.', '.'],
                  ['.', '.', '.', '.', '1', '.', '.', '.', '.'],
                  ['.', '.', '.', '6', '.', '3', '.', '7', '.'],
                  ['5', '.', '.', '2', '.', '.', '.', '.', '.'],
                  ['1', '.', '4', '.', '.', '.', '.', '.', '.']]
    print(is_solvable(hard_board))