Why Not Python?, Part 3

Part 1
of this article introduced the Python programming language
from the perspective of an old C hacker and presented a short program
to solve the "Coconuts" problem. Part 2
described the Sudoku puzzle and showed how a Sudoku-solving program might be
written in Python. The program would contain three steps:

1. read in the values of the cells specified and draw some elementary
   conclusions about what the blanks will be
2. fill in the empty cells; that is, solve the puzzle
3. print out the answer

Last time, we coded the sections of the algorithm for Step 1 and Step 3:

• 1.2: read in each value from the input
  file
• 1.2.1: if unknown (i.e, a '-' or '.'), leave the cell
  alone
• 1.2.2: if known: a. set the data structure's digit (the "if known" part) to
  that known value; andb. remove that value from the set of possible digits in the
  rest of that cell's row, column and 3x3 sub-matrix.

We refer to this code as we refine Step 2 below, which involves
filling in the empty cells--solving the puzzle. The first thing
that came to my mind was something like this:

• 2.1: for each cell whose value we don't yet know, if
  its set_of_possibles has only one member, assign that value to the cell and execute 1.2.2b
• 2.2: for each cell whose value we don't yet know, for each digit in
  its set_of_possibles, if this cell is the only one
  in the row, column or 3x3 sub-matrix that could be that value,
  assign that value to the cell and execute 1.2.2b
• 2.3: repeat 2.1 and 2.2 until no assignments are made or all cells
  are filled in
• 2.4: if any cell is unknown but its set_of_possibles is empty,
  we have an inconsistent puzzle; raise a signal
• 2.5: if all cells are known, declare victory and go to
  Step 3
• 2.6: create a "guess"

Creating a guess involves the following steps:

• a. for each cell, save a copy of its value and its
  set_of_possibles.
• b. hypothetically fill in an unknown cell with the first
  value in its set_of_possibles and execute 1.2.2b
• c. execute 2.1-2.6 recursively
• d. if we get an inconsistency, restore the copy
  from 2.6.1 and then go back to 2.6.2. But, this time use the
  next value in the set_of_possibles; repeat for all
  values in the set_of_possibles unless...
• e. if 2.5 said "go to Step 3", then we're done (assume that
  the puzzle has only one solution, which we've just found).

To see what I mean by 2.1 and 2.2, consider this picture of the above
puzzle, where I've labeled three of the "unknown" cells.

Let's apply step 2.1 to the cells marked "A" and "B" in the figure.
Cell A's row already has a 1, 2, 3 and 4. Its column has 3, 8 and 7.
So it looks like cell A legitimately could be 5, 6, or 9. So 2.1
doesn't help us with A.

Does 2.1 help us with B? Well, B's row has 4, 5, 7 and 8, while its column has
1, 3, 5, 7 and 9. Its submatrix (the grey area) has 3, 4, 5, 6 and 7. The only
possible value for B is 2. So Step 2.1 allows us to set cell B to 2.

Now let's apply step 2.2 to A. Because A could be 5, 6 or 9, let's
start with the value 5 and see if any other cell in A's row (that is, row 0)
also could have the value 5. Well, none of them can. Row 0, column 5 is
in the same (grey) submatrix as row 1, column 3 (=5) so row 0, column 5
cannot also be 5. Row 0 columns 6, 7 and 8 can't be 5, because row 2, column 6
is a 5. So row 0, column 1 is the only cell in its row that could be a 5.
Thus, Step 2.2 allows us to set cell A to 5.

Step 2.3 says to go through the cells until either all of the cells are filled
in or we've made a whole pass without filling in anything. Why do that?
Consider cell C. Before cell B is filled in, we might think that
cell C could be either 2 or 6. But once we set cell B to 2, C
no longer can be 2. Step 2.1 then allows us to set cell C to 6.

Step 2.4 is for the times when we have to make a guess (see Step 2.6).
Sometimes we will guess wrong, and we'll want to get out of that.

Now what's this about guessing? Well, Steps 2.1-2.5 are enough to solve
every puzzle I've tried that came from a newspaper. But there are some
puzzles, such as the one shown below, that require you to guess at some
point. Basically, when Steps 2.1 and 2.2 don't let you fill in anything
at all, we have to fill in a cell tentatively--we have to guess--and
see where it takes us. Sometimes, a guess leads to an inconsistency,
which is what Step 2.4 is for. In this case, we know our guess was
wrong and we have to forget it. We also must forget all the cells we
filled in, including any new guesses, based on that first wrong guess.
And that part about forgetting all the cells that we filled in based on the
wrong guess--that's why we need Steps 2.6.1 and 2.6.4.

But one thing at a time. For now, let's simply code Steps 2.1-2.5. As
I mentioned above, that's enough to solve all the Sudoku puzzles I've
tried from the newspaper.

