Sudoku: Review 2

Still looking at that 20 line class. Yes, I think it needs improvement. Am I serious? I think I am.

A Story

When Chet and I used to teach developer classes, we would take each team’s code, put it up on the screen, and find something that could really use improvement. Kind of a scary thing, you might think: what if there wasn’t anything significant to say? I suppose you could say “Well, this is great, let’s move on to Team B”, but that wouldn’t be satisfying.

The question never arose. We never had trouble finding something that needed improvement.

This story has nothing to do with what is happening here, where I’ve put the first randomly picked twenty lines of my code up here and am finding things to improve.

Here we are again, looking at Solver:

class Solver:
    def __init__(self, puzzle):
        Logger.log().count("Solver Count")
        self.puzzle = puzzle

    def solve(self) -> Puzzle | None:
        if self.puzzle.is_filled_in:
            return self.puzzle
        for new_puzzle in self.puzzle.find_next_puzzles():
            puzzle_after_techniques = self.try_techniques(new_puzzle)
            solved_puzzle = Solver(puzzle_after_techniques).solve()
            if solved_puzzle:
                return solved_puzzle
        return None

    def try_techniques(self, new_puzzle):
        techniques = SudokuTechniques(new_puzzle)
        return techniques.apply()

In particular, the solve method. It is recursive, which may be hard to notice, and anyway that is a huge¹ method with nine lines, two if statements, and a for.

Let’s begin with a simple Extract Method:

    def solve(self) -> Puzzle | None:
        if self.puzzle.is_filled_in:
            return self.puzzle
        return self.solve_sub_puzzle()

    def solve_sub_puzzle(self):
        for new_puzzle in self.puzzle.find_next_puzzles():
            puzzle_after_techniques = self.try_techniques(new_puzzle)
            solved_puzzle = Solver(puzzle_after_techniques).solve()
            if solved_puzzle:
                return solved_puzzle
        return None

Green. Commit: refactoring.²

I think an else would be better there:

    def solve(self) -> Puzzle | None:
        if self.puzzle.is_filled_in:
            return self.puzzle
        else:
            return self.solve_sub_puzzle()

Commit.

I like that. The fact that it says solve_sub_puzzle is suggesting recursion to me. Now how about the other method:

    def solve_sub_puzzle(self):
        for new_puzzle in self.puzzle.find_next_puzzles():
            puzzle_after_techniques = self.try_techniques(new_puzzle)
            solved_puzzle = Solver(puzzle_after_techniques).solve()
            if solved_puzzle:
                return solved_puzzle
        return None

Let’s rename new_puzzle.

    def solve_sub_puzzle(self):
        for sub_puzzle in self.puzzle.find_next_puzzles():
            puzzle_after_techniques = self.try_techniques(sub_puzzle)
            solved_puzzle = Solver(puzzle_after_techniques).solve()
            if solved_puzzle:
                return solved_puzzle
        return None

Commit.

I think solved_puzzle is not an accurate name. We can see here that solve and solve_sub_puzzle can return a puzzle or None. Now, we could argue that this is OK, it’s a common thing to do, return an answer or None …. but it’s not as clean as it might be. Somehow it feels like a speed bump to me.

One moderately large possibility comes to mind. We’ll relegate it to a footnote.

I’m not sure what to do about this. Let’s extract another method while we wait:

    def solve_sub_puzzle(self):
        for sub_puzzle in self.puzzle.find_next_puzzles():
            solved_puzzle = self.try_to_solve_sub_puzzle(sub_puzzle)
            if solved_puzzle:
                return solved_puzzle
        return None

    def try_to_solve_sub_puzzle(self, sub_puzzle):
        puzzle_after_techniques = self.try_techniques(sub_puzzle)
        solved_puzzle = Solver(puzzle_after_techniques).solve()
        return solved_puzzle

Let’s try an inline.

    def try_to_solve_sub_puzzle(self, sub_puzzle):
        puzzle_after_techniques = self.try_techniques(sub_puzzle)
        return Solver(puzzle_after_techniques).solve()

