I’ve thought of an object that we probably need. Let’s find out. Result: A very pleasant refactoring sequence leading to a design that I prefer. Click to find out why.

Aside:

I rather hope that today is not the last birthday of our democracy, but it is very difficult not to worry about it. I use a variety of distractions to avoid worry, not least of which is to write these articles, and to do the programming or other thinking that it takes to write them. If you’re reading this, I thank you for your help in keeping me from spiraling downward, ever downward.

So I was thinking this morning as I resisted waking up, and I thought something about a row or column or sub-grid of Sudoku, and it came to me that our current solver does not have a row or column or sub-grid object. It just has code, like this:

class Puzzle:
    def find_available_values(self, position):
        row = self.used_numbers_in_row(position)
        column = self.used_numbers_in_column(position)
        sub_grid = self.used_numbers_in_sub_grid(position) if self.line_size == 9 else []
        return [c for c in self.available_values if c not in row and c not in column and c not in sub_grid]

    def used_numbers_in_sub_grid(self, position):
        starting_row_of_sub_grid = position - position % (3*self.line_size)
        offset_in_row = position % 9 // 3 * 3
        first_index_in_sub_grid = starting_row_of_sub_grid + offset_in_row
        return self.fetch_sub_grid(first_index_in_sub_grid)

    def fetch_sub_grid(self, first_index_in_sub_grid):
        result = []
        for row_index in range(3):
            cell = first_index_in_sub_grid + row_index*9
            result.extend(self.game[cell:cell+3])
        return result

There’s similar code, of course, for the row and column.

While we’re browsing, let’s look at how the Solver does its thing:

    def solve(self) -> Puzzle | None:
        if self.puzzle.is_solved:
            return self.puzzle
        for guess in self.puzzle.find_available_guesses():
            new_puzzle = Puzzle.new_puzzle_trying_guess(self.puzzle, guess)
            solved_puzzle = Solver(new_puzzle).solve()
            if solved_puzzle:
                return solved_puzzle
        return None

I wanted to get the Solver in front of us for a moment, and we’ll come back to it, but first let’s reflect on the code from Puzzle. It’s all about fetching sets of numbers. Parts of it are agnostic about the puzzle size, but parts are locked in on size 9x9. (the existence of a 9 in fetch_sub_grid is a not very subtle hint.)

But that’s a distraction from the real issue, which is that the Puzzle is thinking about all these collections of numbers. Relatedly, the Solver thinks for a moment about numbers (available guesses) but mostly just thinks about creating new Solver instances and calling them.

Danger
I am probably making a mistake right now. I’m trying to think about multiple ideas at the same time. I’m thinking that Puzzle should have some kind of row / column / sub-grid helper objects, and also thinking that the guesses that Solver deals with are, as implemented, very low-level: they are single-character strings containing a digit to be tried as a guess. Someone does need to keep track of that, but really, Solver doesn’t even have a notion of what a guess is: it just iterates through them, passing them back to the Puzzle.

While I’m still in danger, let me note that we probably don’t want Puzzle to return a collection of Puzzles: if we do that, we might create more than we actually need. They’re small but still, no point in doing something we don’t need to do.

But the danger is that juggling is a lot easier when you only use one ball at a time, and here I’m starting to juggle two or three or more vague ideas. That’s likely to lead to dropping some or all of them.

Let’s jot down an idea for Solver and then turn to Puzzle. Perhaps we could change Puzzle to give Solver a generator called find_available_guesses, and that generator provides Puzzles, but only when they’re needed.

No. That seems almost easy. I thought we’d start with the row / column / sub-grid stuff but let’s belay that and see about the generator idea. We’ll make it work “by intention”, which is a trick I learned from Kent Beck. Essentially it amounts to writing the code you wish worked (your intention) and then making it work. In the presence of tests, it’s often really nice.

Let’s find out.

Puzzle Generator

Change the Solver:

    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

That would be nice, if it worked. Four of 28 tests fail. No worries, there is no method find_next_puzzles in Puzzle.

    def find_next_puzzles(self):
        guesses = self.find_available_guesses()
        puzzles = [Puzzle.new_puzzle_trying_guess(self, guess) for guess in guesses]
        return puzzles

