Sudoku. The Basics

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 9 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 the context it is in along with 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. Near the end we'll look at how the project could also efficiently use bit-wise logical operators on integers to perform the equivalent computation, but probably resulting in less readable code. This could be attractive in a language without built-in sets or where very high speed in important.

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 human reading. 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 every cell every value 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 using them does make it easier to create the small demos.

Interaction of 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 is just 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 enables even 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)
09                discards[key] = discards.get(key,0) + 1
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 :
21                            self.pvals.discard(used)
22            if len(self.pvals) == 1 :
23                self.val=tuple(self.pvals)[0]
24        return True

---------------- work on this some more

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 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 the grpvals set.*grpvals* contains values possible in the other cells (line 10). And together self.pvals they should cover all values 1 to 9. (line 11-13). And with self.pvals if there is only one value 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 iterate over 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.

If after completing an iteration no changes occurred, we are done. Yet another iteration would also produce no changes. Here's the program test3.py which does exactly this.

01  import sys, sudoku
02  from sideBySide import sideBySide

03  def test3 () :
04      game = sudoku.Game(sys.argv[1])
05      before = game.display()
06      for iter in range(100) :
07          changed = error = False
08          for cell in game.cells[:] :
09              earlier = cell.pvals.copy()
10              if not cell.update_pvals(game.cells) :
11                  print cell, cell.error
12                  error = True
13                  break
14              if cell.pvals != earlier :
15                  changed = True
16          if not changed : break
17          after = game.display()
18          print "  Iteration", iter+1
19          print "\n        Before                    After"
20          print sideBySide([before,after])
21          before = after
22          if error : break
23  if __name__ == "__main__" : test3()

At line 5 we save a printable version of the game in before. For a maximum of 100 times (sanity check) we do an iteration, working through the cells and keeping tracked if anything was changed or if an error was discovered.

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 fourth iteration produced no changes since the game was complete

When the going gets tough

The techniques above will handle most easy and 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.

So, test4.py is the code that will do this. It's time now also to look at more closely at the class Game in sudoku.py . We'll discuss some it's less obvious parts below. For now note that the method iterate has been pulled from test3.py

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 iterates four times before zeroing in on the cell (2,5) and setting it to the value 9. (why?). But then it also gets stuck and must split into two possible games.

$ python test4.py test4a.game

      Before                    After
. . . | 4 6 5 | . . .     . . . | 4 6 5 | . . .
. . 2 | . . . | 1 . 6     . . 2 | . 9 . | 1 . 6  << note the 9
. 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 | . . .

The Game.split method is:

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

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

The call to Game.clone in line 9 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.

Finally, test5.py is a fairly complete bit of code to explore a "tree of games" if necessary. This could also be pulled into the Game class as a method. But for our purposes it's fine as it is.

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 > ""]
14          print bad[0], bad[0].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 | . . .


      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]

      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

You can download the project from sudoku.zip and just expand it into an empty directory.

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

Copyright © 2016-2018 Chris Meyers

.