So let me make a few revisions in the class Cell. I need to add a few access
functions, plus a test for whether a certain cell could have a given value.
While I'm at it, I should put the Cell class into a separate module. To do
that, I move everything in the class Cell clause from the main program
into a separate file, cell_class.py.

I'm also going to change the names of the fields in cell_class.py.
I want some fields to be modified only by functions that are part of the
class. So, although Python doesn't let you actually hide data, I can make
it my policy always to use the access routines introduced in Part 2 whenever
I want to access those fields. To that end, I took the names of all the
data fields and prefixed "XYZ" to them, as a kind of "Stop me before I modify
private data again!" tool. Then, in the main part of the program, I can make
sure there aren't any XYZ's and know I've been a good boy.
Here's cell_class.py:

    1   class Cell:
    2      rows = [ [], [], [], [], [], [], [], [], [] ]    # nine each...
    3      columns = [ [], [], [], [], [], [], [], [], [] ]
    4      submatrices = [ [], [], [], [], [], [], [], [], [] ]
    5   
    6      # for step 1.1, do "cells[i]=Cell(i)" for i in range(0,81)
    7      def __init__(self,pos):
    8         # "pos" = position in the puzzle.  Valid values: range (0,81)
    9         global rows, columns, submatrices
   10         if pos not in range(0,81):
   11            raise Illegal_pos_in_Cells_initializer
   12         self.XYZpos = pos
   13         self.XYZvalue = 0
   14         self.XYZset_of_possibles = range(1, 10)  # 1-9 INclusive
   15   
   16         # For step 1.2.2b, track which row, col, sub that I belong to.
   17         myrow = int(pos / 9)
   18         mycol = pos % 9
   19         mysub = int(myrow/3) * 3 + int(mycol/3)
   20   
   21         self.XYZrow = Cell.rows[myrow]
   22         self.XYZcol = Cell.columns[mycol]
   23         self.XYZsub = Cell.submatrices[mysub]
   24   
   25         self.XYZrow.append(self)
   26         self.XYZcol.append(self)
   27         self.XYZsub.append(self)
   28   
   29      def known(self):
   30         return (self.XYZvalue != 0)
   31   
   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.XYZset_of_possibles:
   38            raise setting_impossible_value
   39         if self.known():
   40            raise setvalue_called_but_already_known
   41   
   42         self.XYZvalue = val              # 1.2.2a
   43         self.XYZset_of_possibles = []    # make life easier in step2.6
   44   
   45         # Now do 1.2.2b
   46         for other in self.XYZrow + self.XYZcol + self.XYZsub:
   47            if other is self: continue
   48            if other.known(): continue
   49            if val in other.XYZset_of_possibles:
   50               # Though "remove" isn't in the book, it's not deprecated...
   51               other.XYZset_of_possibles.remove(val)
   52   
   53      def getvalue(self): return self.XYZvalue
   54      def getrow(self): return self.XYZrow
   55      def getcolumn(self): return self.XYZcol
   56      def getsubmatrix(self): return self.XYZsub
   57      def possibles(self): return self.XYZset_of_possibles[:]
   58      def could_be(self,val):
   59         if self.known(): return (val == self.XYZvalue)
   60         return (val in self.possibles())

I slid a few more changes in, which I describe here. In lines 10-11
and 35-40, the "raise" statements are put on their own lines to make
debugging (with pdb) easier. For example, I could set a breakpoint on
line 36, and I'd hit that breakpoint only when I got an illegal value.
This is much more convenient than having a breakpoint on line 35 and
hitting it every time I check for a bad value.

Once a cell's value is decided, there is no point in speculating about
what other values it might have. Line 43 makes that explicit. It's
not really necessary, but the data structure feels a little cleaner this way.

Instead of an .index() and a del call, I put a single .remove() call
in line 51. Learning Python, my reference book of
choise, didn't say anything about .remove, but it is mentioned in on-line
documentation. I didn't see anything that saying .remove was deprecated.

Now, I'll do some minor surgery on what's left. The first few lines now
read:

    1   #!/usr/bin/python
    2   import cell_class
    3   import sys
    4   def doit(argv):
    5      cells = []
    6      for i in range(0,81): cells.insert(i,cell_class.Cell(i))       # 1.1
    7   
    8      # Here, any cell's set_of_possibles should be full

Line 1 was added because I got tired of typing python
s2.py.... I wanted to tell the Linux kernel to run
s2.py as a Python program. Besides adding line 1, though, I also had
to set execute permission on s2.py, which I did like this:

   % chmod +x s2.py

After that, I could type:

    % ./s2.py 1109.puz 

instead of explicitly typing python every time.

Line 2 says we want to use cell_class.py. Note, though, that we simply say
import cell_class; Python will add .py, so it
looks for a file named cell_class.py.

