Soon, dear, soon. We have the ability to set up a test. Let’s see whether that sketched Hidden Pairs idea will work. I think there is at least one more stop before we’re there, though.

Here’s my sketched attempt at finding hidden pairs, as yet not compiled much less tested:

def hidden_pairs(notes_a, notes_b, complement):
	if len(notes_a) < 2 or len(notes_b) < 2:
		return []
	result = []
	for n1, n2 in combinations(notes_a, 2):
		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])
	return result

I changed pairs to combinations in the above, because pairs is not a thing. I also noticed that I wasn’t returning the result, which is a thing I do rather often. Anyway …. now I can just paste that into my test file and see what happens. It’s a free-standing function or static method, with no reference to self. Now to test …

    def test_hidden_pairs(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]
        ]
        comp = Component.with_notes(notes_lists)
        p1 = comp.candidates_at(0)
        p2 = comp.candidates_at(1)
        complement = [notes for notes in comp.all_candidates() if notes is not p1 and notes is not p2]
        result = hidden_pairs(p1, p2, complement)
        assert result == [[1, 2]]

And that test, my dear siblings in code, passes! I believe that a “woot!” may be called for. I do have a concern, which is that I used integers in the notes, not strings, and we might somehow have returned subscripts 1 and 2. I will endure the tedium of changing all those integers to strings

    def test_hidden_pairs(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']
        ]
        comp = Component.with_notes(notes_lists)
        p1 = comp.candidates_at(0)
        p2 = comp.candidates_at(1)
        complement = [notes for notes in comp.all_candidates() if notes is not p1 and notes is not p2]
        result = hidden_pairs(p1, p2, complement)
        assert result == [['1', '2']]

And we still pass. Commit: first test of hidden_pairs finder runs green.

Let’s have a harder test, much like this one, only harder.

    def test_two_hidden_pairs(self):
        notes_lists = [
            ['3', '4', '5', '6', '7'],
            ['1', '2', '3', '4'],
            ['6', '7', '8'],
            ['3', '5', '7'],
            ['1', '2', '5', '6'],
            ['4', '6', '8'],
            ['3', '4'],
            ['5', '6'],
            ['7', '8']
        ]
        comp = Component.with_notes(notes_lists)
        p1 = comp.candidates_at(1)
        p2 = comp.candidates_at(4)
        complement = [notes for notes in comp.all_candidates() if notes is not p1 and notes is not p2]
        result = hidden_pairs(p1, p2, complement)
        assert result == [['1', '2']]

OK, it isn’t much harder, and arguably not harder at all, because the test is doing the pairs. Let’s make the test loop. We’ll be sketching the code for the full loop of the search part of the full hidden pairs algorithm.

    def test_two_hidden_pairs(self):
        notes_lists = [
            ['3', '4', '5', '6', '7'],  # 5 and 6 are hidden pair
            ['1', '2', '3', '4'],  # 1 and 2 are hidden pair
            ['4', '7', '8'],
            ['3', '4', '7'],
            ['1', '2', '5', '6'],  # here they both are
            ['3', '4', '8'],
            ['3', '4'],
            ['4', '7'],
            ['7', '8']
        ]
        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 ['1', '2'] in result
        assert ['5', '6'] in result

Is it possible that two hidden pairs can exist and both pairs occur in one notes position? I think not, because then there’d be four values for that cell, not just two.

[1, 2, 3, 4]
[1, 2, 5, 8]
[3, 4, 6, 7]
[5, 6, 7]
[7, 8]
[...]

That list would be saying that the only places where 1 and 2 can go is the first two and 3 and 4 can only go in the first and third. There’s not enough room, because either 1 or 2 must be in the first cell and either 3 or 4 must also be in that cell. Contradiction. No need to test to see what we’d get.

I do think there is a general concern, which is that if one of our adjustments to the notes has a defect, we are quite likely to produce a puzzle that cannot be solved, and, I suspect, we are not likely to discover the problem until much later, when we find a contradiction in the puzzle.

I do not know what to do about that. Some of the strategies are quite tricky, and I can readily imagine that I’ll produce one with a defect. We’ll try to test them carefully but I am experienced enough to feel dissatisfied with that. But I do not know what to do other than be careful.

