Using dpkg to solve Sudoku

debsudoku.py

#!/usr/bin/python
#
# Needs python 2.5 for the Element Tree module.

from xml.etree import ElementTree
import math
from optparse import OptionParser

def pkg_boilerplate(package, version):
    """Generate the repetitive stuff at the front of a Package stanza
that's needed in order to create a real Packages file that apt will
parse (well enough for us to run dependency resolution, anyway)."""
    
    return '''Package: %(package)s
Version: %(version)s
Filename: %(package)s_%(version)s_all.deb
Architecture: all
Maintainer: Nobody <nobody@nowhere.org>
Installed-Size: 16''' % { 'package' : package, 'version' : version }

def main():
    parser = OptionParser(usage = '%prog [OPTIONS] (N | FILE)',
                          epilog='''Build a Debian Packages file corresponding to a Sudoku board.  Given
    N, build a Packages file for an empty, order-N Sudoku board (the board
    size will be N*N); given FILE, build a Packages file for the given
    ksudoku save file.''')

    parser.add_option('-m', '--mode', dest='mode',
                      metavar='MODE', default='depends',
                      help='''Set the program mode.  MODE may be "print" to display the board
    instead of generating a Packages file, "depends" to print a
    Packages file using a Depends-based reduction (default), or
    "conflicts" to print a Packages file using a Conflicts-based
    reduction.''')

    (options, args) = parser.parse_args()

    if len(args) == 0:
        raise Exception('You must provide at least one input file or board size.')

    for f in args:
        try:
            f = int(f)
        except:
            pass
        s = Sudoku(f)
        if options.mode == 'depends':
            print s.deb_render_depends()
        elif options.mode == 'conflicts':
            print s.deb_render_conflicts()
        elif options.mode == 'print':
            print s
        else:
            raise Exception('Unknown program mode "%s"' % args.mode)

