Sudoku: Review 1

I think we’re nearly done with Sudoku at least for now. Let’s look at the code and see what we can say about it. We find an issue in the first 20 lines. Wow.

I started this exercise, if I recall, because Ken Pugh ran into someone who refuted all of XP or refactoring or something because back in ought-seven I started a Sudoku solver and then stopped, therefore I had failed, TDD had failed, refactoring had failed, incremental design had failed, XP had failed, etc etc. And Ken had started programming some Sudoku. Somehow I got nerd-sniped and here we are now.

Anyway there is another project on the horizon, I hope and believe, so it seems like time to wind this one down. My plan today is primarily to review the code and see what we can say about it. Before we do that, let’s review what we have accomplished:

Overall Result

Starting from nothing, as one does, mostly driven by tests, we have some Sudoku-related code that includes a guess-based recursive solver that can solve any standard Sudoku. It seems to run in well under one second. We have around four Sudoku strategies implemented, including two very simple ones: if there’s only one possibility in a cell, set the cell to that value, and if a cell is the only one in a component with a given possible value, set the cell to that value. And we have two more complex strategies, Naked Pairs and Hidden Pairs, that are used to reduce the possibilities, thus simplifying the problem, making it more likely that the other two strategies will find something to do, and reducing the search space for the big hammer brute force approach.

I think it is clear that we could, if we chose, produce and install more strategies: the main loop just tries them over and over until they all respond that they see nothing to do, so that adding one to its list is quite simple.

An open question, about which I know absolutely nothing, is whether there are meta-strategies that could be used to tell us “don’t even bother to try strategy X, it can’t possibly apply”. Such strategies might conceivably exist and might be helpful, since the more complex strategies do generally look at lots of combinations, and could become expensive to run.

This is all moot for most purposes, if we can solve any Sudoku in well under a second, unless we were to go into the business of solving them at scale, which seems to me to be a very unlikely thing to do.

Subjective Assessment

I feel pretty good about the effort overall. We have 72 tests including solving a supposedly “hard” Sudoku, and the tests, subjectively, seem to work well. When I break something, one or more tests generally break. I feel, again subjectively, that they cover us pretty well at the level of whether everything works.

I recall feeling that there could be more and better tests covering some objects. Component comes to mind. We’ll have a look at that kind of question when we get to the tests and code. I’m sure we’ll find things that could use a little improvement.

Finally, I feel that some of the later code, specifically Hidden Pairs, made better use of Python, and of our own objects, than earlier code. Here again, we’ll see what we find when we inspect the program.

Let’s get down to that.

The Code and Tests

I write the title in that order because I am impatient to look at the code. A case could be made that we should start with the tests, but, well, I don’t want to. Let’s see what we can find.

We’ll pick up the ball of yard from the top, starting with the Solver. That should lead us to everything.

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():
            new_puzzle = self.try_techniques(new_puzzle)
            solved_puzzle = Solver(new_puzzle).solve()
            if solved_puzzle:
                return solved_puzzle
        return None

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

Short and sweet. We might not notice at first glance, but the solve method is recursive: in the solve method, it creates another puzzle, new_puzzle, and calls its solve method. So it’s not recurring on the current puzzle but is instead creating a stack of puzzles to solve. When it finds a puzzle that is_filled_in,, it returns that result.

The recursion can stop, but I guess it’s kind of subtle. If find_next_puzzles were to return an empty collection, the loop would drop through, and the solve would return None. If that ever happens, then the if solved_puzzle condition in the caller would see a None, would not return a solved_puzzle, ,but would continue the loop. If the loop collection is not empty, we continue the search. If we ever drop out, we return None, which will inform our caller that our search was fruitless, and that level will try its next puzzle.

In actual use, if the program is correct, and the Sudoku puzzle is not somehow self-contradictory, we can never return None from the initial call. If we ever do, something has gone very wrong: either the starting puzzle is literally unsolvable, or there is a defect in the program. So far, when I’ve seen a final None, it was a defect in the program. I don’t think it is possible to set up a partially solved Sudoku that adheres to the rules but is unsolvable. I could be wrong about that: I have neither researched the topic nor proven the conjecture.

Anyway we are here to assess this code. There is something not to like, and it is this:

    for new_puzzle in self.puzzle.find_next_puzzles():
        new_puzzle = self.try_techniques(new_puzzle)

Snipe Hunt

We are about to do the best thing we can think of to do, and we are about to waste our precious programmer time. There is a lesson here.

We might ask … why are we reassigning a value to the loop variable? Looking at try_techniqes isn’t terribly enlightening:

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

Aside

Would you inline the temp variable above? Why or why not? But we digress …

