Let’s see about getting the column, row and sub-grid for a given array index.

I’ll just do some tests, then make them work.

    def test_index_to_column(self):
        assert column_index(0) == 0
        assert column_index(17) == 8
        assert column_index(74) == 2

I think that one is easy:

def column_index(cell_number):
    return cell_number % 9

Now for the row index, which I think is also easy:

    def test_index_to_row(self):
        assert row_index(0) == 0
        assert row_index(8) == 0
        assert row_index(17) == 1
        assert row_index(9) == 1
        assert row_index(10) == 1
        assert row_index(72) == 8
        assert row_index(80) == 8

And:

def row_index(cell_number):
    return cell_number // 9

Those were easy and I am pretty sure they’re even correct.

Thursday 0645

The above was yesterday afternoon. This morning, we’ll strike off in a bit of a different direction.

I’ve decided (for values of decided) that we’ll keep dictionaries mapping each cell number 0-80 to a row, column, or sub-grid. (The values will just be a list of the indices of the cells in each row, column or sub-grid.) So, with that decision in hand, we don’t need to compute the row and column and sub-grid indices: we’ll look them up.

So this morning as I drifted into consciousness, I started thinking about how to represent game state and how to process it. I’ll try now to express and expand those vague ideas.

We’ll represent the state of the game itself as a string of 0-9 characters, at least for now. The zero will represent an empty cell and the other values are, of course, the current value in the corresponding cell. We’ll make that an object and probably give it a pretty print.

The process of solving, it seems to me, will consist of a cycle something like this:

  1. Find the next zero cell. If there is none, the game is solved. Ship it!

  2. If there is a zero cell, we want to begin trying values for that cell. We can find possible values by taking the union of the row, column, and sub-grid for the cell, and differencing that against the integers 1-9. If any values remain, those are possibilities for this position, as things stand. If no values remain, we have tried all the possibilities for this position and we need to back up to whatever position we were working on before this one. If there are values, we pick the first one, and go back to 1, finding the next cell to work on.

During this process, we need to remember each tried value, so that if we return to that cell backing up, we know the next one to try.

What if we did this? Suppose we had an object with the game string in starting form, plus an index and a value. Grr, no, belay that idea. I was thinking that perhaps we wouldn’t update the game state string, but we need it updated so that we can find available values.

But still, at each level, we need to know the cell index we are working on, and we need to know which of its available values to try.

Ah. We’re given a game state and we find the first zero in it. We do not let go of the input state at our level of recursion. We create a new game state, copying the old one, to pass into the recursion. Having found the first zero, we find the available values. We look at our new game state to see which of the values to use: we select the first one larger than the one in our cell in the new state, and put that one into our cell in the new state.

First time thru, that cell will be zero and we pick the first value from available, stuff it into the new state, and recur. Next time around, if there is one, the cell will have that value and we pick whatever value from available is larger than that, stuff that into the state and recur.

I think it’s clear that at any given level of recursion, the starting state never changes unless we give up at that level, and the available values never change.

So I’m thinking that the recursion looks roughly like this:

def solve(a_game_state):
    if a_game_state.is_fully_solved():
        # do whatever we do when solved. yay!
    pos = find_first_zero()
    avails = find_available_choices()
    return process(pos, avails)

def process(pos, avails):
    for value in avails:
        new_state = a_game_state.updated(pos, value)
        solve(new_state)
    # bleh ...

Sorry, couldn’t quite get ahold of it. Let’s see. In a normal recursion we just return the result of a recursive call (plus whatever we do inside), except for the case(s) that stop the recursion. Our state that stops the recursion is that the game is fully solved, that is, there are no zeros.

But here, we’re not just recurring, we need backtracking. Maybe we can’t really keep track just in the recursive calls but using a stack.

What would that look like? Hm.

Given a starting game state we init a stack with that state on it. In a loop:

If the game state at the top of the stack is solved, we return it as the solution.

If it is not solved, we find the first zero position. We get the available values at that position. If there are none, we must backtrack. Somehow we’ll need to remember which position and which available value we were on. What if we had the stack element consist of a “record” [pos, val, string]

I think that at a given level, if we …

Nope, I just can’t quite grok it. I have to make this more concrete. Let’s make up an imaginary simple test and try to solve it.

    def test_3x3(self):
        game = '103000010'
        solved = solve(game)
        assert solved == '123231312'

It’s far too hard to just code up code solve so I’ll belay that one and do a couple of simpler tests of components that I think solve will need:

    def test_pos(self):
        def find_zero(a_game):
            return a_game.index('0')

        game = '103000010'
        assert find_zero(game) == 1
        game = '123000010'
        assert find_zero(game) == 3

That was delightfully easy. The available one will be harder:

    def test_avail(self):
        game = '103000010'
        avail = find_available_values(game, 1)
        assert avail == [2,]

I think we “know” that we want avail to be [1, 2, 3] minus the values in its row and column. (There is no sub-grid in this toy example.)

