Subversion Repositories programming

Rev

Rev 406 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 406 Rev 407
Line 35... Line 35...
35 
	def remove_value (self, value, strict=False):
 35 
	def remove_value (self, value, strict=False):
36 
		if strict:
 36 
		if strict:
37 
			if value not in self.domain:
 37 
			if value not in self.domain:
38 
				raise ValueError
 38 
				raise ValueError
39 
 
 39 
 
- 
 
 40 
		if value not in self.domain:
- 
 
 41 
			return False
- 
 
 42 
		else:
40 
		self.domain = [i for i in self.domain if i != value]
 43 
			self.domain = [i for i in self.domain if i != value]
- 
 
 44 
			return True
41 
 
 45 
 
42 
	def set_value (self, value):
 46 
	def set_value (self, value):
43 
		self.domain = [value]
 47 
		self.domain = [value]
44 
 
 48 
 
45 
	def is_singleton (self):
 49 
	def is_singleton (self):
Line 73... Line 77...
73 
# element, and SudokuPuzzle[8,8] to access the last element.
 77 
# element, and SudokuPuzzle[8,8] to access the last element.
74 
#
 78 
#
75 
 
 79 
 
76 
class SudokuPuzzle (object):
 80 
class SudokuPuzzle (object):
77 
 
 81 
 
78 
	def __init__ (self, puzzle=None):
 82 
	def __init__ (self, puzzle=None, printing_enabled=True):
79 
		"""Can possibly take an existing puzzle to set the state"""
 83 
		"""Can possibly take an existing puzzle to set the state"""
80 
		self.__state = []
 84 
		self.__state = []
81 
 
 85 
 
82 
		if puzzle:
 86 
		if puzzle:
83 
			self.__state = puzzle.__state[:]
 87 
			self.__state = puzzle.__state[:]
84 
		else:
 88 
		else:
85 
			for i in xrange(81):
 89 
			for i in xrange(81):
86 
				self.__state.append (SudokuDomain())
 90 
				self.__state.append (SudokuDomain())
87 
 
 91 
 
- 
 
 92 
		self.printing_enabled = printing_enabled
- 
 
 93 
 
88 
	def __getitem__ (self, key):
 94 
	def __getitem__ (self, key):
89 
		row, col = key
 95 
		row, col = key
90 
		return self.__state [row*9+col]
 96 
		return self.__state [row*9+col]
91 
 
 97 
 
92 
	def __setitem__ (self, key, value):
 98 
	def __setitem__ (self, key, value):
Line 174... Line 180...
174 
	def prune (self, row, col, value):
 180 
	def prune (self, row, col, value):
175 
		"""Remove all occurances of $value from all of the places
 181 
		"""Remove all occurances of $value from all of the places
176 
		it cannot be in sudoku for the element at (row, col)."""
 182 
		it cannot be in sudoku for the element at (row, col)."""
177 
 
 183 
 
178 
		for e in self.get_row (row, col):
 184 
		for e in self.get_row (row, col):
179 
			e.remove_value (value)
 185 
			if e.remove_value (value):
- 
 
 186 
				self.print_domain_changed (e, value)
180 
 
 187 
 
181 
		for e in self.get_col (row, col):
 188 
		for e in self.get_col (row, col):
182 
			e.remove_value (value)
 189 
			if e.remove_value (value):
- 
 
 190 
				self.print_domain_changed (e, value)
183 
 
 191 
 
184 
		for e in self.get_small_square (row, col):
 192 
		for e in self.get_small_square (row, col):
185 
			e.remove_value (value)
 193 
			if e.remove_value (value):
- 
 
 194 
				self.print_domain_changed (e, value)
186 
 
 195 
 
187 
	def puzzle_is_solved (self):
 196 
	def puzzle_is_solved (self):
188 
		for i in xrange(9):
 197 
		for i in xrange(9):
189 
			for j in xrange(9):
 198 
			for j in xrange(9):
190 
				if not self[i,j].is_singleton ():
 199 
				if not self[i,j].is_singleton ():
Line 198... Line 207...
198 
				if self[i,j].is_empty ():
 207 
				if self[i,j].is_empty ():
199 
					return True
 208 
					return True
200 
 
 209 
 
201 
		return False
 210 
		return False
202 
 
 211 
 
- 
 
 212 
	def print_domain_changed (self, value, removed_val):
- 
 
 213 
		if not self.printing_enabled:
- 
 
 214 
			return
- 
 
 215 
 
- 
 
 216 
		for i in xrange(9):
- 
 
 217 
			for j in xrange(9):
- 
 
 218 
				if self[i,j] is value:
- 
 
 219 
					print 'removed %d from (%d, %d) -> %s' % \
- 
 
 220 
						(removed_val, i, j, value.domain)
- 
 
 221 
 
- 
 
 222 
	def print_generic (self, s):
- 
 
 223 
		if not self.printing_enabled:
- 
 
 224 
			return
- 
 
 225 
 
- 
 
 226 
		print s
- 
 
 227 
 
- 
 
 228 
 
203 
def solve (puzzle):
 229 
def solve (puzzle):
204 
	changed = True
 230 
	changed = True
205 
 
 231 
 
- 
 
 232 
	# The main Arc Consistency Algorithm implementation
206 
	while changed:
 233 
	while changed:
207 
		changed = False
 234 
		changed = False
