Having come up with the word ‘evolving’, I am ready to tilt once more at the windmill. Will I succeed this time? Spoiler: Yeah but U G L Y!

Note
Here again, second article in a row, I thrash around a lot. A lot of the thrashing, I think, is down to one simple mistake, so tests finally got me to working code. Here again, skimming may be best for you.

Immutable or not immutable, that is the question. Whether ‘tis nobler in the code to change in place, or to create a new instance upon each discovery.

I really think immutable is generally better, but would you write a text editor with an immutable buffer? Would you make a new buffer on each keystroke? Possible not: there might be a better way.

Let’s set the brute solver aside, and consider our more “human” techniques, of which we still have only approximately one and a half. Techniques generally concern themselves with Candidates, the values that a given cell could conceivable contain. They progress by applying various analyses to the Candidates, narrowing one or more candidates, until some candidate has only one possibility. Then they plug in that value as an answer and rinse, repeat.

Let’s look at our only Technique that actually works like that:

Naked Pairs is a technique that is applied to a single Component (row, column, sub-grid). If the component contains exactly two copies of a given pair of possibilities, then all the other candidates in that component can have those possibilities removed, because the cells with just the pair must contain those values in one order or the other.

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

    def apply(self):
        naked_pairs = self.find_all_naked_pairs()
        for naked_pair in naked_pairs:
            self.component.remove_naked_pair(naked_pair)

    def find_all_naked_pairs(self) -> list:
        result = []
        component_candidates = self.component.all_candidates()
        for pos, cand in enumerate(component_candidates):
            if len(cand) == 2:
                if cand in component_candidates[pos+1:]:
                    result.append(cand)
        return result

How does that remove_naked_pair operation work?

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

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

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]

OK, this is absolutely clear: we are modifying the candidates in place. If we want the Puzzle to be truly immutable, all the way down, we’d need to create a new puzzle in Component and return it. As things stand, the Puzzle hasn’t changed. Components are dynamic, recomputed every time they are asked for, not retained in the Puzzle. And the Candidates instance in Puzzle does not change, but its contents do change.

The whole idea of making the Puzzle immutable top to bottom is mostly “received wisdom”. I don’t have any particular stories to tell about how my life was made better by making things immutable, though I have a vague sense that things go better that way. But I am left with low motivation for making the necessary changes.

Let’s do it, not because we are sure it’s the right thing to do, but to see what happens and whether we experience any bad effects.

So let’s see. If we do this, then any Technique, upon apply must return a puzzle, which is either new or not, depending on whether the apply found anything to do.

Let’s see if we can do this top down. I expect some trouble but since we have few Techniques, it may not be so awful.

Well … except that that NakedPairsTechnique doesn’t even know the puzzle. And some of our tests are assuming that things don’t change:

    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']

Here, we refer to the same row instance. If we do make a new puzzle, we’ll have to re-fetch the row. And, in general, no one can be allowed to hold on to a Component for long. Let’s just do it.

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

    def apply(self):
        naked_pairs = self.find_all_naked_pairs()
        for naked_pair in naked_pairs:
            self.puzzle = self.component.remove_naked_pair(naked_pair)
        return self.puzzle

Of course, remove_naked_pair isn’t returning a puzzle yet …

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

Of course, Puzzle isn’t returning a puzzle yet …

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

    def copy(self):
        new_puzzle = Puzzle(self.game)
        new_puzzle.candidates = new_puzzle.candidates.copy()
        return new_puzzle

Just one more thing:

class Candidates:
    def __init__(self, a_game_string):
        self.game = a_game_string
        self.line_size = 0
        self.candidates = self.create_raw_candidates(a_game_string)
        self.fill_in_solved(a_game_string)
        
    def copy(self):

Ah this is nasty. We can’t readily create a Candidates without a lot of rigmarole.

Let’s allow an optional candidates parameter. Didn’t we do this once already? Anyway:

class Candidates:
    def __init__(self, a_game_string, candidates=None):
        if not candidates:
            self.game = a_game_string
            self.line_size = 0
            self.candidates = self.create_raw_candidates(a_game_string)
            self.fill_in_solved(a_game_string)
        else:
            self.game = candidates.game
            self.line_size = candidates.line_size
            self.candidates = candidates

    def copy(self):
        return Candidates(self.game, self.candidates)

