# Sudoku. The Basics

Note: This project edited fairly extensively in May 2018

Sudoku is a one player game (or puzzle) that rapidly became popular around the world about 15 years ago. The game starts as a 9x9 grid of cells some of which are empty and others which already contain a number from 1 to 9.

The 81 cells are further divided into nine 3x3 boxes. A puzzle is complete when each box, each column and each row contain the numbers one to nine exactly once.

# A few comments on the code

The Python code for this project uses some less common features that the reader might not be used to. This inculudes "functional-like" built-ins such as map, filter and reduce as well a couple of instances of list-comprehension. The usage will probably be easily understood from its context including comments. When not, lots of on-line documentation is also available.

The use of sets is also a feature used by the program and why they are so useful will be evident as we proceed. Sets are like lists where each value is unique. The methods union, difference and discard will be used along with converting sets to tuples. We'll demonstrate them with some examples done interactively.

The module sudoku.py contains class definitions for Game and Cell. Small test programs were used for during development to verify code correctness and then, as the project proceeded, much of this code was brought into the appropriate class definition. This approach was so useful that I decided it would be a nice way to explain the code as well.

An instance of the game class is mostly a list of cells along with methods to input a game from a text file and (python-ically) output a text file in exactly the same format. It also handles iterations of changes to the cells as the game proceeds. An instance of the cell class contains a fixed value, or a set of possible values along with some static information such as which other cells belong to the same row, column or 3x3 box.

You can download the project from sudoku.zip and just expand it into an empty directory. If you can run Python from a terminal window then you can follow along very easily.

# The walk through

Below some cells are tagged with a letter to make it easy to refer to them. The cell tagged with an a belongs to row 4, column 4, and even box 4. The neighbors of a are in the same row, in the same column or the same box. Cells tagged with a b are in the same box. Those in the same row are tagged with an r (unless already tagged with a b). And those in the same column as a are likewise tagged with a c. Every cell has 24 neighbors (8*3). But 4 neighbors share a duplicate cell. Here is the diagram:

```\$ python test1.py test1a.game
Before                    After
. . . | . . . | . . .     . . . | c . . | . . .
. . . | . . . | . . .     . . . | c . . | . . .
. . . | . . . | . . .     . . . | c . . | . . .
------+-------+------     ------+-------+------
. . . | a . . | . . .     r r r | a b b | r r r
. . . | . . . | . . .     . . . | b b b | . . .
. . . | . . . | . . .     . . . | b b b | . . .
------+-------+------     ------+-------+------
. . . | . . . | . . .     . . . | c . . | . . .
. . . | . . . | . . .     . . . | c . . | . . .
. . . | . . . | . . .     . . . | c . . | . . .
```

When a cell instance is created, it takes attributes for its number (0,80), row and column (0-8), a value val (0-9) and a set of 1 to 9 possible values pvals. An empty cell takes the value 0. An occupied cell has a value 1-9 and its pval is a set of 1 with the same value. The attributes also include 3 static tuples for sameRow, sameCol and sameBox with the cell numbers of the appropriate neighbors as seen above. Keeping these with the cell removes the need to recalculate them again and again.

Let's play with this a bit:

```>>> from sudoku import Cell
>>>
>>> mycell = Cell(15)  # Provide the cell number
>>> print mycell
(2,7)=0
>>> print mycell.row, mycell.col
1 6
```

A cell can be described with a location tuple and value. Notice the pythonic zero-based indexing in the row and col attributes (used for computation) and the (2,7) one-based values for people. Looking at the static tuples for the neighbors:

```>>> print mycell.sameBox
(6, 7, 8, 16, 17, 24, 25, 26)
>>> print mycell.sameRow
(9, 10, 11, 12, 13, 14, 16, 17)
>>> print mycell.sameCol
(6, 24, 33, 42, 51, 60, 69, 78)
>>> print mycell.pvals
set([1, 2, 3, 4, 5, 6, 7, 8, 9])
>>>
```

