I believe that our naked and hidden pairs code was reporting that it had changed things when it had not. That would be bad. Let’s see about doing it better.

NakedPairsTechnique, if I am not mistaken, only does a single component. Our guideline for Techniques probably should be that a Technique applies itself wherever it can, on a single call to its apply method.

The Naked Pairs rule is, according to an earlier article:

If any Component contains two cells, each with the same pair of possible candidates, then no other cell in that Component can contain either of those candidates, and we should therefore remove the pair elements from any other candidate that includes either of them.

Our code for Naked Pairs is:

class NakedPairsTechnique:
    def __init__(self, puzzle, component):
        self.puzzle = puzzle
        self.component = component

    def apply(self):
        def cond(p1, p2):
            return len(p1) == 2 and p1 == p2

        for naked_pair in self.component.find_candidates_pairs(cond):
            self.puzzle = self.component.remove_naked_pair(naked_pair)
        return self.puzzle

OK, first of all, we note that this is only doing one component. So, like yesterday, we’ll deal with that by putting the loop over components into the SudokuTechniques class, but we should decide on which way things are done and do them all that way. Then we’d refactor to make it so.

Do we have any tests for this baby? We have, and they go like this:

    def test_naked_pairs(self):
        empty = [
            '000000000', '000000000', '000000000', '000000000',
            '000000000', '000000000', '000000000', '000000000',
            '000000000',
        ]
        puzzle = Puzzle.from_list(empty)
        row = Component.row(puzzle, 0)
        row.set_candidates_at(0, ['1', '2'])
        row.set_candidates_at(4, ['1', '2'])
        assert row.candidates_at(0) == ['1', '2']
        technique = NakedPairsTechnique(puzzle, row)
        new_puzzle = technique.apply()
        assert new_puzzle is not puzzle
        new_row = Component.row(new_puzzle, 0)
        for cell in [1, 2, 3, 5, 6, 7, 8]:
            candidates = new_row.candidates_at(cell)
            assert candidates == ['3', '4', '5', '6', '7', '8', '9']

    def test_naked_pairs_2(self):
        empty = [
            '000000000', '000000000', '000000000', '000000000',
            '000000000', '000000000', '000000000', '000000000',
            '000000000',
        ]
        puzzle = Puzzle.from_list(empty)
        row = Component.row(puzzle, 0)
        for cell in range(9):
            assert row.candidates_at(cell) == ['1', '2', '3', '4', '5', '6','7', '8', '9']
        row.set_candidates_at(1, ['8', '9'])
        row.set_candidates_at(3, ['8', '9'])
        technique = NakedPairsTechnique(puzzle, row)
        new_puzzle = technique.apply()
        new_row = Component.row(new_puzzle, 0)
        for cell in [0, 2, 4, 5, 6, 7, 8]:
            candidates = new_row.candidates_at(cell)
            assert candidates == ['1', '2', '3', '4', '5', '6', '7']

We want a test that tests a changed flag, and, of course, then to implement it. We’ll just rip off one of these test’s data and try it twice.

A more careful look at these tests tells me that the Technique is returning either the old puzzle or a new one. That is also clear from the code, if we read it, but so far I was just scanning. We’ll go with the new puzzle convention for now, so that we don’t start changing three things at once. Anyway we can do our new test like this:

    def test_naked_pairs_returns_changed(self):
        puzzle = Puzzle.empty()
        row = Component.row(puzzle, 0)
        for cell in range(9):
            assert row.candidates_at(cell) == ['1', '2', '3', '4', '5', '6','7', '8', '9']
        row.set_candidates_at(1, ['8', '9'])
        row.set_candidates_at(3, ['8', '9'])
        technique = NakedPairsTechnique(puzzle, row)
        new_puzzle_1 = technique.apply()
        assert new_puzzle_1 is not puzzle
        technique = NakedPairsTechnique(puzzle, row)
        new_puzzle_2 = technique.apply()
        assert new_puzzle_2 is puzzle

And this test fails, because new_puzzle_2 is not puzzle.

