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.
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.
In addition, this code is carefully written to run on both Python 2 and Python 3. To do this a few small changes were made.
The keyword "print" in Python 2 is a statement but in Python 3 it is a function. Its use in this code is always looks like the function but there's a trick.
- Python 3: print(4,5,6) outputs "4 5 6"
- Python 2: print(4,5,6) outputs "(4,5,6)" as a tuple
- Python print("%s %s %s" % (4,5,6)) outputs "4 5 6" for both versions. (note a single string)All prints here use the last form. It works because Python 2 does not see a single value enclosed in parens as a tuple unless the value is followed by a comma.
Secondly, functions like range, map, filter and others return lists in Python 2 but iterators in Python 3. This is fine if the code processes results sequentially. But if the results need to be sorted or otherwise accessed non-sequentially the results need to be a list. So you will see things like list(range(20)) which works for either Python version.
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. For printing purposes we convert sets to tuples. Two diffent notations are used. Python 2 prints a set like set([1,2,3]), but Python 3 prints it as {1,2,3}. Often we want to automatically compare output from both Pythons and they need the same representation.
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.
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 # Show off the neighbors
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.
Let's play with this a bit:
>>> from sudoku import Cell
>>>
>>> mycell = Cell(15) # Provide the cell number
>>> print(mycell) # NOTE: you may drop the parens if using Python 2.
(2,7)=0
>>> print(mycell.row, mycell.col)
1 6 *or (1,6) if Python 2*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 a pvals set 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. This 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.
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.)
1 import sys
2 from sudoku import Game, Cell
3 from sideBySide import sideBySide
4
5 def test2 () :
6 "Set up a dual set and show effects"
7 game = Game(sys.argv[1])
8 tagged = game.getTagged()
9 tags=tagged.keys(); tags.sort()
10 before = game.display()
11 for tag in tags :
12 cell = tagged[tag]
13 print(" %s %s %s" % (tag, cell, cell.pvals))
14 cell.update_pvals(game.cells)
15 print(" %s %s %s" % (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()
22Our 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
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 | . . .
. . . | . . . | . . . . . . | . . . | . . .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. You can download sudoku.py
23 def update_pvals(self, cells) :
24 allvals = set([1,2,3,4,5,6,7,8,9]); self.error = ""
25 for friends in (self.sameBox,self.sameRow,self.sameCol) :
26 discards = {} # what may be removed from self.pvals
27 grpvals = set([]) # as a group what vals are possible
28 friends = map(lambda x: cells[x], friends) # list of cell objs
29 for other in friends :
30 key = tuple(other.pvals) # its possible value(s)
31 discards[key] = discards.get(key,0) + 1
32 grpvals.update(other.pvals)
33 if grpvals.union(self.pvals) != allvals :
34 self.error = "Not all values 1-9 possible in %s" % friends
35 return False
36 uncovered = allvals.difference(grpvals)
37 if len(uncovered) == 1 : # only possibility
38 self.pvals = uncovered
39 else :
40 for key in discards.keys() :
41 if len(key) == discards[key] :
42 for used in key :
43 self.pvals.discard(used)
44 if len(self.pvals) == 1 :
45 self.val=tuple(self.pvals)[0]
46 return True
47This method works on a single cell self and tries to reduce self.pvals. The for loop in line 25 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 26-27). The keys of discards are tuples made from others pvals. The discards values are counts of common pvals sets (line 31). Supposing we had this during computation:
>>> print discards
{ (8,): 1, (5,6): 2, (4,3,2): 2 }From this 8, 5 and 6 can be discarded from self.pvals a bit later (line 40-43). But we can't do anything (yet) with 4, 3 and 2. The is one 8 already already among the friends and there are two with the pair 5 and 6. These can be be removed our cell's pvals.
The other way to affect self.pvals is done using the grpvals set. grpvals contains values possible in the other cells (line 32). And together with self.pvals they should cover all values 1 to 9. (line 33-34). And when only one value is missing, that reduces self.pvals to that single entry. (lines 36-38).
In that case, in line 44, self.value is set to this unique possibility and the method returns True for success.
The next step is easier. Each cell gets the opportunity update its pvals set and perhaps set its final value. The order we visit the cells is arbitrary. To keep it simple we'll start at the top left and work across and down to the bottom right.
# sudoku.py
117 def iterate(self) :
118 changed = False
119 for cell in self.cells :
120 earlier = cell.pvals.copy()
121 cell.update_pvals(self.cells)
122 if cell.error :
123 self.error = cell.error
124 return changed
125 if cell.pvals != earlier :
126 changed = True
127 if self.track and len(cell.pvals) == 1 :
128 print("Set (%s,%s) to %s" % (
129 cell.row+1,cell.col+1,list(cell.pvals)[0]))
130 return changed
131If any cell is updated then the board has changed (line 126). If any cell update results in an error, the board itself is in error False is returned (line 124). 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 128)
If the board is returned unchanged (line 130) 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.
1 import sys, sudoku
2 from sideBySide import sideBySide
3
4 def test3 () :
5 game = sudoku.Game(sys.argv[1])
6 sweep = 1
7 before = game.display()
8 while not game.finished() :
9 game.iterate()
10 if game.error :
11 print(game.error)
12 break
13 else :
14 after = game.display()
15 print(" Iteration %s" % sweep)
16 print("\n Before After")
17 print(sideBySide([before,after]))
18 before = after
19 sweep += 1
20
21 if __name__ == "__main__" : test3()
22At 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 7The program stopped here since the game was complete.
The techniques above will handle most of the easy and even moderately difficult puzzles, iterating until the puzzle is complete. But the really hard puzzles will often get stuck somewhere. When people are doing such puzzles they will either give up or find a cell with exactly 2 possibilities. Using a copy machine they will make 2 copies of the partially complete puzzle. The fill the cell on one copy with the first possibility and the other copy with the second.
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.
# sudoku.py
100 def split(self) :
101 # make list of cells that still have mult pvals
102 b = filter(lambda x: len(x.pvals) > 1, self.cells)
103 c = list(b)
104 # sort list by length of pvals. Shortest to the front
105 c.sort(lambda x,y: cmp(len(x.pvals),len(y.pvals)))
106 kidgames = []
107 if c :
108 cell = c[0] # take front most. It will be shortest
109 for val in cell.pvals :
110 g = self.clone() # completely independent
111 cell = g.cells[cell.inx] # reach for the cloned cell
112 cell.val = val # hard set the value
113 cell.pvals = set([val]) # and remove it from its pvals
114 kidgames.append(g)
115 return kidgames
116The use of filter in line 102 gets a list of empty cells. Notice the use of a custom comparison function for the sort in line 105. We're looking for cells with smallest pvals and moving them to the front of list c.
The call to Game.clone in line 110 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.
# test4.py
1 import sys, sudoku
2 from sideBySide import sideBySide
3
4 def test4 () :
5 game = sudoku.Game(sys.argv[1])
6 before = game.display()
7 while game.iterate() : pass
8 after = game.display()
9 print("\n Before After")
10 print(sideBySide([before,after]))
11 if game.valid() and not game.finished() :
12 print("This partial yet valid game splits into")
13 kids = game.split()
14 print(sideBySide([after]+map(lambda x: x.display(), kids)))
15 if not game.valid() :
16 print("This game is not valid and cannot be completed")
17
18 if __name__ == "__main__" : test4()
19Here 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.
1 import sys, sudoku
2 from sideBySide import sideBySide
3
4 def test5 () :
5 game = sudoku.Game(sys.argv[1])
6 explore(game)
7
8 def explore (game) :
9 before = game.display()
10 while game.iterate() : pass
11 after = game.display()
12 if not game.valid() :
13 print("\n Before After (Invalid)")
14 print(sideBySide([before,after]))
15 bad = [cell for cell in game.cells if cell.error > ""]
16 print("%s %s" % (bad[0], bad[0].error))
17 return
18 elif game.finished() :
19 print("\n Before After (Finished)")
20 print(sideBySide([before,after]))
21 return
22 else :
23 print("Partial game must be split")
24 kids = game.split()
25 displays = [kid.display() for kid in kids]
26 print("\n Before After (Splits into .... )")
27 print(sideBySide([after]+displays))
28 poss = 0
29 for kid in kids :
30 poss += 1
31 print("\nExploring split possibility %s" % poss)
32 explore(kid)
33
34 if __name__ == "__main__" : test5()
35The function explore is recursive (line 32). Line 10 iterates until it's stuck. An invalid game will have at least one cell with an error message. Line 16 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 23 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 1If 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.
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.outThis 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
Copyright © 2016-2021 Chris Meyers and Fred Obermann
* * *