We already know of one more ‘smart’ technique that we might apply, but it seems a bit tricky. And how can we provide a ‘menu’ of techniques to be applied? Is this Big Design Up Front?

Our “New” Technique

I got into this phase of the Sudoku project via Tomas, who pointed out that if, in a given component, a particular possible value appears in only one of the lists of possible values for that component’s elements, then that value must be the solution for that element.

If the value ‘6’ can only go into position 30 in that position’s row, well, that’s where it goes, isn’t it? This is different from our existing ‘smart’ technique, which says that if there is only one possible value for an element, we can assign it to that element.

Do you find that hard to think about? I certainly do.

The Menu

At least for testing purposes, and perhaps later, for analyzing performance, we need to be able to control which of our techniques are applied, and in what order they are applied. The technique I’ve been calling “brute force” is special. Most techniques solve only one or two positions. Brute force solves them all, by a repeated process of just guessing. It is smart enough not to guess impossible things, but otherwise it’s just ticking through all possible solutions until it solves the puzzle, or determines that the puzzle is unsolvable.

The other techniques, I think, one tries in order. Is there a value that is forced by the Sudoku rules? Plug it in. Is there any value that is implied by our “new” technique? Plug it in. But every time we apply one of these rules, the situation is changed and we should probably go back and apply all the rules again, one after another.

As I describe the situation to you, and to myself, I am thinking that whether we apply brute force might be a binary choice, while any other techniques we have might be provided in a list. Perhaps when our “smart” techniques run out of ideas, only then do we see whether to give up or run the brute.

The Component

One more topic that has been on my mind, as I think about how to do the new “only one place for this value” technique, is that the current component is just a list of values, if I’m not mistaken. Am I mistaken? Let’s look: we can know the truth.

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

So, right: as it stands, Component is just a list of values (characters in fact) and does not know where they came from.

Let’s take a small risk. I think we’re going to find it valuable for Component to know where the value came from. I could be quite wrong about that, but let’s save the indices, i.e. the positions in the game for which the Component holds the values. We might never use it, but saving it will be trivially easy:

    def __init__(self, puzzle, start, steps):
        self.start = start
        self.indices = [start + step for step in steps]
        self.used = [puzzle.game[index] for index in self.indices]

We make self.indices a concrete collection, and that’s all there is to it. We’re green, so commit: component knows position of each of its used elements.

Writing that message tells me that indices is the wrong name, so before committing:

    def __init__(self, puzzle, start, steps):
        self.start = start
        self.positions = [start + step for step in steps]
        self.used = [puzzle.game[index] for index in self.positions]

Now commit.

Now What?

Welp. Let’s try to test-drive the new technique which we will call “only one place for this value” or something like that.

As things stand now, techniques are handled like this:

class Solver:
    def solve(self) -> Puzzle | None:
        if self.puzzle.is_filled_in:
            return self.puzzle
        for new_puzzle in self.puzzle.find_next_puzzles():
            if self.apply_techniques:
                techniques = SudokuTechniques(new_puzzle)
                new_puzzle = techniques.apply()
            solved_puzzle = Solver(new_puzzle, self.apply_techniques).solve()
            if solved_puzzle:
                return solved_puzzle
        return None

class SudokuTechniques:
    def __init__(self, puzzle):
        self.puzzle = puzzle

    def apply(self):
        self.force()
        return self.puzzle

    def force(self):
        for cell in range(self.puzzle.line_size*self.puzzle.line_size):
            if self.puzzle.game[cell] == '0':
                available = self.puzzle.possible_answers(cell)
                if len(available) == 1:
                    self.puzzle = Puzzle.new_puzzle_trying_guess(self.puzzle, available[0], cell)

For now, the apparent plan is that we apply whatever techniques we know and return the resulting puzzle. We’re treating Puzzle as immutable, so if a technique wants to change anything, it creates a new Puzzle and saves it in the SudokuTechniques instance.

Let’s rename force to only_one_possible_value. Commit that.

We’re going to have a new technique only_one_possible_position, so let’s implement it trivially:

    def apply(self):
        self.only_one_possible_value()
        self.only_one_possible_position()
        return self.puzzle

    def only_one_possible_position(self):
        pass

I find myself worrying about how we’ll manage the looping. Lets try to defer that concern and focus on building this new smart technique.

There’s another thing on my mind, however, and you should be aware of it as you help me: it seems clear that each of these techniques will have its own specialized way of looking at things. As such, it seems nearly certain that each technique should be, not a method on SudokuTechniques, but a class of its own. We could cater to that now, but it defers actually solving the problem. So let’s belay that idea as well, for now.

Only One Possible Position