The sameX tuples contain the cell numbers of the other cells in the same entity (row, col or box). Tuples work fine since these never change. But a cell's possible values, the pvals, are a set so that they can be changed. In fact, while the puzzle is being solved, the size of the pvals sets steadily decreases. Initially, for each empty cell every value of 1-9 is considered a possibility. The method Cell.update_pvals trims this down cell by cell and will be discussed in a bit.

There is one other attribute Cell.tag which lets us attach a tag or label to a cell and this tag will be output instead of a "." if the cell is empty. If the cell has a value (1-9) then the value will always be output. Tags are not necessary for solving the puzzle but having them makes it easier to create some of the demos.

# Interaction between cells

The little program test2.py sets up a game, finds the tagged cells (a,*b*,...) and applies the update_pvals method to them in alphabetically order. A display of the initial game and its update are then printed side by side. (The code for sideBySide.py is fairly simple and what it does is even more so.)

```01 import sys
02 from sudoku import Game, Cell
03 from sideBySide import sideBySide
04
05 def test2 () :
06     "Set up a dual set and show effects"
07     game = Game(sys.argv[1])
08     tagged = game.getTagged()
09     tags=tagged.keys(); tags.sort()
10     before = game.display()
11     for tag in tags :
12         cell = tagged[tag]
13         print " ", tag, cell, cell.pvals
14         cell.update_pvals(game.cells)
15         print " ", tag, cell, cell.pvals
16
17     after = game.display()
18     print "\n        Before                    After"
19     print sideBySide([before,after])
20
21 if __name__ == "__main__" : test2()
```

Our first use of this program will be to simply find the value of the cell tagged a. At its creation this cell has all possible values but with a single invocation of update_pvals it finds that every value except "8" is either in the same row, column or box as itself. a's pvals set is reduced accordingly and reaching a single entry, the value of the cell is set:

```\$ python test2.py test2a.game
a (5,5)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
a (5,5)=8 set([8])

Before                    After
. . . | . . . | . . .     . . . | . . . | . . .
. . . | . . . | . . .     . . . | . . . | . . .
. . . | . . . | . . .     . . . | . . . | . . .
------+-------+------     ------+-------+------
. . . | 9 . . | . . .     . . . | 9 . . | . . .
. 1 2 | . a . | . 3 .     . 1 2 | . 8 . | . 3 .
. . . | . . 4 | . . .     . . . | . . 4 | . . .
------+-------+------     ------+-------+------
. . . | . 5 . | . . .     . . . | . 5 . | . . .
. . . | . 6 . | . . .     . . . | . 6 . | . . .
. . . | . 7 . | . . .     . . . | . 7 . | . . .
```

A more complicated example follows below. Here 4 empty cells are tagged a,b,c,d. Since they are processed alphabetically, d is done last. Cells a, b, c will each lose possibilities 1 to 6 from their pvals since they all share the same 3x3 box. Then d is updated and sees that its column contains 3 cells each with possible values 7,8,9 (a,b,c). Since there are exactly 3 cells with this trio sharing both the same box and the same column, none of these 3 values can appear anywhere else in the column. So d's pvals are reduced to just 4,5,6 after also discarding the 1,2,3 sharing the same row.

This is very general and is the main way pvals can be steadily reduced as the puzzle is worked through many iterations. Whenever a pvals set is changed it may affect the values in other cells. The steady shrinking of pvals cascades into more shrinking later.

