Well, naked pairs, still, but I’ve used up that title. Brother Bill raises a question. I think we’re OK. Let’s try to implement the idea, whatever it is. Result: it goes very nicely.

My brother Bill Wake commented:

Reading on my phone, so I lost some context. The naked pairs don’t require that the two key cells only contain those numbers, right? I know you can work from the inverse (number → set of cells) but the all-pairs from that feels like more work than I do:)

I reviewed my source for the notion, and a couple of others, and I think I have it right. In my own words (well, really, words that I hope we share, since faznat gritso menkador farble):

If two cells m and n in a component contain the same two values A and B, and only those two values, then the cells must be either m:A n:B in the solution, or m:B n:A. Accordingly, A and B cannot possibly occur in any of the other cells (123456789 - m - n) and can be removed from the candidate lists for those cells.

There is a more elaborate technique about “hidden” pairs, which we may come to in due time, and which Bill may be thinking of. Or—and this is actually more common on the ground—Bill is correct and I am mistaken. But this time … I think I’ve got it right.

Coding it is another matter. Where were we? I believe we have one test and a fake solution:

    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(row)
        technique.apply()
        for cell in [1, 2, 3, 5, 6, 7, 8]:
            candidates = row.candidates_at(cell)
            assert candidates == ['3', '4', '5', '6', '7', '8', '9']

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

    def apply(self):
        result = ['3', '4', '5', '6', '7', '8', '9']
        for cell in [1, 2, 3, 5, 6, 7, 8]:
            self.component.set_candidates_at(cell, result)

That implementation is of course grotesquely fake. We did that on purpose, because there was a lot of bridgework to be done in accessing and changing the candidates, and trying to work out the algorithm in the absence of that infrastructure just didn’t seem on to me. Now we can write another test and it will fail grandly, which will provide us a chance to work out the actual algorithm.

I am worried about that: it seems difficult to me.

    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)
        row.set_candidates_at(1, ['8', '9'])
        row.set_candidates_at(3, ['8', '9'])
        technique = NakedPairsTechnique(row)
        technique.apply()
        for cell in [0, 2, 4, 5, 6, 7, 8]:
            candidates = row.candidates_at(cell)
            assert candidates == ['1', '2', '3', '4', '5', '6', '7']

I think we could make the test more clear by asserting the situation prior to the apply:

    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(row)
        technique.apply()
        for cell in [0, 2, 4, 5, 6, 7, 8]:
            candidates = row.candidates_at(cell)
            assert candidates == ['1', '2', '3', '4', '5', '6', '7']

Let’s commit this test, albeit failing, because I’d like to be on a clean commit. If I had a remote, I wouldn’t push it.

Now there’s nothing for it but to implement the strategy. I’ve looked all around and, well, there are ways we could put it off but let’s do it.

An Algorithm

I recall enough of the Python Sudoku that I found to remember that that code looped over the component by index until it found a pair, then looped from there forward until it found the pair again (abandoning the first find if it didn’t find a match) and if it did find a match, looping over the component again, editing it. Or something like that.

I also recall the code being rife with continue and break and lord knows what odd FORTRAN memorabilia. I’d rather not. Let’s try something by intention.

Given a component, let’s find two cells with the same two values, and the indices of those cells. then let’s remove those two values from all the other cells.

Well, almost. That won’t deal with the possibility of more than one such combination, that is, two or more pairs of unique pairs. I don’t know if we’ll cater to that or not. We “shouldn’t”, because we do not have a test that calls for it.

There is also the possibility of errors in the component. Suppose the same pair occur three times. We’ll reduce that third case to empty. However, the original situation is impossible in a valid Sudoku puzzle. My usual practice is to ignore such things, because I don’t guarantee good results for bad inputs. Of course in an application that might crash or crash the vehicle, we’d be more careful.

For now, we’ll deal with what we have in hand, our one failing test. Here’s a sketch:

    def apply(self):
        pair_indices = self.find_pairs_of_indices_of_naked_pairs()
        if not pair_indices:
            return
        for pair in pair_indices:
            cells = set(range(9)) - set(pair)
            to_remove = self.component.candidates_at(pair[0])
            for cell in cells:
                self.component.remove_candidates_at(cell, to_remove)

There’s a lot of wishful thinking in there. We call it “programming by intention”, where we call methods and refer to things that we intend to implement Real Soon Now.

Both my tests are failing now, since this new method does nothing. Let’s fake the find to return our intended result for the first test, namely finding indices 0 and 4.

    def find_pairs_of_indices_of_naked_pairs(self):
        return [[0, 4]]

Note that I am returning a list of pairs. We do not have a test that calls for it, but it’s a perfectly valid if a bit over-elaborate way to make our current tests work.