This works, and I think it makes all the puzzles. I also think if I replace those square brackets with parens, it won’t do that. We do not have a puzzle counter and now I think I’d like to have one.

I’ll instrument our long test:

    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
        puzzle = Puzzle.from_list(puzzle_list)
        Solver.solver_count = 0
        Puzzle.puzzle_count = 0
        solver = Solver(puzzle)
        solved_puzzle = solver.solve()
        solution = solved_puzzle.game
        print(f'\n{Solver.solver_count=}')
        print(f'\n{Puzzle.puzzle_count=}')
        validator = Validator(solution)
        assert validator.is_valid()

I get a number that I am surprised to see:

Solver.solver_count=78431
Puzzle.puzzle_count=78449

Only 18 more Puzzles than Solvers? That seems quite low. I want another instrument, counting the size of the guess list. It matches.

I’m going to set this question aside, make my generator, and leave the statistics for later.

    def find_next_puzzles(self):
        guesses = self.find_available_guesses()
        Puzzle.guess_count += len(guesses)
        puzzles = (Puzzle.new_puzzle_trying_guess(self, guess) for guess in guesses)
        return puzzles

That makes it a generator and should never create a puzzle until it’s iterated, which will only happen in Solver if a previous attempt has failed to solve.

Note
I would not swear in a court of law that that’s a generator and not running all at once creating all the Puzzles. I am pretty sure that I understand when Python gets a generator, and I think that’s it. I will make a note to make certain later.

Green. Commit: Puzzle now gets a generator of puzzles to solve until it finds the answer, not a list of guesses.

OK, this is good, in that the notion of a guess is inside Puzzle, and Solver just deals with Puzzles.

Let’s turn our attention inside Puzzle, thinking about rows and columns and sub-grids.

Helpers for Puzzle?

The notion that I have in mind here is that the Puzzle deals with a fairly wide range of notions, with a string of characters representing the puzzle state, and a bunch of obscure calculations that create collections of single-character strings and so on, and that maybe some helper objects would be nice.

The obvious helpers, I guess, would be a row, a column, and a sub-grid object. Each of those is no more than a collection of nine values from one through nine, the values already used up in that row or column or sub-grid. Let’s make up a name for those things. We’ll call them Components of the puzzle, until we think of a better word.

Let’s begin with the simplest case, the row. We’ll see if we can help ourselves out by creating a little Row object. I freely grant that I’m predicting we’ll have just one base class when we’re done, the Component, but we’ll let that appear when it wants to.

Here’s our row-related code:

class Puzzle:

    def used_numbers_in_row(self, position):
        start = position - position % self.line_size
        used_in_row = self.game[start:start + self.line_size]
        return [c for c in used_in_row if c != '0']

    def find_available_values(self, position):
        row = self.used_numbers_in_row(position)
        column = self.used_numbers_in_column(position)
        sub_grid = self.used_numbers_in_sub_grid(position) if self.line_size == 9 else []
        return [c for c in self.available_values if c not in row and c not in column and c not in sub_grid]

Hm. Looking at this I start thinking about using our components to help with that last little mess. One thing at a time.

Note
I am beginning to wonder whether this is going to pay off. I’m going to proceed on the grounds that tiny objects are part of my people’s culture and because I want to find out.

Let’s first rig used_numbers_in_row to return a Row instead of a list of numbers. We’ll see about inlining and such later. I’ll proceed again by intention.

    def used_numbers_in_row(self, position):
        return Row(self, position)

No surprise that that doesn’t work yet. But if we were to build a little class:

class Row:
    def __init__(self, puzzle, position):
        start = position - position % puzzle.line_size
        self.used = puzzle.game[start:start + puzzle.line_size]

A good start but not good enough. Some detailed tests are failing because they expect a collection. We have that collection, so let’s let them at it.

No. Let’s return the numbers from the method:

    def used_numbers_in_row(self, position):
        return Row(self, position).used

That fixes some of the errors but I expect at least one objecting to in:

No. We can’t return used, it’s a string.

class Row:
    def __init__(self, puzzle, position):
        start = position - position % puzzle.line_size
        self.used = puzzle.game[start:start + puzzle.line_size]

    @property
    def used_numbers(self):
        return [c for c in self.used if c != '0']