```\$ python test2.py test2b.game
a (1,9)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
a (1,9)=0 set([7, 8, 9])

b (2,9)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
b (2,9)=0 set([7, 8, 9])

c (3,9)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
c (3,9)=0 set([7, 8, 9])

d (5,9)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
d (5,9)=0 set([4, 5, 6])

Before                    After
. . . | . . . | 1 2 a     . . . | . . . | 1 2 a
. . . | . . . | 3 4 b     . . . | . . . | 3 4 b
. . . | . . . | 5 6 c     . . . | . . . | 5 6 c
------+-------+------     ------+-------+------
. . . | . . . | . . .     . . . | . . . | . . .
. . . | 1 2 3 | . . d     . . . | 1 2 3 | . . d
. . . | . . . | . . .     . . . | . . . | . . .
------+-------+------     ------+-------+------
. . . | . . . | . . .     . . . | . . . | . . .
. . . | . . . | . . .     . . . | . . . | . . .
. . . | . . . | . . .     . . . | . . . | . . .
```

Below is an extreme example that we humans might visualize as four 7's sweeping the possibilities in the center box, leaving only the center cell possible for the value 7. Our program sees the same thing, but somewhat differently. 8 of 9 cells in the box lose the 7 from their pvals set leaving a group of 8 pvals with the same set of 8 values. And this 8 of 8 reduces the center to just the remaining single value. By tagging the cells in the center box, we can watch this happen step by step:

```\$ python test2.py test2c.game
a (4,4)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9]) # Before update
a (4,4)=0 set([1, 2, 3, 4, 5, 6, 8, 9])    # After update (7 is gone)
b (4,5)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
b (4,5)=0 set([1, 2, 3, 4, 5, 6, 8, 9])    # Ditto
c (4,6)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
c (4,6)=0 set([1, 2, 3, 4, 5, 6, 8, 9])    # Ditto
d (5,4)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
d (5,4)=0 set([1, 2, 3, 4, 5, 6, 8, 9])
e (5,6)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
e (5,6)=0 set([1, 2, 3, 4, 5, 6, 8, 9])
f (6,4)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
f (6,4)=0 set([1, 2, 3, 4, 5, 6, 8, 9])
g (6,5)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
g (6,5)=0 set([1, 2, 3, 4, 5, 6, 8, 9])
h (6,6)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
h (6,6)=0 set([1, 2, 3, 4, 5, 6, 8, 9])
x (5,5)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
x (5,5)=7 set([7])

Before                    After
. . . | . . . | . . .     . . . | . . . | . . .
. . . | 7 . . | . . .     . . . | 7 . . | . . .
. . . | . . . | . . .     . . . | . . . | . . .
------+-------+------     ------+-------+------
. 7 . | a b c | . . .     . 7 . | a b c | . . .
. . . | d x e | . . .     . . . | d 7 e | . . .
. . . | f g h | . 7 .     . . . | f g h | . 7 .
------+-------+------     ------+-------+------
. . . | . . . | . . .     . . . | . . . | . . .
. . . | . . 7 | . . .     . . . | . . 7 | . . .
. . . | . . . | . . .     . . . | . . . | . . .
```

# Finding the last chance cell

There is another way to firmly set a number into a cell that is a bit different than what has been described so far. Sometimes it's needed. Consider the following:

```\$ python test2.py test2d.game
a (5,3)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
a (5,3)=0 set([5, 6, 7])                    # a loses 8 (among lots more)
b (5,7)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
b (5,7)=0 set([6, 7])                       # ditto b
c (5,9)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
c (5,9)=0 set([6, 7])                       # ditto c
x (5,5)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
x (5,5)=8 set([8])

Before                    After
. . . | . . . | . . .     . . . | . . . | . . .
9 . 8 | . . . | . . .     9 . 8 | . . . | . . .
. . . | . . . | . . .     . . . | . . . | . . .
------+-------+------     ------+-------+------
. . . | . . 2 | . 5 .     . . . | . . 2 | . 5 .
1 2 a | 3 x 9 | b 4 c     1 2 a | 3 8 9 | b 4 c
. . . | . . 4 | . 8 .     . . . | . . 4 | . 8 .
------+-------+------     ------+-------+------
. . . | . . . | . . .     . . . | . . . | . . .
. . . | . . . | . . .     . . . | . . . | . . .
. . . | . . . | . . .     . . . | . . . | . . .
```

