We spoke of Sudoku at FGNO, and my ‘failure’ with it, and with me, apparently, the failure of TDD, Extreme Programming and all of Computer Science.

Introduction

FGNO is Friday Geeks Night Out, held every Tuesday. I sometimes refer to it as Zoom Ensemble just to be fancy. Last night one of the members brought up Sudoku (q.v.). Someone, in a discussion of TDD if I recall, had brought up the fact that back in 2006 I started working on Sudoku and abandoned it after a handful of articles. This proved, among other things:

  1. Ron Jeffries is incompetent because “(reader) could code up Sudoku if (reader) wanted to”.
  2. TDD doesn’t work, because (maybe) Jeffries was using TDD and he never solved Sudoku.
  3. XP doesn’t work, see above.
  4. The theory of evolution doesn’t work, because if it did, then Jeffries would be more optimized than he clearly is.

Since I haven’t had anything to program lately and have therefore not been writing much, I was thinking I might do a bit more with Sudoku. I will surely stop before I have written the world’s best Sudoku solver, and while you can call whatever happens here a “failure” if you want, let’s consider two product efforts.

They both have the same objective, to build a product that does some marvelous thing. They have the same budget and staffing, with equally competent or incompetent people.

The first team, called Team One, works for sixteen months, fails to deliver anything, and the people with the money (but much less of it now) cancel the effort. Did this effort fail? I think most of us would say that it did. If it did, does that prove anything about the process the team used, or the competence of the individuals working? I would argue that it tells us a little but nothing “proven”.

The second team, of course called Team B, works for one month, fails to deliver anything, and reports back to the people with the money that the effort is not feasible given the constraints. (We’ll not trouble ourselves with the specifics.) Did Team B fail? Did their effort fail? I think it’s a lot harder to say they failed, since what they did was to quickly determine that, given the constraints, they couldn’t meet the goals and they stopped rather than drain 15 more months of money from the coffers of the money folks.

So if I write a half dozen articles on Sudoku and then stop, is that winning or losing? Does it prove a lot or a little about me, about TDD, about XP, about Darwin? My guess is that it proves very little but if my only purpose in life is to serve as a bad example, I’ll accept that purpose.

Sudoku

So Sudoku. I’ll assume that you have read about the game or played it and of course set it aside long ago, or perhaps you solve them every day as mental exercise. I never try to solve them, though I do sometimes enjoy the videos of those folx who make videos of themselves solving Sudoku. Here’s a very tentative plan for this time.

I’ll do something in Python. I’ll use tests where I find them appropriate. I currently plan to start with a brute-force solver, because just as back in 2006, I have not made a study of Sudoku-solving strategies, although I know there are some patterns that can help us make decisions. I’m going into this thing just about as uninformed as I can manage.

Hold on a moment while I set up a a PyCharm project. I’ll publish it to GitHub in due time. For now, I’ll try to avoid as much as I can of the boilerplate of setting up an article series, in hopes of getting something done that feels like getting something done.

I start with my standard test setup:

import pytest


class TestSudoku:
    def test_hookup(self):
        assert 2+1 == 3

Tests are green and set to run automatically. I don’t expect this program to get very large, and rather than set up with a test folder and source folder and all that folderol (haha) I’ll just put my files at the root of the project.

We all know, I presume, that a game of Sudoku is solved when each row of the 9x9 matrix, each column, and each of the nine 3x3 sub-matrices that cover the 9x9, contain the digits one through nine. (It follows that no row, column, nor 3x3 can contain any duplicated digits.)

A game starts with a subset of the cells filled in, and the implicit rules of the genre are that a provided game should have only one solution. (It should be “clear” that if you don’t fill in enough cells, the game is still open to multiple solutions.)1

So how might we brute force this thing? I’ll speculate a bit. The starting point will be a game with some of the cells filled in. Those can never change during the solution. They’re “given”. Then, if we proceed in the least intelligent way I can think of, we’ll find a cell that’s not filled and we’ll scribble a guess into it, selecting a value that isn’t duplicated in that cell’s row, column or sub-grid. If there is such a number, we’ll remember the state and find another cell to try. Repeating this, if we get to a point where we have scribbled a guess into each cell, we’ve solved the problem.

