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

from PyCompat import *

import sys

import copy

import time

#

# 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

		if value not in self.domain:

			return False

		else:

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

			return True

	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, printing_enabled=True):

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

		self.printing_enabled = printing_enabled

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

		return self.__state.__iter__

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

			if e.remove_value (value):

				self.print_domain_changed (e, value)

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

			if e.remove_value (value):

				self.print_domain_changed (e, value)

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

			if e.remove_value (value):

				self.print_domain_changed (e, 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 print_domain_changed (self, value, removed_val):

		if not self.printing_enabled:

			return

		for i in xrange(9):

			for j in xrange(9):

				if self[i,j] is value:

					print 'removed %d from (%d, %d) -> %s' % \

						(removed_val, i, j, value.domain)

	def print_generic (self, s):

		if not self.printing_enabled:

			return

		print s

def solve (puzzle):

	# Print the puzzle we're trying to solve

	puzzle.print_generic ('\nTrying to solve:')

	puzzle.print_generic ('%s\n' % str(puzzle))

	changed = True

	# The main Arc Consistency Algorithm implementation

	while changed:

		changed = False

		for i in xrange(9):

			for j in xrange(9):

				e = puzzle[i,j]

				if e.is_singleton () and e.used == False:

					puzzle.prune (i, j, e.get_value ())

					e.used = True

					changed = True

					# Check if we failed during the last pruning pass

					if puzzle.puzzle_is_failed ():

						puzzle.print_generic ('Puzzle failed, null entry created!')

						return False

	# Check if we're finished with the puzzle

	if puzzle.puzzle_is_solved ():

		puzzle.print_generic ('Puzzle finished! wheee!')

		return puzzle

	### Find the smallest node in the puzzle. The smallest node

	### is the best cantidate to split.

	size = sys.maxint

	smallest_rc = (10, 10)

	for i in xrange(9):

		for j in xrange(9):

			e = puzzle[i,j]

			if not e.is_singleton ():

				if e.get_len () < size:

					size = e.get_len ()

					smallest_rc = (i, j)

	### SPLIT TIME!

	(r, c) = smallest_rc

	spl = puzzle[r,c].get_len ()

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

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

	# Split Message

	puzzle.print_generic ('splitting at %s (size=%d) -> %s and %s' % \

			(smallest_rc, size, lhalf, rhalf))

	# Solve the "left" half

	lcopy = copy.deepcopy (puzzle)

	lcopy[r,c] = SudokuDomain (lhalf)

	leftsolve = solve(lcopy)

	# If it solved correctly, then return it back up

	if leftsolve:

		return leftsolve

	# Solve the "right" half

	rcopy = copy.deepcopy (puzzle)

	rcopy[r,c] = SudokuDomain (rhalf)

	rightsolve = solve (rcopy)

	# If it solved correctly, then return it back up

	if rightsolve:

		return rightsolve

	# Both splits at this level failed, time to work our way back up the tree

	puzzle.print_generic ('Both splits at this level failed, back up!')

	return False

def main ():

	s = SudokuPuzzle ()

	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

	tstart = time.time ()

	solution = solve (s)

	tend = time.time ()

	print '\nThe solution is:'

	print str(solution)

	print

	print 'Took %s seconds to solve' % str(tend - tstart)

if __name__ == '__main__':

	main ()