Sudoku: Sub-Grid and More
My theory is that once the sub-grid calculation is added to the Puzzle, we should be able to solve a 9x9. Let’s find out.
The current code for finding available values in Puzzle is this:
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]
That’s all there is for a 3x3. For a 9x9, we need to check the sub-grid, the 3x3 square that the open cell is in. And, of course, we need for all_available to be 123456789, not just 123.
I have some tests for the grid thing but before I forget let’s fix the other bit. We already have that longer value set up in __init__, so we just need to use it:
def __init__(self, a_game_string):
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')
def find_available_values(self, position):
row = self.used_numbers_in_row(position)
column = self.used_numbers_in_column(position)
return [c for c in self.available_values if c not in row and c not in column]
Might as well commit that: use correct available values. And that reminded me to run the tests and pin the test tab for auto run, since I had just re-opened PyCharm and it doesn’t remember pinned tabs.
Now the test for the sub-grid … and that reminds me of something else I wanted to do. The initial test file I started with is named ‘test_sudoku.py’ and I think it needs a more generic name. There are really at least two kinds of tests in there, general tests written to help create the little selection functions, and some specific tests testing the Puzzle class. We should really separate those two, and give the files better names, maybe test_puzzle and test_ideas. Let’s do that tidying now, it’ll make it easier to find what we need. We might even notice it as we go.
Yes, this is a throwaway program, and we don’t really need to keep it clean. Except that even on a small program, better organization makes things go faster, and I’d prefer to push on good habits rather than poor ones. So, first, I’ll move the tests that reference Puzzle class into a separate test class, TestPuzzle,
That turns out to be easy … all the tests from line 128 on down reference Puzzle and none of the ones above. So I just insert a class definition. Now let’s move those with PyCharm’s help.
Type F6, edit the file name, click the button. I do love PyCharm. Those JetBrains folks do very good work.
OK. While I’m at it, rename the other file as intended, to ‘test-ideas.py’. Still 25 tests passing. Commit: tidy and rename test files.
OK. Finally we can find the code for the sub-grid. And we find that it isn’t just exactly what we want. Here are the tests:
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 here’s the function we’re testing:
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
That function is producing the indices of the cells in the desired sub-grid. We can get the values readily enough from that list, but honestly I don’t love that code. Let’s put some new tests into TestPuzzle and use what we have here for ideas, like the file name suggests.
An interesting idea for the tests comes to mind: since this function is tested and produces the indices of the values we want, if we built a Puzzle containing the integers from 0 to 80 in order, we could compare our result to the result of the function above. Of course, there would remain the possibility of accidentally returning the indices … Let’s just do the work and not try to be clever.
My first test cut is this:
def test_grid_0(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999,'
'777888999,'
'777888999,'
]
puzzle = Puzzle.from_list(puzzle_lines)
ones = puzzle.used_numbers_in_sub_grid(0)
assert sum(ones) == 9
I had to be a little bit clever, cut me a break. If I get the right sub-grid here, it’ll be all 1’s and will sum to 9. That does leave open a possible error path and we’ll plug it shortly. No, let’s plug it now, while we’re thinking about it.
def test_different_grid_0(self):
puzzle_lines = [
'123222333',
'456222333',
'789222333',
'444555666',
'444555666',
'444555666',
'777888999,'
'777888999,'
'777888999,'
]
puzzle = Puzzle.from_list(puzzle_lines)
ones = puzzle.used_numbers_in_sub_grid(0)
assert sum(ones) == 45
That’s either the right answer or the test will fail when I think it shouldn’t, so we’re good either way. Let’s get to the method.
OK before we look at the method, we need to deal with the PEBKAC. First of all, the tests are malformed because they have commas inside the quotes sometimes. Second, the values that come back from our method are single-character strings, not numbers that we can sum. For example we change this test:
def test_different_grid_0(self):
puzzle_lines = [
'123222333',
'456222333',
'789222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
one_thru_nine = puzzle.used_numbers_in_sub_grid(0)
assert sum(int(c) for c in one_thru_nine) == 45
Both tests start running. Let’s not review the code yet: it may be wrong. Let’s have more tests. This passes:
def test_grid_0(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
ones = puzzle.used_numbers_in_sub_grid(0)
assert sum((int(c) for c in ones)) == 9
for pos in range(0, 9):
res = puzzle.used_numbers_in_sub_grid(pos)
assert res == ones
Thing is, it shouldn’t. I was mistaken when I wrote it. Calm down, dude. Write them out more longhand.
def test_grid_0(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
ones = puzzle.used_numbers_in_sub_grid(0)
assert sum((int(c) for c in ones)) == 9
for pos in [0, 1, 2, 9, 10, 11, 18, 19, 20]:
res = puzzle.used_numbers_in_sub_grid(pos)
assert res == ones
That should pass, and it does. Let’s write a similar one that is likely to fail:
def test_grid_3(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
twos = puzzle.used_numbers_in_sub_grid(3)
print(f'{twos=}')
assert sum((int(c) for c in twos)) == 18
for pos in [0, 1, 2, 9, 10, 11, 18, 19, 20]:
res = puzzle.used_numbers_in_sub_grid(pos)
assert res == twos
That fails nicely. And, sure enough, it’s returning all ones, as the previous result suggested. Time to review the method:
def used_numbers_in_sub_grid(self, position):
first_index_in_row = position // self.line_size * self.line_size
first_index_in_sub_grid = first_index_in_row // (3*self.line_size) * self.line_size
result = []
for row in range(first_index_in_sub_grid, first_index_in_sub_grid+27, 9):
for col in range(0, 3):
result.append(self.game[row+col])
return result
I’m going to ditch that code and start over with the method rather than try to debug it. I’ll keep this part:
def used_numbers_in_sub_grid(self, position):
result = []
for row in range(first_index_in_sub_grid, first_index_in_sub_grid+27, 9):
for col in range(0, 3):
result.append(self.game[row+col])
return result
I should be able to make my new test pass by setting first_index_in_sub_grid directly to 3. And it does pass. Let’s see …
After some messing about:
def used_numbers_in_sub_grid(self, position):
first_index_in_row = position // self.line_size * self.line_size
offset_in_row = position % 9 // 3 * 3
first_index_in_sub_grid = first_index_in_row // 27 * 27 + offset_in_row
print(f'\n{position=}\n{first_index_in_row=}\n{first_index_in_sub_grid=}')
result = []
for row in range(first_index_in_sub_grid, first_index_in_sub_grid+27, 9):
for col in range(0, 3):
result.append(self.game[row+col])
return result
I am quite sure that this works: I’d say about 85%. Let’s have a few more tests. Here are all the sub-grid ones I have now:
def test_grid_0(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
ones = puzzle.used_numbers_in_sub_grid(0)
assert sum((int(c) for c in ones)) == 9
for pos in [0, 1, 2, 9, 10, 11, 18, 19, 20]:
res = puzzle.used_numbers_in_sub_grid(pos)
assert res == ones
def test_grid_3(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
twos = puzzle.used_numbers_in_sub_grid(3)
print(f'{twos=}')
assert sum((int(c) for c in twos)) == 18
for pos in [3, 4, 5, 12, 13, 14, 21, 22, 23]:
res = puzzle.used_numbers_in_sub_grid(pos)
assert res == twos
def test_grid_42(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
res = puzzle.used_numbers_in_sub_grid(52)
print(f'{res=}')
assert sum((int(c) for c in res)) == 54
for pos in [42, 43, 44, 51, 52, 53, 60, 61, 62]:
res = puzzle.used_numbers_in_sub_grid(pos)
assert res == res
def test_grid_75(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
res = puzzle.used_numbers_in_sub_grid(75)
print(f'{res=}')
assert sum((int(c) for c in res)) == 72
for pos in [57, 58, 59, 66, 67, 68, 75, 76, 77]:
res = puzzle.used_numbers_in_sub_grid(pos)
assert res == res
def test_different_grid_0(self):
puzzle_lines = [
'123222333',
'456222333',
'789222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
one_thru_nine = puzzle.used_numbers_in_sub_grid(0)
assert sum(int(c) for c in one_thru_nine) == 45
Those skip around in the big grid and all then check all the values in a given sub-grid.
I really think this works, though I can’t see how anyone could understand the method as it stands.
But let’s commit: sub-grid tests working.
And I want to try a real game before cleaning up the code.
Grr. I did type one in but I am way ahead of myself. For starters, we aren’t calling our new sub-grid function.
def find_available_values(self, position):
row = self.used_numbers_in_row(position)
column = self.used_numbers_in_column(position)
sub_grid = self.used_numbers_in_sub_grid(position) if self.line_size == 9 else []
return [c for c in self.available_values if c not in row and c not in column and c not in sub_grid]
And even so, my big game test is failing with an error I did not expect:
def test_first_9x9(self):
puzzle = [
'005024013',
'006031000',
'001089507',
'160097005',
'758300090',
'009805000',
'507060324',
'010450970',
'043002000'
]
solver = Solver(puzzle)
solved = solver.solve()
assert solved == ''
I found that puzzle on line and hope it’s legit. Oh, and I didn’t call the right constructor.
def test_first_9x9(self):
puzzle_list = [
'005024013',
'006031000',
'001089507',
'160097005',
'758300090',
'009805000',
'507060324',
'010450970',
'043002000'
]
puzzle = Puzzle.from_list(puzzle_list)
solver = Solver(puzzle)
solved = solver.solve()
assert solved == ''
Still fails but now:
Expected :''
Actual :<puzzle.Puzzle object at 0x1019dbc90>
Someone needs to capture me before I kill again. Should be:
def test_first_9x9(self):
puzzle_list = [
'005024013',
'006031000',
'001089507',
'160097005',
'758300090',
'009805000',
'507060324',
'010450970',
'043002000'
]
puzzle = Puzzle.from_list(puzzle_list)
solver = Solver(puzzle)
solved_puzzle = solver.solve()
assert solved_puzzle.game == ''
And now the error is:
Expected :''
Actual :'985724613476531289231689547164297835758316492329845761597168324612453978843972156'
I think this is correct. Let’s pretty-print it at least:
985724613
476531289
231689547
164297835
758316492
329845761
597168324
612453978
843972156
That is NOT the same answer as the one I found on the web. Is it a valid answer? I think it may be. Let’s get a bit more pretty:
985 724 613
476 531 289
231 689 547
164 297 835
758 316 492
329 845 761
597 168 324
612 453 978
843 972 156
A quick eyeball inspection makes me think we have found a solution. We need a better test.
Hm. The solver keeps finding things that it thinks are answers, and that look good to me, but that do not match the provided answers.
Let’s write a validator.
class Validator():
def __init__(self,solution):
self.solution = solution
self.puzzle = Puzzle(solution)
def contains_1_9(self, chars):
if len(chars) != 9:
return False
for c in '123456789':
if c not in chars:
return False
return True
def is_valid(self):
for row in range(0, 81, 9):
chars = self.puzzle.used_numbers_in_row(row)
if not self.contains_1_9(chars):
return False
for col in range(0,9):
chars = self.puzzle.used_numbers_in_column(col)
if not self.contains_1_9(chars):
return False
for check in [0, 3, 6, 27, 30, 33, 54, 57, 60]:
chars = self.puzzle.used_numbers_in_sub_grid(check)
if not self.contains_1_9(chars):
return False
return True
My latest test is passing:
def test_first_9x9(self):
puzzle_list = [
'020000000',
'000600003',
'074080000',
'000003002',
'080040010',
'600500000',
'000010780',
'500000900',
'000000040'
]
puzzle = Puzzle.from_list(puzzle_list)
solver = Solver(puzzle)
solved_puzzle = solver.solve()
solution = solved_puzzle.game
print()
row = 0
for start in range(0, 81, 9):
sl = solution[start:start+9]
print(f'{sl[0:3]} {sl[3:6]} {sl[6:9]}')
row = row + 1
if row%3 == 0:
print()
validator = Validator(solution)
assert validator.is_valid()
The solution does not match the given one but is correct according to my validator.
Time for a break. Past time, in fact. I’ll see if I can force it to get the same answer by providing more cells.
<sigh> When I give it the first row, my solver is failing, saying it can’t solve. The most likely issue, I think, is that I’ve entered the puzzle incorrectly. I’ll type it in again:
And I find the typo in the test and now I have the same valid result!
Way past time for a break.
Later That Day …
First we’ll commit: Solver solves hard 9x9.
It’s about four hours later, after a big of reading, a lovely Sunday breakfast, and our usual viewing, including a bit of the Tour de France. Let’s sum up.
Summary
I know it’s just one test, but it is a known hard Sudoku, and once I got it typed in correctly, we got the same solution as the published one. Plus we have the new Validator class and I am confident in it as well. So I am quite confident that what we have is a valid Solver. It doesn’t use any strategic thinking or advanced Sudoku reasoning: it just tries and tries until it gets it right. It might be fun to instrument the code to find out how many tries it makes.
Let’s take a quick look at how we might do that. How about the seriously simple approach of incrementing a class variable? That works, and tells me that we created 78431 Solver instances in solving that 9x9. Not bad, since there are about 9 factorial to the ninth power possible solutions, so we’re really quite efficient. FWIW, my tests run in 233 milliseconds. The run takes about 20 ms without that solution, so we can estimate that selecting a value to try takes about 200/78000 ms, which is 0.0026 ms or 2.6 microseconds. Good enough.
Next time we’ll look at this code and see about improving it for clarity and perhaps even efficiency. For now, we can draw some key conclusions:
- Jeffries is capable of writing a Sudoku solver that proceeds by a fairly brute-force algorithm, but one that only tries guesses that might conceivably be correct.
- Test-Driven Development can be used in Sudoku without notable difficulty.
- It is really hard to type in a Sudoku problem correctly.
- Extreme Programming may or may not have anything to do with Sudoku, or Ron Jeffries, or vice versa.
- Darwin may have been right.
- Candide was probably right but it depends on what we mean by “best” of all possible worlds.
See you next time! Just for the terminally nerd-sniped, here’s the Solver and Puzzle code:
from puzzle import Puzzle
class Solver:
solver_count = 0
def __init__(self, puzzle):
Solver.solver_count += 1
self.puzzle = puzzle
def solve(self) -> Puzzle | None:
position = self.puzzle.first_unsolved_position()
if position == -1:
return self.puzzle # it's solved
avails = self.puzzle.find_available_values(position)
if not avails:
return None
for guess in avails:
puzzle = Puzzle.trying(self.puzzle, guess, position)
solver = Solver(puzzle)
solved_puzzle = solver.solve()
if solved_puzzle is not None:
return solved_puzzle
return None
class Puzzle:
@classmethod
def trying(cls, 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):
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')
def used_numbers_in_row(self, position):
start = position // self.line_size * self.line_size
used_in_row = self.game[start:start + self.line_size]
return [c for c in used_in_row if c != '0']
def used_numbers_in_column(self, position):
start = position % self.line_size
used_in_column = self.game[start:len(self.game):self.line_size]
return [c for c in used_in_column if c != '0']
def used_numbers_in_sub_grid(self, position):
first_index_in_row = position // self.line_size * self.line_size
offset_in_row = position % 9 // 3 * 3
first_index_in_sub_grid = first_index_in_row // 27 * 27 + offset_in_row
result = []
for row in range(first_index_in_sub_grid, first_index_in_sub_grid+27, 9):
for col in range(0, 3):
result.append(self.game[row+col])
return result
def find_available_values(self, position):
row = self.used_numbers_in_row(position)
column = self.used_numbers_in_column(position)
sub_grid = self.used_numbers_in_sub_grid(position) if self.line_size == 9 else []
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 first_unsolved_position(self):
try:
return self.game.index('0')
except ValueError:
return -1