1.简介

这是周末挑战之三的解决方案:Python中的Sudoku求解器。它的工作原理是将数独难题转化为精确的掩护问题,然后使用Donald Knuth的“算法X”解决精确的掩护问题。该代码应该是不言自明的(假设您已经阅读并理解了Knuth论文),所以我不会再说太多了。

欢迎所有评论。

2。 precisioncover.py

from collections import Iterator, defaultdict
from random import shuffle

class ExactCover(Iterator):
    """An iterator that yields solutions to an EXACT COVER problem.

    An EXACT COVER problem consists of a set of "choices". Each choice
    satisfies one or more "constraints". Choices and constraints may
    be represented by any hashable Python objects, with the proviso
    that all choices must be distinct, as must all constraints.

    A solution is a list of choices such that each constraint is
    satisfied by exactly one of the choices in the solution.

    The constructor takes three arguments:

    constraints  A map from each choice to an iterable of constraints
                 satisfied by that choice.
    initial      An iterable of choices that must appear in every
                 solution. (Default: no choices.)
    random       Generate solutions in random order? (Default: False.)

    For example:

        >>> next(ExactCover(dict(A = [1, 4, 7],
        ...                      B = [1, 4],
        ...                      C = [4, 5, 7],
        ...                      D = [3, 5, 6],
        ...                      E = [2, 3, 6, 7],
        ...                      F = [2, 7])))
        ['B', 'D', 'F']

    """
    # This implements Donald Knuth's "Algorithm X"
    # http://lanl.arxiv.org/pdf/cs/0011047.pdf

    def __init__(self, constraints, initial=(), random=False):
        self.random = random
        self.constraints = constraints

        # A map from constraint to the set of choices that satisfy
        # that constraint.
        self.choices = defaultdict(set)
        for i in self.constraints:
            for j in self.constraints[i]:
                self.choices[j].add(i)

        # The set of constraints which are currently unsatisfied.
        self.unsatisfied = set(self.choices)

        # The partial solution currently under consideration,
        # implemented as a stack of choices.
        self.solution = []

        # Make all the initial choices.
        try:
            for i in initial:
                self._choose(i)
            self.it = self._solve()
        except KeyError:
            # Initial choices were contradictory, so there are no solutions.
            self.it = iter(())

    def __next__(self):
        return next(self.it)

    next = __next__             # for compatibility with Python 2

    def _solve(self):
        if not self.unsatisfied:
            # No remaining unsatisfied constraints.
            yield list(self.solution)
            return

        # Find the constraint with the fewest remaining choices.
        best = min(self.unsatisfied, key=lambda j:len(self.choices[j]))
        choices = list(self.choices[best])
        if self.random:
            shuffle(choices)

        # Try each choice in turn and recurse.
        for i in choices:
            self._choose(i)
            for solution in self._solve():
                yield solution
            self._unchoose(i)

    def _choose(self, i):
        """Make choice i; mark constraints satisfied; and remove any
        choices that clash with it.

        """
        self.solution.append(i)
        for j in self.constraints[i]:
            self.unsatisfied.remove(j)
            for k in self.choices[j]:
                for l in self.constraints[k]:
                    if l != j:
                        self.choices[l].remove(k)

    def _unchoose(self, i):
        """Unmake choice i; restore constraints and choices."""
        self.solution.pop()
        for j in self.constraints[i]:
            self.unsatisfied.add(j)
            for k in self.choices[j]:
                for l in self.constraints[k]:
                    if l != j:
                        self.choices[l].add(k)


3。 sudoku.py

from collections import Iterator
from copy import deepcopy
from exactcover import ExactCover
from itertools import islice, product
from math import ceil, sqrt
from random import shuffle
from string import ascii_lowercase, ascii_uppercase

DIGITS = '123456789' + ascii_uppercase + ascii_lowercase

def make_grid(n):
    """Return a Sudoku grid of size n x n."""
    return [[-1] * n for _ in range(n)]

def puzzle_to_grid(puzzle):
    """Convert printed representation of a Sudoku puzzle into grid
    representation (a list of lists of numbers, or -1 if unknown).

    """
    puzzle = puzzle.split()
    grid = make_grid(len(puzzle))
    for y, row in enumerate(puzzle):
        for x, d in enumerate(row):
            grid[y][x] = DIGITS.find(d)
    return grid

def grid_to_puzzle(grid):
    """Convert grid representation of a Sudoku puzzle (a list of lists of
    numbers, or -1 if unknown) into printed representation.

    """
    return '\n'.join(''.join('.' if d == -1 else DIGITS[d] for d in row)
                     for row in grid)

