Reflection on how things are going makes me think we need to change direction a bit. Can we manage it without rewriting a lot of code? Can we keep all or most of our existing test working? Let’s find out.

My concerns include:

  • The brute force solver will solve anything that can be solved, but isn’t very interesting, in that it doesn’t apply ‘human” strategies at all.
  • The human strategies that I read about involve searching for patterns in the possible values for puzzle cells, and we have very weak support for that sort of thing.
  • The puzzle itself is little more than a string of characters, without providing as much help as an object “should”. (I freely grant that what I’m saying here is that it just doesn’t seem right.)
  • The use of characters instead of numbers 1-9 means that tests tend to refer to the string '3' where 3 would seem more natural.
  • The human solvers, of which we only have about one and a quarter, do not seem to plug into the existing Solver class in a natural way.

I have some ideas for what might be better, including:

  • Represent the puzzle, not as a string of characters, but as a structure where each cell is a collection of possible values for that cell.
  • Given that, probably represent a solved cell as a cell with just one possible value, that is, not otherwise specially indicated.
  • Try to figure out a convenient way to express “human” patterns more directly, more in the fashion that Sudoku experts express them.

Speculating about these ideas leaves me with more and more questions and concerns, most of which are of the form “how might we …”. As soon as I get a couple of those stacked up, the future becomes so foggy that I can’t see anything clearly.

In the olden days, when we believed in doing a lot of design first, I would have tried to figure out all these things in advance. Today, I believe that a paper design is often interesting and always wrong, and that we learn more from trying to build the design than we do in just thinking about it. Not to say that I wouldn’t do paper design: I would, and do. But I try to move it to code as soon as possible.

In the olden days, we worried that that approach would “waste” a lot of code. We might have to throw away our poor starting code and replace it with good, where if we had only thought harder, we might have gone straight to good. In the intervening decades, I’ve learned that I can learn a lot by writing a little code, and that changing from one design to a better one isn’t as big a deal as we used to think it was.

So, we’re going to just get started and see what happens. My prediction is that we’ll encounter only small issues, that the system will be broken only for very short intervals, and that we’ll be able to proceed from where we are to somewhere better without a lo of disruption.

If I’m right, maybe there are ideas here that your team could use. If I’m wrong, it’ll be incredibly amusing, so you win either way.

A Round Tuit

I think we’ll go after a big fish: change the Puzzle so that it contains a collection of possible values, not just a string of characters that are either ‘1’-‘9’, meaning settled, or ‘0’, meaning as yet unsettled.

We’ll start with the idea that, in the possible values collection, if a cell has only one possibility, it’s settled, and if it has more than one, it’s still unsettled. If it contains no possibilities, of course, we’ve done something wrong.

I think we want the possibilities to be integers rather than strings. As such, I think we’d like people to talk with the puzzle in terms of integers rather than strings.

As I say that … it comes to me that the things in the cells in Sudoku are not integers at all. They are simply unique tokens. They could be A-H or dog, cat, pig, owl. There is never any arithmetic done on them. One possibility is that they should be an “enum”, and if I were better with Python enums, and if Python were better at enums, we might go that way.

Based on that little reflection, I think we’ll hold off on the string vs integer issue, and stick with the single-character strings, at least for now.

Let’s look at Puzzle and see about adding possibilities to it. But wait, before we do that, let’s reflect on possibilities, what they are and so on.

It seems to me that the Puzzle will be able to produce the Possibilities for any given cell index. If we were doing object-oriented programming, a Possibilities would be a smart collection of … what … Possibility instances? Or just Guesses? Or just our single-character strings?

We will be wise, according to my standards, to push intelligence down as far as we can, so I think we want to have a PossibilitiesCollection, containing Possibilities, each a smart collection containing PossibleValue instances. Or maybe CellValue.

We’ll sort out the names. Renaming things is nearly trivial in PyCharm.

OK let’s look at Puzzle now.

