Why Not Python?, Part 4
To solve the puzzle presented and discussed in Part 3 of this series, as well as similar puzzles, I have to figure out how to code Step 2.6 in Python. (See Part 3 for an outline of all the steps in this problem-solving exercise.) The code should be straightforward, except for saving (Step 2.6.1) and restoring (Step 2.6.4) values of compound data structures.
In fact, this part of the code turned out to be harder to write than I expected. A list of my mistakes can be seen below in Appendix B, but the important lesson is this: simply assigning a list doesn't copy it, as Learning Python says. Instead, another reference is created to the same list. Here's where we bump into that issue:
% python Python 2.4 (#1, Mar 22 2005, 21:42:42) [GCC 3.3.5 20050117 (prerelease) (SUSE Linux)] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> old = [ 1, 2, 3 ] >>> new = old >>> old.append(4) >>> old [1, 2, 3, 4] >>> new [1, 2, 3, 4] >>>
Here, I saved a copy of "old", but it's useless as a backup, because modifying old causes "new" to change too. This is true because only was ever one list, with both old and new pointing to it. One easy way to prevent this occurrence is to copy a slice of the old list, like this:
>>> old = [ 1, 2, 3 ] >>> new = old[:] # copy a "slice" of "old" >>> old.append(4) # modify "old" >>> old [1, 2, 3, 4] >>> new # "new" is unaffected [1, 2, 3] >>>
Here I modified old, but new kept its original value.
Ultimately I decided to create a few new functions within the class itself--I think Java and C++ people call them "methods". The functions deal with "opaque" objects--opaque to the caller, that is--and are responsible for knowing what information has to go into a copy and what must be restored from it. The getbackup() and restore() member functions serve this purpose. Let's add them to cell_class.py:
61 def getpos(self): return self.XYZpos 62 def getbackup(self): 63 return [ self.XYZvalue, self.XYZset_of_possibles[:] ] 64 def restore(self,bkp): 65 self.XYZvalue = bkp[0] 66 self.XYZset_of_possibles = bkp[1][:]
Now cells[N].getbackup() returns a two-element list. The first element contains the current value of cell N, which may be 0 for unknown. The second element is itself a list, the list of cell N's possible values. But because we can modify the "XYZset_of_possibles" piece of the cell, we need a copy of the list instead of another reference to it. Thus, we have to copy the slice, as shown in the example above.
On the restore() side, if bkp is a value returned from cells[N].getbackup(), restore() puts those values back in. Until very recently, I had this coded as:
def restore(self,bkp):
self.value = bkp[0]
self.set_of_possibles = bkp[1]
But this code contained a subtle problem. I explain it below in Appendix C.
In case getpos() isn't self-explanatory, let me explain it here. As with the other accessor routines, getpos() is there so my only access to the "XYZpos" field of a cell is through this read-only function. I use this to keep track of what the program is doing, for debug messages. Its use will be apparent below.
Why am I so hung up on not using field names outside of the class? The field "pos"--actually "XYZpos", as I've changed it--is something that shouldn't be written after it's created. I've accidentally changed fields/variables unintentionally before, and this time I wanted to protect myself from doing so. I'm not sure it's worth the effort, though; it's not a complete solution, because getrow(), for example, gives a reference to a list. And it's harder to shoot yourself in the foot in Python than it is in C. Think, for example, of the classic mistake if (x=1) {.
With that under our belts, let's take a look at s3.py, the complete program. I've snuck in a few more changes, because this old C hacker still is learning
1 #!/usr/bin/python 2 import cell_class 3 import sys 4 import string 5 6 # Constants 7 YEA = 1 8 NAY = None 9 10 # Rather than using "ord()" all over the place, do this: 11 MyAlphabet = '-123456789' 12 13 # becomes YEA if "-v" specified. 14 verbose = NAY 15 16 # We have to define this somewhere. 17 Inconsistent = "formerly 'Unknown_with_no_hope'" 18 19 cells = [] 20 21 # step 1 22 def loadit(input): 23 global cells 24 for i in range(0,81): cells.insert(i,cell_class.Cell(i)) # 1.1 25 26 # Here, any cell's set_of_possibles should be full 27 28 which_cell = 0 29 for one_input_line in input.readlines(): 30 for char in one_input_line: 31 if char in '\t\n ': continue 32 if char in '-.': 33 which_cell = which_cell + 1 34 elif char in MyAlphabet: 35 cells[which_cell].setvalue(string.index(MyAlphabet,char)) 36 which_cell = which_cell + 1 37 if which_cell > 81: 38 raise too_much_input 39 pass # so the debugger can break here 40 input.close() 41 42 43 def solve_simply(): 44 global cells 45 something_was_set = 1 46 while something_was_set: 47 something_was_set = 0 48 unknown_cells = filter(lambda a: not a.known(), cells) 49 50 # 2.3 quit when all cells are known 51 if len(unknown_cells) == 0: break ## Done! All known. 52 53 for acell in unknown_cells: 54 55 # 2.1 only one member in set_of_possibles? 56 possible_digits = acell.possibles() 57 if len(possible_digits) == 1: 58 acell.setvalue(possible_digits[0]) 59 something_was_set = 1 60 continue 61 62 # 2.4 unknown but no possibilities? 63 if len(possible_digits) == 0: 64 raise Inconsistent 65 66 # 2.2 any digit in only one cell in a row, column or submatrix? 67 global dig 68 for dig in possible_digits: 69 whohas = filter(lambda a: a.could_be(dig), acell.getrow()) 70 if len(whohas) == 1: break # unique in row 71 whohas = filter(lambda a: a.could_be(dig), acell.getcolumn()) 72 if len(whohas) == 1: break # unique in col 73 whohas = filter(lambda a: a.could_be(dig), acell.getsubmatrix()) 74 if len(whohas) == 1: break # unique in sub 75 else: # "acell" has no unique digit (no "break" hit) 76 continue 77 78 # Unique! Set that value 79 acell.setvalue(dig) 80 something_was_set = 1 81 pass # end of "for acell in unknown_cells" 82 pass # end of "while something_was_set" 83 84 # print len(unknown_cells), "unknown cells" 85 return unknown_cells 86 87 88 # Code for step 3 89 def dumpit(): 90 for bor in range(0,81,9): 91 for i in range(bor,bor+9): 92 print MyAlphabet[cells[i].getvalue()], # '-' if unknown 93 print # end of this row 94 pass # end of dumpit() 95 96 97 # return YEA if solved. Stop at first solution. 98 def solve_completely(level): 99 try: 100 unknown_cells = solve_simply() 101 except Inconsistent: # part of 2.6.4 102 return NAY 103 104 if len(unknown_cells) == 0: return YEA # declare victory 105 106 # 2.6, create a guess 107 if verbose: 108 print "level =", level, ";", len(unknown_cells), "cells unknown" 109 dumpit() 110 111 # 2.6.1: Make a copy: a list of objects returned from cell_class.getbackup() 112 mycopy = [] 113 for acell in cells: 114 mycopy.append(acell.getbackup()) 115 116 # unknown_cells.sort( 117 # lambda c1, c2: cmp(len(c1.possibles()), len(c2.possibles()))) 118 mycell = unknown_cells[0] # ... shortest set_of_possibles 119 myset = mycell.possibles() 120 if verbose: print "L=", level, "cell", mycell.getpos(), myset 121 for myval in myset: 122 if verbose: print "L=", level, "; cell[", mycell.getpos(), "] =", myval 123 mycell.setvalue(myval) # 2.6.2 124 if solve_completely(level + 1): # 2.6.3: call myself 125 return YEA # 2.6.5: It worked; we're done! 126 127 # 2.6.4: It didn't work. Restore my backup copy. 128 for i in range(81): 129 cells[i].restore(mycopy[i]) 130 131 pass # Now try the next value in myset 132 return NAY # None of the values worked; tell caller 133 134 135 def doit(argv): 136 global verbose # 'cause we're going to modify it 137 if len(argv) > 1 and argv[1] and argv[1] == '-v': 138 verbose = YEA 139 del argv[1] 140 141 if len(argv) > 1 and argv[1]: 142 input = open(argv[1], 'r') 143 else: 144 input = sys.stdin 145 146 loadit(input) # step 1 147 solve_completely(0) # step 2 148 dumpit() # step 3 149 150 151 # main begins here 152 if __name__ == '__main__': doit(sys.argv)
In lines 7-8 I create YEA and NAY, because Python, like C, doesn't have intuitive names for "yes" and "no". Python does have "1" and "None", but their meanings aren't as obvious to me as YEA and NAY are. I suppose I could have used TRUE and FALSE, but I've run into header file problems in C with them, so I got out of the habit.
A reader of Part 2 pointed out that I was making a lot of calls to ord(). This version uses the string MyAlphabet; see lines 11, 34-35, 90. The change in line 90 will help if we want to enhance the program to deal with 16x16 Sudoku puzzles, in which they use digits and letters, not only digits.
In lines 34-35, I want to do the equivalent of MyAlphabet.index(char), which would work if MyAlphabet were a list. But I have to use string.index() instead, so I need to import Python's built-in string package, which is done in line 4. I prefer using a string here, because Python strings are "immutable". That is, I can't change the contents in place, as I could with a list.
I added a "verbose" flag (line 14) that can be, you guessed it, YEA or NAY. If YEA, the program gives a little extra output so you can see what's going on.
In Step 2.4, I want to raise the "Inconsistent" signal and catch it in certain cases. But to do that, Python requires me to define it, which I do in line 17.
Now we come to the major restructuring. Where s2.py had one large function, doit(), that contained Steps 1, 2 and 3, s3.py breaks this up into functions. The functions are loadit() for Step 1, solve_simply() for Steps 2.1-2.5 and dumpit() for Step 3.
Why did I choose to do this breakup, which incidentally wasn't hard to do? Because we might have to make multiple guesses, and each guess could cause a recursive call into that same routine in order to (possibly) make another guess. I explain further below.
The code for loadit() is basically the same as before, except for the use of string.index, mentioned above. Also, we now read the input lines using more typical Python idioms.
The code for Steps 2.1-2.5 now is contained in solve_simply(), lines 43-85. It's basically unchanged, except that I renamed the signal we raise when we discover that the puzzle is inconsistent, usually because of an incorrect guess. Also, solve_simply() returns unknown_cells, line 85. That is, it returns a list of Cell instances whose values are not yet known.
Step 3 now is implemented by dumpit() in lines 89-94.
The next routine, solve_completely(), basically embodies all the parts of Step 2.6, It takes a single parameter, "level", which basically says how many guesses we've had to make on this path through the puzzle. The first thing it does is call solve_simply(). If solve_simply() runs into an inconsistency, it raises the Inconsistent signal. This causes execution to resume at line 102, and solve_completely() returns right there.
Typically, however, execution proceeds to line 104. For many puzzles, solve_simply() returns an empty list, so solve_completely() returns YEA. In other words, except for very hard puzzles, s3.py acts exactly like s2.py.
But for those harder puzzles, we get to line 104 only to discover that there are 54 unknown cells. This is where the fun starts. In lines 111-114, we execute Step 2.6.1. That means we we create a backup copy of each cell's current value and set_of_possibles, using getbackup(), as described above.
In line 118, we choose a cell from unknown_cells[]. We're going to make a guess at the correct value to assign to "mycell".
Before that, lines 116-117 sorted unknown_cells[], based on the length of each cell's set of possible values. This seemed like a good idea at the time I wrote it, but only because it assumes that sorting is free. Doing the sort makes the program take nearly three times as long to solve the hardest-known puzzle. This is true even if I change line 117 to use ".XYZset_of_possibles" instead of ".possibles()".
The loop in lines 121-131 embodies the core of the guessing algorithm, Steps 2.6.2 through 2.6.5. Basically it plows through each value in myset[] (line 121), assigning it to "mycell" (123) and calling itself (124) with an incremented value for "level". When that happens, the new instance of solve_completely() calls solve_simply at line 100. If an inconsistency is found, line 102 is hit. We resume execution in the old instance at line 127, where we restore the backup copy in lines 128-129. We then try the next value in myset[] by running the next pass of the loop, starting at line 122.
If no inconsistency is found, however, the new instance proceeds as the old one did. It chooses a cell from unknown_cells[], saves a copy of each cell's value and set_of_possibles, tries each value in the set by calling itself and so on.
I should mention here, in case it's not obvious, that each time solve_completely() calls itself, it gets a new set of local variables--unknown_cells, mycell, myset and so on. These local variables do not interact across calls. Each instance or each level of recursion is independent of the others.
As with all recursive routines, we need to be careful of a couple of things. First, we need to make sure the "base cases" are covered, which are those cases where you don't want the routine to call itself at all. On this score, we're okay because, as mentioned above, for the simple case, s3.py behaves exactly like s2.py did. It calls solve_simply(), and if that solves the puzzle, the puzzle is solved.
The second thing to do in recursion is to make sure that you really do get to a base case. In other words, make sure the recursion terminates so you don't have an infinite descent. In this aspect too, solve_completely() is safe, because on each pass, we assign a value to a formerly unknown cell (Step 2.6.2, line 123) before calling solve_completely() again. Thus, we are guaranteed that solve_simply (at line 100) returns a strictly shorter list than it did before. So those aspects of the recursion look reasonable.
If, at any level, we try all the values in myset and never get a solution, when we get to line 132, it returns NAY. On a predecessor level, this should result in another value being tried. So the program eventually should get to a solution, provided that a solution exists--which it may not, if you mis-type the puzzle.
The doit function begins at line 135, where you can see how this all of fits together. The new doit() function:
decides if we're going to run with verbose YEA or NAY (137-139)
figures out where the puzzle input is coming from (141-144)
pulls the puzzle into the cells[] array (146)
calls the complete solver and prints the result (147-148)
So, does it work?
% cat hardest-known
- - - - 7 - 9 4 -
- 7 - - 9 - - - 5
3 - - - - 5 - 7 -
- 8 7 4 - - 1 - -
4 6 3 - - - - - -
- - - - - 7 - 8 -
8 - - 7 - - - - -
7 - - - - - - 2 8
- 5 - 2 6 8 - - -
% ./s3.py hardest-known
2 1 5 8 7 6 9 4 3
6 7 8 3 9 4 2 1 5
3 4 9 1 2 5 8 7 6
5 8 7 4 3 2 1 6 9
4 6 3 9 8 1 7 5 2
1 9 2 6 5 7 3 8 4
8 2 6 7 4 3 5 9 1
7 3 4 5 1 9 6 2 8
9 5 1 2 6 8 4 3 7
%
Sure enough, it does.
Now this program is quite short and does only a small part of the Sudoku problem. That is, it only solves puzzles; it doesn't create them. It assumes that a puzzle has only one solution; it doesn't try to verify that by looking for multiple solutions. And it takes a "dumb" approach to the puzzle; it starts with any old cell and assigns any old value. But it does accomplish what we set out to do--solve any Sudoku puzzle under the sun.
Although the program isn't long--less than 200 lines, not counting blank and all-comment lines--we used a number of Python's features, included:
defining and using a class
elements in a class--data structures and member functions or methods
the __init__ method
some pitfalls of copying lists
importing modules
operations on data structures: strings, lists
loops: "for" and "while"
using "global"
some functional programming features: filter and lambda
opening, reading and closing a file
raising and catching an exception
elementary argument (sys.argv) handling
recursion
elementary debugger operations
This experience has been a lot of fun. Thanks for joining me on this ride.
The code here is rather long, and some of my debugging required a lot of printouts. I'm not going to give you a complete code listing so you can repeat the exact same mistakes on your Linux box. Instead I'll give you a summary. My most recent mistake, or "bug" if you will, is detailed in Appendix C. Also, this part is based on an older version, before cell_class.py was separated from s3.py. So the line numbers may not make much sense.
a. When I tried to run my original version, I got
% python s3_orig.py 1109.puz
File "s3_orig.py", line 141
def save_a_copy()
^
SyntaxError: invalid syntax
%
I forgot the : at the end. I had the same problem a few lines later. D'oh!
b. Next, I hit this:
% python s3_orig.py 1109.puz
Traceback (most recent call last):
File "s3_orig.py", line 197, in ?
doit(sys.argv) ## COMMENT OUT FOR DEBUGGING
File "s3_orig.py", line 193, in doit
solve_completely(0) # step 2
File "s3_orig.py", line 159, in solve_completely
except Inconsistent: # part of 2.6.4
NameError: global name 'Inconsistent' is not defined
%
I should have remembered this from my work on the Coconuts problem. I added this earlier in the program:
# We have to define this somewhere.
Inconsistent = "formerly 'Unknown_with_no_hope'"
c. With that fixed, I got
% python s3.py 1109.puz
Traceback (most recent call last):
File "s3.py", line 199, in ?
doit(sys.argv) ## COMMENT OUT FOR DEBUGGING
File "s3.py", line 195, in doit
solve_completely(0) # step 2
File "s3.py", line 160, in solve_completely
unknown_cells = solve_simply()
TypeError: solve_simply() takes exactly 1 argument (0 given)
%
That's dumb! At some point I thought solve_simply was going to take a "lev" parameter, but there's really no point. So, I fixed it like this:
% diff s3_orig.py s3.py
58a59,60
> # We have to define this somewhere.
> Inconsistent = "formerly 'Unknown_with_no_hope'"
86c88
< def solve_simply(lev):
---
> def solve_simply():
%
d. Then, I got a name problem with cells:
% python s3.py 1109.puz
Traceback (most recent call last):
File "s3.py", line 199, in ?
doit(sys.argv) ## COMMENT OUT FOR DEBUGGING
File "s3.py", line 195, in doit
solve_completely(0) # step 2
File "s3.py", line 160, in solve_completely
unknown_cells = solve_simply()
File "s3.py", line 92, in solve_simply
unknown_cells = filter(lambda a: not a.known(), cells)
NameError: global name 'cells' is not defined
%
What caused that? Formerly, "cells" was defined in the doit() function. When I split doit() into three parts, I forgot to declare cells in the global space and to say "global cells" in every function that modifies it.
e. With that fix, it worked for the simple case.
% python s3.py 1109.puz
1 5 2 3 4 8 7 6 9
8 9 4 5 6 7 3 2 1
3 6 7 2 1 9 5 8 4
6 3 1 7 9 4 2 5 8
4 8 5 6 3 2 1 9 7
7 2 9 1 8 5 6 4 3
5 7 8 4 2 1 9 3 6
2 4 6 9 7 3 8 1 5
9 1 3 8 5 6 4 7 2
%
f. Now what happens when we get to a harder puzzle?
% python s3.py hardest-known
Traceback (most recent call last):
File "s3.py", line 203, in ?
doit(sys.argv) ## COMMENT OUT FOR DEBUGGING
File "s3.py", line 199, in doit
solve_completely(0) # step 2
File "s3.py", line 181, in solve_completely
if solve_completely(level + 1): # 2.6.3: call myself
File "s3.py", line 181, in solve_completely
if solve_completely(level + 1): # 2.6.3: call myself
File "s3.py", line 181, in solve_completely
if solve_completely(level + 1): # 2.6.3: call myself
File "s3.py", line 181, in solve_completely
if solve_completely(level + 1): # 2.6.3: call myself
File "s3.py", line 181, in solve_completely
if solve_completely(level + 1): # 2.6.3: call myself
File "s3.py", line 181, in solve_completely
if solve_completely(level + 1): # 2.6.3: call myself
File "s3.py", line 180, in solve_completely
mycell.setvalue(myval) # 2.6.2
File "s3.py", line 35, in setvalue
if val not in self.set_of_possibles: raise setting_impossible_value
NameError: global name 'setting_impossible_value' is not defined
%
That didn't work so well. I tried running verbose, which didn't help too much. So I added one more output:
myset = mycell.set_of_possibles[:]
+ if verbose: print "L=", level, "cell", mycell.pos, myset
for myval in myset:
if verbose: print "L=", level, "; cell[", mycell.pos, "] =", myval
mycell.setvalue(myval) # 2.6.2
That didn't help either, so I had to run the debugger. First, I commented out "doit". Then, in order to catch the signal, I put the "raise" statements on their own lines, like this:
32 # setvalue is used for 1.2.2 33 def setvalue(self, val): 34 # a couple of sanity checks 35 if val not in range(1,9+1): 36 raise val_must_be_between_1_and_9 37 if val not in self.set_of_possibles: 38 raise setting_impossible_value ### BREAKPOINT HERE ### 39 if self.known(): 40 raise setvalue_called_but_already_known
Let's see how it goes:
% python
Python 2.4 (#1, Mar 22 2005, 21:42:42)
[GCC 3.3.5 20050117 (prerelease) (SUSE Linux)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import s3
>>> import pdb
>>> pdb.run('s3.doit(["whatever", "-v", "hardest-known"])')
> <string>(1)?()
(Pdb) b s3.doit
Breakpoint 1 at /home/collin/sudoku-article/s3.py:194
(Pdb) n
> /home/collin/sudoku-article/s3.py(196)doit()
-> if len(argv) > 1 and argv[1] and argv[1] == '-v':
(Pdb) b 38
Breakpoint 2 at /home/collin/sudoku-article/s3.py:38
(Pdb)
Much debugging output later, I got this:
L= 6 cell 24 [2, 6]
L= 6 ; cell[ 24 ] = 2
L= 6 ; cell[ 24 ] = 6
This is the first time in execution that we are trying to set the same cell to a second value.
> /home/collin/sudoku-article/s3.py(38)setvalue()
-> raise setting_impossible_value
(Pdb) p self
<s3.Cell instance at 0x4049398c>
(Pdb) p self.pos
24
(Pdb) p self.set_of_possibles
[]
Wait a minute, in that new line I added for the verbose output, it printed "myset" as containing [2, 6]. Why is it now saying that cell 24 can't be that?
(Pdb) where
/usr/lib/python2.4/bdb.py(366)run()
-> exec cmd in globals, locals
<string>(1)?()
/home/collin/sudoku-article/s3.py(206)doit()
-> solve_completely(0) # step 2
/home/collin/sudoku-article/s3.py(188)solve_completely()
-> if solve_completely(level + 1): # 2.6.3: call myself
/home/collin/sudoku-article/s3.py(188)solve_completely()
-> if solve_completely(level + 1): # 2.6.3: call myself
/home/collin/sudoku-article/s3.py(188)solve_completely()
-> if solve_completely(level + 1): # 2.6.3: call myself
/home/collin/sudoku-article/s3.py(188)solve_completely()
-> if solve_completely(level + 1): # 2.6.3: call myself
/home/collin/sudoku-article/s3.py(188)solve_completely()
-> if solve_completely(level + 1): # 2.6.3: call myself
/home/collin/sudoku-article/s3.py(188)solve_completely()
-> if solve_completely(level + 1): # 2.6.3: call myself
/home/collin/sudoku-article/s3.py(187)solve_completely()
-> mycell.setvalue(myval) # 2.6.2
> /home/collin/sudoku-article/s3.py(38)setvalue()
-> raise setting_impossible_value
(Pdb) up
> /home/collin/sudoku-article/s3.py(187)solve_completely()
-> mycell.setvalue(myval) # 2.6.2
(Pdb) l
182 mycell = unknown_cells[0] # ... shortest set_of_possibles
183 myset = mycell.set_of_possibles[:]
184 if verbose: print "L=", level, "cell", mycell.pos, myset
185 for myval in myset:
186 if verbose: print "L=", level, "; cell[", mycell.pos, "] =", myval
187 -> mycell.setvalue(myval) # 2.6.2
188 if solve_completely(level + 1): # 2.6.3: call myself
189 return YEA # 2.6.5: Done.
190 # 2.6.4: It didn't work. Restore and try the next value
191 restore_the_copy(mycopy)
192 return NAY # Propagate "didn't work" back
(Pdb) p mycopy[24]
<s3.Cell instance at 0x4049398c>
(Pdb) p mycopy[24].pos
24
(Pdb) p mycopy[24].set_of_possibles
[]
(Pdb) p cells[24].set_of_possibles
[]
(Pdb)
My copying code is wrong. How wrong is it?
(Pdb) p cells[24].value
2
(Pdb) p mycopy[24].value
2
(Pdb) p cells[24]
<s3.Cell instance at 0x4049398c>
(Pdb) p mycopy[24]
<s3.Cell instance at 0x4049398c>
It's totally and completely wrong! See how cells[24] and mycopy[24] refer to the exact same address? This tutorial suggests that maybe a shallow copy could work:
(Pdb) import copy
(Pdb) foo = copy.copy(cells[1])
(Pdb) foo.set_of_possibles = foo.set_of_possibles[:]
(Pdb) print cells[1]
<s3.Cell instance at 0x404934ac>
(Pdb) p foo
<s3.Cell instance at 0x4049cc0c>
(Pdb) p foo.set_of_possibles
[1, 2]
(Pdb) p cells[1].set_of_possibles
[1, 2]
(Pdb) cells[1].setvalue(1)
(Pdb) p cells[1].set_of_possibles
[]
(Pdb) p foo.set_of_possibles
[1, 2]
(Pdb)
Yes, that should work fine. So try this:
# for 2.6.1: maybe overkill since we need only value and
# set_of_possibles
def save_a_copy():
the_copy = []
for acell in cells: # have to copy the set of possibles, not just a ref.
acopy = copy.copy(acell)
acopy.set_of_possibles = acell.set_of_possibles[:]
the_copy.append(acopy)
return the_copy
Fools rush in where wise men fear to tread; uncomment the last line and let 'er rip:
% python s3.py hardest-known
2 1 5 8 7 6 9 4 3
6 7 8 3 9 4 2 1 5
3 4 9 1 2 5 8 7 6
5 8 7 4 3 2 1 6 9
4 6 3 9 8 1 7 5 2
1 9 2 6 5 7 3 8 4
8 2 6 7 4 3 5 9 1
7 3 4 5 1 9 6 2 8
9 5 1 2 6 8 4 3 7
%
Although that worked, it's not so nice, because both save_a_copy() and restore_the_copy() refer to fields in the class. It's violating the object-oriented principle of information hiding. Instead, let's hide the information within the class and treat the backup copy as an opaque object. We only need the value and the set_of_possibles, so that's what we'll put into each opaque object. Add these lines to s3cell_class.py:
def getbackup(self):
return [ self.value, self.set_of_possibles[:] ]
def restore(self,bkp):
self.value = bkp[0]
self.set_of_possibles = bkp[1] # See Appendix C on this.
Now, code save_a_copy and restore_the_copy to use the above routines:
# for 2.6.1: cell.getbackup() returns an opaque (to us) object for
# later use
def save_a_copy():
the_copy = []
for acell in cells:
the_copy.append(acell.getbackup())
return the_copy
# for 2.6.4: restore, using the object given by cell.getbackup()
def restore_the_copy(acopy):
for i in range(81):
cells[i].restore(acopy[i])
pass # end of restore_the_copy
We were discussing these methods:
62 def getbackup(self): 63 return [ self.XYZvalue, self.XYZset_of_possibles[:] ] 64 def restore(self,bkp): 65 self.XYZvalue = bkp[0] 66 self.XYZset_of_possibles = bkp[1][:]
I mentioned that restore originally was coded as
def restore(self,bkp):
self.value = bkp[0]
self.set_of_possibles = bkp[1]
which caused some subtle problems. What kind of problems might this cause? My original thinking was this: for getbackup(), the "original" list--the one in cells[]--is about to change, hence we need to make a copy of the list. But we don't need to do that on restore(), because after all, what's going to happen to the backup copy? We're simply going to restore from it again, aren't we?
That thinking has a fatal flaw. Recall that the backup copy was saved only once (lines 112-114). The copy, and in particular the copy of the set_of_possibles, is completely separate from the data structures in cells[]. But what happens if the loop (lines 121-131) is executed three or four times? Suppose, in other words, that at line 121, myset contains [1,2,4]. We execute lines 123-124 with myval==1. Assuming that we didn't find a solution, we execute the loop in 128-129. When restore() was coded the old way, the set_of_possibles (XYZset_of_possibles) was set to reference the same list that's in mycopy. We don't have a problem yet, because what's in cells[] does match what was there before.
Now we execute 123-124 with myval==2. During the course of that execution, the set_of_possibles[] in various cells is modified. Because the old version of restore() copied references, at this point we were modifying the lists stored in mycopy[]. Let's assume that line 124 returns NAY a second time, and we execute lines 128-129. The restore() call restores the old value that any cell had, but it does absolutely nothing with a cell's XYZset_of_possibles, because the cell's XYZset_of_possibles is a second reference to the same list that mycopy[] has!
So, when we execute lines 123-124 with myval==4, each cell's XYZset_of_possibles is set to the exact same set that it was after the failed attempt that occurred when myval was 2. This results in spurious executions of line 64--Inconsistent is raised--and the puzzle is not solved.
What hid this problem was the sort operation in s3.py:
116 # unknown_cells.sort( 117 # lambda c1, c2: cmp(len(c1.possibles()), len(c2.possibles()))) 118 mycell = unknown_cells[0] # ... shortest set_of_possibles 119 myset = mycell.possibles() 120 if verbose: print "L=", level, "cell", mycell.getpos(), myset 121 for myval in myset: 122 if verbose: print "L=", level, "; cell[", mycell.getpos(), "] =", myval
When lines 116-117 were uncommented, line 118 would set mycell to a cell with a short set_of_possibles. In the case of the hardest-known puzzle--the only puzzle I know of that actually requires guessing--this means len(myset)==2 always. Therefore, the loop (lines 122-131) is executed twice at the most. Because the loop never is executed a third time in the same instance of solve_completely(), we don't run into the case where a cell's XYZset_of_possibles[] loses some values erroneously. Thus, the defect in restore() remained hidden.
So how did I come to find out about the defect? Well, the original program executed the sort operation, and the program took some 25 seconds on my old Toshiba 460CDX laptop (Pentium MMX, bogomips 163). I tried commenting out lines 116-117 and found that the hardest-known puzzle was solved in about eight seconds. So I wondered what would happen if I ran the recursion with the longest list first. I uncommented lines 116-117 and changed the sort to arrange unknown_cells in descending order, like this:
116 unknown_cells.sort( 117 lambda c2, c1: cmp(len(c1.possibles()), len(c2.possibles()))) 118 mycell = unknown_cells[0]
Notice that c1 and c2 are reversed in line 117. Then, line 118 gets a cell with the longest set of possibles--six possible values, actually. That's how I discovered the defect with the original version of restore().
Collin Park works for Network Appliance, where he uses Linux on his desktop and laptop computers. He does data recovery and other Linux-related stuff at home, where he lives with his wife and their two teenage daughters. All use Linux to meet their computing needs.
