Sudoku: One More Thing ...
Is this a game of Sudoku, or a game of Columbo? I keep finding things to do! Fewer classes, a bit more clear … but a few more lines of code.
I really enjoy working with code. Some folks work with paint, some with clay, and I work with code. I enjoy making it do things, and I enjoy reshaping it, generally to forms I consider “better”, but sometimes just to find out what happens.
If I were programming for a living, I would probably not have the time to do quite as much code improvement as I do here, though most of the changes I make are a matter of seconds, and the series I undertake rarely require even an hour of continuous changing. Certainly I try to commit almost every time my tests run green, and I know that if I’ve gone 20 minutes unable to commit, I am probably digging a hole and should revert and start again. Or back away slowly …
That said, these exercises mean that I become better able to spot questionable code, and have better ideas about small steps to make things better. So this kind of practice would be eminently useful in a real programming situation.
But yes: I do this because I enjoy it. I tell myself that my reader, or perhaps even both of them, might enjoy what they see, might get some useful ideas, and might, at least, use me as a bad example of what can happen to a perfectly good boy who falls in with bad companions.
Components: Row, Column, SubGrid
Today I propose to look at the Component and its subclasses, because I think we can do better. Here’s the code. Have a look and then we’ll discuss it.
class Component():
def __iter__(self):
return iter(self.used)
@property
def used_numbers(self):
return [c for c in self.used if c != '0']
@property
def is_valid(self):
for c in '123456789':
if c not in self.used:
return False
return True
class Row(Component):
def __init__(self, puzzle, position):
start = position - position % puzzle.line_size
self.used = puzzle.game[start:start + puzzle.line_size]
class Column(Component):
def __init__(self, puzzle, position):
start = position % puzzle.line_size
self.used = puzzle.game[start:len(puzzle.game):puzzle.line_size]
class SubGrid(Component):
def __init__(self, puzzle, position):
starting_row_of_sub_grid = position - position % (3*puzzle.line_size)
offset_in_row = position % 9 // 3 * 3
first_index_in_sub_grid = starting_row_of_sub_grid + offset_in_row
result = []
if puzzle.line_size == 9:
for row_index in range(3):
cell = first_index_in_sub_grid + row_index*9
result.extend(puzzle.game[cell:cell+3])
self.used = result
If I were to write a docstring for these classes, they might go something like this:
class Row(Component):
"""
Given a Sudoku puzzle and a position in it,
return a Row object that can provide a list of
the values 0-9 currently used in that row.
"""
def __init__(self, puzzle, position):
start = position - position % puzzle.line_size
self.used = puzzle.game[start:start + puzzle.line_size]
We use these objects in a few places. Row has 13 uses in tests and three in actual use:
# puzzle.py
from component import Row, Column, SubGrid
...
class Puzzle:
@property
def rows(self):
return [Row(self, row) for row in range(0, 81, 9)]
def possible_answers(self, position=None):
if position is None:
position = self.guess_position
row = Row(self, position)
column = Column(self, position)
sub_grid = SubGrid(self, position)
return [c for c in self.available_values if c not in row and c not in column and c not in sub_grid]
The first usage is part of validation, where we get all the rows, columns, and sub-grids and check them all for containing 9 elements and values one through nine.
And the second, as you might guess, is computing the possible values that can go into a given position. This is part of the solving: we find a position with no assigned value, get a list of possible values, and try the sequentially, recursively creating a new, more complete game, and trying to solve it.
Issues
As we look at these three classes and their superclass, there are issues that we might notice:
- They each fetch cell values from the puzzle, based on the position being checked.
- They all initialize
usedto contain those values. - The
usedcollections all get checked the same way, in Component. - They get increasingly arcane: the row’s indices are easy, the column’s kind of make sense, and what in the world is happening with the sub-grid?
What might we work toward to improve this little cluster of classes? Well …
- We could try to have just one class, Component, with three factory methods,
row,column, andsub_grid. - We could try to make it more clear how we select the cells, especially those sub-grid ones.
- Instead of three places to fetch the values, we could work to have just one.
Let me elaborate that last idea in case my mumbling wasn’t clear: Currently each subclass fetches the actual values and puts them into used:
class Row(Component):
def __init__(self, puzzle, position):
start = position - position % puzzle.line_size
self.used = puzzle.game[start:start + puzzle.line_size]
class Column(Component):
def __init__(self, puzzle, position):
start = position % puzzle.line_size
self.used = puzzle.game[start:len(puzzle.game):puzzle.line_size]
class SubGrid(Component):
def __init__(self, puzzle, position):
starting_row_of_sub_grid = position - position % (3*puzzle.line_size)
offset_in_row = position % 9 // 3 * 3
first_index_in_sub_grid = starting_row_of_sub_grid + offset_in_row
result = []
if puzzle.line_size == 9:
for row_index in range(3):
cell = first_index_in_sub_grid + row_index*9
result.extend(puzzle.game[cell:cell+3])
self.used = result
Each of those is computing a list of nine values. Two of them slice (one in steps of one and one in steps of 9 (for a real game)). And one is just flat weird.
If we could easily compute the indices of the values we need, we could have our different inits store those and have the shared Component code fetch the values before checking, removing just a bit of duplication.
Anyway, that’s what I meant.
Let’s see about creating those factory methods. I think it’s easy:
class Component:
@classmethod
def row(cls, puzzle, position):
return Row(puzzle, position)
Python is happy enough with that code, so now I can replace references to Row with Component.row, for example like this:
@property
def rows(self):
return [Component.row(self, row) for row in range(0, 81, 9)]
That runs the tests. Commit it, I like where this is going: refactoring away from Row, Column, SubGrid classes.
Let’s do Column and SubGrid similarly. After some chainsaw editing, the job is done. There are no references to Row, Column, or SubGrid outside the component file.
Commit: remove all external references to Row, Column, SubGrid, using class methods instead.
Now we can work internally to the component file to clean things up and remove those classes:
class Component:
@classmethod
def row(cls, puzzle, position):
return Row(puzzle, position)
@classmethod
def column(cls, puzzle, position):
return Column(puzzle, position)
@classmethod
def sub_grid(cls, puzzle, position):
return SubGrid(puzzle, position)
def __iter__(self):
return iter(self.used)
@property
def used_numbers(self):
return [c for c in self.used if c != '0']
@property
def is_valid(self):
for c in '123456789':
if c not in self.used:
return False
return True
class Row(Component):
"""
Given a Sudoku puzzle and a position in it,
return a Row object that can provide a list of
the values 0-9 currently used in that row.
"""
def __init__(self, puzzle, position):
start = position - position % puzzle.line_size
self.used = puzzle.game[start:start + puzzle.line_size]
class Column(Component):
def __init__(self, puzzle, position):
start = position % puzzle.line_size
self.used = puzzle.game[start:len(puzzle.game):puzzle.line_size]
class SubGrid(Component):
def __init__(self, puzzle, position):
starting_row_of_sub_grid = position - position % (3*puzzle.line_size)
offset_in_row = position % 9 // 3 * 3
first_index_in_sub_grid = starting_row_of_sub_grid + offset_in_row
result = []
if puzzle.line_size == 9:
for row_index in range(3):
cell = first_index_in_sub_grid + row_index*9
result.extend(puzzle.game[cell:cell+3])
self.used = result
We can just move the code from each init into the corresponding class method and return an instance of the class, like this:
class Component:
def __init__(self, start, used):
self.start = start
self.used = used
@classmethod
def row(cls, puzzle, position):
start = position - position % puzzle.line_size
used = puzzle.game[start:start + puzzle.line_size]
return cls(start, used)
That works. Remove Row class. Still green. Commit: remove Row class.
Do the other two the same way. Pause between them to commit.
We now have this in Component:
class Component:
def __init__(self, start, used):
self.start = start
self.used = used
@classmethod
def row(cls, puzzle, position):
start = position - position % puzzle.line_size
used = puzzle.game[start:start + puzzle.line_size]
return cls(start, used)
@classmethod
def column(cls, puzzle, position):
start = position % puzzle.line_size
used = puzzle.game[start:len(puzzle.game):puzzle.line_size]
return cls(start, used)
@classmethod
def sub_grid(cls, puzzle, position):
starting_row_of_sub_grid = position - position % (3*puzzle.line_size)
offset_in_row = position % 9 // 3 * 3
start = starting_row_of_sub_grid + offset_in_row
result = []
if puzzle.line_size == 9:
for row_index in range(3):
cell = start + row_index*9
result.extend(puzzle.game[cell:cell+3])
used = result
return cls(start, used)
def __iter__(self):
return iter(self.used)
@property
def used_numbers(self):
return [c for c in self.used if c != '0']
@property
def is_valid(self):
for c in '123456789':
if c not in self.used:
return False
return True
We’re down to one class. I am not at all fond of the sub_grid method, and I find the slices in the other two class methods aren’t really communicating well.
It’s worth reminding ourselves that our tests sometimes use a puzzle size of 3x3, so these methods need to deal with puzzles of size 3x3 or 9x9.
What is the definition of a row? In a 9x9, it starts at position 0, or 9, or 18 … and then continues by a step size of 1:
0 1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16 17
That sort of thing. What if we made that explicit, maybe like this:
@classmethod
def row(cls, puzzle, position):
steps = [0, 1, 2, 3, 4, 5, 6, 7, 8]
steps = steps[0:puzzle.line_size]
start = position - position % puzzle.line_size
indices = (start + step for step in steps)
used = [puzzle.game[index] for index in indices]
return cls(start, used)
That’s green. I’m planning to do the used calculation in __init__, but this will do for now. Let’s see if the explicit steps idea makes the column and sub-grid more clear. Of course it’s sub-grid that I’m really after.
Commit this: refactoring. And then:
@classmethod
def column(cls, puzzle, position):
if puzzle.line_size == 9:
steps = [0, 9, 18, 27, 36, 45, 54, 63, 72]
else:
steps = [0, 3, 6]
start = position % puzzle.line_size
indices = [start + step for step in steps]
used = [puzzle.game[index] for index in indices]
return cls(start, used)
We’re getting lots of nice juicy duplication. Green, commit: refactoring.
Now about sub-grid:
@classmethod
def sub_grid(cls, puzzle, position):
starting_row_of_sub_grid = position - position % (3*puzzle.line_size)
offset_in_row = position % 9 // 3 * 3
start = starting_row_of_sub_grid + offset_in_row
result = []
if puzzle.line_size == 9:
for row_index in range(3):
cell = start + row_index*9
result.extend(puzzle.game[cell:cell+3])
used = result
return cls(start, used)
Now I want to do something that will seem silly. No, let’s first see if we can just generate the indices instead of the data.
Just doing as we have done:
@classmethod
def sub_grid(cls, puzzle, position):
if puzzle.line_size != 9:
steps = []
else:
steps = [0, 1, 2, 9, 10, 11, 18, 19, 20]
starting_row_of_sub_grid = position - position % (3*puzzle.line_size)
offset_in_row = position % 9 // 3 * 3
start = starting_row_of_sub_grid + offset_in_row
indices = [start + step for step in steps]
used = [puzzle.game[index] for index in indices]
return cls(start, used)
If size isn’t nine, we return no values, so an empty steps will accomplish just that.
This is green. Commit: refactoring. Now I want to do something that will seem silly. No, not yet. We have duplication to remove:
class Component:
def __init__(self, puzzle, start, steps):
self.start = start
indices = (start + step for step in steps)
self.used = [puzzle.game[index] for index in indices]
@classmethod
def row(cls, puzzle, position):
steps = [0, 1, 2, 3, 4, 5, 6, 7, 8]
steps = steps[0:puzzle.line_size]
start = position - position % puzzle.line_size
return cls(puzzle, start, steps)
@classmethod
def column(cls, puzzle, position):
if puzzle.line_size == 9:
steps = [0, 9, 18, 27, 36, 45, 54, 63, 72]
else:
steps = [0, 3, 6]
start = position % puzzle.line_size
return cls(puzzle, start, steps)
@classmethod
def sub_grid(cls, puzzle, position):
if puzzle.line_size != 9:
steps = []
else:
steps = [0, 1, 2, 9, 10, 11, 18, 19, 20]
starting_row_of_sub_grid = position - position % (3*puzzle.line_size)
offset_in_row = position % 9 // 3 * 3
start = starting_row_of_sub_grid + offset_in_row
return cls(puzzle, start, steps)
Green. Let’s make those look more similar now that we see them all at once:
class Component:
def __init__(self, puzzle, start, steps):
self.start = start
indices = (start + step for step in steps)
self.used = [puzzle.game[index] for index in indices]
@classmethod
def row(cls, puzzle, position):
if puzzle.line_size == 9:
steps = [0, 1, 2, 3, 4, 5, 6, 7, 8]
else:
steps = [0, 1, 2]
steps = steps[0:puzzle.line_size]
start = position - position % puzzle.line_size
return cls(puzzle, start, steps)
@classmethod
def column(cls, puzzle, position):
if puzzle.line_size == 9:
steps = [0, 9, 18, 27, 36, 45, 54, 63, 72]
else:
steps = [0, 3, 6]
start = position % puzzle.line_size
return cls(puzzle, start, steps)
@classmethod
def sub_grid(cls, puzzle, position):
if puzzle.line_size == 9:
steps = [0, 1, 2, 9, 10, 11, 18, 19, 20]
else:
steps = []
starting_row_of_sub_grid = position - position % (3*puzzle.line_size)
offset_in_row = position % 9 // 3 * 3
start = starting_row_of_sub_grid + offset_in_row
return cls(puzzle, start, steps)
Green. Commit again.
Now for something silly. I’m after that obscure code in sub_grid, which I wrote and do not understand. I have created this amusing array:
starts = [
0, 0, 0, 3, 3, 3, 6, 6, 6,
0, 0, 0, 3, 3, 3, 6, 6, 6,
0, 0, 0, 3, 3, 3, 6, 6, 6,
27, 27, 27, 30, 30, 30, 33, 33, 33,
27, 27, 27, 30, 30, 30, 33, 33, 33,
27, 27, 27, 30, 30, 30, 33, 33, 33,
54, 54, 54, 57, 57, 57, 60, 60, 60,
54, 54, 54, 57, 57, 57, 60, 60, 60,
54, 54, 54, 57, 57, 57, 60, 60, 60,
]
That array provides the starting position of the sub-grid corresponding to each position in the array. For each position, it contains the same value that we’re setting to start in the obscure calculations above. Let’s see if we can pick the value more clearly than what we have.
So isn’t start just the value from that array at position?
@classmethod
def sub_grid(cls, puzzle, position):
starts = [
0, 0, 0, 3, 3, 3, 6, 6, 6,
0, 0, 0, 3, 3, 3, 6, 6, 6,
0, 0, 0, 3, 3, 3, 6, 6, 6,
27, 27, 27, 30, 30, 30, 33, 33, 33,
27, 27, 27, 30, 30, 30, 33, 33, 33,
27, 27, 27, 30, 30, 30, 33, 33, 33,
54, 54, 54, 57, 57, 57, 60, 60, 60,
54, 54, 54, 57, 57, 57, 60, 60, 60,
54, 54, 54, 57, 57, 57, 60, 60, 60,
]
if puzzle.line_size == 9:
steps = [0, 1, 2, 9, 10, 11, 18, 19, 20]
else:
steps = []
start = starts[position]
return cls(puzzle, start, steps)
Yes. Green. And starts should be a class variable, so we wind up with this:
class Component:
starts = [
0, 0, 0, 3, 3, 3, 6, 6, 6,
0, 0, 0, 3, 3, 3, 6, 6, 6,
0, 0, 0, 3, 3, 3, 6, 6, 6,
27, 27, 27, 30, 30, 30, 33, 33, 33,
27, 27, 27, 30, 30, 30, 33, 33, 33,
27, 27, 27, 30, 30, 30, 33, 33, 33,
54, 54, 54, 57, 57, 57, 60, 60, 60,
54, 54, 54, 57, 57, 57, 60, 60, 60,
54, 54, 54, 57, 57, 57, 60, 60, 60,
]
def __init__(self, puzzle, start, steps):
self.start = start
indices = (start + step for step in steps)
self.used = [puzzle.game[index] for index in indices]
@classmethod
def row(cls, puzzle, position):
if puzzle.line_size == 9:
steps = [0, 1, 2, 3, 4, 5, 6, 7, 8]
else:
steps = [0, 1, 2]
start = position - position % puzzle.line_size
return cls(puzzle, start, steps)
@classmethod
def column(cls, puzzle, position):
if puzzle.line_size == 9:
steps = [0, 9, 18, 27, 36, 45, 54, 63, 72]
else:
steps = [0, 3, 6]
start = position % puzzle.line_size
return cls(puzzle, start, steps)
@classmethod
def sub_grid(cls, puzzle, position):
if puzzle.line_size == 9:
steps = [0, 1, 2, 9, 10, 11, 18, 19, 20]
else:
steps = []
start = cls.starts[position]
return cls(puzzle, start, steps)
I like this. Commit one more time: refactoring. That hardly says it, let’s amend to refactoring, Component much simpler.
Let’s sum up.
Summary
First of all, that array! I feel almost like it was cheating, because clearly it is possible to compute the necessary index, since we have had a number of chunks of code that do it. I think this refactoring is called Replace Code with Data, or something like that. It uses a bit more storage, perhaps. It’s absolutely shorter code and faster code, since it comes down to a single array access compared to a nest of multiply divide modulo kind of things.
I think I got this idea from Ken Pugh, who couldn’t be bothered to figure out the arithmetic in his Sudoku program and just typed in the array.
Other than that, we reduced four classes to one, admittedly at the cost of a bit of chainsaw editing to replace Row with Component.Row all over. If we could not have done that, there were alternatives, such as leaving rudimentary Row / Column / SubGrid classes with Component until there were no references.
Oh, I just renamed start to sub_grid_starts for clarity.
However, I note that the new component file is 60 lines long, and the one with the subclasses was only 40. Ten of those lines are in the new array, and we could of course make that shorter, but less clear than it is laid out as it is now. So while we did remove three classes, we added some code in the file that formerly contained those classes.
We could have done the array improvement without collapsing out the subclasses. Would that be better? Honestly, I don’t know.
I’d prefer to have a clear win, fewer classes, clearer code, and less of it. Two out of three isn’t bad.
The most interesting bit of all this, if anything is interesting, is that we made a series of over a dozen committed changes to the code, including some changes that one might consider pretty radical, replacing classes with factory methods and the like, all without breaking anything or even a confusing test error.
Small steps. I’m starting to think that Hill is onto something.
See you next time!