Sudoku: A Tiny Solver?
If the code agrees with me, I think I’d like to sketch a tiny solver this morning. Let’s see if that’s feasible. (Spoiler: It is.)
My thoughts this morning turned to doing a little solver, for a 3x3 “Sudoku”. It seemed feasible to me before I was fully awake. I think the thing to do will be to set one up that includes at least one place where a backtrack will be needed. How about this:
1 0 3
0 0 0
0 0 1
If we solve this from left to right, we should immediately try the 2 in position 1 (remember we are zero-based for our sins). Then in position 3 (middle left) we should find two options, 2, and 3, but 2 won’t work. The solution should be:
1 2 3
3 1 2
2 3 1
That assumes that I am not mistaken, which is a card that might turn up at any point in the game. Many points, in fact, there are a lot of mistakes in my deck.
I am still doing all this in a single test file, which is getting a bit messy with all those tiny functions. Maybe it would be good to start on a Solver object, to begin to bring things together. And surely we should stop working with raw strings: we need to b able to ask questions of the game state.
Let’s start with, oh, Puzzle, which will just hold a puzzle consisting of our standard string of 0-9. It will be able to answer questions about rows, columns and sub-grids.
But wait. I’m going to work with 3x3. OK, for now, our Puzzle expects a smaller string. We’ll write it to work that way and then extend or replace it for our larger problems. Maybe there are even 4x4 or 5x5 ones to work on?
So we have all these mini functions at present:
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
def column_index(cell_number):
return cell_number % 9
def row_index(cell_number):
return cell_number // 9
def row_used(a_game, position):
start = position // 3 * 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]
Some of these cater to 9x9, some to 3x3. We’ll have to deal with that, in due time.
I paused here to think for a moment, usually a good idea. Kent Beck said, regarding changing code: “Make the change easy, then make the easy change.” He noted that the first part might not be all that easy. But let’s see if we can ease into our Puzzle object and maybe even our Solver object.
Let’s take this function:
def row_used(a_game, position):
start = position // 3 * 3
used_in_row = a_game[start:start + 3]
return [c for c in used_in_row if c != '0']
And have it use a Puzzle to get the result. In essence, we’ll be creating a small Puzzle class and moving that code into it.
def row_used(a_game, position):
puzzle = Puzzle(a_game)
return puzzle.used_numbers_in_row(position)
And, trivially:
class Puzzle:
def __init__(self, a_game_string):
self.game = a_game_string
def used_numbers_in_row(self, position):
start = position // 3 * 3
used_in_row = self.game[start:start + 3]
return [c for c in used_in_row if c != '0']
Tests are green. Commit: New Puzzle Class
Now let’s move this to its own file, which will help us clear things out of the test file. F6, type the file name, and the class moves. Commit again: Move Puzzle to its own file.
Now we can kind of unwind things by simple refactoring. We have re-implemented row_used to use Puzzle. We could inline that change into a test such as this one:
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']
Just for fun, let’s see what PyCharm can do for us. I suspect we won’t entirely love it. But I’ll try in-line here. Inlining and just letting it do one, gives us this:
def test_row(self):
game = '103000010'
puzzle = Puzzle(game)
assert puzzle.used_numbers_in_row(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']
If we go the whole way it’ll get nasty for a moment but we’ll clean it up. Here goes the whole megillah:
def test_row(self):
game = '103000010'
puzzle = Puzzle(game)
assert puzzle.used_numbers_in_row(0) == ['1', '3']
puzzle1 = Puzzle(game)
assert puzzle1.used_numbers_in_row(1) == ['1', '3']
puzzle2 = Puzzle(game)
assert puzzle2.used_numbers_in_row(2) == ['1', '3']
puzzle3 = Puzzle(game)
assert puzzle3.used_numbers_in_row(3) == []
puzzle4 = Puzzle(game)
assert puzzle4.used_numbers_in_row(4) == []
puzzle5 = Puzzle(game)
assert puzzle5.used_numbers_in_row(5) == []
puzzle6 = Puzzle(game)
assert puzzle6.used_numbers_in_row(6) == ['1']
puzzle7 = Puzzle(game)
assert puzzle7.used_numbers_in_row(7) == ['1']
puzzle8 = Puzzle(game)
assert puzzle8.used_numbers_in_row(8) == ['1']
Hm, that isn’t as easy to fix up as I was thinking. Still, a few deletes and then a name fix-up gives me this:
def test_row(self):
game = '103000010'
puzzle = Puzzle(game)
assert puzzle.used_numbers_in_row(0) == ['1', '3']
assert puzzle.used_numbers_in_row(1) == ['1', '3']
assert puzzle.used_numbers_in_row(2) == ['1', '3']
assert puzzle.used_numbers_in_row(3) == []
assert puzzle.used_numbers_in_row(4) == []
assert puzzle.used_numbers_in_row(5) == []
assert puzzle.used_numbers_in_row(6) == ['1']
assert puzzle.used_numbers_in_row(7) == ['1']
assert puzzle.used_numbers_in_row(8) == ['1']
Just the work of moments, but the last bit I had to do by hand, selecting and pasting. Oh, I bet there was a cool multi-cursor thing to be done there. I’ll keep that in mind for next time, if there is one. Commit: inline use of Puzzle.
Let’s do the test_column the same way.
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',]
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']
I think I see a “better” way, where I change the test first and then make it work again. But let’s stick with the tried and true and change the function:
def column_used(a_game, position):
puzzle = Puzzle(a_game)
return puzzle.used_numbers_in_column(position)
class Puzzle:
def used_numbers_in_column(self, position):
start = position % 3
used_in_column = self.game[start:len(self.game):3]
return [c for c in used_in_column if c != '0']
Commit: Use Puzzle for column.
Now inline uses from this:
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',]
To this:
def test_column(self):
game = '103000010'
puzzle = Puzzle(game)
assert puzzle.used_numbers_in_column(1) == ['1', ]
puzzle1 = Puzzle(game)
assert puzzle1.used_numbers_in_column(4) == ['1', ]
puzzle2 = Puzzle(game)
assert puzzle2.used_numbers_in_column(7) == ['1', ]
puzzle3 = Puzzle(game)
assert puzzle3.used_numbers_in_column(0) == ['1', ]
puzzle4 = Puzzle(game)
assert puzzle4.used_numbers_in_column(3) == ['1', ]
puzzle5 = Puzzle(game)
assert puzzle5.used_numbers_in_column(6) == ['1', ]
puzzle6 = Puzzle(game)
assert puzzle6.used_numbers_in_column(2) == ['3', ]
puzzle7 = Puzzle(game)
assert puzzle7.used_numbers_in_column(5) == ['3', ]
puzzle8 = Puzzle(game)
assert puzzle8.used_numbers_in_column(8) == ['3', ]
Green. Commit? Sure: Refactoring.
Then remove the puzzleN assignment lines. Then select ‘puzzle’ from the puzzle1 reference line. Control+G until all 8 are selected. Right arrow, right arrow, backspace. They are all changed. Escape. I told you there was a cool multi-cursor way. Commit: use just one Puzzle in test.
Both of these changes have found additional references to the functions we replaced, and the result of that is here:
def find_available_values(a_game, position):
puzzle = Puzzle(a_game)
row = puzzle.used_numbers_in_row(position)
puzzle1 = Puzzle(a_game)
column = puzzle1.used_numbers_in_column(position)
all_available = '123'
return [c for c in all_available if c not in row and c not in column]
Let’s treat this the same way, moving it to Puzzle.
def find_available_values(a_game, position):
puzzle = Puzzle(a_game)
return puzzle.find_available_values(position)
class Puzzle:
def find_available_values(self, position):
row = self.used_numbers_in_row(position)
column = self.used_numbers_in_column(position)
all_available = '123'
return [c for c in all_available if c not in row and c not in column]
Green. Commit: move find_available_values to Puzzle.
As before, inline and rename.
def test_avail(self):
game = '103000010'
puzzle = Puzzle(game)
avail = puzzle.find_available_values(0)
assert avail == ['2',]
avail = puzzle.find_available_values(1)
assert avail == ['2',]
avail = puzzle.find_available_values(2)
assert avail == ['2',]
avail = puzzle.find_available_values(3)
assert avail == ['2', '3']
avail = puzzle.find_available_values(4)
assert avail == ['2', '3']
avail = puzzle.find_available_values(5)
assert avail == ['1', '2']
avail = puzzle.find_available_values(6)
assert avail == ['2', '3']
avail = puzzle.find_available_values(7)
assert avail == ['2', '3']
avail = puzzle.find_available_values(8)
assert avail == ['2',]
Green. Commit: tests use Puzzle class as appropriate.
Time to settle down, look around, see where we are.
Retrospective
We came here an hour ago with the intention of working up a solver. As the first step in making that easy, we decided to create a Puzzle class that holds a string and returns answers about available values at a position. That class is hard-coded to size 3x3, but that’s our next target anyway. We’ll deal with larger when we get there.
Let’s write a new test to check my thinking on the proposed puzzle to solve, which is:
1 0 3
0 0 0
0 0 1
Or, in our real notation, that’s Puzzle('103000001'). I was thinking that there’s just one choice for position 1 and 2 for position 3. Test:
def test_avail_in_proposed_solvable_game(self):
puzzle = Puzzle('103000001')
assert puzzle.find_available_values(1) == ['2',]
assert puzzle.find_available_values(3) == ['2', '3']
As expected. (I even watched it fail first, a good habit to have, which I do not do as often as might be ideal.) Commit: new test for proposed puzzle to solve.
So the question before me is, with the edge taken off the morning with the work so far, do I still want to work toward the solver. Let’s do that. I’m not quite sure what to test, and while my Canadian brother Bryan would start with a test for the whole game, I’m not that powerful a wizard, so let’s imagine a method that a Solver might have and write a test for that.
I think I will want separate tests for this. I’ll start a new test class right inside this one. And I know I’m going to have to work out how to run all the tests in the project, which I have forgotten how to configure, since I’ve not created a new project for a long time.
class TestSolver:
def test_hookup(self):
assert 2 + 1 == 4
This test does not fail. I move it to its own file, where it will continue not to fail. I need to make a configuration. That’s easy, and it looks like this:
And now my hookup fails and 15 tests run. So I fix the test:
class TestSolver:
def test_hookup(self):
assert 2 + 2 == 4
And 16 tests run green. Life is good. Commit: Beginning test for Solver.
Now at 0824, I think I’ll take a little break. OK, 0844, break over. I don’t feel any smarter, didn’t really get a good mind-reset. Let’s push on a bit, see what happens.
We’re going to write a Solver class. How might it work? Well, what if we give it an unsolved Puzzle and ask it to solve, and it returns a solved Puzzle. (There is also the possibility that it will fail. We know it will fail during the process, if we make a bad guess. Let’s suppose that it returns None in that case, at least for now.)
Let’s write a test on a Puzzle that is nearly solved:
1 2 3
3 1 2
2 3 0
That’s the sample I made up at the beginning of this article and I think we can solve it with a ‘1’.
def test_nearly_solved(self):
puzzle = Puzzle('123312230')
solver = Solver(puzzle)
solved = solver.solve()
assert solved.game == '123312231'
For now we’ll just rip the game out of the puzzle to check it. We’ll clean that up shortly: right now I don’t want any obstacles to confuse me.
class Solver:
def __init__(self, puzzle):
self.puzzle = puzzle
def solve(self):
return self.puzzle
This should fail with the wrong answer:
Expected :'123312231'
Actual :'123312230'
So far so good. Now let’s elaborate solve a bit:
def solve(self):
position = self.puzzle.first_unsolved_position()
avails = self.puzzle.find_available_values(position)
return self.puzzle
Here I’ve posited a new method on Puzzle, which we’ll now build. We’d better write a test for it, even though it is trivial.
def test_first_available_position(self):
puzzle = Puzzle('123102103')
assert puzzle.first_unsolved_position() == 4
The Python index method hurls if the item is not found.
def first_unsolved_position(self):
try:
return self.game.index('0')
except ValueError:
return None
I think I don’t like the return of None, because we can’t really check our result for being truthy, since 0 is a possible result. Let’s use -1, and add a test for the case.
def test_first_available_position(self):
puzzle = Puzzle('123102103')
assert puzzle.first_unsolved_position() == 4
puzzle = Puzzle('12331231')
assert puzzle.first_unsolved_position() == -1
So that’s good. My solving test is still failing:
def test_nearly_solved(self):
puzzle = Puzzle('123312230')
solver = Solver(puzzle)
solved = solver.solve()
assert solved.game == '123312231'
Now, however, we can work on solve:
def solve(self):
position = self.puzzle.first_unsolved_position()
avails = self.puzzle.find_available_values(position)
if not avails:
return None
return Puzzle.trying(self. avails[0], position)
Here, I’m positing a class method on Puzzle to produce a new Puzzle with the provided value plugged it at position. That will ensure that only Puzzle knows the underlying data structure of a puzzle. Now I have to do the necessary slice and dice.
I’ll want some tests for trying:
def test_trying_inner(self):
puzzle = Puzzle('aXc')
repl = Puzzle.trying(puzzle, 'b', 1)
assert repl.game == 'abc'
def test_trying_first(self):
puzzle = Puzzle('Xbc')
repl = Puzzle.trying(puzzle, 'a', 0)
assert repl.game == 'abc'
def test_trying_last(self):
puzzle = Puzzle('abX')
repl = Puzzle.trying(puzzle, 'c', 2)
assert repl.game == 'abc'
Those all work, leaving me with the main test still failing:
def test_nearly_solved(self):
puzzle = Puzzle('123312230')
solver = Solver(puzzle)
solved = solver.solve()
assert solved.game == '123312231'
The solve so far, with a typo fixed, is:
def solve(self):
position = self.puzzle.first_unsolved_position()
avails = self.puzzle.find_available_values(position)
if not avails:
return None
return Puzzle.trying(self, avails[0], position)
That’s wrong, should be:
def solve(self):
position = self.puzzle.first_unsolved_position()
avails = self.puzzle.find_available_values(position)
if not avails:
return None
return Puzzle.trying(self.puzzle, avails[0], position)
That actually passes the test. I’m not too surprised, I intended it to work, despite about three mistakes. (Lots of those mistake cards in my deck. Your deck perhaps has fewer, but it has some.)
I’m really happy about all these low-level tests, because they give me confidence that all the questions I want to ask about my puzzle are answered correctly.
It is now 0932. I started at 0648, with a short 20 minute break at 0824. I should wrap this up. I’d like to try to finish the solve but I’m not confident that I can do it immediately. Let’s commit: initial trivial solve method. I’ve been sans commit for quite a while: I’m out of practice.
I’ll make one try at the full solve but just one (I promise myself, knowing how often I break promises to myself.)
def solve(self):
position = self.puzzle.first_unsolved_position()
avails = self.puzzle.find_available_values(position)
if not avails:
return None
for guess in avails:
puzzle = Puzzle.trying(self.puzzle, guess, position)
solved = puzzle.solve()
if solved is not None:
return solved
return None
I actually thought that was going to work, but it didn’t. Let’s at least see what happened. Oh, I have to make a Solver.
OK, I broke my promise, as expected, and did some work. And this is passing:
def solve(self):
position = self.puzzle.first_unsolved_position()
if position == -1:
return self.puzzle # it's solved
avails = self.puzzle.find_available_values(position)
print(f'\nin {self.puzzle.game=} {position=} {avails=}')
if not avails:
return None
for guess in avails:
puzzle = Puzzle.trying(self.puzzle, guess, position)
print(f'trying {guess=} {position=} = {puzzle.game}')
solver = Solver(puzzle)
solved = solver.solve()
if solved is not None:
return solved
return None
Very tempting to give it my real puzzle, but I’m going to resist. I’m due a break. Let’s sum up.
Summary
The morning’s objective was to get a good start on a solver, and we have done so. In fact, we have one that has actually solved a very simple puzzle. It might work on the harder one and I swear that I’m not going to find out until the next article.
We have proceeded in a fashion that has moved us from a lot of carefully tested free-standing functions to two small classes:
class Puzzle:
@classmethod
def trying(cls, puzzle, guess, position):
old = puzzle.game
new = old[:position] + guess + old[position+1:]
return cls(new)
def __init__(self, a_game_string):
self.game = a_game_string
def used_numbers_in_row(self, position):
start = position // 3 * 3
used_in_row = self.game[start:start + 3]
return [c for c in used_in_row if c != '0']
def used_numbers_in_column(self, position):
start = position % 3
used_in_column = self.game[start:len(self.game):3]
return [c for c in used_in_column if c != '0']
def find_available_values(self, position):
row = self.used_numbers_in_row(position)
column = self.used_numbers_in_column(position)
all_available = '123'
return [c for c in all_available if c not in row and c not in column]
def first_unsolved_position(self):
try:
return self.game.index('0')
except ValueError:
return -1
class Solver:
def __init__(self, puzzle):
self.puzzle = puzzle
def solve(self):
position = self.puzzle.first_unsolved_position()
if position == -1:
return self.puzzle # it's solved
avails = self.puzzle.find_available_values(position)
print(f'\nin {self.puzzle.game=} {position=} {avails=}')
if not avails:
return None
for guess in avails:
puzzle = Puzzle.trying(self.puzzle, guess, position)
print(f'trying {guess=} {position=} = {puzzle.game}')
solver = Solver(puzzle)
solved = solver.solve()
if solved is not None:
return solved
return None
Note the print statements that I used to figure out what was going on.
I’ll move the Solver class to its own file and commit: initial Solver solves easy problem.
We have 21 tests now, and they are testing the individual bits of what are not Puzzle and Solver. I am glad to have them, because as I built those pieces, I did make some mistakes, and if I had not had the detailed tests, those defects would have given me bad answers and much confusion. I do not need more confusion, I can get as much as that as I need by just doing things.
I have a good feeling about this. Why? Well, for starters it has felt like a continual sequence of small steps progressing more or less toward a solution. But, more, perhaps this article, which I’ll put references to in the old ones, can serve to indicate that the prior “failure” was not due to my ignorance or incompetence, or at least that it didn’t prove that Darwin was wrong and that, instead, Candide was possibly correct.
Be that as it may, things are going well, in small steps supported by tests, and that’s what we like around here.
See you next time!