I’ve forgotten to commit. Do so. It’s hard to remember to commit on green. At least hard for me.

Let’s look at the whole picture again:

    def solve(self) -> Puzzle | None:
        if self.puzzle.is_filled_in:
            return self.puzzle
        else:
            return self.solve_sub_puzzle()

    def solve_sub_puzzle(self):
        for sub_puzzle in self.puzzle.find_next_puzzles():
            solved_puzzle = self.try_to_solve_sub_puzzle(sub_puzzle)
            if solved_puzzle:
                return solved_puzzle
        return None

    def try_to_solve_sub_puzzle(self, sub_puzzle):
        puzzle_after_techniques = self.try_techniques(sub_puzzle)
        return Solver(puzzle_after_techniques).solve()

    def try_techniques(self, new_puzzle):
        techniques = SudokuTechniques(new_puzzle)
        return techniques.apply()

PyCharm offers the option to provide some type hints. I don’t know how well it can do but let’s find out. It doesn’t do well, because I’ve not generally provided hints but I do some by hand, with this result:

    def solve(self) -> Puzzle | None:
        if self.puzzle.is_filled_in:
            return self.puzzle
        else:
            return self.solve_sub_puzzle()

    def solve_sub_puzzle(self) -> Puzzle | None:
        for sub_puzzle in self.puzzle.find_next_puzzles():
            solved_puzzle = self.try_to_solve_sub_puzzle(sub_puzzle)
            if solved_puzzle:
                return solved_puzzle
        return None

    def try_to_solve_sub_puzzle(self, sub_puzzle: Puzzle) -> Puzzle | None:
        puzzle_after_techniques = self.try_techniques(sub_puzzle)
        return Solver(puzzle_after_techniques).solve()

    def try_techniques(self, new_puzzle: Puzzle) -> Puzzle:
        techniques = SudokuTechniques(new_puzzle)
        return techniques.apply()

I have mixed feelings about that, but I lean toward thinking that the explicit Puzzle | None return type is a useful hint.

The solve_sub_puzzle method remains problematical, in that it contains an early return if the puzzle is solved and terminates the loop. But the fact is, that’s what happens.

The generator find_next_puzzles produces a (virtual) list of puzzles, each one with a different guess. Let’s have a glance at that:

class Puzzle:
    def find_next_puzzles(self):
        position = self.first_unsolved_position()
        guesses = self.possible_answers(position)
        Logger.log().count("Puzzle Guesses", len(guesses))
        puzzles = (Puzzle.evolve_with_change(self, guess, position) for guess in guesses)
        return puzzles

Because the final line is enclosed in parens, not braces, this is a generator, so we do not do all the evolve calls at once, we do them on demand. But it acts like we have created the list, which are all the puzzles making a sensible guess at the first unsolved position. That is, we only guess possible answers as recorded in the Notes. We could find that out buy drilling down if we wanted to.

So the loop runs out if we run out of guesses. And, if we ever do run out of guesses at any position, it’s (sub)game over, the recursive path we’re on is not a solution.

Recursive solutions are hard to think about: at least for me, at least this year. There was a year when I was really into them and then maybe they weren’t so hard to think about.

Anyway, for now, I think we have done enough … let’s look at what we’ve done and decide what we think about it.

class Solver:
    def __init__(self, puzzle: Puzzle):
        Logger.log().count("Solver Count")
        self.puzzle: Puzzle = puzzle

    def solve(self) -> Puzzle | None:
        if self.puzzle.is_filled_in:
            return self.puzzle
        else:
            return self.solve_sub_puzzle()

    def solve_sub_puzzle(self) -> Puzzle | None:
        for sub_puzzle in self.puzzle.find_next_puzzles():
            solved_puzzle = self.try_to_solve_sub_puzzle(sub_puzzle)
            if solved_puzzle:
                return solved_puzzle
        return None

    def try_to_solve_sub_puzzle(self, sub_puzzle: Puzzle) -> Puzzle | None:
        puzzle_after_techniques = self.try_techniques(sub_puzzle)
        return Solver(puzzle_after_techniques).solve()

    def try_techniques(self, new_puzzle: Puzzle) -> Puzzle:
        techniques = SudokuTechniques(new_puzzle)
        return techniques.apply()