I wonder whether there is a way to check the puzzle for contradictions early on. I don’t recall reading about such a thing. Certainly one thing that could happen is that when we eliminate some possibilities from some cell’s notes, there are no possibilities left. If we are applying the rules correctly, that would mean that we have placed a wrong guess somewhere. That happened to me yesterday, when I was solving a Sudoku by hand, telling me that I had made a mistake.

I think our hidden_pairs function could return more than one pair from a given pair of cells.

def hidden_pairs(notes_a, notes_b, complement):
    if len(notes_a) < 2 or len(notes_b) < 2:
        return []
    result = []
    for n1, n2 in combinations(notes_a, 2):
        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])
    return result

Suppose that both notes_a and notes_b were [ ‘1’, ‘2’, ‘3’, ‘4’] and that none of those values appeared in the complement. The Sudoku is unsolvable, but the function would return six results if I have done my math correctly. Let’s test that.

    def test_bad_hidden_pairs(self):
        # impossible situation, documenting what the code does
        notes_lists = [
            ['1', '2', '3', '4'],  # 1 and 2 are hidden pair
            ['1', '2', '3', '4'],  # 1 and 2 are hidden pair
            ['6', '7', '8'],
            ['5', '6', '7'],
            ['5', '7'],
            ['7', '8'],
            ['5', '8'],
            ['6', '7'],
            ['5', '6']
        ]
        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) == 6
        assert ['1', '2'] in result
        assert ['1', '3'] in result
        assert ['1', '4'] in result
        assert ['2', '3'] in result
        assert ['2', '4'] in result
        assert ['3', '4'] in result

That passes. Now one thing we could do is this: as soon as we find a hidden pair in the two notes sets we’re processing, we could return just that one result, on the grounds that if the puzzle is good there can be no more.

With that change, I think all the tests but the last one should pass:

def hidden_pairs(notes_a, notes_b, complement):
    if len(notes_a) < 2 or len(notes_b) < 2:
        return []
    for n1, n2 in combinations(notes_a, 2):
        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:
                return [[n1, n2]]
    return []

Right. Fix last test.

        assert len(result) == 1
        assert ['1', '2'] in result

With that change in our understanding and algorithm, we can return, not a collection of lists, but just the pair of values in a simple list. Would that be more useful? And should we return an empty list, or None?

Let’s see how we like it with None.

def hidden_pairs(notes_a, notes_b, complement):
    if len(notes_a) < 2 or len(notes_b) < 2:
        return None
    for n1, n2 in combinations(notes_a, 2):
        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:
                return [n1, n2]
    return None

And the tests get tweaked just a bit:

        ...
        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]
            pair = hidden_pairs(p1, p2, complement)
            if pair:
                result.extend([pair])
        assert ['1', '2'] in result
        assert ['5', '6'] in result

I think I don’t like that. Let’s put it back as it was, and find out when we use the result what we really want. Why revert? Because the user code was simpler and the algorithm really only changed by a couple of [].

Commit: more testing.

Winding Down

We’re about ready to sum up. Let’s review hidden_pairs one more time, to see if we have improvements to make.

def hidden_pairs(notes_a, notes_b, complement):
    if len(notes_a) < 2 or len(notes_b) < 2:
        return []
    for n1, n2 in combinations(notes_a, 2):
        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:
                return [[n1, n2]]
    return []

I am not as fond of the nested if as I might be. And I don’t find n1 and n2 to be communicating much.

def hidden_pairs(notes_a, notes_b, complement):
    if len(notes_a) < 2 or len(notes_b) < 2:
        return []
    for n1, n2 in combinations(notes_a, 2):
        pair_also_in_notes_b = n1 in notes_b and n2 in notes_b
        n1_nowhere_else = all([n1 not in c for c in complement])
        n2_nowhere_else = all([n2 not in c for c in complement])
        if pair_also_in_notes_b and n1_nowhere_else and n2_nowhere_else:
            return [[n1, n2]]
    return []

We could extract another function. Let’s step toward that:

First extract variable:

def hidden_pairs(notes_a, notes_b, complement):
    if len(notes_a) < 2 or len(notes_b) < 2:
        return []
    for n1, n2 in combinations(notes_a, 2):
        pair_also_in_notes_b = n1 in notes_b and n2 in notes_b
        n1_nowhere_else = all([n1 not in c for c in complement])
        n2_nowhere_else = all([n2 not in c for c in complement])
        is_hidden_pair = pair_also_in_notes_b and n1_nowhere_else and n2_nowhere_else
        if is_hidden_pair:
            return [[n1, n2]]
    return []

