I’ve found some Python code for Sudoku techniques. I do not like it. But it’ll be useful, I reckon, even though we aren’t likely to copy it.

Discoveries

Here’s the site I found. It’s interesting and has decent verbal descriptions of the strategies. I’ve also been reading the Sudoku Wiki, which has descriptions of many strategies, some of them quite deep and far from obvious to the likes of me.

You can peruse the Python code on FSU.org at your leisure. It is highly procedural and, well, not the kind of code I like to work with. But we have to observe that it works and does more than anything I’ve ever written for Sudoku. So in that regard it is a credit to its author. The site also links to a set of puzzles that I think we’ll make use of later on.

Note:
I should mention that the text on the solver page has a mistake. It shows a puzzle text and a picture purporting to be the same puzzle. It is not. Probably some kind of copy-paste or late update that didn’t quite connect the dots.

Thoughts

In reflecting on the program, as I do from time to time during the day and especially in the morning before officially waking up, I’ve been evolving my thinking about the Component, what it contains, and what it does, relating to the Puzzle class as well.

I think that the Puzzle should contain a (partially) solved puzzle, and a corresponding collection of what we’ve been calling Possibilities, a set of collections, for each cell, of the values that are possible at each location. The FSU article refers to these values as “candidates” which might in fact be a better term. Perhaps we’ll switch.

Now, you’re probably not surprised that I think the Puzzle should be like that, because it pretty much is like that. But my thinking, up until recently, was that we could perhaps use the Possibilities list as the only representation of the puzzle, since once the set of candidates is down to only 1, that one value is the solution value at that location. So I am setting that thinking aside, and instead supposing that the Puzzle will keep the partial solution and the possibilities separate. Of course, if our design is any good at all, the way we keep track inside Puzzle will be unknown to most other objects, ideally unknown to any other objects.

Much of our work is done using the Components (row, column, sub-grid (box)), so I’m thinking there that the Component should have enough information to be able to fetch and store Possibilities and puzzle values for any cell in the Component.

All this is just thinking. We’ll do some work toward these ideas, but we’ll try, mostly, to make things possible, but not to force too much design into the system before we need it.

One concern on this is whether the Component should know the Puzzle. It seems to me that it must, but I am leery of designs where the child objects have pointers back to their parents, though if the parents do not also point to the children, I think it’s generally OK.

We’ll keep these thoughts near our mind as we work.

Work

Where were we? Our last two commits were:

  • ignore slow tests temporarily. update possibilities to support Component.
  • create and use class Possibilities

So let’s have a look at Possibilities and what we do with it. But first, let’s do rename it to Candidates, because I keep mistyping “Possibiltes”.

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 create_raw_candidates(self, a_game_string):
        if len(a_game_string) == 9:
            available_values = '123'
        elif len(a_game_string) == 81:
            available_values = '123456789'
        else:
            raise ValueError('problem must have length 9 or 81')
        self.line_size = len(available_values)
        all_possible = [value for value in available_values]
        return [all_possible for cell in range(len(a_game_string))]

    def fill_in_solved(self, a_game_string):
        for cell, value in enumerate(a_game_string):
            if value != '0':
                self.candidates[cell] = [value]
                row = Component.row(self, cell)
                col = Component.column(self, cell)
                sub = Component.sub_grid(self, cell)
                positions = set(row.positions) | set(col.positions) | set(sub.positions)
                positions.discard(cell)
                for pos in positions:
                    self.candidates[pos] = [v for v in self.candidates[pos] if v != value]
                self.candidates[cell] = [value]

PyCharm helped with the renaming, even offering to change the file name for me. Nice. Commit: rename Possibilities to Candidates in the hope that we can spell the latter.

I note that Candidates accepts a “game string” as a constructor parameter. That’s a bit iffy, but I have in mind that we’ll improve it. Let me digress.

Digression:
I have a vague feeling that the Puzzle could be more helpful, I think we should stay alert for cases where we use it and need to know too many details. I think that as we work we’ll find a better balance between Puzzle, Candidates, and the Components. I freely state that at this moment I don’t know what should change.