Well, that works. Tests are green. I am not loving where we are, and a distraction has me feeling uncertain. I could roll back and start over, it’s only a few lines of code. Let’s look first at our real user:

class Puzzle:
    def find_available_values(self, position):
        row = self.used_numbers_in_row(position)
        column = self.used_numbers_in_column(position)
        sub_grid = self.used_numbers_in_sub_grid(position) if self.line_size == 9 else []
        return [c for c in self.available_values if c not in row and c not in column and c not in sub_grid]

    def used_numbers_in_row(self, position):
        return Row(self, position).used_numbers

Let’s just get the Row and make it work:

    def find_available_values(self, position):
        row = Row(self, position)
        column = self.used_numbers_in_column(position)
        sub_grid = self.used_numbers_in_sub_grid(position) if self.line_size == 9 else []
        return [c for c in self.available_values if c not in row and c not in column and c not in sub_grid]

This should fail because row doesn’t grok in.

>   return [c for c in self.available_values if c not in row and c not in column and c not in sub_grid]
E   TypeError: argument of type 'Row' is not iterable

We can make it iterable. We really can. We have the technology. Should we?

    def __iter__(self):
        return iter(self.used)

Oh hell yes, that’s trivially easy! Nummy Python.

Tests are green. I might nearly like this. I like it well enough to commit: Initial Row object.

Thus lifted up, we proceed to Column. We’ll do it the same way but then I expect to see some duplication.

    def find_available_values(self, position):
        row = Row(self, position)
        column = Column(self, position)
        sub_grid = self.used_numbers_in_sub_grid(position) if self.line_size == 9 else []
        return [c for c in self.available_values if c not in row and c not in column and c not in sub_grid]

And:

class Column:
    def __init__(self, puzzle, position):
        start = position % puzzle.line_size
        self.used = puzzle.game[start:len(puzzle.game):puzzle.line_size]

    def __iter__(self):
        return iter(self.used)

    @property
    def used_numbers(self):
        return [c for c in self.used if c != '0']

Green. Commit: Initial Column object.

We have duplication in the two Row / Column classes, and we have some crufty methods left in Puzzle, that are going to wind up used only in tests. I think we’ll hold off on those, but let’s deal with this duplication:

class Row:
    def __init__(self, puzzle, position):
        start = position - position % puzzle.line_size
        self.used = puzzle.game[start:start + puzzle.line_size]

    def __iter__(self):
        return iter(self. used)

    @property
    def used_numbers(self):
        return [c for c in self.used if c != '0']


class Column:
    def __init__(self, puzzle, position):
        start = position % puzzle.line_size
        self.used = puzzle.game[start:len(puzzle.game):puzzle.line_size]

    def __iter__(self):
        return iter(self.used)

    @property
    def used_numbers(self):
        return [c for c in self.used if c != '0']

Now (Pace, Hill)1 I plan to use implementation inheritance here. Like this:

class Component():
    def __iter__(self):
        return iter(self. used)

    @property
    def used_numbers(self):
        return [c for c in self.used if c != '0']

    
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]

And green. This is going swimmingly. Commit: Row and Column inherit behavior from Component.

Our next step is pretty clear. Using the “wishful thinking” approach “by intention”:

    def find_available_values(self, position):
        row = Row(self, position)
        column = Column(self, position)
        # sub_grid = self.used_numbers_in_sub_grid(position) if self.line_size == 9 else []
        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]

I commented that line because I want to remember that the sub-grid acts empty for small grids.

Now:

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

I got that init by cut / paste / hack from these two methods of Puzzle:

    def used_numbers_in_sub_grid(self, position):
        starting_row_of_sub_grid = position - position % (3*self.line_size)
        offset_in_row = position % 9 // 3 * 3
        first_index_in_sub_grid = starting_row_of_sub_grid + offset_in_row
        return self.fetch_sub_grid(first_index_in_sub_grid)

    def fetch_sub_grid(self, first_index_in_sub_grid):
        result = []
        for row_index in range(3):
            cell = first_index_in_sub_grid + row_index*9
            result.extend(self.game[cell:cell+3])
        return result

