Subversion Repositories programming

#!/usr/bin/env python

__author__    = "Ira W. Snyder (devel@irasnyder.com)"
__copyright__ = "Copyright (c) 2006, Ira W. Snyder (devel@irasnyder.com)"
__license__   = "GNU GPL v2 (or, at your option, any later version)"

import copy
from Stack import Stack

#
# Domain class.
#
# This will hold the domain for each place in the SudokuPuzzle class.
#

class SudokuDomain (object):

        DEFAULT = [1, 2, 3, 4, 5, 6, 7, 8, 9]

        def __init__ (self, domain=None):
                self.domain = self.DEFAULT[:]
                self.used = False

                if domain:
                        self.domain = domain

        def __repr__ (self):
                if len(self.domain) == 0:
                        return 'E'
                elif len(self.domain) == 1:
                        return str(self.domain[0])
                else:
                        return ' '

        def remove_value (self, value, strict=False):
                if strict:
                        if value not in self.domain:
                                raise ValueError

                self.domain = [i for i in self.domain if i != value]

        def set_value (self, value):
                self.domain = [value]

        def is_singleton (self):
                if self.get_len() == 1:
                        return True

                return False

        def is_empty (self):
                if self.get_len () == 0:
                        return True

                return False

        def get_len (self):
                return len(self.domain)

        def get_value (self):
                """Only works if this is a singleton"""
                if not self.is_singleton ():
                        raise ValueError

                return self.domain[0]

#
# SudokuPuzzle class.
#
# This will hold all of the current domains for each position in a sudoku
# puzzle, and allow each value to be retrieved by its row,col pair.
# This access can be done by using SudokuPuzzle[0,0] to access the first
# element, and SudokuPuzzle[8,8] to access the last element.
#

class SudokuPuzzle (object):

        def __init__ (self, puzzle=None):
                """Can possibly take an existing puzzle to set the state"""
                self.__state = []

                if puzzle:
                        self.__state = puzzle.__state[:]
                else:
                        for i in xrange(81):
                                self.__state.append (SudokuDomain())

        def __getitem__ (self, key):
                row, col = key
                return self.__state [row*9+col]

        def __setitem__ (self, key, value):
                row, col = key
                self.__state [row*9+col] = value
                return value

        def __repr__ (self):
                s = ''

                for i in xrange (9):
                        if i % 3 == 0:
                                s += '=' * 25
                                s += '\n'

                        for j in xrange (9):
                                if j % 3 == 0:
                                        s += '| '

                                s += '%s ' % str(self[i,j])

                        s += '|\n'

                s += '=' * 25
                return s

        def __iter__ (self):
                for e in self.__state:
                        yield e

        def valid_index (self, index):
                if index < 0 or index > 8:
                        return False

                return True

        def get_row (self, row, col):
                """Return a list that represents the list that $row is a part of.
                This will exclude the element at $row."""
                if not self.valid_index (row) or not self.valid_index (col):
                        raise ValueError # Bad index

                li = []
                for i in xrange(9):
                        if i != col:
                                li.append (self[row,i])

                return li

        def get_col (self, row, col):
                """Return a list that represents the list that $col is a part of.
                This will exclude the element at $col."""
                if not self.valid_index (row) or not self.valid_index (col):
                        raise ValueError # Bad index

                li = []
                for i in xrange(9):
                        if i != row:
                                li.append (self[i,col])

                return li

        def get_upper_left (self, row, col):
                """Return the row and column of the upper left part of the small
                box that contains self[row,col]."""
                new_row = row / 3 * 3
                new_col = col / 3 * 3

                return (new_row, new_col)

        def get_small_square (self, row, col):
                """Return a list that represents the small square that (row, col) is a
                member of. This will exclude the element at (row, col)."""

                (ul_row, ul_col) = self.get_upper_left (row, col)
                li = []

                for i in xrange(ul_row, ul_row+3):
                        for j in xrange(ul_col, ul_col+3):
                                if not (i == row and j == col):
                                        li.append (self[i,j])

                return li

        def prune (self, row, col, value):
                """Remove all occurances of $value from all of the places
                it cannot be in sudoku for the element at (row, col)."""

                for e in self.get_row (row, col):
                        e.remove_value (value)

                for e in self.get_col (row, col):
                        e.remove_value (value)

                for e in self.get_small_square (row, col):
                        e.remove_value (value)

        def puzzle_is_solved (self):
                for i in xrange(9):
                        for j in xrange(9):
                                if not self[i,j].is_singleton ():
                                        return False

                return True

        def puzzle_is_failed (self):
                for i in xrange(9):
                        for j in xrange(9):
                                if self[i,j].is_empty ():
                                        return True

                return False

        def solve (self):
                changed = True

                while changed:
                        changed = False
                        for i in xrange(9):
                                for j in xrange(9):
                                        e = self[i,j]
                                        if e.is_singleton () and e.used == False:
                                                self.prune (i, j, e.get_value ())
                                                e.used = True
                                                changed = True

                if self.puzzle_is_failed ():
                        print 'puzzle failed'
                        return False

                if self.puzzle_is_solved ():
                        return self

                size = 10000
                smallest_rc = (10, 10)

                for i in xrange(9):
                        for j in xrange(9):
                                e = self[i,j]
                                if not e.is_singleton ():
                                        if e.get_len () < size:
                                                size = e.get_len ()
                                                smallest_rc = (i, j)

                print 'splitting at %s (size=%d)' % (smallest_rc, size)

                (r, c) = smallest_rc
                spl = self[r,c].get_len ()

                lhalf = self[r,c].domain[:spl/2]
                rhalf = self[r,c].domain[spl/2:]

                lcopy = copy.deepcopy (self)
                lcopy[r,c] = SudokuDomain (lhalf)
                leftsolve = lcopy.solve ()

                rcopy = copy.deepcopy (self)
                rcopy[r,c] = SudokuDomain (rhalf)
                rightsolve = rcopy.solve ()

                print 'UNABLE TO SOLVE'
                return False



def main ():
        s = SudokuPuzzle ()

        print s

        #e = raw_input ('Enter \'row col val\': ')
        #while e:
        #       r, c, v = [int(i) for i in e.split()]
        #       s[r, c].set_value (v)
        #
        #       e = raw_input ('Enter \'row col val\': ')

        print 'Enter a row at a time. Use \'e\' for empty squares.'
        for i in xrange(9):
                e = raw_input('line %d: ' % i)
                temp = e.split ()

                count = 0
                for j in temp:
                        try:
                                s[i,count].set_value (int(j))
                        except:
                                pass

                        count += 1


        print s

        #print 'r,c: %s' % str((r, c))
        #print 'val: %s' % s[r,c]
        #print 'row: %s' % s.get_row (r, c)
        #print 'col: %s' % s.get_col (r, c)
        #
        #print 'upl: %s' % str(s.get_upper_left (r, c))
        #print 'ssq: %s' % s.get_small_square (r, c)

        print s.solve ()

if __name__ == '__main__':
        main ()