I think we’re ready to try to find a real hidden pairs situation and adjust the notes accordingly. I am sure we’re going to find an interfacing issue that will be a bit interesting. Includes notes on ‘think-squared’.

I am confident in the code that finds hidden pairs, so it’s time to set up a puzzle containing hidden pairs, and resolve them. Or … let’s try to stick to how we work best … time to take some small steps in that direction.

The rule for hidden pairs is that if in some component, there are two cells whose notes each include some two values, among other values, and if those two values occur nowhere else in the component, then those two cells notes can have all their other values removed, because those two cells are the only places in that component, where our two values can appear.

Let’s review how our hidden_pairs function works:

def hidden_pairs(notes_a, notes_b, complement):
    if len(notes_a) < 2 or len(notes_b) < 2:
        return []
    # Is 2 correct here? Are the two required to be more than 2?
    for value_1, value_2 in combinations(notes_a, 2):
        if is_hidden_pair(value_1, value_2, notes_b, complement):
            return [[value_1, value_2]]
    return []


def is_hidden_pair(value_1, value_2, notes_b, complement):
    # could be more efficient
    pair_also_in_notes_b = value_1 in notes_b and value_2 in notes_b
    n1_nowhere_else = all([value_1 not in c for c in complement])
    n2_nowhere_else = all([value_2 not in c for c in complement])
    return pair_also_in_notes_b and n1_nowhere_else and n2_nowhere_else

You’ll note that I have a couple of concerns here. First of all, is it important that one or both of the cells have more than two values in the notes? What if one cell has three but the other only has two? I’m not sure.

One thing seems clear: if both cells only contain two values, our work here is done. We have naked pairs, which is a different pattern and technique. Certainly the current if eliminates the clear cases where there aren’t even two values to check. What if one of the notes has 3 and the other only 2 elements?

I just do not know. For now, we’ll let this ride. It may be inefficient but that’s OK, at least for now. I feel confident that it does the right thing.

And the is_hidden_pair method could be more efficient, with early exits that could avoid some list searches. I’ll leave both these concerns for now.

From SudokuWidi I’ve found an example of a puzzle with hidden pairs. Let’s build a test, or a series of tests, around that puzzle.

    def test_hidden_pairs_puzzle(self):
        # https://www.sudokuwiki.org/Hidden_Candidates
        puzzle_list = [
            '000000000',
            '904607000',
            '076804100',
            '309701080',
            '708000301',
            '051308702',
            '007502610',
            '005403208',
            '000000000',
        ]
        puzzle = Puzzle.from_list(puzzle_list)

Fetching candidates from this puzzle will create and init the notes. Remind me to rename that method, but not right now, we’re in the middle of something that might get tossed.

Given that the sample puzzle has notes filled in, I’ll check some of ours to see if we are getting the same results. If we are not … it might mean that I’ve transcribed the puzzle incorrectly. If the issue isn’t that … well, we’ll worry about that if it happens.

        assert puzzle.candidates.at(8) == ['3', '4', '5', '6', '7', '9']

I am delighted to have that pass. Let’s see what component was supposed to have hidden pairs, according to the wiki, and test that directly.

I think we should find [6,7] as a hidden pair in row zero. Let’s find out:

    def test_hidden_pairs_puzzle(self):
        # https://www.sudokuwiki.org/Hidden_Candidates
        puzzle_list = [
            '000000000',
            '904607000',
            '076804100',
            '309701080',
            '708000301',
            '051308702',
            '007502610',
            '005403208',
            '000000000',
        ]
        puzzle = Puzzle.from_list(puzzle_list)
        assert puzzle.candidates.at(8) == ['3', '4', '5', '6', '7', '9']
        row_0 = Component.row(puzzle, 0)
        notes_a = row_0.candidates_at(7)
        notes_b = row_0.candidates_at(8)
        comp = [notes for notes in row_0.all_candidates() if notes is not notes_a and notes is not notes_b]
        pairs = hidden_pairs(notes_a, notes_b, comp)
        assert pairs == [['6', '7']]

It passes! I am delighted! Commit: can find hidden pairs in sudokuwiki example.

OK. Now we are ready … I think we were already ready but I am glad to have this puzzle anyway … we are ready to do the replacement part of the hidden pairs technique.

When we find a hidden pair, that is, when hidden_pairs returns a non-empty result, we want to replace the notes for the two cells whose notes we’re processing (notes_a and notes_b) with the result that has come back.

We do not have that information in any existing test, so let’s write a new test and drive out that info.

Apologia pro vita sua

Often, when I don’t quite know how to write something, rather than try to write it in the production object or function that I’m working on, I’ll create the code in a test. This gives me a chance to focus on it with fewer distractions, and fewer constraints. That helps me grasp the essence of what has to be done.