If we didn’t know the answer, we’d have to drill into SudokuTechniques. Let’s see how hard it is to uncover the answer. SudokuTechniques is 64 lines long. Do you want to scan it to see if you can quickly pick out what’s going on? OK:

class SudokuTechniques:
    def __init__(self, puzzle):
        self.puzzle = puzzle
        self. changed = False

    def apply(self):
        self.changed = True
        while self.changed:
            self.changed = False
            self.changed |= self.only_one_possible_value()
            self.changed |= self.only_one_possible_position()
            self.changed |= self.naked_pairs()
            self.changed |= self.hidden_pairs()
        return self.puzzle

    def hidden_pairs(self):
        if self.puzzle.line_size != 9:
            return False
        hp_technique = HiddenPairsTechnique(self.puzzle)
        return hp_technique.apply()

    def naked_pairs(self):
        if self.puzzle.line_size != 9:
            return False
        return NakedPairsTechnique(self.puzzle).apply()

    def only_one_possible_value(self) -> bool:
        overall_change = False
        try_again = True
        while try_again:
            try_again = False
            for cell in self.puzzle.unknown_cells():
                available = self.puzzle.possible_answers(cell)
                if len(available) == 1:
                    overall_change = True
                    try_again = True
                    Logger.log().count("Techniques only_one")
                    self.puzzle = Puzzle.evolve_with_change(self.puzzle, available[0], cell)
        return overall_change

    def only_one_possible_position(self) -> bool:
        if self.puzzle.line_size != 9:
            return False
        overall_change = False
        while self.fixed_a_lonely_one():
            Logger.log().count("Techniques only_one_position")
            overall_change = True
        return overall_change

    def fixed_a_lonely_one(self):
        components = self.puzzle.all_components()
        for component in components:
            lonely_ones = component.get_lonely_ones()
            for lonely_value, lonely_cell in lonely_ones:
                self.puzzle = Puzzle.evolve_with_change(self.puzzle, lonely_value, lonely_cell)
                return True
        return False

If we study this carefully enough—which might not be too difficult—we will see that only_one_possible_value and only_one_possible_position may set a new Puzzle into self.puzzle and we always return self.puzzle, so that SudokuTechniques may return a new puzzle, or it may not. OK, fine. Interesting, but what does that have to do with the solve method? Again:

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

There is no reason at all to reuse the loop variable here. Spoiler, do not click.¹

I think this is better:

    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

End Snipe Hunt

We did not find out why the loop variable was clobbered, despite some time spent studying the only code that could possible be requiring it. Our innocent use of that variable just wasted precious programmer time and little grey cells.

We have read this whole other class and see nothing that explains why we might have clobbered that variable. We might as well not have looked there: our knowledge of the language could have told us it didn’t matter … but the only reason we could imagine was that it must be something down below, so we felt compelled to at least check. Spoiler, do not click.²

The new code is better. Green, commit: add temp variable to reduce confusion.

Reflection

I plan to end this article with this one example, because there is plenty to unpack here. And, no promises, I plan to continue right into another article this morning.

My first take is this: it is fascinating that in the first place we look, a class of only two real methods and about twenty lines, we find something that needs improvement. Further, now that I look at solve above, I can see other concerns about it. It includes two visible chunks, a guard clause and then a for loop. Shouldn’t that method be broken up? Let’s come back to that, later in this article or maybe even later than that.

The code as presented immediately raised a question in the reader’s mind: why is this code clobbering the loop value? It took a fair bit of exploration of another class, three times larger than the one we were looking at, and we never really find the answer: it’s just that I remembered why the code was that way. No other programmer could possibly remember that. Our changed code doesn’t clobber the variable, and doesn’t raise the question. We just read along without that “huh?”.

We could argue that Solver is inherently a bit tricky to understand, because it is recursive, and in an odd way because it doesn’t just call a method recursively, it creates a new instance and calls the method on that. Using that argument, we might successfully resist trying to make Solver more clear.

But if we do not rely on that argument, we might find ways to make it more clear what’s going on. I want to jump into that right here, but no. Let’s wrap this and then return next time, which, for me, will be a few minutes from now.

What we have already seen is that in the very first place we looked, a simple little 20 line class, we found code that was just mysterious enough to send us on a snipe hunt where we dug around for a while and never really found the answer. (I remembered the answer. It was not in the code.)

Simply using a new variable instead of clobbering the loop variable made the question go away. We might still have other questions, but no snipe hunt.

Lesson

Twenty lines and an improvement that could save some future programmer a half hour of confusion. Think about that. Then … do whatever seems right. I’m not the boss of you.

See you next time, in a few minutes by my watch!