Here we have tagged cells a, b, c and x. They will be evaluated in that order. Cell a is blocked from all except 5, 6 and 7. Cells b and c share the doublet 6,7 leaving cell x with only 5, 8 for possibilities. But things would stop there unless we also take into account that x is the only cell that can accept the value 8. When that happens the cell must take that value even if it sees other possibilities.

That pretty much wraps up the workings of the method Cell.update_pvals. Let's look at the code for it.

```01    def update_pvals(self, cells) :
02        allvals = set([1,2,3,4,5,6,7,8,9]); self.error = ""
03        for friends in (self.sameBox,self.sameRow,self.sameCol) :
04            discards = {}      # what may be removed from self.pvals
05            grpvals  = set([]) # as a group what vals are possible
06            friends = map(lambda x: cells[x], friends) # list of cell objs
07            for other in friends :
08                key = tuple(other.pvals)  # its possible value(s)
10                grpvals.update(other.pvals)
11            if grpvals.union(self.pvals) != allvals :
12                self.error = "Not all values 1-9 possible in %s" % friends
13                return False
14            uncovered = allvals.difference(grpvals)
15            if len(uncovered) == 1 :      # only possibility
16                self.pvals = uncovered
17            else :
18                for key in discards.keys() :
19                    if len(key) == discards[key] :
20                        for used in key :
22            if len(self.pvals) == 1 :
23                self.val=tuple(self.pvals)[0]
24        return True
```

This method works on a single cell self and tries to reduce self.pvals. The for loop in line 3 matches the self's value against the 3 groups that need uniqueness, its row, column and box. The groups are treated independently.

The dictionary discards and the set grpvals are initialized for each group (lines 4-5). The keys of discards are tuples made from others pvals and discards values are counts of common pvals sets (line 9). Supposing we had this during computation:

```>>> print discards
{ (8,): 1, (5,6): 2, (4,3,2): 2 }
```

From this 8, 5 and 6 can a bit later (line 18-21) be discarded from self.pvals. But we can't do anything (yet) with 4, 3 and 2.

The other way to affect self.pvals is done using the grpvals set. grpvals contains values possible in the other cells (line 10). And together with self.pvals they should cover all values 1 to 9. (line 11-13). And when only one value is missing, that reduces self.pvals to that single entry. (lines 14-16).

Finally, in lines 18-23, self.value is set to its unique possibility. The method returns True if no error was encountered.

# Updating cells iteratively

The next step is easy. We test each cell of the board and, if possible, update its pvals set. The order we visit the cells is arbitrary, so to keep it simple we'll start at the top left and work across and down to the bottom right.

```01     def iterate(self) :
02         changed = False
03         for cell in self.cells :
04             earlier = cell.pvals.copy()
05             cell.update_pvals(self.cells)
06             if cell.error :
07                 self.error = cell.error
08                 return changed
09             if cell.pvals != earlier :
10                 changed = True
11                 if self.track and len(cell.pvals) == 1 :
12                     print "Set (%s,%s) to %s" % (
13                         cell.row+1,cell.col+1,list(cell.pvals)[0])
14         return changed
15
```

If any cell is updated then the board has changed (line 10). If any cell update results in an error, the board is in error and returned (line 8). If a cells possible values are reduced to just one and if tracking is on, we get a print of the value being set (line 12)

If the board is returned unchanged (line 14) then the puzzle is complete. Otherwise, game.iterate is called again until no further changes are made.

Here's the program test3.py which does exactly this.

```01 import sys, sudoku
02 from sideBySide import sideBySide
03
04 def test3 () :
05     game = sudoku.Game(sys.argv[1])
06     sweep = 1
07     before = game.display()
08     while not game.finished() :
09         game.iterate()
10         if game.error :
11             print game.error
12             break
13         else :
14             after = game.display()
15             print "  Sweep", sweep
16             print "\n        Before                    After"
17             print sideBySide([before,after])
18             before = after
19             sweep += 1
20
21 if __name__ == "__main__" : test3()
22
```

