Sudoku: final(?) Look
It has been a while since I looked at the Sudoku code. I don’t have anything in mind for it, but let’s see what we can find just by looking.
The current code that I’m reviewing can be seen here. I’ll just browse through it and call out things that I notice.
I see that there are three test files, test-ideas, test-puzzle, and test-solver. Probably wise to peruse those first.
test_ideas
I know what this is, but a brand new reader might not. If they had access to me, they’d just ask, and I’d tell them. If no team member was available who knew the code, I could imagine that some Python docstring comments would be useful. What might they say? Oh … maybe something like this:
"""
This file contains small tests used to try out small functions such as
functions to access rows or columns or sub-grids. The file is essentially
self-contained, testing nothing but what is here. The tests were used to
answer questions like "How can we easily get the array indices for a column?"
"""
Naturally, I put that comment in, and while I was at it, I cleaned up all the PyCharm warnings, the most important of which was to put spaces around my % operators. And it wants one blank line at the end of the file, but not more than one. OK, Guido, whatever.
There are two tests commented out. The one is pretty clearly just something I used to print some output for an article. The other, I predict, will no longer run, because if refers to a function that does not exist, solve. Let’s just delete that so that it won’t confuse anyone else.
If I were to look into history back, I would probably find either that it never worked, or that it did and then I removed the function for some reason. Frankly, I don’t care.
test_puzzle
This set of tests refers to Puzzle class, and to the Components Row, Column, and SubGrid. If we knew some history, we’d know that the Components were put in late in the process, so that these tests have been retrofitted to use Components. How do we know they aren’t new? The component tests are at the top of the file, and almost always our tests are in chronological order, building up to some thrilling conclusion.
There are three tests like this one:
def test_trying_inner(self):
puzzle = Puzzle('aXczzzzzz')
repl = Puzzle.new_puzzle_trying_guess(puzzle, 'b', 1)
assert repl.game == 'abczzzzzz'
I think their names could make more clear what they are testing. What are they testing? They’re testing that the new_puzzle_trying(puzzle, value, position) method actually slices the new value into the proper place in the puzzle string.
How about these?
def test_we_can_replace_value_at_one(self):
puzzle = Puzzle('aXcdefghi')
repl = Puzzle.new_puzzle_trying_guess(puzzle, 'b', 1)
assert repl.game == 'abcdefghi'
def test_we_can_replace_value_at_zero(self):
puzzle = Puzzle('Xbcdefghi')
repl = Puzzle.new_puzzle_trying_guess(puzzle, 'a', 0)
assert repl.game == 'abcdefghi'
def test_we_can_replace_value_at_end(self):
puzzle = Puzzle('abcdefghX')
repl = Puzzle.new_puzzle_trying_guess(puzzle, 'i', 8)
assert repl.game == 'abcdefghi'
I changed the input/output strings a bit for clarity and consistency. I’m not satisfied but hope this is better. The correct test names might be something like
def test_that_new_puzzle_trying_guess_returns_puzzle_with_correct_position_changed(self)
In the old days, we actually believed that people would read the tests to find out what the code was supposed to do. In practice, that seems rare. We’re lucky if they keep the tests running. So there’s not great value to improving these, but when passing through any code, I think it’s a good habit to take a few moments to improve it.
I rename test_grid_42 to test_grid_containing_42, and all the other similar ones.
test_solver
I found nothing really needing improvement in this file. Removed the extra lines at the bottom and added this comment:
assert puzzle_list == puzzle_list_2 # ensuring no typos
What Now?
We’ve reviewed the tests for a few minutes. Made a few changes. Commit: tidying.
We have four non-test files, component, puzzle, solver, and validator. What order should we look at them in? Let’s go kind of top down, starting with validator.
Validator contains no surprises:
def is_valid(self):
for row in range(0, 81, 9):
puzzle = self.puzzle
chars = Row(puzzle, row).used_numbers
if not self.contains_1_9(chars):
return False
for col in range(0, 9):
puzzle1 = self.puzzle
chars = Column(puzzle1, col).used_numbers
if not self.contains_1_9(chars):
return False
for check in [0, 3, 6, 27, 30, 33, 54, 57, 60]:
puzzle2 = self.puzzle
chars = SubGrid(puzzle2, check).used_numbers
if not self.contains_1_9(chars):
return False
return True
A fanatic (I’m looking at you, Chet) might extract three methods here. I think I set out to do that before and it was tricky because of those returns from the middle of the function. Let’s do it just because. Instead of returning from each of the loops, we can have each one save its result and check them at the end, like this:
def is_valid(self):
for row in range(0, 81, 9):
puzzle = self.puzzle
chars = Row(puzzle, row).used_numbers
row_ok = self.contains_1_9(chars)
for col in range(0, 9):
puzzle1 = self.puzzle
chars = Column(puzzle1, col).used_numbers
col_ok = self.contains_1_9(chars)
for check in [0, 3, 6, 27, 30, 33, 54, 57, 60]:
puzzle2 = self.puzzle
chars = SubGrid(puzzle2, check).used_numbers
grid_ok = self.contains_1_9(chars)
return row_ok and col_ok and grid_ok
PyCharm doesn’t like that because it’s afraid that those ok values might not be initialized although it is clear that they are. But this is just an intermediate step anyway. Now can we extract methods here?
- Note
- It is far from clear that they are correctly set. I am mistaken but will discover that soon. PyCharm’s warning was quite apt.
def is_valid(self):
row_ok = self.are_rows_ok()
col_ok = self.are_columns_ok()
grid_ok = self.are_sub_grids_ok()
return row_ok and col_ok and grid_ok
That of course goes with the new methods, such as … thinking …
… Oh. PyCharm was right. We can’t remove the returns that way. And I wonder why my tests are still passing.
The issue is that the return approach returns False as soon as it finds a bad row, column, sub-grid. But what we have now always returns the last such value.
Revert all that.
OK, sometimes the bear bites you. I think I’d like to have a test that will fail with those changes in effect. I almost wish I hadn’t rolled back: I could have seen the test go red.
I undo the rollback. Let’s write a failing test.
def test_validator_detects_early_fails(self):
solution = '126437958895621473374985126457193862983246517612578394269314785548769231731852649'
unsolved = '226437958895621473374985126457193862983246517612578394269314785548769231731852649'
valid = Validator(unsolved).is_valid()
assert not valid
This fails, because I have that poorly “refactored” method in. Now roll back again, and it should pass. It does. Now let’s look at that method again and see whether we can make it better.
def is_valid(self):
for row in range(0, 81, 9):
puzzle = self.puzzle
chars = Row(puzzle, row).used_numbers
if not self.contains_1_9(chars):
return False
for col in range(0,9):
puzzle1 = self.puzzle
chars = Column(puzzle1, col).used_numbers
if not self.contains_1_9(chars):
return False
for check in [0, 3, 6, 27, 30, 33, 54, 57, 60]:
puzzle2 = self.puzzle
chars = SubGrid(puzzle2, check).used_numbers
if not self.contains_1_9(chars):
return False
return True
- Note
- I think any reasonable person now would be inclined to leave it alone. But a) I make no claims on that dimension, and b) the method as written has confused me at least once already, so it may really want to be improved.
Each of those segments in the method is answering the question “are all the components valid”.
- A light bulb goes on
- I was going somewhere else with that idea but why in the world wouldn’t we ask the components whether they are valid instead of asking ourselves? Here’s our Validator method:
def contains_1_9(self, chars):
if len(chars) != 9:
return False
for c in '123456789':
if c not in chars:
return False
return True
Let’s put a method on Component to check validity. We could test-drive it, but we have tests that we are confident will fail if we get this wrong, so we can proceed.
class Component:
@property
def is_valid(self):
for c in '123456789':
if c not in self.used:
return False
return True
Yes, I am going to inherit behavior.
Now in the Validator:
def is_valid(self):
for row in range(0, 81, 9):
if not Row(self.puzzle, row).is_valid:
return False
for col in range(0,9):
if not Column(self.puzzle, col).is_valid:
return False
for check in [0, 3, 6, 27, 30, 33, 54, 57, 60]:
if not SubGrid(self.puzzle, check).is_valid:
return False
return True
OK, that’s better. But why can’t the Puzzle return, say, all its columns?
Like this:
class Puzzle:
@property
def columns(self):
return [Column(self,col) for col in range(0, 9)]
Let’s see about using that thus:
def is_valid(self):
for row in range(0, 81, 9):
if not Row(self.puzzle, row).is_valid:
return False
for column in self.puzzle.columns:
if not column.is_valid:
return False
for check in [0, 3, 6, 27, 30, 33, 54, 57, 60]:
if not SubGrid(self.puzzle, check).is_valid:
return False
return True
Now I feel ready to try something.
def is_valid(self):
for row in range(0, 81, 9):
if not Row(self.puzzle, row).is_valid:
return False
for check in [0, 3, 6, 27, 30, 33, 54, 57, 60]:
if not SubGrid(self.puzzle, check).is_valid:
return False
columns_are_valid = all(column.is_valid for column in self.puzzle.columns)
return True and columns_are_valid
Another light bulb :Again I thought where I would go would be to do this three times. But, again, I see that there is a better way: Ask the puzzle.
I think this is going to collapse the entire validator class right out of existence. And it’ll happen in small steps. I am confident enough to start committing.
Commit: refactoring validator and puzzle responsibilities.
Now let’s push this notion of columns_are_valid over to Puzzle. PyCharm seems to have o help here but I can grab the all and do this:
class Puzzle:
@property
def columns_are_valid(self):
return all(column.is_valid for column in self.columns)
And then this:
class Validator:
def is_valid(self):
for row in range(0, 81, 9):
if not Row(self.puzzle, row).is_valid:
return False
for check in [0, 3, 6, 27, 30, 33, 54, 57, 60]:
if not SubGrid(self.puzzle, check).is_valid:
return False
return True and self.puzzle.columns_are_valid
Well, we see where this is going, so let’s write the code we wish worked and then make it work. (Beck’s “programming by intention”)
def is_valid(self):
return self.puzzle.rows_are_valid\
and self.puzzle.columns_are_valid\
and self.puzzle.sub_grids_are_valid
And over in Puzzle:
@property
def rows(self):
return [Row(self, row) for row in range(0, 81, 9)]
@property
def rows_are_valid(self):
return all(row.is_valid for row in self.rows)
@property
def sub_grids(self):
return [SubGrid(self, pos) for pos in [0, 3, 6, 27, 30, 33, 54, 57, 60]]
@property
def sub_grids_are_valid(self):
return all(sub_grid.is_valid for sub_grid in self.sub_grids)
And we are green. Commit: continued refactoring.
But wait, there’s more:
class Validator:
def is_valid(self):
return self.puzzle.is_valid
class Puzzle:
@property
def is_valid(self):
return self.rows_are_valid\
and self.columns_are_valid\
and self.sub_grids_are_valid
So now Validator is essentially empty:
class Validator():
def __init__(self,solution):
self.puzzle = Puzzle(solution)
def is_valid(self):
return self.puzzle.is_valid
So let’s find its uses and ask the puzzle.
def test_validator_detects_early_fails(self):
solution = '126437958895621473374985126457193862983246517612578394269314785548769231731852649'
unsolved = '226437958895621473374985126457193862983246517612578394269314785548769231731852649'
assert not Puzzle(unsolved).is_valid
def test_first_9x9(self):
puzzle_list = [
'020000000',
'000600003',
'074080000',
'000003002',
'080040010',
'600500000',
'000010780',
'500009000',
'000000040'
]
puzzle_list_2 = [
'020000000',
'000600003',
'074080000',
'000003002',
'080040010',
'600500000',
'000010780',
'500009000',
'000000040'
]
assert puzzle_list == puzzle_list_2 # ensuring no typos
puzzle = Puzzle.from_list(puzzle_list)
Solver.solver_count = 0
Puzzle.puzzle_count = 0
Puzzle.guess_count = 0
solver = Solver(puzzle)
solved_puzzle = solver.solve()
assert solved_puzzle.is_valid
print(f'\n{Solver.solver_count=}')
print(f'{Puzzle.puzzle_count=}')
print(f'{Puzzle.guess_count=}')
Green. remove class Validator. Still green. Commit: class Validator removed, puzzle knows is_valid.
Wow. I’ve noticed one thing that I don’t like. I wish that Puzzle.is_valid was Puzzle.is_solved. But the is_solved method already exists, thus:
@property
def is_solved(self):
return self.guess_position == -1
That’s really checking to see if there are no remaining 0 cells, cells wanting to be filled in. Let’s see who calls it. Just one:
class Solver:
solver_count = 0
def __init__(self, puzzle):
Solver.solver_count += 1
self.puzzle = puzzle
def solve(self) -> Puzzle | None:
if self.puzzle.is_solved:
return self.puzzle
for new_puzzle in self.puzzle.find_next_puzzles():
solved_puzzle = Solver(new_puzzle).solve()
if solved_puzzle:
return solved_puzzle
return None
Let’s rename is_solved to is_filled_in and is_valid to is_correctly_solved Done, green. Commit: rename methods.
Let’s sum up:
Summary
In retrospect, at first this seems smooth and without anything notable.
We look around, see a few things to clean up. Find a method that’s clearly asking to be turned into three calls. One attempt to do that fails.
We notice why it failed and realize that we could use a new test, so we write the test and see it failing on the changed code. Reverting, we start again with all tests green.
Then, step by reasonable step, we create methods. We notice that the methods are really not asking questions about their own information but about the information that another class has. That always suggests that the other class should do the work.
Inch by inch, we push the behavior over to the other class, Puzzle. Suddenly, there is nothing going on in Validator … and we can remove the entire class.
But there were at least two notable things that the text above glosses over. At least twice, as I was on a path to do one thing, a light bulb lit up, telling me that there was probably a better way to go. I took those surprise paths and they worked out very nicely.
- Lesson
- One good thing that happens when we go in small steps, without much insistence on exactly where we are going, is that often we see better paths that lead to better places. I had no idea that I would be able to get rid of the whole Validator class, but following reasonable steps, it just kind of faded away.
-
Brother Hill pushes us toward Many More Much Smaller Steps. There are many advantages to that style, and just one of them is serendipity.
Is this code now perfect? No, I don’t think so. Here are two things we might want to do:
-
Puzzle may now have more responsibility than it should. We pushed a bunch of responsibility into it, so we should review it to see if there’s too much.
-
The Row, Column, and SubGrid classes may not be bearing their weight. I suspect we could replace them with just the Component class and a few class methods that know how to create a row Component, column Component, and sub-grid Component.
We’ll explore those notions in the future. If we feel like it.
See you next time! Here’s the code.