#!/usr/bin/python # # Needs python 2.5 for the Element Tree module. from xml.etree import ElementTree import xml.parsers.expat import math from optparse import OptionParser def parse_cell(cell): """Parse a single Sudoku cell, returning the number it contains or 0 if it is empty. This handles several Sudoku formats automagically: (1) Alphabetic characters are assumed to be ksudoku-style cells, where 'b' represents 1 and later characters are consecutively mapped ('c' = 2, etc). (2) Digits represent themselves. (3) The characters '_' and '.' represent blanks.""" if cell.isdigit(): return ord(cell) - ord('1') + 1 elif cell >= 'a' and cell <= 'z': return ord(cell) - ord('a') elif cell == '_' or cell == '.': return 0 else: raise Exception("Can't parse this file format.") 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 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='conflicts', 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: try: 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.') except xml.parsers.expat.ExpatError: board = file(f).read().strip() board_size = len(board) order = int(round(math.sqrt(board_size))) self.N = int(round(math.sqrt(order))) if order * order <> board_size: raise Exception('The board size of a Sudoku puzzle should be a perfect square.') if self.N * self.N <> order: raise Exception('The order of a Sudoku puzzle should be a perfect square.') for col in range(0, order): col_values = [] for row in range(0, order): cell = board self.board = [] for col in range(0, order): col_values = [] for row in range(0, order): cell = board[col * order + row] col_values.append(parse_cell(cell)) 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()