Now extract “method”:

def hidden_pairs(notes_a, notes_b, complement):
    if len(notes_a) < 2 or len(notes_b) < 2:
        return []
    for n1, n2 in combinations(notes_a, 2):
        is_hidden_pair = are_hidden_pair(n1, n2, notes_b, complement)
        if is_hidden_pair:
            return [[n1, n2]]
    return []


def are_hidden_pair(n1, n2, notes_b, complement):
    pair_also_in_notes_b = n1 in notes_b and n2 in notes_b
    n1_nowhere_else = all([n1 not in c for c in complement])
    n2_nowhere_else = all([n2 not in c for c in complement])
    is_hidden_pair = pair_also_in_notes_b and n1_nowhere_else and n2_nowhere_else
    return is_hidden_pair

Inline a couple of things:

def hidden_pairs(notes_a, notes_b, complement):
    if len(notes_a) < 2 or len(notes_b) < 2:
        return []
    for n1, n2 in combinations(notes_a, 2):
        if are_hidden_pair(n1, n2, notes_b, complement):
            return [[n1, n2]]
    return []


def are_hidden_pair(n1, n2, notes_b, complement):
    pair_also_in_notes_b = n1 in notes_b and n2 in notes_b
    n1_nowhere_else = all([n1 not in c for c in complement])
    n2_nowhere_else = all([n2 not in c for c in complement])
    return pair_also_in_notes_b and n1_nowhere_else and n2_nowhere_else

I named the function are just because I didn’t want to have a variable named the same as the function. Now I can rename it.

def hidden_pairs(notes_a, notes_b, complement):
    if len(notes_a) < 2 or len(notes_b) < 2:
        return []
    for n1, n2 in combinations(notes_a, 2):
        if is_hidden_pair(n1, n2, notes_b, complement):
            return [[n1, n2]]
    return []


def is_hidden_pair(n1, n2, notes_b, complement):
    pair_also_in_notes_b = n1 in notes_b and n2 in notes_b
    n1_nowhere_else = all([n1 not in c for c in complement])
    n2_nowhere_else = all([n2 not in c for c in complement])
    return pair_also_in_notes_b and n1_nowhere_else and n2_nowhere_else

Looking at this, I’m pretty satisfied, but I do wonder about the length of the two notes sets. If they are to be hidden pairs, I think we’d expect there to be more than just two values in there. I suspect it doesn’t matter, but we’ll try to remember to think about it. I think I’ll put a comment in there to remind me.

Let’s sum up: I want to make my chai and continue reading The Book of Elsewhere. It’s not bad at all, despite the sort of concerns one might have. I figure you can trust China Mieville.

Summary

The little algorithm that I sketched basically worked. Had I tried to write it in the style of the fsu.edu nested loops, I am pretty sure that I’d have had some serious debugging to do. In the version we have here, the code pretty much expresses the definition of hidden pairs.

If in some component, there are two notes sets, each containing the same two values, and those values appear in no other note sets in the component, then those two values must appear in those two cells, and we can remove any other values from those two note sets.

Perhaps n1 and n2 should be renamed to value_1 and value_2? Let’s try it.

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):
    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
Note
Even right in the middle of summing up, if we notice a possible improvement, we will often make that improvement immediately. Our tests will tell us if it’s OK, while our eyes will tell us if we prefer the code.

For me, this implementation of hidden_pairs is much easier to read than the nested loop version. I suspect it would be easier for most developers, though it will almost certainly make them slow down to think. Reading the nested loop version, I think one kind of skips over it and starts assuming it’s OK. I know that I do.

I kind of wish there was a none function, the opposite of all, but we can’t always get what we want.

I am not saying that this is perfect: I don’t think it is. I am saying that we’re using the objects better and using the language better, taking advantage of its more powerful constructs.

YMMV, of course, and I am open to hearing better ideas from any of you out there.

For today, we’ve put some confidence behind our little algorithm, and set ourselves up for the second phase of hidden pairs, refining the notes sets based on having found the pair.

We’ll do that next time, I imagine. See you then!