class Puzzle:
    puzzle_count = 0
    guess_count = 0

    @classmethod
    def new_puzzle_trying_guess(cls, puzzle, guess, position=None):
        if position is None:
            position = puzzle.guess_position
        old = puzzle.game
        new = old[:position] + guess + old[position+1:]
        return cls(new)

    @classmethod
    def from_list(cls, a_list):
        joined = ''.join(a_list)
        return cls(joined)

    def __init__(self, a_game_string):
        Puzzle.puzzle_count += 1
        self.game = a_game_string
        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.guess_position = self.first_unsolved_position()

    @property
    def is_filled_in(self):
        return self.guess_position == -1

    @property
    def columns(self):
        return [Component.column(self,col) for col in range(0, 9)]

    @property
    def columns_are_valid(self):
        return all(column.is_valid for column in self.columns)

    @property
    def rows(self):
        return [Component.row(self, row) for row in range(0, 81, 9)]

    @property
    def rows_are_valid(self):
        return all(row.is_valid for row in self.rows)

    @property
    def sub_grids(self):
        return [Component.sub_grid(self, pos) for pos in [0, 3, 6, 27, 30, 33, 54, 57, 60]]

    @property
    def sub_grids_are_valid(self):
        return all(sub_grid.is_valid for sub_grid in self.sub_grids)

    @property
    def is_correctly_solved(self):
        return self.rows_are_valid\
            and self.columns_are_valid\
            and self.sub_grids_are_valid

    def possible_answers(self, position=None):
        if position is None:
            position = self.guess_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]

    def find_next_puzzles(self):
        guesses = self.possible_answers()
        Puzzle.guess_count += len(guesses)
        puzzles = (Puzzle.new_puzzle_trying_guess(self, guess) for guess in guesses)
        return puzzles

    def first_unsolved_position(self):
        try:
            return self.game.index('0')
        except ValueError:
            return -1

I think that our direction is to have a new object in Puzzle, the collection of possibilities, etc etc on down. We do have code that creates the individual cell entries:

    def possible_answers(self, position=None):
        if position is None:
            position = self.guess_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]

Let’s refactor that right now. I don’t like that position=None trick. Who’s using that, anyway? Just tests? No, it’s the other way around. The only user of the None is in find_next_puzzles right below. Refactor:

    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]

    def find_next_puzzles(self):
        guesses = self.possible_answers(self.guess_position)
        Puzzle.guess_count += len(guesses)
        puzzles = (Puzzle.new_puzzle_trying_guess(self, guess) for guess in guesses)
        return puzzles

Commit that: eliminate None possibility in possible_answers.

Now, when we create an instance, let’s naively fill in all the possibilities. I think we should do that by initializing a completely open puzzle and then putting in the known values, adjusting the possibilities as we go.

Note
I have a concern here that I can’t quite put a finger on, but it’s something about getting out of phase. I think we should move quickly to having only the one representation, not two, i.e. not both the puzzle string and possibilities collection.

First step is to reorder the init:

    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.game = a_game_string
        self.guess_position = self.first_unsolved_position()

Let’s commit that. I’ll just mark these refactoring unless I mention another name.

Now we’ll init the possibilities. We’ll just stick with the little arrays of characters for now, but we need to get some objects in there soon.

    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 = self.create_possibilities(a_game_string)
        self.game = a_game_string
        self.guess_position = self.first_unsolved_position()

Things are broken, no such method. We create:

    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 = self.create_possibilities(a_game_string)
        self.game = a_game_string
        self.guess_position = self.first_unsolved_position()

    def create_possibilities(self, a_game_string):
        self.possibilities = self.create_raw_possibilities()
        self.fill_in_solved(a_game_string)

    def create_raw_possibilities(self):
        all_possible = [value for value in self.available_values]
        size = self.line_size * self.line_size
        return [all_possible for cell in range(size)]

    def fill_in_solved(self, a_game_string):
        pass

I realize, of course, that I don’t have a test for this. Really should have.

    def test_create_raw_possibilities(self):
        game_string = '103000010'
        assert len(game_string) == 9
        possibilities = Puzzle.create_raw_possibilities()

This fails, because the method relies on line size. I don’t think we want that to be the case. We should pass the game string down.

Why? Well, it isn’t really obvious, but if we’re going to have a smart object here sometime soon, we shouldn’t be referring to member variables in Puzzle. I think it’ll become clear that this is better. Not sure? Neither am I, but it feels squidgy to be referring to members at this point.

class TestPuzzle:
    def test_create_raw_possibilities(self):
        game_string = '103000010'
        assert len(game_string) == 9
        possibilities = Puzzle.create_raw_possibilities(game_string)

