Let’s review our list and see what needs work. I want to try super tiny steps today, just as a matter of practice. (cf. Charles Beaudelaire)

The notes on my cards include:

  • Finish NakedPairsTechnique
  • Component Tests
  • HiddenPairs <illegible>
  • How far can we iterate?
  • Verify get_all_components (Older. Component does need better tests.)
  • Two lonely in one puzzle? (Older. A suggestion for a test, I think.)
  • Explore why only_one is so large

“How far can we iterate?” asks me to consider the overall flow of applying our various techniques. When should we iterate the same technique, when should we back up and start again from the top? That one, I feel nearly sure, is not for today.

A review of a previous article tells me that the illegible word is “Extras”, and was intended to remind me to examine our hidden pairs test puzzle to be sure that the additional pairs found in the test are legitimate hidden pairs.

The one about only_one refers, I think, to a time when I was looking at the rough statistics that were printing out and wondering why we had applied the only_one strategy so often. I think I subsequently decided that it was because each guess by the brute solver entrained a lot of only_one applications until finally the brute discovered that it had made a bad guess and popped up and recurred again, over and over, furrowing into your soul.1

Some people would call the repeated calls for better tests “technical debt”. I prefer to use that term to reflect the difference between the design I’d use now and the design in the code, which serves as an invitation to refactor toward that better design. It reflects that we’ve been learning. Skimping on tests reflects a bad habit: we haven’t been learning, we’ve just been skimping on our investment of time.

YMMV, of course. You can call things whatever you want, I suppose.

I think I should start putting dates on these note cards.

The Plan

So, it is easy to see that I should work on tests. I don’t want to do that today and you don’t want me to do that today. We have no evidence that the lack of tests is hurting us, no outstanding bugs or surprising results. We’ll work on tests when we have more slack time and we’ll try to improve them as we work, but today … today I want to see about finishing the NakedPairsTechnique.

Note
You have just seen what is very likely a poor decision being made. It’s not a fake made-up poor decision. I really don’t want to work on tests today, even though there are clear indications that we need that work. We’ll see whether I come back to tests, we’ll see whether I push a few extra tests in as I work, and best of all, we’ll see whether I get away with it.

The good news is that I am very clear in my mind that I am making what is very likely a poor decision. Let’s start reaping the results.

We’ll start by looking at Solver, where we will need to install our NakedPairs. And what about HiddenPairs? Is that still hanging too? There are too many loose ends, I can’t remember them all.

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_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()

It is not obvious at first glance, but after whatever techniques we apply are tried, we just do one guess in the solver, because we create one new_puzzle, one new Solver, and make one call to solve. So that call will again run the techniques.

That’s good, because it means we will make as few guesses as possible. It could have been implemented without calling the techniques and thus just given up and gone brute all the way.

So what’s in SudokuTechniques?

class SudokuTechniques:
    only_one = 0

    def __init__(self, puzzle):
        self.puzzle = puzzle

    def apply(self):
        self.only_one_possible_value()
        self.only_one_possible_position()
        return self.puzzle

Now, it turns out that those two methods in apply have the corresponding techniques coded right in SudokuTechiques class. And we see quite clearly that, no, we are not applying NakedPairs, nor HiddenPairs.

We can also see that, as written, we apply the techniques only once at this level. However, what about the techniques themselves?

    def only_one_possible_value(self):
        changed = True
        while changed:
            changed = False
            for cell in self.puzzle.unknown_cells():
                available = self.puzzle.possible_answers(cell)
                if len(available) == 1:
                    SudokuTechniques.only_one += 1
                    self.puzzle = Puzzle.evolve_with_change(self.puzzle, available[0], cell)
                    changed = True

This technique is the trivial one that checks possible answers for each cell and if there is only one answer, plugs it into the cell. We create a new puzzle instance every time we do that. If we find ten in a row, entirely possible, we’ll create ten new puzzles, throwing away ten counting the one we started with. Wasteful, and the reason why we had to invent that ListEditor class to get the price of creating a puzzle down.

Anyway, this technique does iterate. What about the other?

    def only_one_possible_position(self):
        if self.puzzle.line_size != 9:
            return
        while self.fixed_a_lonely_one():
            pass

