The purpose of this code is to solve the following problem: Make a sudoku puzzle whose clues are the first 9 digits of pi in the same order.

.gitignore

**/__pycache__

pi_sudoku.doctest

>>> import pi_sudoku


# ++ _SelectionGenerator

>>> generator = pi_sudoku._SelectionGenerator(4, 2)
>>> list(generator.current_indices)
[0, 1]
>>> generator.advance()
>>> list(generator.current_indices)
[0, 2]
>>> generator.advance(0)
>>> list(generator.current_indices)
[1, 2]
>>> generator.advance(1)
>>> list(generator.current_indices)
[1, 3]
>>> generator.advance()
>>> list(generator.current_indices)
[2, 3]


# ++ generate_prospective_puzzles

# Super simple case, but now, we begin combinatorial explosion.
>>> prospectives = list(pi_sudoku.generate_prospective_puzzles([1]))
>>> len(prospectives)
81
>>> def expected_one():
...     for i in range(9):
...             for j in range(9):
...                     result = [[None] * 9 for _ in range(9)]
...                     result[i][j] = 1
...                     yield result
...
>>> len(list(expected_one()))
81
>>> all(actual == expected for actual, expected in zip(prospectives, expected_one()))
True

# Let's define couple of simple helpers.
>>> def flatten(in_list):
...     out_list = []
...     for e in in_list:
...             if isinstance(e, list):
...                     out_list.extend(flatten(e))
...             else:
...                     out_list.append(e)
...     return out_list
...
>>> flatten([1,2,[3,[4], 5], 6, [7]])
[1, 2, 3, 4, 5, 6, 7]

>>> def fact(start, stop=1):
...     current = start
...     result = 1
...     while current >= stop:
...           result *= current
...           current -= 1
...     return result
...
>>> fact(1) == 1
True
>>> fact(5) == 5 * 4 * 3 * 2
True
>>> fact(7, 4) == 7 * 6 * 5 * 4
True

# Onto more interesting cases that look more like typical thing we
# might run into.
>>> clues = [5, 7]
>>> total = 0
>>> for p in pi_sudoku.generate_prospective_puzzles(clues):
...     assert len(p) == 9, 'wrong number of rows: %r' % (p,)
...     assert all(len(row) == 9 for row in p), 'wrong number of columns: %r' % (p,)
...     assert list(filter(None, flatten(p))) == clues, 'wrong clue sequence: %r' % (p,)
...     total += 1
...
>>> fact(81, 81 - len(clues) + 1) / fact(len(clues)) == total
True


# ++ _volates_uniqueness_requirement
# TODO


# ++ solve
>>> example1 = [
... [1, None, None, 3, 6, None, 8, None, None],
... [6, None, 9, None, None, 5, 4, None, None],
... [None, 7, None, None, 9, None, 6, None, None],
... [None, None, None, 7, None, None, 5, 8, None],
... [4, 2, None, 8, None, 6, None, 9, 1],
... [None, 1, 5, None, None, 3, None, None, None],
... [None, None, 3, None, 1, None, None, 6, None],
... [None, None, 2, 5, None, None, 1, None, 4],
... [None, None, 1, None, 7, 2, None, None, 8]]
>>> solution = pi_sudoku.solve(example1)
>>> solution
[[1, 5, 4, 3, 6, 7, 8, 2, 9], [6, 3, 9, 2, 8, 5, 4, 1, 7], [2, 7, 8, 1, 9, 4, 6, 5, 3], [3, 9, 6, 7, 4, 1, 5, 8, 2], [4, 2, 7, 8, 5, 6, 3, 9, 1], [8, 1, 5, 9, 2, 3, 7, 4, 6], [7, 8, 3, 4, 1, 9, 2, 6, 5], [9, 6, 2, 5, 3, 8, 1, 7, 4], [5, 4, 1, 6, 7, 2, 9, 3, 8]]
>>> len(solution)
9
>>> all(len(r) == 9 for r in solution)
True
>>> pi_sudoku._violates_uniqueness_requirement(solution)
False

# matches example
>>> for r1, r2 in zip(solution, example1):
...     for e1, e2 in zip(r1, r2):
...         if e2 is None:
...             continue
...         assert e1 == e2, (
...             'Solution does not match clues: %r' % solution)
...

pi_sudoku.py

import sys
import time


class Unsatisfiable(Exception): pass