At line 7 we capture printable version of the game (a multi-line string) in before. We repeat iterations, each working through the cells until the game is finished or an error occured.

Here is a typical game in progress played to completion after four iterations over the cells.

```\$ python test3.py test3a.game
Iteration 1

Before                    After
. . 1 | . 4 5 | . 7 .     . . 1 | . 4 5 | . 7 .
5 9 7 | 2 . . | . . .     5 9 7 | 2 . . | . . .
6 . . | . . 7 | 3 . 8     6 2 4 | 1 9 7 | 3 5 8
------+-------+------     ------+-------+------
7 . . | . 2 . | 5 3 .     7 . 6 | 8 2 . | 5 3 4
9 . . | 4 . 6 | . . 1     9 . . | 4 . 6 | . 2 1
. 4 2 | . 7 . | . . 9     . 4 2 | 5 7 . | . . 9
------+-------+------     ------+-------+------
2 . 8 | 3 . . | . . 5     2 . 8 | 3 1 4 | . . 5
. . . | . . 8 | 2 1 3     4 . 9 | 7 5 8 | 2 1 3
. 5 . | 9 6 . | 4 . .     . 5 3 | 9 6 2 | 4 8 7

Iteration 2

Before                    After
. . 1 | . 4 5 | . 7 .     . . 1 | 6 4 5 | 9 7 2
5 9 7 | 2 . . | . . .     5 9 7 | 2 8 3 | 1 4 6
6 2 4 | 1 9 7 | 3 5 8     6 2 4 | 1 9 7 | 3 5 8
------+-------+------     ------+-------+------
7 . 6 | 8 2 . | 5 3 4     7 1 6 | 8 2 9 | 5 3 4
9 . . | 4 . 6 | . 2 1     9 8 5 | 4 3 6 | 7 2 1
. 4 2 | 5 7 . | . . 9     3 4 2 | 5 7 1 | 8 6 9
------+-------+------     ------+-------+------
2 . 8 | 3 1 4 | . . 5     2 . 8 | 3 1 4 | 6 9 5
4 . 9 | 7 5 8 | 2 1 3     4 6 9 | 7 5 8 | 2 1 3
. 5 3 | 9 6 2 | 4 8 7     1 5 3 | 9 6 2 | 4 8 7

Iteration 3

Before                    After
. . 1 | 6 4 5 | 9 7 2     8 3 1 | 6 4 5 | 9 7 2
5 9 7 | 2 8 3 | 1 4 6     5 9 7 | 2 8 3 | 1 4 6
6 2 4 | 1 9 7 | 3 5 8     6 2 4 | 1 9 7 | 3 5 8
------+-------+------     ------+-------+------
7 1 6 | 8 2 9 | 5 3 4     7 1 6 | 8 2 9 | 5 3 4
9 8 5 | 4 3 6 | 7 2 1     9 8 5 | 4 3 6 | 7 2 1
3 4 2 | 5 7 1 | 8 6 9     3 4 2 | 5 7 1 | 8 6 9
------+-------+------     ------+-------+------
2 . 8 | 3 1 4 | 6 9 5     2 7 8 | 3 1 4 | 6 9 5
4 6 9 | 7 5 8 | 2 1 3     4 6 9 | 7 5 8 | 2 1 3
1 5 3 | 9 6 2 | 4 8 7     1 5 3 | 9 6 2 | 4 8 7
```

The program stopped here since the game was complete.

# When the going gets tough

The techniques above will handle most easy and even moderately difficult puzzles iterating along until the puzzle is complete. But the really hard puzzles will get stuck somewhere. When people are doing such puzzles they will either give up or find some cells with just 2 possibilities each. Using a copy machine they will make 2 copies of the partially complete puzzle and having selected one of these cells (that looks particularly promising), write in the 2 values, one for each copy.