I do have one notion in mind. I’ve seen two Python Sudoku programs that use numpy to hold the puzzle. One advantage to that is that the puzzle can be addressed by row and column number rather than just cell number. Numpy even allows some wild slicing of the 2D array, which might be nice. I’m wondering whether we need an object to contain either our puzzle, or the Candidates, that makes them addressable in more convenient ways.

We can play with that using the Candidates, and will try to stay alert to a need to address them, or the puzzle, in that fashion. That need may never arise.

OK, enough cogitation, let’s get down to cases. Where are we and what should we do? In Puzzle, we now have our Candidates in place:

class Puzzle:
    def __init__(self, a_game_string):
        Puzzle.puzzle_count += 1
        if len(a_game_string) == 9:
            self.available_values = '123'
            self.line_size = 3
        elif len(a_game_string) == 81:
            self.available_values = '123456789'
            self.line_size = 9
        else:
            raise ValueError('problem must have length 9 or 81')
        self.possibilities = Candidates(a_game_string)
        self.game = a_game_string
        self.guess_position = self.first_unsolved_position()

That member should be renamed to candidates. Done, committed. Do we use it for anything? Not in Puzzle. That’s probably OK. What about the Solver and Techniques, though?

Solver works 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

It’s not clear how that works, is it? Let’s try an extract method:

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

    def try_techniques(self, new_puzzle):
        if self.apply_techniques:
            techniques = SudokuTechniques(new_puzzle)
            new_puzzle = techniques.apply()
        return new_puzzle

What is still not clear here is that find_next_puzzles returns puzzles, based on the current puzzle, with one new value filled in with possible answers. Since we do this recursively, sooner or later, we get to the last unfilled value and if all the others were good guesses, we’re solved. If not, we return and iterate to the next guess.

There are things not to like here, not least that we always try to run the brute solution, and if the puzzle is valid, it will always work. So we’re going to need to test the Techniques separately, not using the solver. That’ll be OK. Let’s explore that class.

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

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

    def only_one_possible_value(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)

    def only_one_possible_position(self):
        pass

We only have one technique really implemented, only_one_possible_value. Let’s see how that works and whether our new Candidates object is involved and helping.

What does this line mean?

    if self.puzzle.game[cell] == '0':

Well, it means that the cell is not yet “solved”, that is, set to a unique value, which could be a guess or could be definitive. We’re looking for ones that are not known.

But wait .. then what do these two lines mean?

for cell in range(self.puzzle.line_size*self.puzzle.line_size):
    if self.puzzle.game[cell] == '0':

They mean, do what follows for every unknown cell in the puzzle. So let’s require the Puzzle to be more helpful:

    def only_one_possible_value(self):
        for cell in self.puzzle.unknown_cells():
            available = self.puzzle.possible_answers(cell)
            if len(available) == 1:
                self.puzzle = Puzzle.new_puzzle_trying_guess(self.puzzle, available[0], cell)

This demands:

class Puzzle:
    def unknown_cells(self):
        return [cell for cell in range(len(self.game)) if self.game[cell] == '0']

Green. Commit: refactoring.

Now what about possible_answers? How does the puzzle get that value? Well, the hard way:

class Puzzle:
    def possible_answers(self, position):
        if self.game[position] != '0':
            return [self.game[position]]
        row = Component.row(self, position)
        column = Component.column(self, position)
        sub_grid = Component.sub_grid(self, position)
        return [c for c in self.available_values if c not in row and c not in column and c not in sub_grid]

It is our intention that the candidates have this answer already. We want this to work:

    def possible_answers(self, position):
        if self.game[position] != '0':
            return [self.game[position]]
        return self.candidates[position]

This change causes 8 tests to fail. Either there is a silly mistake, or, quite likely, we are mot maintaining the invariant that the candidates reflect current reality in the puzzle, possibly due to missing an update somewhere.

OK, silly mistake: Candidates is not subscriptable. Well, by golly it should be. But for now we’ll give it an accessor.

class Candidates:
    def at(self, cell):
        return self.candidates[cell]

And:

class Puzzle:
    def possible_answers(self, position):
        if self.game[position] != '0':
            return [self.game[position]]
        return self.candidates.at(position)

Tests are green. I am not confident, but we’re green and can commit: Techniques and Puzzle start using Candidates.