I think it is legitimate not to deep copy the candidates. We don’t modify the inner collections, if I’m not mistaken, we only replace them. We have two tests failing, needing revision to accommodate the fact that we return a new puzzle now.

    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']

Similarly for the other similar test. However, the test still failed until I did this:

class Candidates:
    def __init__(self, a_game_string, candidates=None):
        self.game = a_game_string
        if not candidates:
            self.line_size = 0
            self.candidates = self.create_raw_candidates(a_game_string)
            self.fill_in_solved(a_game_string)
        else:
            self.line_size = candidates.line_size
            self.candidates = candidates.candidates

    def copy(self):
        return Candidates(self.game, self)

There’s definitely something naff about candidates.candidates. We need some kind of naming improvement there, at the very least. However, we are green except for our new test, which I now expect to work:

    def test_does_not_lose_info(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, ['7', '8'])
        assert row.candidates_at(1) == ['7', '8']
        new_puzzle = Puzzle.new_puzzle_trying_guess(puzzle, '1', 0)
        new_row = Component.row(new_puzzle, 0)
        assert new_row.candidates_at(1) == ['7', '8']

Oh, well, why would I expect that to work? I haven’t done anything about the new_puzzle_trying_guess yet.

    @classmethod
    def new_puzzle_trying_guess(cls, puzzle, guess, position):
        old_string = puzzle.game
        new_string = old_string[:position] + guess + old_string[position+1:]
        return cls(new_string)

We want to rename this to something about evolve, and to make it do the right thing about preserving the Candidates.

However, I’ve kind of lost the thread here. I think we want something like this:

    @classmethod
    def evolve_with_change(cls, puzzle, change, position):
        old_string = puzzle.game
        new_string = old_string[:position] + change + old_string[position+1:]
        copy = puzzle.copy()
        copy.game = new_string
        return copy

That broke something and I changed this:

class Puzzle:
    def copy(self):
        new_puzzle = Puzzle(self.game)
        new_puzzle.candidates = new_puzzle.candidates.copy()
        return new_puzzle

It seems that can’t possibly be right and should be:

    def copy(self):
        new_puzzle = Puzzle(self.game)
        new_puzzle.candidates = self.candidates.copy()
        return new_puzzle

That, unfortunately, breaks a new test, the little 3x3, because we now are not accommodating the assignment of the new value.

This is too intricate but I think we can make it work. If it works, I think we can probably make it right. We want this:

    @classmethod
    def evolve_with_change(cls, puzzle, change, position):
        old_string = puzzle.game
        new_string = old_string[:position] + change + old_string[position+1:]
        copy = puzzle.copy()
        copy.game = new_string
        # update the components holding position not to have `change` in them
        return copy

I think I can do this.

    @classmethod
    def evolve_with_change(cls, puzzle, change, position):
        old_string = puzzle.game
        new_string = old_string[:position] + change + old_string[position+1:]
        copy = puzzle.copy()
        copy.game = new_string
        # update the components holding position not to have `change` in them
        positions_needing_update = Component.all_impacted_positions(copy, position)
        for position in positions_needing_update:
            values = [v for v in puzzle.candidates.at(position) if v != change]
            puzzle.candidates.set_at(position, values)
        return copy

I really thought this would work. But the 3x3 is now failing.

I think that means that a big puzzle will fail as well. Just to be sure, I’ll turn one on. Yes, it fails. So we can see why the 3x3 is unhappy. The brute solver is returning None.

Let’s just see what our evolve is doing to it.

Note
That evolve is So Messy. I should probably ditch this as a bad job and start again again again.

But let’s get some info.

I resort to some debugging and a couple of levels down in the Solver recursion I find that the candidates for an empty cell have reduced to none. That should never be the case, as it says that the problem is not solvable. I want a trace.

The trace tells me something that I sort of already knew: we’re reducing a candidates list to empty. In the solver, that’s OK … it can make a bad guess. However, it should unwind when we pop the stack. I have what I think it is a pretty good guess: the candidates copy isn’t deep enough. I can write a test for that:

    def test_evolve(self):
        game_string = '103000001'
        puzzle = Puzzle(game_string)
        assert puzzle.candidates.at(1) == ['2']
        puzzle_2: Puzzle = Puzzle.evolve_with_change(puzzle, '2', 1)
        assert puzzle.candidates.at(1) == ['2']