Yes, we iterate this one as well. And, looking down, I see that this one, too, creates a new puzzle on each change … and this one only changes the candidates / notes, not cell values. I think it will turn out that the only techniques that change values will be only_one_possible_value, and the guessing in Solver.

I’ve made a note about creating new puzzles, but I think creating a new one with a given change is probably better than making multiple changes in place, or trying to create just one new puzzle, which, offhand, seems to me to be a bit tricksy.

I believe that we should iterate techniques until none of them have found anything to do. There are at least two ways we could do that. One, direct: have each Technique return a boolean saying whether it has made any changes. One, indirect: have Techniques make changes by creating new puzzles, and detect in the apply that the puzzle has changed.

I think direct will be better. Let’s implement that now, before we plug in the unused Techniques.

class SudokuTechniques:
    only_one = 0

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

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

Green. Tiny change. Commit: moving toward changed flag and iteration of techniques.

Now let’s make one of the techniques return a result.

    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
                    SudokuTechniques.only_one += 1
                    self.puzzle = Puzzle.evolve_with_change(self.puzzle, available[0], cell)
        return overall_change

I put a type hint in the def, which enabled PyCharm to remind me to do the return. I should do that all the time, because I so often forget to return my result. I’m not entirely happy with this method having two changed flags, one for having done anything, and one that keeps it looping locally. However, because it’s very common for singleton possible to crop up after a change, it’s well worth staying in this method to do all that show up before trying the other techniques, which often involve extensive searching.

Now can I use this flag? Not easily. Or can I? Wait. We are green. Commit: only_one_possible_value returns changed flag.

Then I can do this:

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

Accumulating the flag. We’ll do that for every technique. Commit: use changed flag.

Then

    def only_one_possible_position(self) -> bool:
        if self.puzzle.line_size != 9:
            return False
        overall_change = False
        while self.fixed_a_lonely_one():
            overall_change = True
        return overall_change

Green. Commit: setting overall change flag.

Use the flag:

    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()
        return self.puzzle

Green. Commit: using changed flag to iterate all techniques.

Let’s reflect briefly.

Reflection

There was a bug in apply, briefly. I had not tabbed the return self.puzzle out, so it was returning whether or not changed came up. No test caught that.

Honestly, I do not know a good way to test this conditional logic, even though, of all the things we should test, conditional logic is surely the most important. Thing is, to test it I’d need to have puzzles that do and don’t have one or more cases where these techniques do or don’t find something to do. A London school tester might be able to mock things up for this purpose.

OK, I do know a way, but it isn’t a good way. We could write a test for this class that monkey-patches the detail methods to return True or False as we wish and then, I don’t know, count the number of times they are called or something. I’m not going to do that.

Before we put this much to bed, I would like to know the impact of this change on the overall solution time of our big puzzle. We do always print our results:

    def test_first_9x9_with_technique(self):
        assert self.puzzle_list == self.puzzle_list_2  # ensuring no typos
        puzzle = Puzzle.from_list(self.puzzle_list)
        Solver.solver_count = 0
        SudokuTechniques.only_one = 0
        solver = Solver(puzzle)
        solved_puzzle = solver.solve()
        assert solved_puzzle.is_correctly_solved
        print(f'\n{Solver.solver_count=}')
        print(f'{Puzzle.puzzle_count=}')
        print(f'{Puzzle.guess_count=}')
        assert Solver.solver_count < 800
        assert SudokuTechniques.only_one < 15000

Right now, with our changes in, what do we get?

Solver.solver_count=14
Puzzle.puzzle_count=448
Puzzle.guess_count=21

The total test time is down to 112ms, which seems much smaller than before. Let’s patch (but not monkey-patch) to turn this change off.

Solver.solver_count=17
Puzzle.puzzle_count=458
Puzzle.guess_count=24

Time about the same. A small improvement in the stats. Not too surprising because a) we already iterate as many forced solutions as we can in one pass and b) the only_one_possible_position doesn’t seem likely to find many things. Let’s instrument it and get some info. And make a note to come up with better logging.

Solver.solver_count=14
Puzzle.puzzle_count=439
Puzzle.guess_count=18
SudokuTechniques.only_one=6
SudokuTechniques.only_one_position=420