Now, I’m afraid, we actually have to do some work. In particular, we’re concerned about

    def apply(self):
        def cond(p1, p2):
            return len(p1) == 2 and p1 == p2

        for naked_pair in self.component.find_candidates_pairs(cond):
            self.puzzle = self.component.remove_naked_pair(naked_pair)
        return self.puzzle

How does the component do that remove?

class Component:
    def remove_naked_pair(self, pair):
        return self.puzzle.remove_naked_pair(pair, self.positions)

class Puzzle:
    def remove_naked_pair(self, pair, positions):
        new_puzzle = self.copy()
        new_puzzle.candidates.remove_naked_pair(pair, positions)
        return new_puzzle

class Candidates:
    def remove_naked_pair(self, pair, positions):
        for pos in positions:
            if (cand := self.candidates[pos]) != pair:
                self.candidates[pos] = [v for v in cand if v not in pair]

Well, that’s rather irritating, isn’t it? The code just assumes that it needs a new puzzle. But there in Candidates, if the job has already been done, we just set candidates to the same value again, and didn’t really need to create the new puzzle after all.

This is a bit, um, puzzling. But wait. I think that our rule is that we can change the candidates / notes in the puzzle without creating a new one. It’s only if we change cell values that we want a new puzzle. Let’s check other cases to be sure. (We’ll still want to know if we changed anything, but if we don’t create a new puzzle we can return a changed flag instead.)

There are no other real cases. The base techniques actually do set a value, and HiddenPairs isn’t installed here either. However, it does not evolve a game when it changes things. So, new rule, if you don’t change a cell value, you don’t create a new game. Let’s first change NakedPairs to work that way.

This:

    def remove_naked_pair(self, pair, positions):
        new_puzzle = self.copy()
        new_puzzle.candidates.remove_naked_pair(pair, positions)
        return new_puzzle

Becomes this:

    def remove_naked_pair(self, pair, positions):
        changed = self.candidates.remove_naked_pair(pair, positions)
        return changed

All our naked pairs tests fail. They are all expecting a new puzzle back. Change them all. I changed them all to return a changed flag instead of a puzzle, similar to this one:

    def test_naked_pairs_returns_changed(self):
        puzzle = Puzzle.empty()
        row = Component.row(puzzle, 0)
        for cell in range(9):
            assert row.candidates_at(cell) == ['1', '2', '3', '4', '5', '6','7', '8', '9']
        row.set_candidates_at(1, ['8', '9'])
        row.set_candidates_at(3, ['8', '9'])
        technique = NakedPairsTechnique(puzzle, row)
        changed_1 = technique.apply()
        assert changed_1 is True
        technique = NakedPairsTechnique(puzzle, row)
        change_2 = technique.apply()
        assert change_2 is False

So right now, all three are failing on the change flag.

This is getting a bit chaotic. If it doesn’t sort out quickly, I should roll back and go smaller. But I think we are nearly OK.

class NakedPairsTechnique:
    def __init__(self, puzzle, component):
        self.puzzle = puzzle
        self.component = component

    def apply(self):
        def cond(p1, p2):
            return len(p1) == 2 and p1 == p2

        changed = False
        for naked_pair in self.component.find_candidates_pairs(cond):
            changed |= True
            self.puzzle = self.component.remove_naked_pair(naked_pair)
        return changed

Now the two tests that aren’t checking two calls pass, because we return True. But we aren’t returning it correctly. We want the real answer. Let’s go down to the bottom and get the flag there.

    def remove_naked_pair(self, pair, positions):
        for pos in positions:
            if (cand := self.candidates[pos]) != pair:
                self.candidates[pos] = [v for v in cand if v not in pair]

We want to return True if we actually found one or both of the elements of v in candidates[pos]. How about this:

    def remove_naked_pair(self, pair, positions):
        changed = False
        for pos in positions:
            if (cand := self.candidates[pos]) != pair:
                p0, p1 = pair
                if p0 in cand or p1 in cand:
                    changed |= True
                    self.candidates[pos] = [v for v in cand if v not in pair]
        return changed

Now we can do this:

