Now that we have our foot in the door with find_candidates_pairs tacking a condition function, what would we have to say to define hidden pairs? Spoiler: We improve our ability to test.

Monday 1400

What is the definition of a hidden pair, I might ask. Sudoku wiki just has examples. Sudoku.com says:

“Hidden pairs” technique works the same way as “Hidden singles”. The only thing that changes is the number of cells and Notes. If you can find two cells within a row, column, or 3x3 block where two Notes appear nowhere outside these cells, these two Notes must be placed in the two cells. All other Notes can be eliminated from these two cells.

I wonder what hidden singles is. I think it is the same as what I called lonely.

The point of “Hidden singles” is that a Note is the only one of its kind in an entire row, column, or 3x3 block. However, this technique requires careful attention from the player, because it can be quite hard to spot the single Notes.

Hm. Anyway, yes, that’s what it is. We should rename our lonely accordingly. Also I notice that the “literature” often refers to “notes” where I have called them “candidates”. Another possibility for renaming, more difficult because there will be a lot of references to the word. Perhaps worth doing as we work, or even in a sweep.

For now, let’s think about the hidden pairs.

We want to discover two cells with a special property. Let’s mumble about that special property a bit …

  • The two cells contain two notes such that those two notes do not occur anywhere else in the component.

  • This suggests that, as I suspected, we may well want the complement of the pair of note sets we’re considering.

  • It seems likely that we need to iterate over pairs of notes in one of the pairs we look at, since there might be a large number of values in there, of which two are the ones we need. So combinations without combinations.

Let’s try to sketch an algorithm.

Given two notes sets A and B (candidate lists) from a component, the notes ‘x’ and ‘y’ are a hidden pair if:

  1. Both ‘x’ and ‘y’ are in A and in B;
  2. Neither ‘x’ nor ‘y’ are in any other notes set of the component.

So that’s something like:

def hidden_pairs(notes_a, notes_b, complement):
	if len(notes_a) < 2 or len(notes_b) < 2:
		return []
	result = []
	for n1, n2 in pairs(notes_a):
		if n1 in notes_b and n2 in notes_b:
			n1_absent = all([n1 not in c for c in complement])
			n2_absent = all([n2 not in c for c in complement])
			if n1_absent and n2_absent:
				result.append([n1, n2])

I just typed that into the article, no idea if it would even compile, much less work. But it seems reasonable to me.

As that stands, it doesn’t line up well with our find_candidates_pairs method, but we’ll not worry about that.

I think the first thing I’ll do, when I get around to doing, will be to build a combinations kind of thing that returns the pair (n-tuple?) and the complement set. I’m not sure offhand quite how I’ll do that but how hard can it be.

For now, I have to work on something else. I’ll pick this up later today, or tomorrow.

Tuesday 0829

Right, here we are, all nice clean and ready to go. I’ve done a bit of thinking about this, mostly about how to produce the things that hidden_pairs needs, assuming that it is called as above. I won’t call any shots, my thoughts weren’t that organized, but I have general ideas about getting the complement with some kind of “easy” comprehension, and so on.

A possibly interesting question is this: given a hidden_pairs method like the above, what object should implement it? As it stands, it looks like a pure function or static method: it does not reference self at all. Its parameters, as it stands, seem to be a couple of lists of something (we happen to know that they are single-character strings), and another list of lists of whatever those things are.

By my lights, that’s not a good way to live. We could imagine that the Component has or acts as a list of Notes objects, each Notes containing one or more of the game tokens, which in our case are single character strings like '3'. But I am hesitant to posit such an object without a clear need and use for it.

I don’t know. Too much speculation. Let’s write a test and see if we can make a function like hidden_pairs work at all. We’ll try to write tests at the Component level this time, not the Puzzle level, The latter is too far away and they’re too hard to write.

But there’s an issue. This may be good news, though it seems bad at first blush. The Component is a list of integer subscripts in range(81), with a Puzzle attached:

class Component:
    def __init__(self, puzzle, start, steps):
        self.puzzle = puzzle
        self.start = start
        self.positions = [start + step for step in steps]

The Component really needs to be like that, because if has to be able to put adjusted notes collections back into the Puzzle.

Let’s see about making a mostly fake Component in our test, and maybe that will drive out a factory kind of method for a test Component.

Eek, I just opened PyCharm and tests are failing. Have I typed into a window accidentally?

I chuckle. I didn’t copy that init. I cut it. That could break things. Roll back. Tests pass. Whew.

We do not have a test file named ‘test_component’. That’s a clear sign that the object is likely recalcitrant. I’ll create the file and tests now, then maybe we’ll look to see where the tests are. I’m sure there are some.

class TestComponent:
    def test_hookup(self):
        assert 3 == 2