I added those new counts, and made sure to zero everything i the test. And I am surprised at the results. This reports that we only found six values that only had one possible value to plug in. It seems to me that the sum of only_one and solver_count must equal the number of empty cells in the puzzle, or they are not all filled in.

There are only those two calls to evolve:

    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
                    SudokuTechniques.only_one += 1
                    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():
            SudokuTechniques.only_one_position += 1
            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

I wonder if get_lonely_ones might be returning more than it should.

class Component:
    def get_lonely_ones(self):
        result = []
        for value in '123456789':
            positions = [pos for pos in range(9) if value in self.candidates_at(pos)]
            if len(positions) == 1:
                result.append([value, self.positions[positions[0]]])
        return result

I think this isn’t right. Well, I think it isn’t what I thought it was.

Let’s see what this does. In this component, we consider each possible cell value 1-9. We see which positions in our component have that value as a candidates. If there is only one such cell, we return the value and the true cell number of the only position where we found it.

Would you believe that there are no tests for this method?

Anyway … if we do find any such value/cell pairs, we create a new puzzle with that change, and return true, which will tally the discovery.

Ah. I think it is OK that this second method finds so many answers and the first does not. It examines the whole component to see if there are any values that can only go in one possible cell and it fills them in. The first method examines the component to see whether any notes have only one value and it fills them in.

The second method will find all the cases where the notes have just one value and if the notes just have one value it is dead certain that no other notes will contain that value, because Sudoku. so this method vacuums most of the up. All good.

It is, however, less efficient than the first method. Let’s have it just do one instead of all of them and see what happens.

Solver.solver_count=16  # was 14
Puzzle.puzzle_count=440  # was 439
Puzzle.guess_count=20  # was 18
SudokuTechniques.only_one=339  # was 6
SudokuTechniques.only_one_position=86  # was 420

Well, I think the change in the SudokuTechniques numbers is as expected. I’m not clear on why we have two more solvers than before.

    def only_one_possible_position(self) -> bool:
        if self.puzzle.line_size != 9:
            return False
        overall_change = False
        if self.fixed_a_lonely_one():
            SudokuTechniques.only_one_position += 1
            overall_change = True
        return overall_change

I thought I saw the reason why those numbers changed a little bit. What I mostly see is that I don’t quite know what is going on.

What I do know is that with the if in place, one of the 3x3 tests fails. I think it was relying on the loop but anyway, for now, we’ll leave things as they are, looping inside the only_one_possible_position method. And I am confident that we aren’t making any actual mistakes in solving the puzzle, because we verify the result.

Puzzle guess_count is interesting because it is this:

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

That’s the number of guesses that are made available to the Solver, not the number that are actually used. The solver_count is the number of actual Solver instances we created. I don’t see why those numbers should have changed. New item: explore changes in statistics per Sunday article. It’s time for chai, let’s sum up.

Summary

As always happens, reality does not conform to plan. Some people consider that to be bad and a failure of planning. Wise planners know that a plan almost never survives contact with reality. Planning is important, but responding to reality is more important. At the time we create the plan, we know less about reality than we ever will again.

We thought we’d move toward installing NakedPairs and HiddenPairs into the Solver. But upon viewing Solver, we decided that it was more valuable to get the iteration of techniques built into Solver, so we did that. Along the way, we chose, wisely I think, to check our statistics. That checking confirms that we’re iterating as we intended, but also showed us that I (note pronoun switch) cannot fully predict what’s going to happen with small changes in the iteration.

We can be very confident that our two existing techniques are not breaking anything, because the puzzle ends up solved. If they made an incorrect decision, the puzzle would not resolve. And we know they’re helping because without them the puzzle requires 78000 guesses to be solved, instead of 14 or 16. A noticeable improvement!

So today has been fruitful in progress toward good handling of the techniques, and in improving our stats a bit. Notes made are:

  • Creating many new puzzles in only_one_possible_value;
  • Better logging;
  • Explore changes in stats per Sunday article.

We’ll do those things. Though these changes have been small, I feel good about the progress. And the steps … wow were they tiny! Most of them were just a line or two and few of them even touched more than one method.

A good morning. See you next time!


  1. Somehow this phrase from my favorite guest article popped into my head. Flowers of Evil: Ask Charles Beaudelaire. ↩