from component import Row, Column, SubGrid
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 [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 [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 [SubGrid(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
row = Row(self, position)
column = Column(self, position)
sub_grid = SubGrid(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
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:
if self.puzzle.is_filled_in:
return self.puzzle
for new_puzzle in self.puzzle.find_next_puzzles():
solved_puzzle = Solver(new_puzzle).solve()
if solved_puzzle:
return solved_puzzle
return None
class Component():
def __iter__(self):
return iter(self.used)
@property
def used_numbers(self):
return [c for c in self.used if c != '0']
@property
def is_valid(self):
for c in '123456789':
if c not in self.used:
return False
return True
class Row(Component):
def __init__(self, puzzle, position):
start = position - position % puzzle.line_size
self.used = puzzle.game[start:start + puzzle.line_size]
class Column(Component):
def __init__(self, puzzle, position):
start = position % puzzle.line_size
self.used = puzzle.game[start:len(puzzle.game):puzzle.line_size]
class SubGrid(Component):
def __init__(self, puzzle, position):
starting_row_of_sub_grid = position - position % (3*puzzle.line_size)
offset_in_row = position % 9 // 3 * 3
first_index_in_sub_grid = starting_row_of_sub_grid + offset_in_row
result = []
if puzzle.line_size == 9:
for row_index in range(3):
cell = first_index_in_sub_grid + row_index*9
result.extend(puzzle.game[cell:cell+3])
self.used = result
"""
This file contains small tests used to try out small functions such as
functions to access rows or columns or sub-grids. The file is essentially
self-contained, testing nothing but what is here. The tests were used to
answer questions like "How can we easily get the array indices for a column?"
"""
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 pn(cells):
s = ''
ct = 0
for v in cells:
s += f' {v:2d} |'
ct += 1
if ct == 3 or ct == 6:
s += '|'
return s
def pretty_print(solution):
row = 0
print()
s = ''
for start in range(0, 81, 9):
s += '|' + pn(solution[start:start+9]) + '\n'
row = row + 1
if row % 3 == 0:
s += '||\n'
print(s)
class TestIdeas:
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]
"""
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
"""
def test_indexes(self):
grid = '\n'
for c in range(9):
start = c*9
for r in range(9):
v = start + r
v = f"{v:2.0f} "
grid += v
grid += '\n'
# print(grid)
# assert False
def test_index_to_column(self):
assert column_index(0) == 0
assert column_index(17) == 8
assert column_index(74) == 2
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
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
def test_column_print(self):
# cells = [i for i in range(81)]
# pretty_print(cells)
# cells = [i % 9 for i in range(81)]
# pretty_print(cells)
# cells = [i - i % 9 for i in range(81)]
# pretty_print(cells)
# cells = [i - i % 27 for i in range(81)]
# pretty_print(cells)
# cells = [(i - i % 27) + (i % 9)//3*3 for i in range(81)]
# pretty_print(cells)
assert True
from puzzle import Puzzle
from component import Row, Column, SubGrid
class TestPuzzle:
def test_row(self):
game = '103000010'
puzzle = Puzzle(game)
assert Row(puzzle, 0).used_numbers == ['1', '3']
assert Row(puzzle, 1).used_numbers == ['1', '3']
assert Row(puzzle, 2).used_numbers == ['1', '3']
assert Row(puzzle, 3).used_numbers == []
assert Row(puzzle, 4).used_numbers == []
assert Row(puzzle, 5).used_numbers == []
assert Row(puzzle, 6).used_numbers == ['1']
assert Row(puzzle, 7).used_numbers == ['1']
assert Row(puzzle, 8).used_numbers == ['1']
def test_column(self):
game = '103000010'
puzzle = Puzzle(game)
assert Column(puzzle, 1).used_numbers == ['1', ]
assert Column(puzzle, 4).used_numbers == ['1', ]
assert Column(puzzle, 7).used_numbers == ['1', ]
assert Column(puzzle, 0).used_numbers == ['1', ]
assert Column(puzzle, 3).used_numbers == ['1', ]
assert Column(puzzle, 6).used_numbers == ['1', ]
assert Column(puzzle, 2).used_numbers == ['3', ]
assert Column(puzzle, 5).used_numbers == ['3', ]
assert Column(puzzle, 8).used_numbers == ['3', ]
def test_avail(self):
game = '103000010'
puzzle = Puzzle(game)
avail = puzzle.possible_answers(0)
assert avail == ['2',]
avail = puzzle.possible_answers(1)
assert avail == ['2',]
avail = puzzle.possible_answers(2)
assert avail == ['2',]
avail = puzzle.possible_answers(3)
assert avail == ['2', '3']
avail = puzzle.possible_answers(4)
assert avail == ['2', '3']
avail = puzzle.possible_answers(5)
assert avail == ['1', '2']
avail = puzzle.possible_answers(6)
assert avail == ['2', '3']
avail = puzzle.possible_answers(7)
assert avail == ['2', '3']
avail = puzzle.possible_answers(8)
assert avail == ['2',]
def test_avail_in_proposed_solvable_game(self):
puzzle = Puzzle('103000001')
assert puzzle.possible_answers(1) == ['2', ]
assert puzzle.possible_answers(3) == ['2', '3']
def test_first_available_position(self):
puzzle = Puzzle('123102103')
assert puzzle.first_unsolved_position() == 4
puzzle = Puzzle('123312312')
assert puzzle.first_unsolved_position() == -1
def test_we_can_replace_value_at_one(self):
puzzle = Puzzle('aXcdefghi')
repl = Puzzle.new_puzzle_trying_guess(puzzle, 'b', 1)
assert repl.game == 'abcdefghi'
def test_we_can_replace_value_at_zero(self):
puzzle = Puzzle('Xbcdefghi')
repl = Puzzle.new_puzzle_trying_guess(puzzle, 'a', 0)
assert repl.game == 'abcdefghi'
def test_we_can_replace_value_at_end(self):
puzzle = Puzzle('abcdefghX')
repl = Puzzle.new_puzzle_trying_guess(puzzle, 'i', 8)
assert repl.game == 'abcdefghi'
def test_used_in_row(self):
puzzle_lines = [
'123456780',
'023456789',
'123400789',
'123456789',
'123456789',
'123456789',
'123456789',
'123456789',
'123456789',
]
puzzle = Puzzle.from_list(puzzle_lines)
used = Row(puzzle, 4).used_numbers
assert used == ['1', '2', '3', '4', '5', '6', '7', '8']
used = Row(puzzle, 13).used_numbers
assert used == ['2', '3', '4', '5', '6', '7', '8', '9']
used = Row(puzzle, 22).used_numbers
assert used == ['1', '2', '3', '4', '7', '8', '9']
def test_used_in_column(self):
puzzle_lines = [
'023456789',
'103456798',
'203456987',
'345678910',
'453456785',
'563456784',
'673456783',
'783456782',
'893456781',
]
puzzle = Puzzle.from_list(puzzle_lines)
used = Column(puzzle, 9).used_numbers # first column
assert used == ['1', '2', '3', '4', '5', '6', '7', '8']
used = Column(puzzle, 19).used_numbers # second column
assert used == ['2', '4', '5', '6', '7', '8', '9']
used = Column(puzzle, 26).used_numbers # last column
assert used == ['9', '8', '7', '5', '4', '3', '2', '1']
def test_grid_containing_0(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
ones = SubGrid(puzzle, 0).used_numbers
assert sum((int(c) for c in ones)) == 9
for pos in [0, 1, 2, 9, 10, 11, 18, 19, 20]:
res = SubGrid(puzzle, pos).used_numbers
assert res == ones
def test_grid_containing_3(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
twos = SubGrid(puzzle, 3).used_numbers
# 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 = SubGrid(puzzle, pos).used_numbers
assert res == twos
def test_grid_containing_42(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
res = SubGrid(puzzle, 42).used_numbers
# 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 = SubGrid(puzzle, pos).used_numbers
assert res == res
def test_grid_containing_75(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
res = SubGrid(puzzle, 75).used_numbers
# 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 = SubGrid(puzzle, pos).used_numbers
assert res == res
def test_different_grid_containing_0(self):
"""belt and suspenders. just felt nervous."""
puzzle_lines = [
'123222333',
'456222333',
'789222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
one_thru_nine = SubGrid(puzzle, 0).used_numbers
assert sum(int(c) for c in one_thru_nine) == 45
from puzzle import Puzzle
from component import Row, Column, SubGrid
class TestPuzzle:
def test_row(self):
game = '103000010'
puzzle = Puzzle(game)
assert Row(puzzle, 0).used_numbers == ['1', '3']
assert Row(puzzle, 1).used_numbers == ['1', '3']
assert Row(puzzle, 2).used_numbers == ['1', '3']
assert Row(puzzle, 3).used_numbers == []
assert Row(puzzle, 4).used_numbers == []
assert Row(puzzle, 5).used_numbers == []
assert Row(puzzle, 6).used_numbers == ['1']
assert Row(puzzle, 7).used_numbers == ['1']
assert Row(puzzle, 8).used_numbers == ['1']
def test_column(self):
game = '103000010'
puzzle = Puzzle(game)
assert Column(puzzle, 1).used_numbers == ['1', ]
assert Column(puzzle, 4).used_numbers == ['1', ]
assert Column(puzzle, 7).used_numbers == ['1', ]
assert Column(puzzle, 0).used_numbers == ['1', ]
assert Column(puzzle, 3).used_numbers == ['1', ]
assert Column(puzzle, 6).used_numbers == ['1', ]
assert Column(puzzle, 2).used_numbers == ['3', ]
assert Column(puzzle, 5).used_numbers == ['3', ]
assert Column(puzzle, 8).used_numbers == ['3', ]
def test_avail(self):
game = '103000010'
puzzle = Puzzle(game)
avail = puzzle.possible_answers(0)
assert avail == ['2',]
avail = puzzle.possible_answers(1)
assert avail == ['2',]
avail = puzzle.possible_answers(2)
assert avail == ['2',]
avail = puzzle.possible_answers(3)
assert avail == ['2', '3']
avail = puzzle.possible_answers(4)
assert avail == ['2', '3']
avail = puzzle.possible_answers(5)
assert avail == ['1', '2']
avail = puzzle.possible_answers(6)
assert avail == ['2', '3']
avail = puzzle.possible_answers(7)
assert avail == ['2', '3']
avail = puzzle.possible_answers(8)
assert avail == ['2',]
def test_avail_in_proposed_solvable_game(self):
puzzle = Puzzle('103000001')
assert puzzle.possible_answers(1) == ['2', ]
assert puzzle.possible_answers(3) == ['2', '3']
def test_first_available_position(self):
puzzle = Puzzle('123102103')
assert puzzle.first_unsolved_position() == 4
puzzle = Puzzle('123312312')
assert puzzle.first_unsolved_position() == -1
def test_we_can_replace_value_at_one(self):
puzzle = Puzzle('aXcdefghi')
repl = Puzzle.new_puzzle_trying_guess(puzzle, 'b', 1)
assert repl.game == 'abcdefghi'
def test_we_can_replace_value_at_zero(self):
puzzle = Puzzle('Xbcdefghi')
repl = Puzzle.new_puzzle_trying_guess(puzzle, 'a', 0)
assert repl.game == 'abcdefghi'
def test_we_can_replace_value_at_end(self):
puzzle = Puzzle('abcdefghX')
repl = Puzzle.new_puzzle_trying_guess(puzzle, 'i', 8)
assert repl.game == 'abcdefghi'
def test_used_in_row(self):
puzzle_lines = [
'123456780',
'023456789',
'123400789',
'123456789',
'123456789',
'123456789',
'123456789',
'123456789',
'123456789',
]
puzzle = Puzzle.from_list(puzzle_lines)
used = Row(puzzle, 4).used_numbers
assert used == ['1', '2', '3', '4', '5', '6', '7', '8']
used = Row(puzzle, 13).used_numbers
assert used == ['2', '3', '4', '5', '6', '7', '8', '9']
used = Row(puzzle, 22).used_numbers
assert used == ['1', '2', '3', '4', '7', '8', '9']
def test_used_in_column(self):
puzzle_lines = [
'023456789',
'103456798',
'203456987',
'345678910',
'453456785',
'563456784',
'673456783',
'783456782',
'893456781',
]
puzzle = Puzzle.from_list(puzzle_lines)
used = Column(puzzle, 9).used_numbers # first column
assert used == ['1', '2', '3', '4', '5', '6', '7', '8']
used = Column(puzzle, 19).used_numbers # second column
assert used == ['2', '4', '5', '6', '7', '8', '9']
used = Column(puzzle, 26).used_numbers # last column
assert used == ['9', '8', '7', '5', '4', '3', '2', '1']
def test_grid_containing_0(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
ones = SubGrid(puzzle, 0).used_numbers
assert sum((int(c) for c in ones)) == 9
for pos in [0, 1, 2, 9, 10, 11, 18, 19, 20]:
res = SubGrid(puzzle, pos).used_numbers
assert res == ones
def test_grid_containing_3(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
twos = SubGrid(puzzle, 3).used_numbers
# 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 = SubGrid(puzzle, pos).used_numbers
assert res == twos
def test_grid_containing_42(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
res = SubGrid(puzzle, 42).used_numbers
# 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 = SubGrid(puzzle, pos).used_numbers
assert res == res
def test_grid_containing_75(self):
puzzle_lines = [
'111222333',
'111222333',
'111222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
res = SubGrid(puzzle, 75).used_numbers
# 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 = SubGrid(puzzle, pos).used_numbers
assert res == res
def test_different_grid_containing_0(self):
"""belt and suspenders. just felt nervous."""
puzzle_lines = [
'123222333',
'456222333',
'789222333',
'444555666',
'444555666',
'444555666',
'777888999',
'777888999',
'777888999',
]
puzzle = Puzzle.from_list(puzzle_lines)
one_thru_nine = SubGrid(puzzle, 0).used_numbers
assert sum(int(c) for c in one_thru_nine) == 45