We have already done this with the hidden_pairs function. It’s a free-standing function in the test file and has not been moved into whatever object will deal with hidden pairs in the app code.

Let’s get to it.

As things stand, the Component can do set_candidates_at, given a notes set and a position in itself. So in our final code, and in our upcoming test, we’ll want to have the positions, not just the notes sets. Previously, we’ve done this sort of thing:

        comp = Component.with_notes(notes_lists)
        all_notes = comp.all_candidates()
        result = []
        for p1, p2 in combinations(all_notes, 2):
            complement = [notes for notes in comp.all_candidates() if notes is not p1 and notes is not p2]
            result.extend(hidden_pairs(p1, p2, complement))
        assert len(result) == 1
        assert ['1', '2'] in result

We’ve done the combinations on a list of candidates (notes). We’ll need to keep the positions. So in this next test:

        puzzle = Puzzle.from_list(puzzle_list)
        row_0 = Component.row(puzzle, 0)
        for pos_1, pos_2 in combinations(range(8), 2):
            notes_a = row_0.candidates_at(pos_1)
            notes_b = row_0.candidates_at(pos_2)
            comp = [notes for notes in row_0.all_candidates() if notes is not notes_a and notes is not notes_b]
            pairs = hidden_pairs(notes_a, notes_b, comp)
            if pairs:
                row_0.set_candidates_at(pos_1, pairs)
                row_0.set_candidates_at(pos_2, pairs)
        assert row_0.candidates.at(7) == ['6', '7']
        assert row_0.candidates.at(8) == ['6', '7']

I really kind of expected that to work but it does not. What does the test say?

LOL. It says row_zero does not understand candidates. Should have said this:

        assert row_0.candidates_at(7) == ['6', '7']
        assert row_0.candidates_at(8) == ['6', '7']

Still fails, now saying:

>       assert row_0.candidates_at(7) == ['6', '7']
E       AssertionError: assert ['2', '3', '4', '5', '6', '7', '9'] == ['6', '7']
E         
E         At index 0 diff: '2' != '6'
E         Left contains 5 more items, first extra item: '4'
E         
E         Full diff:
E           [
E         +     '2',
E         +     '3',
E         +     '4',
E         +     '5',
E               '6',
E               '7',
E         +     '9',
E           ]

This makes me suspect that I’ve found no pairs. Ha, he laughed. I set the range to 8 not 9.

Now I get this failure:

Expected :['6', '7']
Actual   :[['6', '7']]

Of course. We’ve done that odd thing where we return a collection of pairs even though we only ever return at most one. For now, fix the code to accommodate that:

        puzzle = Puzzle.from_list(puzzle_list)
        row_0 = Component.row(puzzle, 0)
        for pos_1, pos_2 in combinations(range(9), 2):
            notes_a = row_0.candidates_at(pos_1)
            notes_b = row_0.candidates_at(pos_2)
            comp = [notes for notes in row_0.all_candidates() if notes is not notes_a and notes is not notes_b]
            pairs = hidden_pairs(notes_a, notes_b, comp)
            if pairs:
                notes = pairs[0]
                row_0.set_candidates_at(pos_1, notes)
                row_0.set_candidates_at(pos_2, notes)
        assert row_0.candidates_at(7) == ['6', '7']
        assert row_0.candidates_at(8) == ['6', '7']

And we’re green. Commit: test_hidden_pairs_sets_new_notes passes. First round trip complete.

Let’s reflect, in the light of the code, dim though it may be.

Reflection

There’s an odd progression here, from positions to notes sets to collection of one notes set back to positions. It’s not necessarily bad, though we would prefer it if at most one level of code had to worry about the position to notes and back notion. We’re probably OK there.

The situation gets me thinking about a smarter Notes thing, that knew its place. The thing is, its place is in the Puzzle, which holds the collection of notes, and we have a component, which is a view of the puzzle, mapping indices 0-8 to indices 0-80.

It’s also kind of upside down, isn’t it? The lower-level operation, hidden_pairs, processes the values in a notes set. I think of it as being fairly abstract, though it is really just manipulating lists of values. And then the upper-level operation yet to be written but sketched in our test, has to think about integers and map them to notes sets. You’d kind of think that the upper level code would deal with something more abstract, not less abstract.

Reflection phases into action …

I am hatching a clever idea. That’s always a bad sign but hear me out, this time it might not be too crazy, just crazy enough that it might work. (Pretty sure I’ve heard that line in more than one bad movie.)