Let’s review the Technique:

class SudokuTechniques:
    def only_one_possible_value(self):
        for cell in self.puzzle.unknown_cells():
            available = self.puzzle.possible_answers(cell)
            if len(available) == 1:
                self.puzzle = Puzzle.new_puzzle_trying_guess(self.puzzle, available[0], cell)

This should be working just fine … assuming that we’ve updated the Candidates and since we create a new Puzzle each time we find a candidate, we should be OK … except that, well, we’ve created a new puzzle but we’re still looping over the original. So … our self.puzzle will get the cumulative updates OK … but since the loop is already set up, any new singletons won’t show up this time through.

This will require some thinking and we may have done all the thinking we need for this morning. I can think of two ways to go:

One possibility is to loop over this loop until we have found no values to change. That would be easy enough to even try it. It would go like this:

    def only_one_possible_value(self):
        changed = True
        while changed:
            changed = False
            for cell in self.puzzle.unknown_cells():
                available = self.puzzle.possible_answers(cell)
                if len(available) == 1:
                    self.puzzle = Puzzle.new_puzzle_trying_guess(self.puzzle, available[0], cell)
                    changed = True

Another way would be to write a fiendishly clever generator in Puzzle, and, instead of creating a new Puzzle every time through (which we know to be expensive), we could update the current puzzle. (Or, a possible alternative might be to speed up the creation of a new puzzle, which would let us keep puzzles (close to) immutable. (There is the issue of whether we’re updating the Candidates in an existing puzzle.) Point is, immutability is something we should think about.)

We’ll skip the fiendishly clever idea for now. And perhaps, if we are wise, forever.

I’d kind of like to know how many times we actually use this technique.

class SudokuTechniques:
    def only_one_possible_value(self):
        changed = True
        while changed:
            changed = False
            for cell in self.puzzle.unknown_cells():
                available = self.puzzle.possible_answers(cell)
                SudokuTechniques.only_one += 1
                if len(available) == 1:
                    self.puzzle = Puzzle.new_puzzle_trying_guess(self.puzzle, available[0], cell)
                    changed = True

class TestSolver:
    def test_first_9x9_with_technique(self):
        assert self.puzzle_list == self.puzzle_list_2  # ensuring no typos
        puzzle = Puzzle.from_list(self.puzzle_list)
        Solver.solver_count = 0
        SudokuTechniques.only_one = 0
        solver = Solver(puzzle, apply_techniques=True)
        solved_puzzle = solver.solve()
        assert solved_puzzle.is_correctly_solved
        assert Solver.solver_count < 4000
        assert SudokuTechniques.only_one > 70000

In fact the number is about 78000. Seems like a lot. I make a note to look into it. For now, it’s time to summarize and move to the next phase of the day. Commit: improvement to only_one_possible method.

Summary

After some general design thinking, we did a bit of renaming and then made just a few changes to our only existing technique, only_one_possible_value. We made Puzzle provide what we wanted, instead of computing it from more elementary values from Puzzle, and we change Puzzle to use its Candidates instead of recomputing possible answers. And we changed the technique to apply itself repeatedly, until it found nothing to change, because each time we fill in a value in the puzzle, that potentially eliminates candidates in other cells.

We are not doing that as efficiently as we might, because we create a whole new puzzle and new puzzles recompute the whole candidate matrix, while only three components can actually change as a result of a single cell’s setting.

I think that most of our future techniques will change candidates and not set values into the puzzle. That should drive out some more interesting behavior, and, in particular, will raise the question of whether we can and should consider the Puzzle to be immutable. Currently, I believe that it is. Once created, nothing in the Puzzle changes. I think.

And we need to explore whether 78000 “only one” executions makes sense in the context of our 9x9 puzzle. I’m far from sanguine about that number, but the tests are all green. This may be a sign that things are OK, but I am not sanguine, which I may have mentioned, and that makes me wonder whether there is a missing test that would show up a mistake.

We will surely find out soon! See you next time!

Added in Post:
Ah. I think that when we return possible_answers for a cell, we return a singleton list with the cell’s known value if it is known, and I think that means that our code for only_one will reset it. So that’s probably the source of the large number of only_one hits. We’ll explore that anon.