class Sudoku(Iterator):
    """An iterator that yields the solutions to a Sudoku problem.

    The constructor takes three arguments:

    puzzle   The puzzle to solve, in the form of a string of n
             words, each word consisting of n characters, either a
             digit or a dot indicating a blank square.
             (Default: the blank puzzle.)
    n        The size of the puzzle. (Default: 9.)
    m        The width of the blocks. (Default: the square root of n,
             rounded up.)
    random   Generate solutions in random order? (Default: False.)

    For example:

        >>> print(next(Sudoku('''...84...9
        ...                      ..1.....5
        ...                      8...2146.
        ...                      7.8....9.
        ...                      .........
        ...                      .5....3.1
        ...                      .2491...7
        ...                      9.....5..
        ...                      3...84...''')))
        632845179
        471369285
        895721463
        748153692
        163492758
        259678341
        524916837
        986237514
        317584926

    """
    def __init__(self, puzzle=None, n=9, m=None, random=False):
        if puzzle:
            puzzle = puzzle.split()
            self.n = n = len(puzzle)
            initial = self._encode_puzzle(puzzle)
        else:
            self.n = n
            initial = ()
        if m is None:
            m = int(ceil(sqrt(n)))
        assert(0 < n <= len(DIGITS))
        assert(n % m == 0)
        def constraints(choice):
            d, x, y = self._decode_choice(choice)
            block = m * (x // m) + y // (n // m)
            return [a + 4 * (b + n * c) for a, b, c in [
                (0, x, y),     # Any digit at x, y.
                (1, d, y),     # Digit d in row y.
                (2, d, x),     # Digit d in column x.
                (3, d, block), # Digit d in block.
            ]]
        self.solver = ExactCover({i: constraints(i) for i in range(n ** 3)},
                                 initial, random)

    def __next__(self):
        return self._decode_solution(next(self.solver))

    next = __next__             # for compatibility with Python 2

    def _encode_choice(self, d, x, y):
        """Encode the placement of d at (x, y) as a choice."""
        n = self.n
        assert(0 <= d < n and 0 <= x < n and 0 <= y < n)
        return d + n * (x + n * y)

    def _decode_choice(self, choice):
        """Decode a choice into a (digit, x, y) tuple."""
        choice, digit = divmod(choice, self.n)
        y, x = divmod(choice, self.n)
        return digit, x, y

    def _encode_puzzle(self, puzzle):
        """Encode a Sudoku puzzle and yield initial choices."""
        for y, row in enumerate(puzzle):
            for x, d in enumerate(row):
                digit = DIGITS.find(d)
                if digit != -1:
                    yield self._encode_choice(digit, x, y)

    def _decode_solution(self, solution):
        """Decode a Sudoku solution and return it as a string."""
        grid = make_grid(self.n)
        for d, x, y in map(self._decode_choice, solution):
            grid[y][x] = d
        return grid_to_puzzle(grid)

class ImpossiblePuzzle(Exception): pass
class AmbiguousPuzzle(Exception): pass

def solve(puzzle, m=None):
    """Solve the Sudoku puzzle and return its unique solution. If the
    puzzle is impossible, raise ImpossiblePuzzle. If the puzzle has
    multiple solutions, raise AmbiguousPuzzle.

    Optional argument m is the width of the blocks (default: the
    square root of n, rounded up).

    For example:

        >>> print(solve('''.6.5..9..
        ...                ..4.....6
        ...                .29..3..8
        ...                ....32..4
        ...                ..61.75..
        ...                1..95....
        ...                6..4..27.
        ...                2.....4..
        ...                ..7..6.8.'''))
        768514923
        314829756
        529763148
        975632814
        836147592
        142958637
        693481275
        281375469
        457296381
        >>> print(solve('''...8.....
        ...                ..1.....5
        ...                8....1...
        ...                7.8....9.
        ...                ...1.....
        ...                .5....3.1
        ...                ....1...7
        ...                9.....5..
        ...                3........'''))
        ... # doctest: +IGNORE_EXCEPTION_DETAIL
        Traceback (most recent call last):
          ...
        ImpossiblePuzzle: no solutions

    """
    solutions = list(islice(Sudoku(puzzle, m=m), 2))
    if len(solutions) == 1:
        return solutions[0]
    elif len(solutions) == 0:
        raise ImpossiblePuzzle('no solutions')
    else:
        raise AmbiguousPuzzle('two or more solutions')

def make_puzzle(n=9, m=None):
    """Return a random nxn Sudoku puzzle with 180-degree rotational
    symmetry. The puzzle returned is minimal in the sense that no
    symmetric pair of givens can be removed without making the puzzle
    ambiguous.

    The optional arguments are n, the size of the puzzle (default: 9)
    and m, the width of the blocks (default: the square root of n,
    rounded up).

    """
    grid = puzzle_to_grid(next(Sudoku(n=n, m=m, random=True)))
    coords = list(divmod(i, n) for i in range((n ** 2 + 1) // 2))
    shuffle(coords)
    for i, j in coords:
        g = deepcopy(grid)
        g[i][j] = g[n - i - 1][n - j - 1] = -1
        try:
            solve(grid_to_puzzle(g))
            grid = g
        except AmbiguousPuzzle:
            pass
    return grid_to_puzzle(grid)


4。示例

 >>> for puzzle in map(make_puzzle, (4, 6, 9, 12, 16)):
...     print('\n'.join('{}    {}'.format(*a) for a in zip(puzzle.split(), solve(puzzle).split())), '\n')
...3    1243
.4..    3412
..2.    4321
2...    2134 

..2..4    632514
.1.2..    415236
3.4...    354162
...3.5    126345
..1.5.    241653
5..4..    563421 

...3...4.    678325149
1.94.....    139476528
...98.3.7    452981367
.87....34    587612934
..4...7..    214893756
39....81.    396754812
7.5.69...    725169483
.....72.1    863547291
.4...8...    941238675 

6A....7.8...    6ABC42758391
.952C.A...4.    3952C8A17B46
4..1....5...    47819B635C2A
83...1..96..    832471BA96C5
7......921.4    7B658C3921A4
.....6.4.7..    91CA2654B783
..A.3.2.....    B5A7342C1869
C.196......B    C4196A87325B
..38..1...7C    2638591BA47C
...3....6..2    1C73A54869B2
.8...3.2451.    A896B3C24517
...B.7....38    524B1796CA38 

.F3D..A.......87    1F3D95AEC46BG287
.9B.63....5.F...    E9BC63D87G52FA14
.62.....91.AD...    862GB74F91EADC35
457..G.1....9...    457ACG21FD8396BE
.8..5..G..AC....    F8D25E6G13AC497B
..6E.48.D..7.1.G    CB6E3489D5F7A12G
5.14D...G...68..    5314D27AGEB968FC
.A.7.FC.8.4.....    9AG71FCB82465ED3
.....D.5.82.3.C.    GE4FAD95B82137C6
..91...4...G25.F    BD918CE4367G25AF
7.A.G..3.CD.EB..    72A6G1F35CD4EB98
....76..A..E..G.    3C8576B2AF9E14GD
...8....E.3..G62    D4C8F917EA35BG62
...92.3C.....FE.    67592A3C4BGD8FE1
...B.8....CF.35.    21EB48GD69CF735A
AG.......7..CD4.    AGF3EB562718CD49 
 


#1 楼

这不太正确:

def _unchoose(self, i):
    """Unmake choice i; restore constraints and choices."""
    self.solution.pop()


它承诺撤消任意选择i,但实际上弹出self.solution中的最新选择。当您仅使用if来撤消最新选择时,建议删除该参数:

def _unchoose(self):
    """Unmake latest choice; restore constraints and choices."""
    i = self.solution.pop()


实际上,选择不选模式对我来说有点尴尬。我更喜欢函数式编程。让我感到更舒服的另一个想法是创建一个上下文管理器:

@contextlib.contextmanager
def _tentative_choice(self, i):
    self._choose(i)
    yield
    self._unchoose(i)


使用:

    for i in choices:
        with self._tentative_choice(i):
            for solution in self._solve():
                yield solution


另一个小问题是,您在具有实例变量choices的类的方法中使用局部变量self.choices。这可能导致混乱;我会使用其他名称。

评论


\ $ \ begingroup \ $
好评!但是您能解释一下try:...最终:在上下文管理器中的用法吗?如果_solve引发了一个异常,那么一定是发生了非常严重的错误,以至于我不能指望能够继续搜索,因此,您确实不必担心在这种情况下还原上下文吗?
\ $ \ endgroup \ $
–加雷斯·里斯(Gareth Rees)
2013年12月16日14:22

\ $ \ begingroup \ $
@GarethRees你是对的。我本来希望获得一种更具防守性的风格,但现在看不到实际的好处。
\ $ \ endgroup \ $
–珍妮·卡里拉(Janne Karila)
2013年12月16日18:51

#2 楼

我只有一个小意见:

ExactCover.__init__中,我将使用iteritems而不是遍历constraints的键:

for choice, constraintsList in self.constraints.iteritems():
    for constraint in constraintsList:
        self.choices[choice].add(constraint)


编写好的代码,分解成漂亮的小功能,目的明确。干得好!