def _violates_uniqueness_requirement(puzzle):
    def _region_violates_uniqueness_requirement(region):
        """Returns True if there are two entries with the same value.

        Args:
          region: An iterable that generates coordinates, that is,
            (row, column) pairs where uniqueness is to be checked.
        """
        seen = set()
        for i, j in region:
            e = puzzle[i][j]
            if e is None:
                continue
            if e in seen:
                return True
            seen.add(e)
        return False

    # Inspect rows.
    for i in range(9):
        if _region_violates_uniqueness_requirement(
                (i, j) for j in range(9)):
            return True

    # Inspect columns.
    for j in range(9):
        if _region_violates_uniqueness_requirement(
                (i, j) for i in range(9)):
            return True

    # Inspect blocks.
    for i in range(0, 9, 3):
        for j in range(0, 9, 3):
            if _region_violates_uniqueness_requirement(
                    (i + di, j + dj)
                    for di in range(3) for dj in range(3)):
                return True

    # All regions inspected with no violations found. Ergo, report
    # that there are no violations.
    return False


# TODO: Prioritize guessing where only one posibility remains. This
# would probably involve adding a return value to push_guess, since
# making a guess can have the knock on effect of bringing some other
# location down to one uneliminated guess.
class _Solver:
    """Book keeping device for the solve function."""

    class OverConstrained(Exception): pass

    class Region:

        def __init__(self, coordinates_list):
            # Not used yet, but  could be used by callers to check
            # the sanity of method calls.
            self._coordinates_list = list(coordinates_list)
            # Clues and guesses that already/currently exist.
            self._eliminated = set()

        @property
        def eliminated_guesses(self):
            return iter(self._eliminated)

        def eliminate(self, n):
            if n in self._eliminated:
                raise ValueError(
                    'Unable to eliminate because of clue or previous '
                    'guess in the same region.', n)
            self._eliminated.add(n)

        def uneliminate(self, n):
            self._eliminated.remove(n)

    def __init__(self, clues):
        self._rows = [_Solver.Region((i, j) for j in range(9))
                      for i in range(9)]
        self._columns = [_Solver.Region((i, j) for i in range(9))
                         for j in range(9)]

        self._blocks = []
        for i in range(0, 9, 3):
            row = []
            for j in range(0, 9, 3):
                row.append(_Solver.Region(
                    (i + di, j + dj)
                    for di in range(3) for dj in range(3)))
            self._blocks.append(row)

        self._location_to_guess = {}  # (i, j) -> n
        for i, row in enumerate(clues):
            for j, clue in enumerate(row):
                if clue is None:
                    continue
                self.push_guess(i, j, clue)

    @property
    def clues_and_guesses(self):
        result = [[None] * 9 for i in range(9)]
        for (i, j), guess in self._location_to_guess.items():
            result[i][j] = guess
        return result

    def _regions(self, i, j):
        return [self._rows[i],
                self._columns[j],
                self._blocks[i // 3][j // 3]]

    def has_guess(self, i, j):
        return (i, j) in self._location_to_guess

    def eliminated_guesses(self, i, j):
        result = set()
        for region in self._regions(i, j):
            result.update(region.eliminated_guesses)
        return result

    def push_guess(self, i, j, n):
        """

        Raises:
          ValueError: Some previous guess blocks new guess from being.
          _Solver.OverConstrained: Some region that containing
            coordinates (i, j) has no more about what numbers can
            have.
        """
        if (i, j) in self._location_to_guess:
            raise ValueError(
                'Previous guess was made at the same location.',
                self._guess[i, j], i, j, n)
        if n in self.eliminated_guesses(i, j):
            raise ValueError(
                'Would collide with another clue or previous guess.',
                i, j, n)

        for region in self._regions(i, j):
            region.eliminate(n)

        self._location_to_guess[i, j] = n

    def pop_guess(self, i, j):
        """

        Returns:
          Previously pushed guess. This is useful for the caller to
          sanity check herself, but is not necessary.

        Raises:
          KeyError: No guess has been made at (i, j).
        """
        n = self._location_to_guess[i, j]
        for region in self._regions(i, j):
            region.uneliminate(n)
        del self._location_to_guess[i, j]
        return n


def solve(puzzle):
    class SuperBreak(Exception): pass

    if _violates_uniqueness_requirement(puzzle):
        raise Unsatisfiable
    solver = _Solver(puzzle)

    def _work_on_next_blank(previous_i, previous_j):
        # Scan for next blank.
        start = 9 * previous_i + previous_j + 1
        for k in range(start, 9 * 9):
            next_i, next_j = divmod(k, 9)
            if puzzle[next_i][next_j] is None:
                break
        else:
            result = solver.clues_and_guesses
            # Assert that result is a complete solution. This should
            # be the case, since we have scanned through all the
            # blanks and filled them in with during one of the
            # parent calls.
            for row in result:
                for e in row:
                    assert e is not None, (
                        'solve terminated, but solution is not '
                        'complete: %r'
                        % (result,))
            return result

        uneliminated_guesses = (
            set(range(1, 10)) -
            solver.eliminated_guesses(next_i, next_j))
        for guess in uneliminated_guesses:
            solver.push_guess(next_i, next_j, guess)

            try:
                # Try adding more clues. If successful, then a
                # solution has been found. Yay!
                return _work_on_next_blank(next_i, next_j)
            except Unsatisfiable:
                # Darn. There is something wrong with the guess that
                # we made (i.e. there is no way to solve with the
                # push_guess call that we made a few lines ago) Undo
                # that guess before trying a different value (at the
                # same location).
                popped = solver.pop_guess(next_i, next_j)
                assert popped == guess, (
                    'Popped guess is not the sane as pushed guess: '
                    '%r vs %r' % (popped, guess))
                continue

        # We tried everything we could, but nothing worked out.
        raise Unsatisfiable

    return _work_on_next_blank(0, -1)


class _SelectionGenerator:
    """Generates all subsets of size sample_len in order.

    Helper for generate_prospective_puzzles.

    Suppose you have list(range(population_len)), and you wanted
    all subsets of size sample_len in lexicographic order. This class
    would help you do that. E.g.

      >>> list(_SelectionGenerator(4, 2))
      [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
    """

    def __init__(self, population_len, sample_len):
        if sample_len > population_len:
            raise ValueError(
                'sample_len must not be greater than population_len')
        self._population_len = population_len
        self._sample_len = sample_len

        # Invariant: len(self._current_indices) == self._sample_len.
        # Maybe we should do away with self._sample_len entirely then?
        self._current_indices = list(range(self._sample_len))
        self._started = False

    @property
    def current_indices(self):
        return iter(self._current_indices)

    def advance(self, index=-1):
        i = index
        # Index from the end, not the beginning.
        if i >= 0:
            i -= self._sample_len

        while -i <= self._sample_len:
            index = self._current_indices[i]
            maximum_index = self._population_len + i
            if index == maximum_index:
                i -= 1
                continue

            assert index < maximum_index, (
                'Invalid internal state: %r' % (self.__dict__,))
            index += 1
            self._current_indices[i:] = list(
                range(index, index - i))
            return

        raise StopIteration


def generate_prospective_puzzles(clue_sequence):
    """Does what the name says.

    Each object yielded is a 9 x 9 list of lists (that is a list of
    length 9, each element being a list of length 9). Each element
    is either a number 1 through 9 or None (which indicates blank).

    Furthermore, if this list of lists is flattened, and Nones are
    removed, then (a list equal to) clue_sequence is obtained.

    By "prospective", we mean that there is no guarantee that a
    solution exists.

    Args:
      clue_sequence: A list whose elements are 1 through 9, and
        whose length is < 9 * 9.
    """
    generator = _SelectionGenerator(9 * 9, len(clue_sequence))
    while True:
        prospective = [[None] * 9 for _ in range(9)]
        for n, (clue, flattened_index) in enumerate(zip(
                clue_sequence, generator.current_indices)):
            i, j = divmod(flattened_index, 9)
            prospective[i][j] = clue
            if _violates_uniqueness_requirement(prospective):
                # Do not bother trying to add any more clues, because
                # we already know that it isn't going to work out.
                # Moreover, we can skip ahead (prune), by advancing
                # the nth index in generator, rather than the last
                # index.
                try:
                    generator.advance(n)
                # Allowing this to percolate to the next level in the
                # call stack doesn't seem to be a valid way to end a
                # generator. Not sure why that is, but returning is a
                # well-understood way to achieve that end. Ditto
                # bellow.
                except StopIteration:
                    return
                break
        else:
            yield prospective

            try:
                generator.advance()  # Could raise StopIteration.
            # Ditto above.
            except StopIteration:
                return


def print_puzzle(puzzle):
    for row in puzzle:
        print(' '.join(str(i) if i else '_' for i in row))


def main(argv):
    clue_sequence = list(map(int, argv))
    start = time.time()
    last = start
    try:
        for i, prospective_puzzle in enumerate(
                generate_prospective_puzzles(clue_sequence)):
            # Periodically print progress report.
            now = time.time()
            elapsed_s = now - start
            since_last_report_s = now - last
            if since_last_report_s > 0.2:
                last = now
                print('%d prospective puzzles considered in %0.1f s' % (
                    i, elapsed_s), file=sys.stderr, end='\r')

            try:
                solution = solve(prospective_puzzle)
            except Unsatisfiable:
                continue
            else:
                print('\n', file=sys.stderr)
                print('Success!')
                print_puzzle(prospective_puzzle)
                print('Solution:')
                print_puzzle(solution)
                return
    except KeyboardInterrupt:
        print('\nAborted.', file=sys.stderr)
        sys.exit(2)

    print('Unsatisfiable.', file=sys.stderr)
    sys.exit(1)


if __name__ == '__main__':
    main(sys.argv[1:])