The class is now longer by about six or eight lines, owing to the additional small methods.

I don’t love these names, but I feel pretty good, around 0.8 good, about the general breakout. Things that are not expressed that perhaps could be:

• It’s not so much a sub-puzzle as it is making a guess at one position and then trying to solve the resulting puzzle.
• The puzzle_after_techniques isn’t the same puzzle we were handed: it may have evolved further. (This is not shown in this code: we saw it in the previous article, being done in the SudokuTechniques.)
• It’s not entirely clear whether the SudokuTechniques need to evolve the puzzle to assign values.
• We might, therefore, be evolving at the wrong level.
• Maybe we should, given a puzzle, apply techniques repeatedly and only after that, try guessing.
• We “sort of” do that already but it isn’t obvious.

It’s odd. This code is working well and, I think, does the right things in the right order. But it doesn’t quite say that.

Could better names for these methods improve our understanding? Possibly: maybe Puzzle.find_next_puzzles should be renamed to something like find_some_guesses_to_make. Maybe like this:

    def solve_sub_puzzle(self) -> Puzzle | None:
        for sub_puzzle in self.puzzle.find_some_guesses_to_make():
            solved_puzzle = self.try_each_guess(sub_puzzle)
            if solved_puzzle:
                return solved_puzzle
        return None

    def try_each_guess(self, sub_puzzle: Puzzle) -> Puzzle | None:
        puzzle_after_techniques = self.try_techniques(sub_puzzle)
        return Solver(puzzle_after_techniques).solve()

I think I might prefer that. Commit.

Let’s back away slowly and sum up.

Summary

Twenty lines. So many questions, so many opportunities to make it “better”. And, of course, there are probably people who would prefer this:

    def solve(self) -> Puzzle | None:
        if self.puzzle.is_filled_in:
            return self.puzzle
        for sub_puzzle in self.puzzle.find_some_guesses_to_make():
            solved_puzzle = Solver(SudokuTechniques(sub_puzzle).apply()).solve()
            if solved_puzzle:
                return solved_puzzle
        return None

I am not one of those people. Roll that back.

What lessons might we learn from this?

Stop When It Works

We might have said, it’s twenty lines, yeah, it’s a little obscure but if it was hard to write it should be hard to read, get over it, it passes the tests.

Improve What We Can Readily See

We might do as we’ve done here, spend just a little time extracting methods and renaming, then move on.

Resolve Every Concern

We could keep working on this until we have it perfect, with no concerns. There are two problems with this idea. First, there is no guarantee that it will converge. We may never come up with a solution that fully satisfies all our concerns. And second, and probably more important, surely there is some investment of time that is too much.

Stop When the Cost of Improving Exceeds the Cost of Learning

Ideally we would improve things until the next change would cost more than the cost of the programmer figuring it out for themselves. The issues here include this important one: we have no idea what the cost of leaving things as they are might be. If no one ever looks at this code again (very likely here at my house) leaving it alone is the best strategy. If a thousand programmers are going to download our code and all spend an hour trying to work out the issue, a little investment could be worth it.

I think it’s a judgment call. Here, in these articles, I have the luxury of no deadlines, so I can push far beyond the point where we’d probably stop if we had the wolf at our door. And, even in the presence of deadlines, I think I’d like to push something as far as possible from time to time, because we learn something about better ways of expressing our ideas when we do that. So maybe I’d suggest that the team spend a couple of hours on Friday afternoon with a Crazy Refactoring session.

What will we do here? I think we’ll move on: my initial purpose was to review the whole program, draw a few lessons, and then move on to another project. But I do wonder whether there’s a way to make this part of the program more clear …

Feel free to toot me your thoughts. Don’t tweet or xeet, though: I don’t go there any more.

See you next time!