Sudoku. The Basics

Sudoku is a one player game (or puzzle) that rapidly became popular around the world about 10 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 should be quite straight-forward although it does use 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 and if not lots of on-line documentation is 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. Near the end we will see how the project could also efficiently use bit-wise logical operators on integers to perform the equivalent computation, but probably with less readability. This would be attractive in a language without sets built-in or where 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.

A game is mostly a list of cells along with methods to take input from a text file and (pythonically) output a display in exactly the same format. It also handles iterations of changes to the cells as the game proceeds. A cell 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 the cell tagged with an a belongs to the row whose cells are tagged with an r, to the column whose cells are tagged with a c and to the box whose cells are tagged with a b. Actually 2 cells below a also belong to its column and two cells to the right of a also belong to its row:

$ 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 gets attributes for its number (0,80), row and column (0-8), a value val (1-9) or a set of possible values pvals. An empty cell takes the value 0. An occupied cell has a value 1-9. The attributes also include 3 lists for sameRow, sameCol and sameBox with the cell numbers of the appropriate neighbors as seen above. Keeping these lists 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
>>> 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 method Cell.__str__ will print the row and column as well as the value of the cell. As mentioned an empty cell will contain the value zero. The cell's row and column are output starting at one (not zero), which is easier for human readers to relate to the visual representation. But internally, the rows and columns start at zero.

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 these sets steadily decreases. Initially, for every cell every value 1-9 is considered a possibility. The method Cell.update_pvals trims this down 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 simply makes it easier to set up the small demos that follow.

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 obvious and what it does is even more so.

import sys
from sudoku import Game, Cell
from sideBySide import sideBySide

def test2 () :
    "Set up a dual set and show effects"
    game = Game(sys.argv[1])
    tagged = game.getTagged()
    tags=tagged.keys(); tags.sort()
    before = game.display()
    for tag in tags :
        cell = tagged[tag]
        print " ", tag, cell, cell.pvals
        cell.update_pvals(game.cells)
        print " ", tag, cell, cell.pvals

    after = game.display()
    print "\n        Before                    After"
    print sideBySide(before,after)

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. The 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 the are processed alphabetically, d is done last. Cells a, b, c will each lose 1 to 6 from their pvals since they 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, 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 available. The code sees the same thing somewhat differently. 8 of 9 cells in the box lose the 7 from their pval 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.

$ python test2.py test2c.game
a (4,4)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
a (4,4)=0 set([1, 2, 3, 4, 5, 6, 8, 9])
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])
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])
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. 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])
b (5,7)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
b (5,7)=0 set([6, 7])
c (5,9)=0 set([1, 2, 3, 4, 5, 6, 7, 8, 9])
c (5,9)=0 set([6, 7])
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

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 dictionary discards will contain a count of common pvals found in the friends and if that count equals the length of the common pval, these values may be discarded from self.pvals. The set grpvals is a set of values 1 to 9 that must be covered by the entity (row, col, box) and if any value is missing the sudoku layout is corrupt and an error is set in line 12. If just one value is missing, then self.pvals is assigned to this set (of 1 element). Otherwise the values found in discards keys (tuples of values 1-9) have been used or reserved by other cells in the entity (row,column,box) and can be discarded from self.pvals, if they are still present. Finally, if self.pvals has been reduced to a single element, it is assigned to the cells value. The method returns True if no error was encountered.

Updating cells iteratively

You may well have seen the next step coming. We play the board in rounds, looking at each cell and updating it pvals set. The order we work 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.

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

    # test3.py
    #  update all iteratively until no changes happen
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(10) :
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()

We save a printable version of the game in before. For a maximum of 10 times (safety) 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

    # test4.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
. 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 | . . .

This partial yet valid game 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 | . . .

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 gets the empty cells. List comprehension could also be used here and perhaps would be preferable. Also notice the use of a custom comparison function for the sort in line four. That may be new for you. These are all well documented elsewhere. (google)

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

    # test5.py
    #
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
  [(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

A simple alternative to using sets

Since the Python sets are used in this project just to represent a group of values from zero to nine they can be represented nicely by bits set in a (binary) integer. Below I'm using Python's 0b mode to input numbers in binary in order to show off their bits.

We want to set up some lookup dictionaries. A pvals set will be represented with an integer and the possibilities as bits set in the integer. So a pvals set of (1,3,4) would correspond to 0b000001101, or decimal 13. I'm calling these bit-sets. The operations we used above (union, difference and discard) are easily replicated in our new bit-sets.

  • union is simply the arithmetic OR of 2 bit-sets
  • difference of two bit-sets (b-a) would be b & ~a (b and not a)
  • discarding a value x from bit-set b with arithmetic AND b & valClear(x)
  • does a bit-set have just a single possibility? It does if its integer value is a key in bit2val

One might argue that using dictionaries is no more efficient than using sets. But in this case where the possible values are very small, the dictionaries could be replaced by sparsely populated 512 element arrays with direct lookups. In C that would be inexpensive and lightning fast.

bit2val = {
    0b000000001: 1, 0b000000010: 2, 0b000000100: 3,
    0b000001000: 4, 0b000010000: 5, 0b000100000: 6,
    0b001000000: 7, 0b010000000: 8, 0b100000000: 9,
}

val2bit= {
    1: 0b000000001, 2: 0b000000010, 3: 0b000000100,
    4: 0b000001000, 5: 0b000010000, 6: 0b000100000,
    7: 0b001000000, 8: 0b010000000, 9: 0b100000000,
}

valClear= {
    1: 0b111111110, 2: 0b111111101, 3: 0b111111011,
    4: 0b111110111, 5: 0b111101111, 6: 0b111011111,
    7: 0b110111111, 8: 0b101111111, 9: 0b011111111,
}

allvals = 0b111111111

Copyright © 2016 Chris Meyers

.