Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/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()
Add Comment
Please, Sign In to add comment