Now, assuming the solution to the puzzle is unique, one of these copies will eventually produce an error (since you put in a wrong value) but the other copy will very likely proceed to completion. Or perhaps it may need to be split again. I've only seen this happen once.

The split method in the Game class takes a partially complete puzzle and generates a cell with the fewest (usually just two) pvals. It then generates a new game for each pval (lines 11-15) and returns them in a list.

```01     def split(self) :
02         # make list of cells that still have mult pvals
03         b = filter(lambda x: len(x.pvals) > 1, self.cells)
04         c = list(b)
05         # sort list by length of pvals. Shortest to the front
06         c.sort(lambda x,y: cmp(len(x.pvals),len(y.pvals)))
07         kidgames = []
08         if c :
09             cell = c[0]   # take front most. It will be shortest
10             for val in cell.pvals :
11                 g = self.clone()         # completely independent
12                 cell = g.cells[cell.inx] # reach for the cloned cell
13                 cell.val = val           # hard set the value
14                 cell.pvals = set([val])  # and remove it from its pvals
15                 kidgames.append(g)
16         return kidgames
17
```

The use of filter in line 3 gets a list of empty cells. Notice the use of a custom comparison function for the sort in line 6. We're looking for cells with smallest pvals and moving them to the front of list c.

The call to Game.clone in line 11 leads to a call Python's copy.deepcopy method. This will return new game with all new parts. Without the "deep" new games would still reference the older existing cells resulting in chaos.

And here is test4.py that uses the method Game.split.

```01  import sys, sudoku
02  from sideBySide import sideBySide

03  def test4 () :
04      game = sudoku.Game(sys.argv[1])
05      before = game.display()
06      while game.iterate() : pass
07      after = game.display()
08      print "\n        Before                    After"
09      print sideBySide([before,after])
10      if game.valid() and not game.finished() :
11          print "This partial yet valid game splits into"
12          kids = game.split()
13          print sideBySide([after]+map(lambda x: x.display(), kids))
14      if not game.valid() :
15          print "This game is not valid and cannot be completed"

16  if __name__ == "__main__" : test4()
```

Here is a run on a fairly difficult puzzle. The game test4a.game was partially done manually but then I got stuck. The program takes over and also gets stuck and must split into two possible games.

```\$ python test4.py test4a.game

This partial yet valid game splits into

Before                    After
. . . | 4 6 5 | . . .     . . . | 4 6 5 | . . .
. . 2 | . . . | 1 . 6     . . 2 | . 9 . | 1 . 6
. 6 . | 2 . 1 | . 7 .     . 6 . | 2 . 1 | . 7 .
------+-------+------     ------+-------+------
7 . 4 | 9 1 . | 3 6 5     7 . 4 | 9 1 . | 3 6 5
9 . 1 | 6 5 3 | 7 . 4     9 . 1 | 6 5 3 | 7 . 4
3 5 6 | . 4 . | . 1 9     3 5 6 | . 4 . | . 1 9
------+-------+------     ------+-------+------
. 4 . | . . 6 | . 9 .     . 4 . | . . 6 | . 9 .
. 9 8 | . . 4 | 6 . .     . 9 8 | . . 4 | 6 . .
6 . . | 5 2 9 | . . .     6 . . | 5 2 9 | . . .

Since cell 1,1 has pval=(1,8) (why?) this partial solution can split into

1 . . | 4 6 5 | . . .     8 . . | 4 6 5 | . . . << Note the 1 and 8
. . 2 | . 9 . | 1 . 6     . . 2 | . 9 . | 1 . 6
. 6 . | 2 . 1 | . 7 .     . 6 . | 2 . 1 | . 7 .
------+-------+------     ------+-------+------
7 . 4 | 9 1 . | 3 6 5     7 . 4 | 9 1 . | 3 6 5
9 . 1 | 6 5 3 | 7 . 4     9 . 1 | 6 5 3 | 7 . 4
3 5 6 | . 4 . | . 1 9     3 5 6 | . 4 . | . 1 9
------+-------+------     ------+-------+------
. 4 . | . . 6 | . 9 .     . 4 . | . . 6 | . 9 .
. 9 8 | . . 4 | 6 . .     . 9 8 | . . 4 | 6 . .
6 . . | 5 2 9 | . . .     6 . . | 5 2 9 | . . .
```