Suppose we had a little object, a Notes, that contains the notes values we expect, and also holds an index and an owner. The owner will be a Component, let’s try not to generalize too far all in one go. The Notes object has a method: become(values) that pushes its values into the owner (Component).

And here’s the clever bit: the Notes doesn’t really have the values at all: it fetches them from its owner upon demand. The Notes is a view of its owner, a Component.

Let’s make a copy of our existing test and see if we can express this idea in Notes.

        puzzle = Puzzle.from_list(puzzle_list)
        row_0 = Component.row(puzzle, 0)
        row_notes = row_0.notes()
        for notes_a, notes_b in combinations(row_notes, 2):
            comp = [notes for notes in row_notes if notes is not notes_a and notes is not notes_b]
            pairs = hidden_pairs(notes_a, notes_b, comp)
            if pairs:
                notes = pairs[0]
                notes_a.become(notes)
                notes_b.become(notes)
        assert row_0.candidates_at(7) == ['6', '7']
        assert row_0.candidates_at(8) == ['6', '7']

This relies on a new method on Component, notes() and on whatever a notes is, the ability to become, and, we haven’t really discovered this yet, the ability to pass through hidden_pairs safely.

I think I’ll follow my nose on this for a bit. We’ll put the Notes class in with Component for now.

class Component:
    def notes(self):
        return [Notes(self, pos) for pos in range(9)]

class Notes:
    def __init__(self, component, pos):
        self.owner = component
        self.pos = pos

    def become(self, values):
        self.owner.set_candidates_at(self.pos, values)

This should be enough to make the test fail in hidden_pairs:

    def hidden_pairs(notes_a, notes_b, complement):
>       if len(notes_a) < 2 or len(notes_b) < 2:
E       TypeError: object of type 'Notes' has no len()

We would like our Notes object to behave like a collection of values from the viewpoint of hidden_pairs:

def hidden_pairs(notes_a, notes_b, complement):
    if len(notes_a) < 2 or len(notes_b) < 2:
        return []
    # Is 2 correct here? Are the two required to be more than 2?
    for value_1, value_2 in combinations(notes_a, 2):
        if is_hidden_pair(value_1, value_2, notes_b, complement):
            return [[value_1, value_2]]
    return []

Will it suffice to provide __iter__?

    def __iter__(self):
        return iter(self.owner.candidates.at(self.pos))

Apparently not like that. We fail:

Oh, we’re still failing on len. I sort of thought __iter__ would handle that. Let’s just implement it:

    def len(self):
        return len(self.owner.candidates.at(self.pos))

That should get me to the next error.

By the way
I am close to rolling this back as an idea whose time has not yet come. But we might be close. We’re not committed to using this idea, just to learning about it.

Duh. I am tempted to edit above. You don’t implement len as a method.

    def __len__(self):
        return len(self.owner.candidates_at(self.pos))

    def __iter__(self):
        return iter(self.owner.candidates_at(self.pos))

I noticed that I had said candidates.at and here we have to say candidates_at. The test is passing.

Notes works.

Let’s have a break and a chai on this high point.

Summary

Overall, we have added a few new tests that take us from beginning to end with hidden pairs, actually resolving them in an actual test we found on the Internet. Woot!

And we have an interesting little idea, the Notes object, which

  1. Acts like a collection of possible values for analysis;
  2. Accepts a become message to change its values;
  3. Acts as a view of Component;
  4. And thus a view of a view of the Puzzle.
  5. Ensures that changed values go back where they belong.

I have a good feeling about this little object. I think what might happen is that we might populate the Puzzle’s candidates list with Notes, which would point back to Puzzle, with true puzzle positions. The Component might become agnostic about positions, holding 9 Note instances that do the mapping back to the Puzzle. I think^2 that this may simplify things.

Think-squared? What is that?

I could be wrong. The value of think is of course a number between zero and one, strictly less than one or I’d have said am certain, which I try really hard never to say. So think^2, think-squared is a number substantially less than think, and somewhere between there and the fourth power, think^n becomes wild-guess.

But I do have a good feeling about it. I also felt my grasp slipping as I worked through it, probably because it was being used in such different ways, as an indexed list and as a view. And also because the path from Component to Puzzle and back is littered with things like candidates.at and candidates_at which for the love of chocolate should not be allowed to persist.

I’ve been saying off and on that this area is messy, and I’m sure you’ve been screaming “So do something about it tiny fool”. But I’ve not had a sense of what to do. This might help. We’ll see.

Maybe … maybe the Notes actually has access to the value as well? Maybe it’s a Cell with a Notes and Value component? That’s definitely in the range of think^7, but maybe.

But we’ve done well today, with two nice sketches of ways to complete hidden pairs.

Commit: Notes object working in hidden pairs. See you next time!