class Puzzle:
    def create_possibilities(self, a_game_string):
        self.possibilities = self.create_raw_possibilities(a_game_string)
        self.fill_in_solved(a_game_string)

    def create_raw_possibilities(self, a_game_string):
        line_size = len(a_game_string)
        size = line_size * line_size
        all_possible = [value for value in self.available_values]
        return [all_possible for cell in range(size)]

    def fill_in_solved(self, a_game_string):
        pass

The tests run, but Oh! So Slowly! Why? Well, because in our recursive solver, we’re creating this array every darn time we recur.

Let’s fix that with what may be a hack but might actually be OK … I have to change more than I’d like:

class TestPuzzle:
    def test_create_raw_possibilities(self):
        game_string = '103000010'
        assert len(game_string) == 9
        puzzle = Puzzle(game_string)
        possibilities = puzzle.possibilities
        assert len(possibilities) == 9

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 = self.create_possibilities(a_game_string)
        self.game = a_game_string
        self.guess_position = self.first_unsolved_position()

    def create_possibilities(self, a_game_string):
        possibilities = self.create_raw_possibilities(a_game_string)
        possibilities = self.fill_in_solved(possibilities, a_game_string)
        return possibilities

    def create_raw_possibilities(self, a_game_string):
        all_possible = [value for value in self.available_values]
        return [all_possible for cell in range(len(a_game_string))]

    def fill_in_solved(self, possibilities, a_game_string):
        return possibilities

The tests are now a bit too slow, but not terribly so. They were terribly slow for a while, until I realized that I was creating a possibility collection that was the square of the size of the puzzle. 81 squared was taking a while in each of the 83,000 recursions of the solver.

It’s still a bit of an issue, the tests take a couple of seconds to run, but for now I’ll let it ride.

Let’s fill in the solved values. To do that we’ll need to adjust the other values in the possibilities. We have code that does that, using components.

We can do that here … or we can recognize that we want a smart collection here and create it now. Let’s create it now. We’re green. Commit: possibilities under way.

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 = Possibilities(a_game_string)
        self.game = a_game_string
        self.guess_position = self.first_unsolved_position()

class Possibilities:
    def __init__(self, a_game_string):
        self.possibilites = self.create_raw_possibilities(a_game_string)
        self.fill_in_solved(a_game_string)

    def create_raw_possibilities(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')
        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):
        pass

Green. Commit: create and use class Possibilities.

Possibilities has not plugged in the known values, and it has no methods for accessing components, which is going to be an issue.

We’ve already got more duplication than I’d like, with the duplicated check for the size of the game. I think in the end, we’re going to wind up doing everything with Possibilities. How about now for that? A bit early. Let’s plug in the known values and deal with adjusting the components.

But … here’s the thing. If we go in this direction, won’t we have to duplicate the component stuff? No, wait .. Component is its own class and I doesn’t really know what kind of object it’s looking at. It might just work.

Let’s extend our test, but just print the result.

    def test_create_raw_possibilities(self):
        game_string = '103000010'
        assert len(game_string) == 9
        puzzle = Puzzle(game_string)
        possibilities = puzzle.possibilities.possibilites
        assert len(possibilities) == 9
        print(possibilities)
        assert False

At this point, it just prints 9 occurrences of [1, 2 3]. So let’s do the plugging in:

Eww. Component expects a puzzle, not a Possibilities. We’ll see if we can use a little duck typing here:

class Possibilities:
    def fill_in_solved(self, a_game_string):
        for cell, value in enumerate(a_game_string):
            self.possibilities[cell] = [value]
            row = Component.row(self, cell)

This explodes, of course, because Possibilities doesn’t understand some messages that are being sent by Component.

Providing the right values is pretty easy:

class Possibilities:
    def __init__(self, a_game_string):
        self.game = a_game_string
        self.line_size = 0
        self.possibilities = self.create_raw_possibilities(a_game_string)
        self.fill_in_solved(a_game_string)

    def create_raw_possibilities(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):
            self.possibilities[cell] = [value]
            row = Component.row(self, cell)

The big puzzle is again very slow. This time it’s the component thing and we haven’t even done the work.