I think we have an example of this situation, because Tomas pointed it out. Ah yes, the top left sub-grid of our “hard” problem:

     
1389 2 135689
189 159 1589
139 7 4
     


Notice the ‘6’ in position 2: it is not possible anywhere else in the component and therefore it must go in position 2.

So for testing, we should be able to pull out just that sub-grid component and work with it.

What we need to work with is the collection of possible answers at each position in the component. Let’s try to write a test.

I want to be sure I’m getting the same values as above, so as my first partial test I have done this much:

    def test_only_one_possible_position(self):
        puzzle = Puzzle.from_list(self.puzzle_list)
        sub_grid = Component.sub_grid(puzzle, 0)
        print(f'\n{sub_grid.used=}')
        available_values = [puzzle.possible_answers(position) for position in sub_grid.positions]
        print(f'{available_values=}')
        assert False

The first time through, I found that possible_answers in Puzzle doesn’t check to see if the cell it’s analyzing is already solved. I changed that and a test broke because it was assuming the old scheme. I changed the test to reflect this new definition, which I think makes more sense.

My print tells me that I am getting the same values that we had in the version Tomas referred to. The elements are:

['1', '3', '8', '9'], 
['2'], 
['1', '3', '5', '6', '8', '9'], 
['1', '8', '9'], 
['1', '5', '9'], 
['1', '5', '8', '9'], 
['1', '3', '9'], 
['7'], 
['4']

We see (again) that the value ‘6’ appears in only one position. Since ‘6’ must go somewhere, it must go there.

We vaguely recall from earlier testing that we want to difference each collection against all the other collections and fi at the end there is just one thing left, stuff it into the puzzle.

I’m thinking that what we really should do is to have a new little object, a PuzzleEdit, consisting of a value and a position. Our techniques should return a PuzzleEdit, which we would apply. Or they can return None, signifying that they have nothing to do. I think that’s going to be better than checking to see if they modified our member variable.

Now we can advance our test. I think I’ll put the solution in the test file until it takes a reasonable form.

    def test_only_one_possible_position(self):
        puzzle = Puzzle.from_list(self.puzzle_list)
        sub_grid = Component.sub_grid(puzzle, 0)
        available_values = [puzzle.possible_answers(position) for position in sub_grid.positions]
        cell_to_check = 2
        values = available_values[2]
        for cell in range(9):
            if cell != cell_to_check:
                values = [value for value in values if value not in available_values[cell]]
        assert len(values) == 1
        assert values[0] == '6'

Test passes. This code, a bit clunky for creating all those lists, is correct. I feel quite sure about that. We need to check the others and make sure we have an algorithm that will do the right thing, in particular when the cell is already considered “solved”, that is, already contains only one value in the Component.

I’m feeling like the Component should be helping us more here.

And I am discernibly tired and there is important Tour de France to watch. Let’s quickly sum up.

Summary

So, we did some design thinking. Is that “Big Design Up Front”? No, when we coined that phrase we had in mind taking a few months to design before getting started, not a few minutes. Stand down.

Recall that I took a flyer and included the source cell in Component, thinking that it would be useful. And I believe we can see that, now that we have that magical value ‘6’, we want to put it back, not into position 2 in the component, but into whatever cell in the game position 2 refers to. (That happens to be absolute position 2. We may need a better test, but I think we can create one.)

Then I decided to implement my solution first as part of the test file. Why? It would be “easy enough” to posit a method in SudokuTechniques and build what we need there. Often, I’ll do that very thing, programming “by intention” as Beck called it. Why not this time?

I’m not sure. It’s something about confidence, something about complexity. The method in SudokuTechniques will need to consider all positions in whatever component it looks at, and I think it’ll look, at least potentially, at every component in the game. And I wanted to test just one. So the code in the techniques class will contain something like the code in the test, somewhere, but with a lot of other code around it.

I wanted to isolate out this tiny bit, how to test one position. Thinking about that gave us the notion of a “PuzzleEdit” object, which seems it might be a good idea.

So I’m glad that I did it that way. And I think I’m glad that I don’t always do it that way, because sometimes it seems like too small a step (which is probably not even possible). Other times, there is support in the object we’re testing against, and we want to take advantage of that.

So this feeling is possibly suggesting something we suspect anyway: the techniques want to have their own unique support, probably in their own class, rather than to appear as methods in one big class.

We’ll have to wait to see whether that turns out to be the case, but I’d bet quite a lot that it will. We can see right now that if we keep them all in SudokuTechniques the description of the class will be, “well, it does this and then it does that and then …” and that, my friends, is the description of a junk class that needs to be split up.

So, we’ve learned a bit and probably started some thoughts running that will help us with the next phase. For now, it’s break time! See you again soon!