If, on the other hand, we’re working on a given cell and there is no guess that won’t cause a duplication in the cell’s row, column, or sub-grid, a prior guess was wrong. So we’ll back down one level and see if we can make another guess for that cell. If we can, we proceed forward again. If not, we back down again, try another value, then proceed.

So let’s think about some things we might want to “know” about the game state. Some cells are given, and we cannot modify those. If we ever back down to the point where we want to modify a given, either the game is malformed (very unlikely) or our algorithm is wrong (less unlikely).

For the remaining, originally blank cells, we can imagine a list of the numbers that cannot go there. Those will be all the other numbers in the row, column or sub-grid where that number lives. We can also imagine all the numbers that might go there, the numbers one through nine that are not in the list of those that cannot be in there.

Since we are brute-forcing, we might just go through those numbers from low to high, making our current guess for that cell the least of the available numbers. (Or we might keep an index of the last number tried. Let’s not get too clever nor committed to a particular solution.)

A brute-force solution of this kind is typically recursive. We select a cell to fill in, we choose a guess from available guesses, we save whatever information we need to save, and we call our solver on the current grid setup. In simple recursive solvers, everything can be on the call stack. I’m not seeing quite how we could manage that unless we copy the whole grid on every guess, and even then I’m not sure how we would know which cell to unwind.

Possibly we would do the cells in a standard order left to right top to bottom or something, but I’d like to leave open the possibility of picking the next cell to try “intelligently”. For example by selecting a cell that doesn’t have many alternatives left, which should help us fail earlier, always a good thing in a recursive search.

Some Test / Code Ideas

I’m pretty ready to solidify some of these vague notions, by turning them to tests and code. I am not committing to any particular design, other than recursive search. But I would like to experiment with a few things, like these:

  1. Finding Sudoku problems and getting them into my program. Is there a well-known commonly used form for them, suitable for computers?
  2. Checking row, column, sub-grid for containing 1-9.
  3. Determining available values for a given cell.
  4. Noticing that there are no available values, a dead giveaway that we need to back up.

I figure as soon as I start working on these, additional ideas and different ideas will come up. We’ll just see what happens.

Now we’ll pause while I look for some samples.

I have found a CSV file with a million games expressed as strings of 81 characters zero through nine. Maybe I’ll use that, its only 164meg. So let’s assume that our input format is 81 characters in a row. I’ll start there.

I scarf up one line and put it in this test:

    def test_setup(self):
        puzzle = '004300209005009001070060043006002087190007400050083000600000105003508690042910300'
        assert len(puzzle) == 81

Passes, so that’s nice. What should our internal format for Sudoku be?

We could keep them in strings and slice and dice. We could keep them in a list and slice and dice. We could come up with some clever indexed structure.

We have nine rows, nine columns, and nine sub-grids. Let’s think in terms of the indices of the cells for each of those. I think a test might go like this:

    def test_make_rows(self):
        rows = make_rows()
        assert rows[8] == [72, 73, 74, 75, 76, 77, 78, 79, 80]

I’m thinking that the zeroth row has 0, 1, 2, 3, 4, 5, 6, 7, 8 and the 8th row is as above, the subscripts of the corresponding cells. Those could be indexes into a flat list or even character indexes into a string.

And I code this:

def make_rows():
    rows = []
    for r in range(9):
        rows.append([])
        for c in range(r*9, r*9+9):
            rows[r].append(c)
    return rows

Test passes.

Let’s do the columns, which aren’t much harder.

    def test_make_columns(self):
        columns = make_columns()
        assert columns[0] == [0, 9, 18, 27, 36, 45, 54, 63, 72]
        assert columns[8] == [8, 17, 26, 35, 44, 54, 62, 71, 80]

I think that’s right. Let’s code. Ha. Test is wrong, should be:

    def test_make_columns(self):
        columns = make_columns()
        assert columns[0] == [0, 9, 18, 27, 36, 45, 54, 63, 72]
        assert columns[8] == [8, 17, 26, 35, 44, 53, 62, 71, 80]

And the code:

def make_columns():
    columns = []
    for r in range(9):
        columns.append([])
        for c in range(9):
            columns[r].append(r + c*9)
    return columns