Let me work on fill_in_solved and get that settled.

    def fill_in_solved(self, a_game_string):
        for cell, value in enumerate(a_game_string):
            if value != '0':
                self.possibilities[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)
                for pos in positions:
                    self.possibilities[pos] = [v for v in self.possibilities[pos] if v != value]

The result printed isn’t what I expect:

    def test_create_raw_possibilities(self):
        game_string = '103000010'
        assert len(game_string) == 9
        puzzle = Puzzle(game_string)
        possibilities = puzzle.possibilities.possibilities
        assert len(possibilities) == 9
        print(possibilities)
        assert False

[[],             ['2'],         [], 
['2', '3'], ['2', '3'], ['1', '2'], 
['2', '3'],         [],     ['2']]

I expect to see the existing values plugged in. I think I just straight up forgot to do that. Fix:

    def fill_in_solved(self, a_game_string):
        for cell, value in enumerate(a_game_string):
            if value != '0':
                self.possibilities[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)
                for pos in positions:
                    self.possibilities[pos] = [v for v in self.possibilities[pos] if v != value]
                self.possibilities[cell] = [value]

['1'],           ['2'],      ['3'], 
['2', '3'], ['2', '3'], ['1', '2'], 
['2', '3'],      ['1'],      ['2']

That is what I expect. What I do not expect is that the tests are now requiring 40 seconds to run. Why? Because whenever we recur to run a new Solver instance, we recreate the possibilities from scratch … and we have more and more to plug in every time around.

I think that with a bit of cleverness we can get that down to constant time, since on each recursion we only change one value, so if we pass in the prior possibilities we should just have to adjust that one’s row, column and sub-grid.

But for now, I think we have accomplished a fair bit, because I am rather confident that our Possibilities object is working correctly. How confident? I’d say about 8.5 out of 10. There’s certainly more to be done. One thing is really quite clear: we’ll want a method to update row, column, sub-grid for a single value. Can we extract that right now?

Isn’t that just this … wait, this is odd:

    def fill_in_solved(self, a_game_string):
        for cell, value in enumerate(a_game_string):
            if value != '0':
                self.possibilities[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)
                for pos in positions:
                    self.possibilities[pos] = [v for v in self.possibilities[pos] if v != value]
                self.possibilities[cell] = [value]

We were setting the cell already but the setting at the top isn’t taking, because we’re clobbering it in the loop. Let’s improve that:

    def fill_in_solved(self, a_game_string):
        for cell, value in enumerate(a_game_string):
            if value != '0':
                self.possibilities[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.possibilities[pos] = [v for v in self.possibilities[pos] if v != value]
                self.possibilities[cell] = [value]

We discard the current cell from the set of positions we’ll change. And then we set it appropriately.

I think there’s a better way to do that. We should think of an invariant, perhaps. What might it be? Something like

  • In each component single-value cells are invariant, multiple-value cells cannot contain any of the single values of any of their components.

That could do with improvement. As could we all. Let’s sum up.

Summary

Most interesting error: I had two misspellings of “possibilities” as “possibilites” and they cancelled out. A subsequent correct spelling found the error.

The Possibilities idea is a fairly big deal, and it’s certainly not complete yet. In particular we’ll want to be able to update a single cell, and we’ll want, ultimately, to replace the Puzzle’s string game with just the Possibilities. And that’s going to require us to come up with something better than recreating it every time we create a new game in the Solver’s recursion.

One possibility (sic) would be to provide the brute-force solver with its own underlying data structure custom made for it. Once we set it loose it goes all the way, so there is no point retaining the possibilities in the long form.

That said, the Solver does recreate possibilities of its own, so a special version may not save that much if we optimize a bit. And, on the gripping hand, we kind of hate the brute anyway, and are moving toward more human approaches. So maybe we just ignore it.

I think there is a bit of raggedness around the Component, that showed up when we made it work with a Possibilities as well as with a Puzzle. We should keep an eye on it.

Overall, however, I think we’ve made a decent step in a better direction for human solutions, and we’ve done it without breaking any tests, though we have slowed two of them down substantially. For now, I’ll switch those off most of the time, maybe running them before the day’s final commit, just to be sure that we haven’t broken Solver.

I’m pleased with progress. It wasn’t elegant, but never got really nasty. A credible Monday, I think. See you next time!