class NakedPairsTechnique:
    def __init__(self, puzzle, component):
        self.puzzle = puzzle
        self.component = component

    def apply(self):
        def cond(p1, p2):
            return len(p1) == 2 and p1 == p2

        changed = False
        for naked_pair in self.component.find_candidates_pairs(cond):
            changed |= self.component.remove_naked_pair(naked_pair)
        return changed

And our test for not doing the job twice passes! Woot! Commit: NakedPairs does not return changed unless an actual change was made.

Now there are at least two things we could do next:

  • Fold our tents and creep away;
  • Install NakedPairs in SudokuTechniques;
  • Update HiddenPairs to use a changed flag properly.
N.B.
See how cleverly I avoided my usual mistake of saying “two” and then coming up with three or more?

Let’s install NakedPairs. If we do that we’ll deliver a feature and it is well past time to do that.

class SudokuTechniques:
    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

We “merely” have to add a new method:

Wait, before I do this, I need a test. Tiny fool!

I notice that some old tests are creating an empty puzzle the old-fashioned way, before I finally got smart and implemented Puzzle.empty(). I change them and commit.

Now then, we should be able to create a new test for the NakedPairs technique by copying that last one.

    def test_naked_pairs_via_sudoku_techniques(self):
        puzzle = Puzzle.empty()
        row = Component.row(puzzle, 0)
        for cell in range(9):
            assert row.candidates_at(cell) == ['1', '2', '3', '4', '5', '6','7', '8', '9']
        row.set_candidates_at(1, ['8', '9'])
        row.set_candidates_at(3, ['8', '9'])
        techniques = SudokuTechniques(puzzle)
        changed_1 = techniques.apply()
        assert changed_1 is True
        change_2 = techniques.apply()
        assert change_2 is False

This fails on the first assert, because we find nothing to do with our current techniques. So we implement:

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

    def naked_pairs(self):
        changed = False
        for component in self.puzzle.all_components():
            np = NakedPairsTechnique(self.puzzle, component)
            changed |= np.apply()
        return changed

I really thought this would work. Instead four tests fail. What has happened? Ah, they are all tests on 3x3 puzzles. Let’s hack:

    def naked_pairs(self):
        if self.puzzle.line_size != 9:
            return False
        changed = False
        for component in self.puzzle.all_components():
            np = NakedPairsTechnique(self.puzzle, component)
            changed |= np.apply()
        return changed

Like I say, hack. But now my actual test is failing. I wonder why.

test_techniques.py:111 (TestTechniques.test_naked_pairs_via_sudoku_techniques)
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000 != True

We seem to have returned a puzzle from techniques.apply, which, so far, is the correct thing to do. So how can we test this, since our general techniques never change the puzzle?

Let’s at least test the result. We can get that check from one of the earlier tests.

    def test_naked_pairs_via_sudoku_techniques(self):
        puzzle = Puzzle.empty()
        row = Component.row(puzzle, 0)
        for cell in range(9):
            assert row.candidates_at(cell) == ['1', '2', '3', '4', '5', '6','7', '8', '9']
        row.set_candidates_at(1, ['8', '9'])
        row.set_candidates_at(3, ['8', '9'])
        techniques = SudokuTechniques(puzzle)
        techniques.apply()
        new_row = Component.row(puzzle, 0)
        for cell in [0, 2, 4, 5, 6, 7, 8]:
            candidates = new_row.candidates_at(cell)
            assert candidates == ['1', '2', '3', '4', '5', '6', '7']

This is green as my finger after wearing my Captain Midnight Secret Decoder Ring all day. Commit: NakedPairs installed in SudokuTechniques class.

Do we need to double-check that the NakedPairsTechnique does not return changed when it makes no changes? No, we have a test for that. Here, we have a test that ensures it is called.

I think we’re OK. I’m quite sure that we’re OK … it’s just that I’d be more comfortable if we could know, somehow, that a second call to apply on SudokuTechniques didn’t get a changed indication from NakedPairs. I can think of no reasonable way to test that. If the conversation allows, maybe I’ll ask the Zoom folks tonight.

For now, let’s sum up.

Summary

Today we did, fairly easily, what we did not accomplish yesterday. This is often the way. Two important thing that we did today were to take smaller steps, and to test each smaller step separately.