We’re green. Commit: initial SubGrid object.

Having dealt with the size thing, I’ll remove that commented line and commit: remove reminder.

Brief Retrospective

Let’s catch our breath and observe how this went. We did all the necessary learning with Row, and there wasn’t much. There was a bit of fumbling, I think because I tried to make it too easy and might have done better to have committed immediately to Row being able to deal with in. But even with that stumble, Row worked quickly.

Column was a direct copy except for the values accessed. That made the anticipated Component class trivially easy, and that made the final step to SubGrid also easy, with just the necessity to move a fair amount of code into its init.

We should deal with that.

We also have a lot more code in Puzzle now than we actually need. Let’s look at (almost) the whole thing:

class Puzzle:
    def __init__(self, a_game_string):
        Puzzle.puzzle_count += 1
        self.game = a_game_string
        if len(a_game_string) == 9:
            self.available_values = '123'
            self.line_size = 3
        elif len(a_game_string) == 81:
            self.available_values = '123456789'
            self.line_size = 9
        else:
            raise ValueError('problem must have length 9 or 81')
        self.guess_position = self.first_unsolved_position()

    @property
    def is_solved(self):
        return self.guess_position == -1

    def used_numbers_in_column(self, position):
        start = position % self.line_size
        used_in_column = self.game[start:len(self.game):self.line_size]
        return [c for c in used_in_column if c != '0']

    def used_numbers_in_row(self, position):
        return Row(self, position).used_numbers

    def used_numbers_in_sub_grid(self, position):
        starting_row_of_sub_grid = position - position % (3*self.line_size)
        offset_in_row = position % 9 // 3 * 3
        first_index_in_sub_grid = starting_row_of_sub_grid + offset_in_row
        return self.fetch_sub_grid(first_index_in_sub_grid)

    def fetch_sub_grid(self, first_index_in_sub_grid):
        result = []
        for row_index in range(3):
            cell = first_index_in_sub_grid + row_index*9
            result.extend(self.game[cell:cell+3])
        return result

    def find_available_guesses(self):
        return self.find_available_values(self.guess_position)

    def find_available_values(self, 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]

    def find_next_puzzles(self):
        guesses = self.find_available_guesses()
        Puzzle.guess_count += len(guesses)
        puzzles = (Puzzle.new_puzzle_trying_guess(self, guess) for guess in guesses)
        return puzzles

    def first_unsolved_position(self):
        try:
            return self.game.index('0')
        except ValueError:
            return -1

I said “almost” because I left out the two class variables I’m using to count things, and the class methods used to create new puzzles from list or given a guess and position to try.

Let’s focus in on these two:

    def used_numbers_in_column(self, position):
        start = position % self.line_size
        used_in_column = self.game[start:len(self.game):self.line_size]
        return [c for c in used_in_column if c != '0']

    def used_numbers_in_row(self, position):
        return Row(self, position).used_numbers

These methods are now used only in tests, and in Validator. Let’s try to inline that second one. Command+Option+N, I believe. Yes. Gone, but of course now there are lots of references to Row. Fine, it needs tests.

We’ll change used_numbers_in_column to be similar and then inline it:

    def used_numbers_in_column(self, position):
        return Column(self, position).used_numbers

And inline. Gone. We should be committing: Inlining unused methods back into tests.

Same with this one:

    def used_numbers_in_sub_grid(self, position):
        starting_row_of_sub_grid = position - position % (3*self.line_size)
        offset_in_row = position % 9 // 3 * 3
        first_index_in_sub_grid = starting_row_of_sub_grid + offset_in_row
        return self.fetch_sub_grid(first_index_in_sub_grid)

First to this:

    def used_numbers_in_sub_grid(self, position):
        return SubGrid(self, position).used_numbers

Then inline it away. Commit: Tidying, inlining.

This method is now unused:

    def fetch_sub_grid(self, first_index_in_sub_grid):
        result = []
        for row_index in range(3):
            cell = first_index_in_sub_grid + row_index*9
            result.extend(self.game[cell:cell+3])
        return result

Remove it. Commit: tidying.