I always start that way. I could make a template if I knew how. Anyway, I do that because the failing test tells me that my IDE has found the new tests. If I don’t get the failure, something is wrong somewhere.

    def test_faked_component(self):
        fake_puzzle = [list() for i in range(9)]
        fake_component = Component(fake_puzzle, start=0, steps=range(9))
        assert fake_component.positions == [c for c in range(9)]

This much gives us a Component with positions 0-8, pointing to a fake puzzle with room for 9 elements.

Now we can set up some kind of situation in the Component. It’ll be tedious but not difficult. Try this for size:

    def test_faked_component(self):
        fake_puzzle = [list() for i in range(9)]
        fake_component = Component(fake_puzzle, start=0, steps=range(9))
        assert fake_component.positions == [c for c in range(9)]
        notes_lists = [
            [1, 2, 3, 4],
            [1, 2, 5, 6],  # hidden pair 1, 2
            [3, 4, 5, 6, 7],
            [6, 7, 8],
            [3, 5, 7],
            [4, 6, 8],
            [3, 4],
            [5, 6],
            [7, 8]
        ]
        for i, notes in enumerate(notes_lists):
            fake_component.set_candidates_at(i, notes)
        assert fake_component.candidates_at(2) == [3, 4, 5, 6, 7]

I had high hopes for this but my fake puzzle is just a list and doesn’t understand the set_candidates_at that Component calls. We need to create a real Puzzle. OK, how hard can it be?

Meh, it can be harder than we’d like, because Puzzle will initialize the candidates.

Let’s create a new class method on Puzzle, empty:

    def test_faked_component(self):
        fake_puzzle = Puzzle.empty()
        ...

class Puzzle:
    @classmethod
    def empty(cls):
        return cls.from_list(['0' for i in range(81)])

Our test is green. Let’s see what we have learned that might be useful:

    def test_faked_component(self):
        fake_puzzle = Puzzle.empty()
        fake_component = Component(fake_puzzle, start=0, steps=range(9))
        assert fake_component.positions == [c for c in range(9)]
        notes_lists = [
            [1, 2, 3, 4],
            [1, 2, 5, 6],  # hidden pair 1, 2
            [3, 4, 5, 6, 7],
            [6, 7, 8],
            [3, 5, 7],
            [4, 6, 8],
            [3, 4],
            [5, 6],
            [7, 8]
        ]
        for i, notes in enumerate(notes_lists):
            fake_component.set_candidates_at(i, notes)
        assert fake_component.candidates_at(2) == [3, 4, 5, 6, 7]

How about a method on Component that we can call like this:

    def test_component_with_notes(self):
        notes_lists = [
            [1, 2, 3, 4],
            [1, 2, 5, 6],  # hidden pair 1, 2
            [3, 4, 5, 6, 7],
            [6, 7, 8],
            [3, 5, 7],
            [4, 6, 8],
            [3, 4],
            [5, 6],
            [7, 8]
        ]
        fake_component = Component.with_notes(notes_lists)
        assert fake_component.candidates_at(2) == [3, 4, 5, 6, 7]

We might test more positions in the fake, but for now that will give us this:

class Component:
    @classmethod
    def with_notes(cls, notes_list):
        # special constructor for testing
        from puzzle import Puzzle
        assert len(notes_list) == 9
        puzzle = Puzzle.empty()
        instance = cls(puzzle, 0, range(9))
        for i, notes in enumerate(notes_list):
            instance.set_candidates_at(i, notes)
        return instance

We needed to import puzzle locally to avoid a loop in the imports. I’m sure there’s another way to do that, but I freely grant that I have not learned it. Feel free to educate me in the better way if you happen to read this and happen to know the answer.

The test, meanwhile, is green. Let’s commit: Can create Components with desired notes (candidates) for testing.

Now then. It happens that my sample list was devised, ever so cleverly, as a list with a hidden pair in it, as noted in a comment somewhere above. So we’re ready for testing the hidden pairs idea.

We’ll save that for later. Let’s sum up for now.

Summary

We needed to test a moderately complex algorithm dealing with the component / candidates / notes area. Rather than try to set up a puzzle such that the creation of the candidates lists would produce the desired situation—who ever thought that was a good idea?—we first used our trusty ball-peen hammer to hammer out a Component with the desired candidates, and then moved the code for doing that, manually, over to Puzzle, to create an empty puzzle, and to Component, to create a component with known notes.

None of this was rocket science: it was all quite simple and straightforward. And yet, for quite a few features and manipulations of Component, I’ve been living with tests that were quite hard to create, working through a Puzzle that I crafted on paper to produce the configuration I wanted.

Why did I put up with that? I don’t know why we do things. I’m just happy that I finally got irritated enough to find a better way. Perhaps all the better ways we have in life are, in the end, the result of someone getting ticked off at the old way. It could be.

For now, we’re set up to build some tests much more readily, and I think we’ll be glad we have that capability. Next time, we’ll use it. See you then!