208 
		for i in xrange(9):
 235 
		for i in xrange(9):
209 
			for j in xrange(9):
 236 
			for j in xrange(9):
210 
				e = puzzle[i,j]
 237 
				e = puzzle[i,j]
211 
				if e.is_singleton () and e.used == False:
 238 
				if e.is_singleton () and e.used == False:
212 
					puzzle.prune (i, j, e.get_value ())
 239 
					puzzle.prune (i, j, e.get_value ())
213 
					e.used = True
 240 
					e.used = True
214 
					changed = True
 241 
					changed = True
215 
 
 242 
 
- 
 
 243 
					# Check if we failed during the last pruning pass
216 
	if puzzle.puzzle_is_failed ():
 244 
					if puzzle.puzzle_is_failed ():
217 
		print 'puzzle failed'
 245 
						puzzle.print_generic ('Puzzle failed, null entry created!')
218 
		return False
 246 
						return False
219 
 
 247 
 
- 
 
 248 
	# Check if we're finished with the puzzle
220 
	if puzzle.puzzle_is_solved ():
 249 
	if puzzle.puzzle_is_solved ():
- 
 
 250 
		puzzle.print_generic ('Puzzle finished! wheee!')
221 
		return puzzle
 251 
		return puzzle
222 
 
 252 
 
- 
 
 253 
	### Find the smallest node in the puzzle. The smallest node
- 
 
 254 
	### is the best cantidate to split.
223 
	size = sys.maxint
 255 
	size = sys.maxint
224 
	smallest_rc = (10, 10)
 256 
	smallest_rc = (10, 10)
225 
 
 257 
 
226 
	for i in xrange(9):
 258 
	for i in xrange(9):
227 
		for j in xrange(9):
 259 
		for j in xrange(9):
Line 229... Line 261...
229 
			if not e.is_singleton ():
 261 
			if not e.is_singleton ():
230 
				if e.get_len () < size:
 262 
				if e.get_len () < size:
231 
					size = e.get_len ()
 263 
					size = e.get_len ()
232 
					smallest_rc = (i, j)
 264 
					smallest_rc = (i, j)
233 
 
 265 
 
234 
	print 'splitting at %s (size=%d)' % (smallest_rc, size)
 266 
	### SPLIT TIME!
235 
 
 - 
 
236 
	(r, c) = smallest_rc
 267 
	(r, c) = smallest_rc
237 
	spl = puzzle[r,c].get_len ()
 268 
	spl = puzzle[r,c].get_len ()
238 
 
 269 
 
239 
	lhalf = puzzle[r,c].domain[:spl/2]
 270 
	lhalf = puzzle[r,c].domain[:spl/2]
240 
	rhalf = puzzle[r,c].domain[spl/2:]
 271 
	rhalf = puzzle[r,c].domain[spl/2:]
241 
 
 272 
 
- 
 
 273 
	# Split Message
- 
 
 274 
	puzzle.print_generic ('splitting at %s (size=%d) -> %s and %s' % \
- 
 
 275 
			(smallest_rc, size, lhalf, rhalf))
- 
 
 276 
 
- 
 
 277 
	# Solve the "left" half
242 
	lcopy = copy.deepcopy (puzzle)
 278 
	lcopy = copy.deepcopy (puzzle)
243 
	lcopy[r,c] = SudokuDomain (lhalf)
 279 
	lcopy[r,c] = SudokuDomain (lhalf)
244 
	leftsolve = solve(lcopy) #.solve ()
 280 
	leftsolve = solve(lcopy)
245 
 
 281 
 
- 
 
 282 
	# If it solved correctly, then return it back up
246 
	if leftsolve:
 283 
	if leftsolve:
247 
		return leftsolve
 284 
		return leftsolve
248 
 
 285 
 
- 
 
 286 
	# Solve the "right" half
249 
	rcopy = copy.deepcopy (puzzle)
 287 
	rcopy = copy.deepcopy (puzzle)
250 
	rcopy[r,c] = SudokuDomain (rhalf)
 288 
	rcopy[r,c] = SudokuDomain (rhalf)
251 
	rightsolve = solve (rcopy) #.solve ()
 289 
	rightsolve = solve (rcopy)
252 
 
 290 
 
- 
 
 291 
	# If it solved correctly, then return it back up
253 
	if rightsolve:
 292 
	if rightsolve:
254 
		return rightsolve
 293 
		return rightsolve
255 
 
 294 
 
- 
 
 295 
	# Both splits at this level failed, time to work our way back up the tree
256 
	print 'UNABLE TO SOLVE'
 296 
	puzzle.print_generic ('Both splits at this level failed, back up!')
257 
	return False
 297 
	return False
258 
 
 298 
 
259 
 
 299 
 
260 
 
 300 
 
261 
def main ():
 301 
def main ():
Line 276... Line 316...
276 
			count += 1
 316 
			count += 1
277 
 
 317 
 
278 
	print '\nThe puzzle entered was:'
 318 
	print '\nThe puzzle entered was:'
279 
	print s
 319 
	print s
280 
 
 320 
 
- 
 
 321 
	print '\nThe solution is:'
281 
	print solve (s)
 322 
	print solve (s)
282 
 
 323 
 
283 
if __name__ == '__main__':
 324 
if __name__ == '__main__':
284 
	main ()
 325 
	main ()