Four years ago I wrote a Sudoku puzzle solver, and now I'm trying to understand how it works so that I can reuse parts of it for a KenKen puzzle solver. I thought I'd better compactify loops into list comprehensions and pick more self-explanatory names for variables.
There's a class Puz which contains the input puzzle as a list of (81) digits; 1 through 9 where the cell's value is known, and 0 where it is not.
Class Puz also contains a working version of the puzzle, except that here each of the (81) items in the list is a set; where the answer for a cell is known, the set contains one value from 1 to 9, e.g., set([4]), and where the answer is unknown, the set contains the remaining possibilities, e.g., set([3,5,7,9]). When Puz._init__(self, puz) is called, those "maybe" sets in the work list are set to set([1,2,3,4,5,6,7,8,9]), and the first step in getting to a solution is to strike out all the values which appear as answers in that cell's row, column, and 3x3 block.
Originally, the work list was filled in using a for loop: for 0 to 80, if it's an answer, put in the answer as a set, else put in set( range( 1, 10)). I couldn't figure out how to get this kind of conditional into a list comprehension, so I broke it out into a separate "filling function", of which 3 versions are shown below. The fill_funcs differ in their "not-an-answer branches":
return set( range( 1,(self.dim+1)))
return set( self.r_dim_1_based)
return self.set_dim_1_based
As you see, increasing amounts of processing are moved outside the function back to where the little variables are initialized.
The trouble is, the first two variations slip into the Sudoku solver and work exactly the way the original code did. BUT --- the third variation breaks, saying that the 6th set in the working list is (or becomes) empty. YET --- the lists of sets produced by all three variations evaluate as equal:
p.W1 == p.W2 == p.W3 --> True
I'm stumped.
Here's some code for making the lists of sets:
#!/usr/bin/env python
import copy
from math import sqrt
'''
Puzzle #15, from The Guardian: 050624: #41: rated difficult
'''
puz = [
0,0,1, 9,0,0, 3,0,0,
0,0,0, 0,0,0, 2,0,0,
7,6,0, 0,2,0, 0,0,9,
3,0,0, 0,6,0, 0,0,5,
0,0,2, 1,0,3, 4,0,0,
4,0,0, 0,9,0, 0,0,3,
1,0,0, 0,3,0, 0,9,7,
0,0,4, 0,0,0, 0,0,0,
0,0,5, 0,0,8, 6,0,0
]
class GroupInfo: pass
class Puz(GroupInfo):
def __init__(self, puz):
self.A = copy.deepcopy(puz)
self.ncells = len( self.A)
self.r_ncells = range( 0,self.ncells)
self.dim = int( sqrt( self.ncells))
assert (self.dim ** 2) == self.ncells, "puz is not square"
self.r_dim_0_based = range( 0,self.dim)
self.r_dim_1_based = range( 1, self.dim + 1)
self.set_dim_1_based = set( self.r_dim_1_based) ## <<---- causes to fail!
##### with 'empty set at W[5]' !?!?!?
def W1_fill_func( val):
if (val == 0):
return set( range( 1,(self.dim+1)))
else:
return set( [val])
self.W1 = [ W1_fill_func( self.A[cid])
for cid in self.r_ncells ]
def W2_fill_func( val):
if (val == 0):
return set( self.r_dim_1_based)
else:
return set( [val])
self.W2 = [ W2_fill_func( self.A[cid])
for cid in self.r_ncells ]
def W3_fill_func( val):
if (val == 0):
return self.set_dim_1_based
else:
return set( [val])
self.W3 = [ W3_fill_func( self.A[cid])
for cid in self.r_ncells ]
return
#def Puz.__init__()
#class Puz
p = Puz(puz)
print p.W1 == p.W2 == p.W3