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 ()