Finally, test5.py is a fairly complete bit of code to explore a "tree of games" as necessary.

```01  import sys, sudoku
02  from sideBySide import sideBySide

03  def test5 () :
04      game = sudoku.Game(sys.argv[1])
05      explore(game)

06  def explore (game) :
07      before = game.display()
08      while game.iterate() : pass
09      after = game.display()
10      if not game.valid() :
11          print "\n        Before                    After   (Invalid)"
12          print sideBySide([before,after])
13          bad = [cell for cell in game.cells if cell.error > ""]
15          return
16      elif game.finished() :
17          print "\n        Before                    After   (Finished)"
18          print sideBySide([before,after])
19          return
20      else :
21          message = "Partial game splits"
22          kids = game.split()
23          displays = [kid.display() for kid in kids]
24          print "\n        Before                    After   (Splits into .... )"
25          print sideBySide([after]+displays)
26          for kid in kids :
27              explore(kid)

28  if __name__ == "__main__" : test5()
```

The function explore is recursive (line 27). Line 8 iterates until it's stuck. An invalid game will have at least one cell with an error message. Line 14 prints the first error and returns, abandoning any further exploration of this branch of tree. A finished game also is printed and we're done. At line 21 things are more interesting; the game splits into "n" new games that are then further explored.

Here's a run on the same game as in test 4:

```\$ python test5.py test5a.game

Before                    After   (Splits into .... )
. . . | 4 6 5 | . . .     1 . . | 4 6 5 | . . .     8 . . | 4 6 5 | . . .
. . 2 | . 9 . | 1 . 6     . . 2 | . 9 . | 1 . 6     . . 2 | . 9 . | 1 . 6
. 6 . | 2 . 1 | . 7 .     . 6 . | 2 . 1 | . 7 .     . 6 . | 2 . 1 | . 7 .
------+-------+------     ------+-------+------     ------+-------+------
7 . 4 | 9 1 . | 3 6 5     7 . 4 | 9 1 . | 3 6 5     7 . 4 | 9 1 . | 3 6 5
9 . 1 | 6 5 3 | 7 . 4     9 . 1 | 6 5 3 | 7 . 4     9 . 1 | 6 5 3 | 7 . 4
3 5 6 | . 4 . | . 1 9     3 5 6 | . 4 . | . 1 9     3 5 6 | . 4 . | . 1 9
------+-------+------     ------+-------+------     ------+-------+------
. 4 . | . . 6 | . 9 .     . 4 . | . . 6 | . 9 .     . 4 . | . . 6 | . 9 .
. 9 8 | . . 4 | 6 . .     . 9 8 | . . 4 | 6 . .     . 9 8 | . . 4 | 6 . .
6 . . | 5 2 9 | . . .     6 . . | 5 2 9 | . . .     6 . . | 5 2 9 | . . .

First Child
Before                    After   (Invalid)
1 . . | 4 6 5 | . . .     1 7 9 | 4 6 5 | 8 2 .
. . 2 | . 9 . | 1 . 6     8 3 2 | 7 9 . | 1 . 6
. 6 . | 2 . 1 | . 7 .     4 6 5 | 2 8 1 | 9 7 3
------+-------+------     ------+-------+------
7 . 4 | 9 1 . | 3 6 5     7 8 4 | 9 1 2 | 3 6 5
9 . 1 | 6 5 3 | 7 . 4     9 2 1 | 6 5 3 | 7 8 4
3 5 6 | . 4 . | . 1 9     3 5 6 | 8 4 7 | 2 1 9
------+-------+------     ------+-------+------
. 4 . | . . 6 | . 9 .     2 4 7 | 8 3 6 | 5 9 1
. 9 8 | . . 4 | 6 . .     5 9 8 | 1 7 4 | 6 3 2
6 . . | 5 2 9 | . . .     6 1 3 | 5 2 9 | 4 8 8

(1,1)=1 Not all values 1-9 possible in              << Here's why
[(1,2)=7, (1,3)=9, (1,4)=4, (1,5)=6, (1,6)=5, (1,7)=8, (1,8)=2, (1,9)=0]

Second Child
Before                    After   (Finished)
8 . . | 4 6 5 | . . .     8 1 7 | 4 6 5 | 9 3 2
. . 2 | . 9 . | 1 . 6     5 3 2 | 8 9 7 | 1 4 6
. 6 . | 2 . 1 | . 7 .     4 6 9 | 2 3 1 | 5 7 8
------+-------+------     ------+-------+------
7 . 4 | 9 1 . | 3 6 5     7 2 4 | 9 1 8 | 3 6 5
9 . 1 | 6 5 3 | 7 . 4     9 8 1 | 6 5 3 | 7 2 4
3 5 6 | . 4 . | . 1 9     3 5 6 | 7 4 2 | 8 1 9
------+-------+------     ------+-------+------
. 4 . | . . 6 | . 9 .     1 4 5 | 3 8 6 | 2 9 7
. 9 8 | . . 4 | 6 . .     2 9 8 | 1 7 4 | 6 5 3
6 . . | 5 2 9 | . . .     6 7 3 | 5 2 9 | 4 8 1
```