Finally, line 6 was changed from

    for i in range(0,81): cells.insert(i,Cell(i))          # 1.1

to

    for i in range(0,81): cells.insert(i,cell_class.Cell(i))          # 1.1

I did this because, as the tutorial explains, you have to give the name of the
module (cell_class in this case) as part of the name:

>>> import fibo

This does not enter the names of the functions defined in
fibo directly in the current symbol table; it only enters the
module name fibo there. Using the module name you can access
the functions:

>>> fibo.fib(1000)

(from docs.python.org/tut/node8.html)

Initially, I forgot to do this; see Appendix A. I then consulted the tutorial
and saw the error of my ways.

Below is the complete s2.py program. It contains the code for Steps 1,
2.1-2.5 and 3 as described in this article series. It solves many, but
not all, Sudoku puzzles.

Note that there is no XYZ to be found, so the only accesses to
cell's data fields are in fact via the access routines. In other
words, I have tamed my inner hacker--for now, anyway. Step 2
code starts after line 30:

    1   #!/usr/bin/python
    2   import cell_class
    3   import sys
    4   def doit(argv):
    5      cells = []
    6      for i in range(0,81): cells.insert(i,cell_class.Cell(i))        # 1.1
    7   
    8      # Here, any cell's set_of_possibles should be full
    9   
   10      if len(argv) > 1 and argv[1]:
   11         input = open(argv[1], 'r')
   12      else:
   13         input = sys.stdin
   14   
   15      all_input_lines = input.readlines()
   16      input.close()
   17   
   18      which_cell = 0
   19      for one_input_line in all_input_lines:
   20         for char in one_input_line:
   21            if char in '\t\n ': continue
   22            if char in '-.': 
   23               which_cell = which_cell + 1
   24            elif ord(char) in range (ord('1'), ord('9')+1):
   25               cells[which_cell].setvalue(ord(char)-ord('0'))
   26               which_cell = which_cell + 1
   27            if which_cell > 81: raise too_much_input
   28      pass   # so the debugger can break here
   29   
   30      # Step 2 should go here
   31      something_was_set = 1
   32      while something_was_set:
   33         something_was_set = 0
   34         unknown_cells = filter(lambda a: not a.known(), cells)
   35   
   36         # 2.3 quit when all cells are known
   37         if len(unknown_cells) == 0: break         ## Done!  All known.
   38   
   39         for acell in unknown_cells:
   40   
   41            # 2.1 only one member in set_of_possibles?
   42            possible_digits = acell.possibles()
   43            if len(possible_digits) == 1:
   44               acell.setvalue(possible_digits[0])
   45               something_was_set = 1
   46               continue
   47            
   48            # 2.4 unknown but no possibilities?
   49            if len(possible_digits) == 0: raise Unknown_with_no_hope
   50   
   51           # 2.2 any digit in only one cell in a row, column, or submatrix?
   52            global dig
   53            for dig in possible_digits:
   54             whohas = filter(lambda a: a.could_be(dig), acell.getrow())
   55             if len(whohas) == 1: break # unique in row
   56             whohas = filter(lambda a: a.could_be(dig), acell.getcolumn())
   57             if len(whohas) == 1: break # unique in col
   58             whohas = filter(lambda a: a.could_be(dig), acell.getsubmatrix())
   59             if len(whohas) == 1: break # unique in sub
   60            else: # "acell" has no unique digit (no "break" hit)
   61               continue  
   62   
   63            # Unique!  Set that value
   64            acell.setvalue(dig)
   65            something_was_set = 1
   66            pass # end of "for acell in unknown_cells"
   67         pass # end of "while something_was_set"
   68      
   69      print len(unknown_cells), "unknown cells"
   70   
   71      # Code for step 3
   72      for bor in range(0,81,9):
   73         for i in range(bor,bor+9):
   74            if cells[i].known(): print cells[i].getvalue(),     # usual case
   75            else: print '-',                                    # unknown
   76         print                        # end of this row
   77   
   78   # main begins here
   79   if __name__ == '__main__': doit(sys.argv)     

Let me explain some of the less obvious parts. Lines 31-33 set up the
main loop for Steps 2.1-2.5, where I try to deduce the value of the
unknown cells using, well, Steps 2.1 and 2.2. When I go through the
entire list of unknown cells and can't determine any value, it's time
to give up rather than spin my wheels. So we try, and each time we
set the value of a cell (with setvalue()), we make
something_was_set "true"; see lines 44-45 and 64-65.

Line 34 uses both "filter" and "lambda". What I'm trying to do in this
line is create a list of cells whose values we don't know. These are the
cells that we'll look at in Steps 2.1 and 2.2. Now, as the tutorial
says:

"filter(function, sequence)" returns a sequence (of the same type,
if possible) consisting of those items from the sequence for which
function(item) is true. For example, to compute some primes:

      >>> def f(x): return x%2 != 0 and x%3 != 0
      ...
      >>> filter(f, range(2, 25))
      [5, 7, 11, 13, 17, 19, 23]

The example from the tutorial uses "f" for the function. What if I don't have
a convenient function "f" lying around, and I'm too lazy to define
one? After all, the function--I might call it "cell_is_unknown"
or something--is going to be used in only one place. Well, it turns
out that Python offers a way to create an anonymous function using
this lambda thing. In line 34, lambda a: not
a.known() means we have a function that returns "true" whenever its single
argument refers to a cell of unknown value. So, the effect of line
34 is to put the unknown cells (from the array "cells") into the
list "unknown_cells".

If there are no unknown cells, the puzzle is solved already,
so we should declare victory and go print out the answer (Step 2.3,
line 37). Otherwise, we look at each unknown cell in the loop
(lines 39-66).

Lines 42-46 implement Step 2.1. If a given cell can have only one
value, we go ahead and set that value (line 44) and then tel the loop
that we did something so it's worth trying again (line 45).

Line 49 is going to be important to Step 2.6. Here, the basic idea is:
if any of the cells isn't known, but it can't be anything, then the
puzzle--as it is right now--can't be solved, because we can't fill in the value for this cell.
This is coded as an exception because, at least before we code Step 2.6,
it shouldn't ever happen.

Lines 52-60 check to see if, for any of the possible values
this cell could have, nobody else in this cell's row (lines 54-55),
column (lines 56-57) or submatrix (lines 58-59) possibly could
hold that value. If so, we execute lines 64-65 and set that value.

I didn't realize that I would need to declare "dig" as
a global in line 52. It's needed because otherwise the
"lambda" in line 54 (or 56 or 58) wouldn't know about "dig", due to
the Python naming rules. In Learning Python,
Lutz and Ascher refer to this as the "LGB" rule--Local, Global, Built-in, the three naming
scopes. Line 53 knows about dig because it's local (to the present
function), but the lambdas don't. They are lexically separate from
the module or function that creates them.

At line 69, the program tells you how many cells are still unknown.
I may remove this later. Line 79 is a way that the program can
run with or without the debugger. (A reader provided this tip.)

So, let's apply this program to the puzzle shown in Part 2 of this
article. The file 1109.puz is an ASCII representation of that puzzle:

    % cat 1109.puz 
     1 - 2 3 4 - - - -
     - - - 5 6 7 - - -
     - - 7 - - - 5 8 4
     6 3 - 7 - 4 - - -
     4 8 - - - - - 9 7
     - - - 1 - 5 - 4 3
     5 7 8 - - - 9 - -
     - - - 9 7 3 - - -
     - - - - 5 6 4 - 2
    % 

When we run s2.py on that file, we get:

    % ./s2.py 1109.puz 
    0 unknown cells
    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
    %
 

As before, in the spirit of full disclosure, my debugging diary appears in
Appendix A below.

Now, does this program solve all possible puzzles? It does solve all
of the ones I tried from the newspaper, but it doesn't solve this one:

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

According to some of the postings on
Sudoku.com, it's the hardest known
puzzle having a unique solution. It's certainly too hard for my
simple program above.
Appendix A: Debugging Steps 2.1-2.5
As I said before, the working code for steps 2.1-2.5 didn't just
happen. My first attempt to run the code looked something like this:

        % python s2_orig.py 1109.puz 
        Traceback (innermost last):
          File "s2_orig.py", line 79, in ?
            doit(sys.argv)     ## COMMENT OUT FOR DEBUGGING
          File "s2_orig.py", line 53, in doit
            whohas = filter(lambda a: cell_could_be(a,dig), acell.getrow())
          File "s2_orig.py", line 53, in <lambda>
            whohas = filter(lambda a: cell_could_be(a,dig), acell.getrow())
        NameError: dig
        %
 

I had forgotten to declare "dig" as global, so the lambda expression in
line 53 (now 54) couldn't find it; the remedy was provided here:

       52            global dig

After fixing that, there was another problem:

        % python s2_orig.py 1109.puz 
        Traceback (innermost last):
          File "s2_orig.py", line 80, in ?
            doit(sys.argv)     ## COMMENT OUT FOR DEBUGGING
          File "s2_orig.py", line 61, in doit
            unknown_cells = unknown_cells + 1
        TypeError: illegal argument type for built-in operation
        %
 

What was I thinking? unknown_cells is a list!
I probably thought I was counting up the number of unknown cells. So, I
simply deleted the line, because we're using the length of
"unknown_cells"; the length is recomputed each time.

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.