Yay! This fails, with the candidate set to empty. We have a deep copy problem.

I think we can test more directly:

    def test_candidates_copy(self):
        game_string = '103000001'
        puzzle = Puzzle(game_string)
        assert puzzle.candidates.at(1) == ['2']
        new_candidates = puzzle.candidates.copy()
        assert new_candidates.at(1) is not puzzle.candidates.at(1)

Now we know for sure that our list in Candidates is just copied.

class Candidates:
    def __init__(self, a_game_string, candidates=None):
        self.game = a_game_string
        if not candidates:
            self.line_size = 0
            self.candidates = self.create_raw_candidates(a_game_string)
            self.fill_in_solved(a_game_string)
        else:
            self.line_size = candidates.line_size
            self.candidates = candidates.candidates

    def copy(self):
        return Candidates(self.game, self)

I found the bug. This is the correct code:

    @classmethod
    def evolve_with_change(cls, puzzle, change, position):
        old_string = puzzle.game
        new_string = old_string[:position] + change + old_string[position+1:]
        copy = puzzle.copy()
        copy.game = new_string
        positions_needing_update = Component.all_impacted_positions(copy, position)
        for position in positions_needing_update:
            values = [v for v in copy.candidates.at(position) if v != change]
            copy.candidates.set_at(position, values)
        return copy

Previously, the last few lines referred to puzzle, not to copy, so they were setting the wrong candidates entirely. I do think that the other change was also necessary. We could remove it to find out but no.

The 3x3 solver passes. I’ll unskip a big test to be sure we’re solid. It’s a lot slower than it was, 24 seconds where it used to be one or two. The issue, of course, is that we’re now copying all the candidate tables on every recursion of the Solver. There are a lot of them, more than 70,000 if I recall correctly.

But we are green, and I believe that we are treating the Puzzle and its Candidates as immutable. I believe that strongly … but since there exist methods that can change things inside, I am not certain of it. We should do something about that.

But not this morning. It’s almost five hours since I started with the preceding article, way past time for me to break. Let’s sum up.

Summary

In retrospect … I kind of think that backing away and rolling back was a better move in at least a couple of instances this morning. That said, I do think we have the Puzzle immutable now (except during creation), and I propose to increase my certainty about that, and then to get moving again in a more clean situation.

The notion of “evolve” seems to me to be better than the “guess” notion we had before. I think it helps with understanding even though it is used the same as before.

I think it will pay off to have all Technique instances returning a possibly new puzzle rather than modifying the one their are given. Why? Because if some technique does mess things up, there will be a clear place to stand to improve its testing, and, probably a better way to discover which technique is doing something wrong.

I’m not sorry that I started by coding the NakedPairsTechnique to return a new puzzle. It broke a lot more than I had hoped, owing to the fact that we really do need a fairly deep copy of the Puzzle in order to evolve it.

It is possible that there’s a better way. Rather than deep copy the Candidates, could we perhaps come up with a lazy way to update them, so that se can give our new Puzzle the old candidates, but as we update them, they veer away from the original? I think perhaps we could.

I think that the fact that the Candidates object has an instance member named candidates, and that that member is a list of lists, is not helping much at all. One occurrence of candidates.candidates is a pretty solid sign that confusion lies ahead. And we surely have more than one.

But the good news is that even if the code is a bit nasty … and it is, I think we are closer to a design that is robust, with the Puzzle being immutable. Now, we need to get a couple more techniques under our belt, and to work a bit to clean up the mess.

One Majorish Issue

The creation method for Puzzle has become weird because it creates the Candidates in two different ways. We surely need a factory method or two, instead of a direct creation. The factory methods will create the Candidates and pass them in, I would guess. Which will mean that the Candidates class probably needs to be more intelligent … it will probably teach us something. I still think these objects aren’t quite right.

I am not displeased with the morning, but it was not the best morning ever. That I got out with running code saved the morning: had we been red at this point I’d have been quite distressed.

Was that mostly luck? No, it was mostly decades of experience, but I did have to work a lot harder than I care to. I even ran the debugger a bit. Bad Ron, but I’m going to have a biscuit anyway.

See you next time!