class Sudoku:
    '''A class that can represent a sudoku game and convert it into a
collection of Debian package relationships.

The game is represented as a list of N columns, each containing N
cells.  Cells contain a number from 0 to N, inclusive, with 0
representing an empty cell.'''
    
    def __init__(self, f = None):
        '''Load a ksudoku save file into this Sudoku instance.'''
        if isinstance(f, int):
            self.N = f
            self.board = [[0] * self.N * self.N] * self.N * self.N
        else:
            e = ElementTree.ElementTree(None, f)
            for game in e.findall('game'):
                for puzzle in game.findall('puzzle'):
                    graph = puzzle.find('graph')
                    order = int(graph.get('order'))
                    self.N = int(round(math.sqrt(order)))
                    if self.N * self.N <> order:
                        raise Exception('The order of a Sudoku puzzle should be a perfect square.')

                    board = puzzle.findtext('values').strip()
                    if len(board) <> order * order:
                        raise Exception('Wrong board length.')

                    self.board = []
                    for col in range(0, order):
                        col_values = []
                        for row in range(0, order):
                            cell = board[col * order + row]
                            if cell == '_':
                                col_values.append(0)
                            else:
                                col_values.append(ord(cell) - ord('a'))

                        self.board.append(col_values)

    def flatten(self):
        '''Return an iterable that gives the values of this Sudoku
        board as a series of (row, column, value) triples, with row
        and column being zero-based.'''
        for row in range(0, self.N * self.N):
            for col in range(0, self.N * self.N):
                yield(row, col, self.board[col][row])

    def __str__(self):
        """Print a human-readable representation of the board."""

        rval = []
        cell_hrule = ('+' + '-' * self.N) * self.N + '+\n'
        for block_row in range(0, self.N):
            rval.append(cell_hrule)
            for row in range(self.N * block_row, self.N * (block_row + 1)):
                for block_col in range(0, self.N):
                    rval.append('|')
                    for col in range(self.N * block_col, self.N * (block_col + 1)):
                        cell = self.board[col][row]
                        if cell == 0:
                            rval.append(' ')
                        elif cell < 10:
                            rval.append(str(cell))
                        else:
                            rval.append(chr(ord('a') + cell - 10))
                rval.append('|\n')

        rval.append(cell_hrule)
        return ''.join(rval)

    def deb_render_conflicts(self):
        """Generate a Packages file that uses Conflicts as the main
mechanism for describing the Sudoku board.  This version is much more
tractable for package managers than its Depends-based cousin."""
        
        rval = []

        # First, generate the constraints describing the Sudoku board.

        for row in range(1, self.N * self.N + 1):
            block_row = (row - 1) / self.N + 1
            for col in range(1, self.N * self.N + 1):
                block_col = (col - 1) / self.N + 1
                for n in range(1, self.N * self.N + 1):
                    boilerplate = pkg_boilerplate('cell%d.%d-%d' % (row, col, n),
                                                  '1.0-1')
                    rval.append('''%(boilerplate)s
Provides: cell%(row)d.%(col)d, block%(block_row)d.%(block_col)d-%(n)d, row%(row)d-%(n)d, col%(col)d-%(n)d
Conflicts: cell%(row)d.%(col)d, block%(block_row)d.%(block_col)d-%(n)d, row%(row)d-%(n)d, col%(col)d-%(n)d\n\n''' % {
                        'row' : row, 'col' : col, 'n' : n,
                        'block_row' : block_row, 'block_col' : block_col,
                        'boilerplate' : boilerplate } )

        # Now add the package representing a solution.
        rval.append('%s\nDepends: ' % pkg_boilerplate('puzzle', '1.0-1'))
        cells = []
        for row, col, value in self.flatten():
            if value == 0:
                # Unconstrained, but require *something* in this cell.
                cells.append('cell%d.%d' % (row + 1, col + 1))
            else:
                cells.append('cell%d.%d-%d' % (row + 1, col + 1, value))

        rval.append(', '.join(cells))
        rval.append('\n')

        return ''.join(rval)

    def deb_render_depends(self):
        """Generate a Packages file that uses Depends as the main
mechanism for describing the Sudoku board.  This version is much LESS
tractable for package managers than its Conflicts-based cousin."""
        rval = []

        # First, generate the constraints describing the Sudoku board.

        # Each row must contain one instance of each number.
        for row in range(1, self.N * self.N + 1):
            boilerplate = pkg_boilerplate('row%d' % row, '1.0-1')
            rval.append('''%s
Depends: %s\n\n''' % (boilerplate, ', '.join(['row%d-%d' % (row, n) for n in range(1, self.N * self.N + 1)])))
        # Each column must contain one instance of each number.
        for col in range(1, self.N * self.N + 1):
            boilerplate = pkg_boilerplate('col%d' % col, '1.0-1')
            rval.append('''%s
Depends: %s\n\n''' % (boilerplate, ', '.join(['col%d-%d' % (col, n) for n in range(1, self.N * self.N + 1)])))
        # Each block must contain one instance of each number.
        for block_row in range(1, self.N + 1):
            for block_col in range(1, self.N + 1):
                boilerplate = pkg_boilerplate('block%d.%d' % (block_row, block_col),
                                              '1.0-1')
                rval.append('''%s
Depends: %s\n\n''' % (boilerplate, ', '.join(['block%d.%d-%d' % (block_row, block_col, n) for n in range(1, self.N * self.N + 1)])))

        # Each cell must only have a single value.
        for row in range(1, self.N * self.N + 1):
            block_row = (row - 1) / self.N + 1
            for col in range(1, self.N * self.N + 1):
                block_col = (col - 1) / self.N + 1
                for n in range(1, self.N * self.N + 1):
                    boilerplate = pkg_boilerplate('cell%d.%d' % (row, col),
                                                  '%d' % n)
                    rval.append('''%(boilerplate)s
Provides: block%(block_row)d.%(block_col)d-%(n)d, row%(row)d-%(n)d, col%(col)d-%(n)d\n\n''' % {
                        'row' : row, 'col' : col, 'n': n,
                        'block_row' : block_row, 'block_col' : block_col,
                        'boilerplate' : boilerplate } )

        boilerplate = pkg_boilerplate('puzzle', '1.0')

        # Generate dependencies that ensure that rows, columns, and
        # blocks are all correct.
        structure_depends = []
        for row in range(1, self.N * self.N + 1):
            structure_depends.append('row%d' % row)
        for col in range(1, self.N * self.N + 1):
            structure_depends.append('col%d' % col)
        for block_row in range(1, self.N + 1):
            for block_col in range(1, self.N + 1):
                structure_depends.append('block%d.%d' % (block_row, block_col))

        # Generate dependencies corresponding to the values in the
        # input problem.
        problem_cell_depends = ['cell%d.%d (= %d)' % (row + 1, col + 1, value)
                                            for row, col, value in self.flatten() if value > 0]
        rval.append('''%s
Depends: %s\n''' % (boilerplate, ', '.join(structure_depends + problem_cell_depends)))

        return ''.join(rval)




main()

Copied from https://web.archive.org/web/20160308091618/http://algebraicthunk.net/~dburrows/blog/entry/attachments/debsudoku.py

Explanation: https://web.archive.org/web/20160326062818/http://algebraicthunk.net/~dburrows/blog/entry/package-management-sudoku/