Was that the cause of our greater success today? Certainly didn’t hurt. I think that our troubles yesterday also probably alerted us to issues today, and without really thinking about yesterday or checking notes, we “intuitively” made moves that were less wrong.

We encountered one glitch that we have seen often: The small 3x3 tests tend to break when we add in our new techniques. We hacked a solution, which was not to run the technique on small puzzles. The actual issue is that all_components assumes a 9x9:

class Puzzle:
    def all_components(self):
        rows = [Component.row(self, pos) for pos in range(0, 81, 9)]
        cols = [Component.column(self, pos) for pos in range(9)]
        subs = [Component.sub_grid(self, pos) for pos in [0, 3, 6, 27, 30, 33, 54, 57, 60]]
        return rows + cols + subs

We should perhaps remove our 3x3 tests, but they did serve as foundation for some things and thus kind of have historical significance. I don’t really believe that people review tests that way, but I don’t like to remove tests that still fun.

We could fix all_components to return the right thing in the 3x3 case. Perhaps we “should” but it’s really not very interesting.

But that hack in the technique? That’s ugly. I’ll make a note to deal with it. Maybe I’ll go after it, or push the problem down. I think that our techniques have the right to assume that the lower level methods they call will do the right thing.

Another note that I just made says: Naked Pairs bounces around a lot.

What I mean by that is that NakedPairsTechnique has a component. (And a puzzle, does it even use that? It does not. Note made.) It sends two messages to the component:

    def apply(self):
        def cond(p1, p2):
            return len(p1) == 2 and p1 == p2

        changed = False
        for naked_pair in self.component.find_candidates_pairs(cond):
            changed |= self.component.remove_naked_pair(naked_pair)
        return changed

That is arguably feature envy, and should probably be a single method find_and_remove_naked_pairs.

Inside component, remove_naked_pair calls on puzzle to do the work

class Component:
    def remove_naked_pair(self, pair):
        return self.puzzle.remove_naked_pair(pair, self.positions)

Puzzle calls Candidates:

class Puzzle:
    def remove_naked_pair(self, pair, positions):
        changed = self.candidates.remove_naked_pair(pair, positions)
        return changed

And Candidates does the work:

    def remove_naked_pair(self, pair, positions):
        changed = False
        for pos in positions:
            if (cand := self.candidates[pos]) != pair:
                p0, p1 = pair
                if p0 in cand or p1 in cand:
                    changed |= True
                    self.candidates[pos] = [v for v in cand if v not in pair]
        return changed

That flow feels to me like bouncing, but I think that’s a bug in my mind. Truly, Candidates is “below” Puzzle, so the flow is actually drilling down into finer-grained objects, which is a good thing.

But it does feel odd to me, and that keeps me wondering about whether these objects are just right.

They all work well together … but when the code feels like a bit of a bump in my mind, I always try to stay alert to see whether there’s something to improve.

For now, we have Naked Pairs installed. There is one final concern that comes to mind:

SudokuTechniques is creating and looping over NakedPairTechnique objects, each of which checks one component. Should that loop be in SudokuTechniques, or should it be a private matter all embodied in NakedPairTechnique? I am inclined toward the latter.

Note made on that as well.

Summary Summary

We progressed rather smoothly through creating a few more tests, slipping the change flag into the handling of Naked Pairs. It was following an older design (technical debt!) where we returned a new puzzle. That was no longer appropriate.

Now we have a nice new technique. And I wonder if it is being used in our 9x9.

I was going to stop here. But now I have to at least add a counter.

class Component:
    def remove_naked_pair(self, pair):
        changed = self.puzzle.remove_naked_pair(pair, self.positions)
        if changed:
            Logger.log().count("NakedPair")
        return changed

In our 9x9, we do not see a log entry. So we never found a naked pair during that solution. Interesting but credible I guess. Now I have to think about that tomorrow as well. Note made. I think we need to scarf up some puzzles from the internet and get some batch statistics one of these first days.

So, summary summary summary, a pleasant morning with release of an actual technique which is well known in the Sudoku industry and which may or may not be helpful.

I am pleased enough. See you next time!