Subversion Repositories programming

Rev

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

Rev 405 Rev 406
Line 2... Line 2...
2 
 
 2 
 
3 
__author__    = "Ira W. Snyder (devel@irasnyder.com)"
 3 
__author__    = "Ira W. Snyder (devel@irasnyder.com)"
4 
__copyright__ = "Copyright (c) 2006, Ira W. Snyder (devel@irasnyder.com)"
 4 
__copyright__ = "Copyright (c) 2006, Ira W. Snyder (devel@irasnyder.com)"
5 
__license__   = "GNU GPL v2 (or, at your option, any later version)"
 5 
__license__   = "GNU GPL v2 (or, at your option, any later version)"
6 
 
 6 
 
- 
 
 7 
import sys
7 
import copy
 8 
import copy
8 
from Stack import Stack
 - 
 
9 
 
 9 
 
10 
#
 10 
#
11 
# Domain class.
 11 
# Domain class.
12 
#
 12 
#
13 
# This will hold the domain for each place in the SudokuPuzzle class.
 13 
# This will hold the domain for each place in the SudokuPuzzle class.
Line 198... Line 198...
198 
				if self[i,j].is_empty ():
 198 
				if self[i,j].is_empty ():
199 
					return True
 199 
					return True
200 
 
 200 
 
201 
		return False
 201 
		return False
202 
 
 202 
 
203 
	def solve (self):
 203 
def solve (puzzle):
204 
		changed = True
 204 
	changed = True
205 
 
 205 
 
206 
		while changed:
 206 
	while changed:
207 
			changed = False
 207 
		changed = False
208 
			for i in xrange(9):
 208 
		for i in xrange(9):
209 
				for j in xrange(9):
 209 
			for j in xrange(9):
210 
					e = self[i,j]
 210 
				e = puzzle[i,j]
211 
					if e.is_singleton () and e.used == False:
 211 
				if e.is_singleton () and e.used == False:
212 
						self.prune (i, j, e.get_value ())
 212 
					puzzle.prune (i, j, e.get_value ())
213 
						e.used = True
 213 
					e.used = True
214 
						changed = True
 214 
					changed = True
215 
 
 215 
 
216 
		if self.puzzle_is_failed ():
 216 
	if puzzle.puzzle_is_failed ():
217 
			print 'puzzle failed'
 217 
		print 'puzzle failed'
218 
			return False
 218 
		return False
219 
 
 219 
 
220 
		if self.puzzle_is_solved ():
 220 
	if puzzle.puzzle_is_solved ():
221 
			return self
 221 
		return puzzle
222 
 
 222 
 
223 
		size = 10000
 223 
	size = sys.maxint
224 
		smallest_rc = (10, 10)
 224 
	smallest_rc = (10, 10)
225 
 
 225 
 
226 
		for i in xrange(9):
 226 
	for i in xrange(9):
227 
			for j in xrange(9):
 227 
		for j in xrange(9):
228 
				e = self[i,j]
 228 
			e = puzzle[i,j]
229 
				if not e.is_singleton ():
 229 
			if not e.is_singleton ():
230 
					if e.get_len () < size:
 230 
				if e.get_len () < size:
231 
						size = e.get_len ()
 231 
					size = e.get_len ()
232 
						smallest_rc = (i, j)
 232 
					smallest_rc = (i, j)
233 
 
 233 
 
234 
		print 'splitting at %s (size=%d)' % (smallest_rc, size)
 234 
	print 'splitting at %s (size=%d)' % (smallest_rc, size)
235 
 
 235 
 
236 
		(r, c) = smallest_rc
 236 
	(r, c) = smallest_rc
237 
		spl = self[r,c].get_len ()
 237 
	spl = puzzle[r,c].get_len ()
238 
 
 238 
 
239 
		lhalf = self[r,c].domain[:spl/2]
 239 
	lhalf = puzzle[r,c].domain[:spl/2]
240 
		rhalf = self[r,c].domain[spl/2:]
 240 
	rhalf = puzzle[r,c].domain[spl/2:]
241 
 
 241 
 
242 
		lcopy = copy.deepcopy (self)
 242 
	lcopy = copy.deepcopy (puzzle)
243 
		lcopy[r,c] = SudokuDomain (lhalf)
 243 
	lcopy[r,c] = SudokuDomain (lhalf)
244 
		leftsolve = lcopy.solve ()
 244 
	leftsolve = solve(lcopy) #.solve ()
245 
 
 245 
 
246 
		rcopy = copy.deepcopy (self)
 246 
	if leftsolve:
247 
		rcopy[r,c] = SudokuDomain (rhalf)
 - 
 
248 
		rightsolve = rcopy.solve ()
 247 
		return leftsolve
249 
 
 248 
 
250 
		print 'UNABLE TO SOLVE'
 249 
	rcopy = copy.deepcopy (puzzle)
251 
		return False
 250 
	rcopy[r,c] = SudokuDomain (rhalf)
- 
 
 251 
	rightsolve = solve (rcopy) #.solve ()
252 
 
 252 
 
- 
 
 253 
	if rightsolve:
- 
 
 254 
		return rightsolve
253 
 
 255 
 
- 
 
 256 
	print 'UNABLE TO SOLVE'
- 
 
 257 
	return False
254 
 
 258 
 
255 
def main ():
 - 
 
256 
	s = SudokuPuzzle ()
 - 
 
257 
 
 259 
 
258 
	print s
 - 
 
259 
 
 260 
 
260 
	#e = raw_input ('Enter \'row col val\': ')
 - 
 
261 
	#while e:
 261 
def main ():
262 
	#	r, c, v = [int(i) for i in e.split()]
 - 
 
263 
	#	s[r, c].set_value (v)
 262 
	s = SudokuPuzzle ()
264 
	#
 - 
 
265 
	#	e = raw_input ('Enter \'row col val\': ')
 - 
 
266 
 
 263 
 
267 
	print 'Enter a row at a time. Use \'e\' for empty squares.'
 264 
	print 'Enter a row at a time. Use \'e\' for empty squares.'
268 
	for i in xrange(9):
 265 
	for i in xrange(9):
269 
		e = raw_input('line %d: ' % i)
 266 
		e = raw_input('line %d: ' % i)
270 
		temp = e.split ()
 267 
		temp = e.split ()
Line 276... Line 273...
276 
			except:
 273 
			except:
277 
				pass
 274 
				pass
278 
 
 275 
 
279 
			count += 1
 276 
			count += 1
280 
 
 277 
 
281 
 
 - 
 
- 
 
 278 
	print '\nThe puzzle entered was:'
282 
	print s
 279 
	print s
283 
 
 280 
 
284 
	#print 'r,c: %s' % str((r, c))
 - 
 
285 
	#print 'val: %s' % s[r,c]
 - 
 
286 
	#print 'row: %s' % s.get_row (r, c)
 - 
 
287 
	#print 'col: %s' % s.get_col (r, c)
 - 
 
288 
	#
 - 
 
289 
	#print 'upl: %s' % str(s.get_upper_left (r, c))
 - 
 
290 
	#print 'ssq: %s' % s.get_small_square (r, c)
 - 
 
291 
 
 - 
 
292 
	print s.solve ()
 281 
	print solve (s)
293 
 
 282 
 
294 
if __name__ == '__main__':
 283 
if __name__ == '__main__':
295 
	main ()
 284 
	main ()