Note that I am asking the Component to do the removal for us. That seems to make sense: we shouldn’t know too much about what it’s got on the inside. Let’s see if we can write that. But first I seem to need a reboot.

OK … as I was saying, let’s see if we can get the Component to do whatever I had in mind ten minutes ago before I rebooted, made an iced chair and had a little chat with my dear wife. We have this call breaking our tests:

    self.component.remove_candidates_at(cell, to_remove)

    def remove_candidates_at(self, position, to_remove):
        candidates = self.candidates_at(position)
        candidates = [candidate for candidate in candidates if candidate not in to_remove]
        self.set_candidates_at(position, candidates)

This is too invasive, we should ask the candidates collection to do this job but it has made our first test pass. Recall that we faked the values to return from our find_ method. We should be able to make the first test fail and second test work by changing that return. Just for fun, I do it and that’s what happens. So our remove thingie apparently works. Now the find.

I have in mind that find_pairs_of_indices_of_naked_pairs will return a list of pairs, one pair for each matching pair of naked pairs in the component. From this component:

0 1 2 3 4 5 6 7 8
78 123 56 78 478 1234 349 56 89


We want to return [ [0, 3], [2, 7] ]. You know what? We should write a test for that very thing and use it to build up our find method.

    def test_find_etc(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, ['7', '8'])
        row.set_candidates_at(3, ['7', '8'])
        row.set_candidates_at(2, ['5', '6'])
        row.set_candidates_at(7, ['5', '6'])
        technique = NakedPairsTechnique(row)
        pairs = technique.find_pairs_of_indices_of_naked_pairs()
        assert pairs[0] == [0, 3]
        assert pairs[1] == [2, 7]

OK, we can’t put this off much longer. Better do it.

As much as I hate the idea, I think maybe a nested loop thing might be the trick.

    def find_pairs_of_indices_of_naked_pairs(self):
        result = []
        for first_position in range(9):
            candidates = self.component.candidates_at(first_position)
            if len(candidates) == 2:
                for second_position in range(first_position+1, 9):
                    second_candidates = self.component.candidates_at(second_position)
                    if second_candidates == candidates:
                        result.append([first_position, second_position])
        return result

Guess what. My find test runs, and so do both my naked pairs tests. I think this works.

The morning has been a bit chaotic and I am of a mind to commit and sum up. Commit: indications are that NakedPairsTechnique works.

Summary

Rule Number Something:
If by chance you get ahead, consider quitting while you’re ahead.

I think this actually works, though I want to reflect on it later and we will probably want some more tests. But I do think it works. Let’s talk about why, and how it got that way.

First of all, last time, I put the infrastructure in place that allows us to access candidates all the way up in users of Component, through Puzzle, down into Candidates. There is reason to think that more work should be being down by the lower-down classes, but our first phase at least got us to the point where we could stand where we sort of understood things, in the Technique, and could sketch the overall flow. We created a fake algorithm that returned a fixed answer.

That was enough to get the NakedPairsTechnique class and its main method apply created and in place.

Then, today, we created an apply method that was plausible but didn’t work, because it called two methods that didn’t even exist, ,the one that did the finding and the one that did the removing. We wrote a credible loop to call the removing one for what seems to be the right list of cells.

We faked the find code to return the answer that would make the first test pass. Then, when we made the remove work, that test passed, showing us that the remove was probably good. Then we wrote the find, which wasn’t even too difficult. I do want to look at it tomorrow … in fact to look at all the code tomorrow … but I do think it’s working as intended.

So, assuming that this has worked, it has gone quite smoothly. We wrote a test, faked it, wrote a bit of code assuming methods we could implement. Faked one of those, wrote the other. Wrote the first.

All through of this morning, there were no surprises, no long periods of confusion, just tick tick tick.

How might you replicate this good experience? Heck, I don’t even know how I can reliably replicate it. I do feel confident that these guidelines are part of the answer:

  1. Try always to take the smallest steps possible. These were not tiny, but were as small as I could devise.
  2. When things seem pretty complicated, consider faking the code so as to get the test and the basic calls in place. Then make the fake real.
  3. Use the wishful-thinking “by intention” approach not just to sketch an algorithm, but actually to implement it. Fill in the wishful parts one by one.

And tests. This would have been so difficult without those nice tests. I do think testing could have been easier: We’re really only considering a Component but we had to create a Puzzle to init the Component. Maybe we would profit from a more direct way to do that.

Anyway, it has gone very nicely, and I rather suspect that NakedPairsTechnique actually works. We’ll verify that, because it was almost too easy. It can pay off to be paranoid.

See you next time!