I need more helper tests. Let’s discuss that briefly in the light of this one:

    def test_row(self):
        def row_used(a_game, position):
            start = position//3
            slice = a_game[start:start+3]
            return [c for c in slice if c != '0']

        game = '103000010'
        assert row_used(game, 1) == ['1', '3']

We’re going to get the values that are already used in the row and column for the position we’re going to work with. Each of those tiny functions really needs to work, so I want to test each one individually? Why? Because if I write them and they don’t work, and then I use them in my more complicated algorithm, and I do test that one, I won’t understand what broke. Was it the algorithm or one of its subs? I’d rather o lots of tiny tests and be confident in them. (And, even so, sometimes my tests are incomplete or mistaken. Even this careful approach isn’t perfect, nor am I.)

In addition, when I write these tiny functions, it helps me create the more complicated things that I need, as we’ll see in a moment, I hope. Let’s do the next test, for the column.

    def test_column(self):
        def column_used(a_game,position):
            start = position%3
            slice = a_game[start:len(a_game):3]
            return [c for c in slice if c != '0']

        game = '103000010'
        assert column_used(game, 1) == ['1',]

Now we can do the test for the available values:

    def test_avail(self):
        def row_used(a_game, position):
            start = position//3
            used_in_row = a_game[start:start+3]
            return [c for c in used_in_row if c != '0']

        def column_used(a_game,position):
            start = position%3
            used_in_column = a_game[start:len(a_game):3]
            return [c for c in used_in_column if c != '0']

        def find_available_values(a_game, position):
            row = row_used(a_game, position)
            column = column_used(a_game,position)
            all_available = '123'
            return [c for c in all_available if c not in row and c not in column]

        game = '103000010'
        avail = find_available_values(game, 1)
        assert avail == ['2',]

Let’s check a few more … and the next one I try fails:

        avail = find_available_values(game, 3)
        assert avail == ['2', '3']

I needed better tests for the row_used. Here’s the test and the fixed version:

    def test_row(self):
        game = '103000010'
        assert row_used(game, 0) == ['1', '3']
        assert row_used(game, 1) == ['1', '3']
        assert row_used(game, 2) == ['1', '3']
        assert row_used(game, 3) == []
        assert row_used(game, 4) == []
        assert row_used(game, 5) == []
        assert row_used(game, 6) == ['1']
        assert row_used(game, 7) == ['1']
        assert row_used(game, 8) == ['1']

def row_used(a_game, position):
    print(f'{position=}')
    start = position // 3 * 3
    print(f'{start=}')
    used_in_row = a_game[start:start + 3]
    print(f'{used_in_row=}')
    return [c for c in used_in_row if c != '0']

With this lesson under my belt, I decide I’d better expand the column test as well.

    def test_column(self):
        game = '103000010'
        assert column_used(game, 1) == ['1',]
        assert column_used(game, 4) == ['1',]
        assert column_used(game, 7) == ['1',]
        assert column_used(game, 0) == ['1',]
        assert column_used(game, 3) == ['1',]
        assert column_used(game, 6) == ['1',]
        assert column_used(game, 2) == ['3',]
        assert column_used(game, 5) == ['3',]
        assert column_used(game, 8) == ['3',]

I could imagine something even more robust, with more values, but now I am feeling confident again.

    def test_avail(self):
        def find_available_values(a_game, position):
            row = row_used(a_game, position)
            column = column_used(a_game,position)
            all_available = '123'
            return [c for c in all_available if c not in row and c not in column]

        game = '103000010'
        avail = find_available_values(game, 0)
        assert avail == ['2',]
        avail = find_available_values(game, 1)
        assert avail == ['2',]
        avail = find_available_values(game, 2)
        assert avail == ['2',]
        avail = find_available_values(game, 3)
        assert avail == ['2', '3']
        avail = find_available_values(game, 4)
        assert avail == ['2', '3']
        avail = find_available_values(game, 5)
        assert avail == ['1', '2']
        avail = find_available_values(game, 6)
        assert avail == ['2', '3']
        avail = find_available_values(game, 7)
        assert avail == ['2', '3']
        avail = find_available_values(game, 8)
        assert avail == ['2',]

And now I feel confident in find_available_values, so I promote it to a free-standing function. Sometimes I like working with functions locally until they are working: it keeps the code and test close together.

We’re getting a lot of free-standing functions building up. That’s OK for now, it’s early days.

I have miles to go before lunch, so let’s sum up.

Summary

We don’t have a lot of Sudoku going on here, but we do have some: we have some utility functions that show us how to ge the used and available values from a game string. Today’s tests were on a 3x3 matrix, so they are suspect, but their shape is correct, despite their needing a bit of adjustment.

But basically, we’re just building up facility with handling these string definitions of Sudoku games.

And I did a little thinking about the algorithm, and I hope it’s clear that I don’t quite see yet what needs to be on the stack, nor quite what the shape of the search needs to be. That will come … at least I am assuming that it will. If not, we have another debacle on our hands.

It won’t be my first debacle, nor my worst. So far, so good. See you next time!