If line 4 is changed to ask for tracking, we'll get a line for each cell that is set. This is between the displays we've seen so far and looks like

```Exploring split possibility 1
Set (1,3) to 9
Set (2,1) to 8
Set (3,1) to 4
Set (3,3) to 5
Set (3,5) to 8
Set (3,7) to 9
Set (3,9) to 3
Set (6,6) to 7
Set (6,7) to 2
Set (7,7) to 5
Set (8,4) to 1
Set (9,2) to 1
Set (9,7) to 4
Set (1,2) to 7
Set (1,7) to 8
Set (1,8) to 2

Before                    After   (Invalid)
1 . . | 4 6 5 | . . .     1 7 9 | 4 6 5 | 8 2 .
. . 2 | . 9 . | 1 . 6     8 . 2 | . 9 . | 1 . 6
. 6 . | 2 . 1 | . 7 .     4 6 5 | 2 8 1 | 9 7 3
------+-------+------     ------+-------+------
7 . 4 | 9 1 . | 3 6 5     7 . 4 | 9 1 . | 3 6 5
9 . 1 | 6 5 3 | 7 . 4     9 . 1 | 6 5 3 | 7 . 4
3 5 6 | . 4 . | . 1 9     3 5 6 | . 4 7 | 2 1 9
------+-------+------     ------+-------+------
. 4 . | . . 6 | . 9 .     . 4 . | . . 6 | 5 9 .
. 9 8 | . . 4 | 6 . .     . 9 8 | 1 . 4 | 6 . .
6 . . | 5 2 9 | . . .     6 1 . | 5 2 9 | 4 . .
```

You can download the project from sudoku.zip and just expand it into an empty directory. Run the tests like above. Look at the remaining methods (all are simple) in sudoku.py and, of course, add your own ideas.

# Testing the Installation

A little test script will run each of the programs above and sumcheck the output. They should match the runs in the test directory.

```\$ ./testall.sh
41006     1
31166     1
47453     2
26167     2
47837     3

\$ sum test/*.out
41006     1 test/test1a.out
31166     1 test/test2a.out
47453     2 test/test3a.out
26167     2 test/test4a.out
47837     3 test/test5a.out
```

This is also useful if you are making changes the code. Differences in the sums should appear only where you expect them to. And, of course, the unix utility diff can be used to chase those down. Have Fun !

If you have comments or suggestions You can email me at mail me