These three look odd:

    def find_available_guesses(self):
        return self.find_available_values(self.guess_position)

    def find_available_values(self, 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]

    def find_next_puzzles(self):
        guesses = self.find_available_guesses()
        Puzzle.guess_count += len(guesses)
        puzzles = (Puzzle.new_puzzle_trying_guess(self, guess) for guess in guesses)
        return puzzles

I’m not entirely sure how we did that. Probably in that early fumbling around.

We can inline:

    def find_available_values(self, 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]

    def find_next_puzzles(self):
        guesses = self.find_available_values(self.guess_position)
        Puzzle.guess_count += len(guesses)
        puzzles = (Puzzle.new_puzzle_trying_guess(self, guess) for guess in guesses)
        return puzzles

But you know what? I like it better the other way. Undo that.

There are 12 users of the find_available_values method, 11 tests and the code we see here.

Let’s modify find_available_values to make its second parameter optional, using self.position if it’s not provided:

    def find_available_values(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]

Now we can use that same method here:

    def find_next_puzzles(self):
        guesses = self.find_available_values()
        Puzzle.guess_count += len(guesses)
        puzzles = (Puzzle.new_puzzle_trying_guess(self, guess) for guess in guesses)
        return puzzles

And remove the other one. Now rename find_available_values:

    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]

    def find_next_puzzles(self):
        guesses = self.possible_answers()
        Puzzle.guess_count += len(guesses)
        puzzles = (Puzzle.new_puzzle_trying_guess(self, guess) for guess in guesses)
        return puzzles

Green all along. Commit: tidying.

I think we’re good for today. I’ll move the Components classes to their own file and we’ll get out of here.

F6, type a name, check some boxes, done. I love me some PyCharm.

Commit: Components have their own file.

Let’s sum up, and I’ll put the Puzzle code at the end just in case you want to review it. If you want me to put it up on GitHub, let me know.

Summary

We have reduced the complexity of the Puzzle class, removing all its attention to the detailed subscripts of its component rows, columns, and sub-grids. The arithmetic for each of those has been isolated into the __init__ of the unique classes Row, Column, and SubGrid.

Notes

I should note that early on I predicted just one class, Component, and we now have four. We could get down to one with class methods on Component, but frankly I like having Row and Column and SubGrid. We might consider that idea subsequently.

Note also that early on I was doubting whether the objects would improve things. I went ahead anyway, based on my general finding that little objects help. And they did, another win for tiny objects.

I hit a moment where rolling back came to mind. As I often do, I bulled ahead, and, in this case, things quickly sorted out. It might have been more wise to do the roll-back but we’ll never know.

There’s an issue in Component that I just noticed. The superclass refers to self.used, which is only actually defined in the subclasses. I’ll have to think about that. It works fine, of course, because duck typing.

Those classes consist of nothing but __init__, with the operational aspects all implemented in and inherited from Component.

An idea has popped into my head. I was thinking that if I were to add one comment to Component, it would be to say that __iter__ is implemented just to support the in operation that we use to get the values. The idea is that since Row and Column and SubGrid all know how to iterate, we could have another Component that is the available values to guess, with a operation among Components that “subtracts” values from a starting Component. That might allow Puzzle to avoid knowing about guess values at all.

We might do that, it seems possibly fruitful. But not today.

Anyway … by creating these tiny Component objects, we have reduced the complexity of Puzzle rather substantially. It talks much more in terms of what it wants to do and much less in terms of obscure integer calculations.

Here in this tiny app, that may not be worthwhile. In a larger program, the approach of pushing implementation details like subscripts down into small objects leaves us mostly working with simpler and more abstract objects, with much less need to drop into more strange calculations, since those are all handled down below.

We do, of course, create more new objects that way. I am used to trusting my language’s creation and collection mechanisms. If something actually got burdensome we could pull some calculations up and deal with it, but day in and day out, better abstractions make my work easier.

So I am pleased with this outcome.

See you next time!

Today’s code


  1. That’s Latin “pace” (pa-chay or pa-say)(Church Latin, Real Latin). Means “Peace, Hill”, because the inestimable GeePaw Hill recommends strongly against inheriting implementation. I myself think that the language is here to serve me, not the other way around. ↩