Now for the sub-grids. The first one goes:

 0  1  2
 9 10 11
18 19 20

The second across is therefore:

 4  5  6
12 13 14
21 22 23

And the second one down is:

27 28 29
36 37 38
45 46 47

So we see the pattern, I think. I’ll start with those in the test but will surely do more:

    def test_make_grids(self):
        grids = make_grids()
        assert grids[0] == [0, 1, 2, 9, 10, 11, 18, 19, 20]
        assert grids[1] == [4, 5, 6, 12, 13, 14, 21, 22, 23]
        assert grids[4] == [27, 28, 29, 36, 37, 38, 45, 46, 47]

And let’s see if we can see the pattern here. We’ll loop r and c in range(3), thinking of r and c as the row and column in my little matrices above. And grid[0] will be c plus r times 9, I think. Turning to code.

I find that I can’t quite write that out longhand. Getting tired here. Let’s try one row at a time:

def make_grids():
    grids = []
    for r in range(3):
        grids.extend(make_grid_row(r))
    return grids

This pattern might be called Put Off the Inevitable or something. Now I “just” have to write make_grid_row, which is clearly much simpler than make_grid.

def make_grids():
    grids = []
    for r in range(3):
        grids.extend(make_grid_row(r))
    return grids


def make_grid_row(row):
    grid_row = []
    for col in range(3):
        grid_row.append([])
        for r in range(3):
            for c in range(3):
                grid_row[col].append(row*27 + r*9 + c)
    return grid_row

I thought that was working. But it isn’t.

Expected :[4, 5, 6, 12, 13, 14, 21, 22, 23]
Actual   :[0, 1, 2, 9, 10, 11, 18, 19, 20]

The test is of course wrong, which isn’t helping. I should draw a picture instead of counting on my fingers.

    def test_make_grids(self):
        grids = make_grids()
        assert grids[0] == [0, 1, 2, 9, 10, 11, 18, 19, 20]
        assert grids[1] == [3, 4, 5, 12, 13, 14, 21, 22, 23]
        assert grids[4] == [27, 28, 29, 36, 37, 38, 45, 46, 47]
        # assert grids[8] == [58, 59, 60, 69, 70, 71, 78, 79, 80]

I find that I want to get a bigger picture of things, and to do that I want to see how my current guess does against all the tests, not just whichever fails first. So I break that single test into four.

I’m still thinking that I have the basic form of make_grid_row correct. Currently I have this:

def make_grid_row(row):
    grid_row = []
    for col in range(3):
        grid_row.append([])
        for r in range(3):
            for c in range(3):
                grid_row[col].append(c + r*9)
    return grid_row

The tests and results are:

    def test_make_grids_0(self):
        grids = make_grids()
        assert grids[0] == [0, 1, 2, 9, 10, 11, 18, 19, 20]

    def test_make_grids_1(self):
        grids = make_grids()
        assert grids[1] == [3, 4, 5, 12, 13, 14, 21, 22, 23]

Expected :[3, 4, 5, 12, 13, 14, 21, 22, 23]
Actual   :[0, 1, 2, 9, 10, 11, 18, 19, 20]

    def test_make_grids_4(self):
        grids = make_grids()
        assert grids[4] == [27, 28, 29, 36, 37, 38, 45, 46, 47]

Expected :[27, 28, 29, 36, 37, 38, 45, 46, 47]
Actual   :[0, 1, 2, 9, 10, 11, 18, 19, 20]

    def test_make_grids_8(self):
        grids = make_grids()
        assert grids[8] == [58, 59, 60, 69, 70, 71, 78, 79, 80]

Expected :[58, 59, 60, 69, 70, 71, 78, 79, 80]
Actual   :[0, 1, 2, 9, 10, 11, 18, 19, 20]

We need our major row times 27 for sure.

OK, dammit, I’m going to draw out a grid and use it. I’m not getting these last tests right doing them in my head.

 0  1  2  3  4  5  6  7  8
 9 10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25 26
27 28 29 30 31 32 33 34 35
36 37 38 39 40 41 42 43 44
45 46 47 48 49 50 51 52 53
54 55 56 57 58 59 60 61 62
63 64 65 66 67 68 69 70 71
72 73 74 75 76 77 78 79 80

I typed that in by hand, so it is probably wrong. Let’s do it by computer to be “sure”.

 0  1  2  3  4  5  6  7  8 
 9 10 11 12 13 14 15 16 17 
18 19 20 21 22 23 24 25 26 
27 28 29 30 31 32 33 34 35 
36 37 38 39 40 41 42 43 44 
45 46 47 48 49 50 51 52 53 
54 55 56 57 58 59 60 61 62 
63 64 65 66 67 68 69 70 71 
72 73 74 75 76 77 78 79 80 

After way too much numerology and way too much local distraction, I decide to formulate the test differently. We’ll number the sub-grids:

0 1 2
3 4 5
6 7 8

And create each one using just that single index.

My tests were still wrong, because the thing I was calling 4 is number 3. Zero base vs one base. Tests, finally:

class TestSudoku:
    def test_setup(self):
        puzzle = '004300209005009001070060043006002087190007400050083000600000105003508690042910300'
        assert len(puzzle) == 81

    def test_make_rows(self):
        rows = make_rows()
        assert rows[8] == [72, 73, 74, 75, 76, 77, 78, 79, 80]

    def test_make_columns(self):
        columns = make_columns()
        assert columns[0] == [0, 9, 18, 27, 36, 45, 54, 63, 72]
        assert columns[8] == [8, 17, 26, 35, 44, 53, 62, 71, 80]

    def test_make_grids_0(self):
        grid = make_grid(0)
        assert grid == [0, 1, 2, 9, 10, 11, 18, 19, 20]

    def test_make_grids_1(self):
        grid = make_grid(1)
        assert grid == [3, 4, 5, 12, 13, 14, 21, 22, 23]

    def test_make_grids_3(self):
        grid = make_grid(3)
        assert grid == [27, 28, 29, 36, 37, 38, 45, 46, 47]

    def test_make_grids_8(self):
        grid = make_grid(8)
        assert grid == [60, 61, 62, 69, 70, 71, 78, 79, 80]

And the code:

def make_rows():
    rows = []
    for r in range(9):
        rows.append([])
        for c in range(r*9, r*9+9):
            rows[r].append(c)
    return rows


def make_columns():
    columns = []
    for r in range(9):
        columns.append([])
        for c in range(9):
            columns[r].append(r + c*9)
    return columns


def make_grid(grid_index):
    grid = []
    first_row_base = grid_index//3*27
    grid_column = grid_index%3
    column_addition = grid_column*3
    for r in range(3):
        row_addition = r*9
        for c in range(3):
            grid.append(first_row_base + row_addition + column_addition + c)
    return grid

We are green, and I am ready for a break. Let me sum up.

Summary

Today can kind of be seen as a finger exercise warmup, but it has started to teach me some lessons.

One of them is something about my inability to visualize the matrix and get the indices right. With luck, we won’t be doing much more of that.

My thinking with the rows and columns and grids is that when we are looking at a cell in the range 0-80, we’ll get the column it’s in (cell_number%9?), the row it’s in (cell_number//9?) and grid (mumble?), which we’ll then use to see what possibilities exist for that cell. And since I can’t just tell you what mumble is, I foresee some more confusion and I am a bit suspicious that the sub-grids might need better numbering. We’ll see what happens: I feel no deep commitment to what we have here.

Next time, I think we’ll probably work on converting cell number to column, row, and sub-grid indexes, and then, hopefully in the same session, work toward finding out what’s used and what’s available in that chunk.

I am thinking that the three chunks are all the same from the viewpoint of our code, they are just three batches of indices with the property that the corresponding cells are supposed to contain the digits from 1 through 9.

Note

A look at the sample million Sudoku problems tells me that they aren’t very good. I’ll look for a better source. We don’t need a million anyway.

Summary Summary

Haven’t failed yet, nor succeeded. Made some progress, building up a little learning. And I still do not plan to do any research into Sudoku algorithms or the like. I’ll just see what I can figure out here at home.

See you next time!



  1. As with “left to the reader”, we write “clear” when something may or may not be clear but we don’t care to write up a sensible exploration of the topic.