Let’s write a sudoku puzzle as a text file.
%%file sudoku.txt
..3.2.6..
9..3.5..1
..18.64..
..81.29..
7.......8
..67.82..
..26.95..
8..2.3..9
..5.1.3..
Overwriting sudoku.txt
lines = open("sudoku.txt").readlines()
lines
['..3.2.6..\n',
'9..3.5..1\n',
'..18.64..\n',
'..81.29..\n',
'7.......8\n',
'..67.82..\n',
'..26.95..\n',
'8..2.3..9\n',
'..5.1.3..\n']
list("hello")
['h', 'e', 'l', 'l', 'o']
grid = [list(line.strip()) for line in lines]
grid
[['.', '.', '3', '.', '2', '.', '6', '.', '.'],
['9', '.', '.', '3', '.', '5', '.', '.', '1'],
['.', '.', '1', '8', '.', '6', '4', '.', '.'],
['.', '.', '8', '1', '.', '2', '9', '.', '.'],
['7', '.', '.', '.', '.', '.', '.', '.', '8'],
['.', '.', '6', '7', '.', '8', '2', '.', '.'],
['.', '.', '2', '6', '.', '9', '5', '.', '.'],
['8', '.', '.', '2', '.', '3', '.', '.', '9'],
['.', '.', '5', '.', '1', '.', '3', '.', '.']]
def read_puzzle(filename):
lines = open(filename).readlines()
return [list(line.strip()) for line in lines]
def print_grid(grid):
for i in range(9):
if i % 3 == 0:
print("+-------" * 3 + "+")
print_row(grid[i])
print("+-------" * 3 + "+")
def group(values, n):
return [values[i:i+n] for i in range(0, len(values), n)]
def print_row(row):
text = " | ".join([" ".join(part) for part in group(row, 3)])
print("| " + text + " |")
- now lets print the grid
print_grid(grid)
+-------+-------+-------+
| . . 3 | . 2 . | 6 . . |
| 9 . . | 3 . 5 | . . 1 |
| . . 1 | 8 . 6 | 4 . . |
+-------+-------+-------+
| . . 8 | 1 . 2 | 9 . . |
| 7 . . | . . . | . . 8 |
| . . 6 | 7 . 8 | 2 . . |
+-------+-------+-------+
| . . 2 | 6 . 9 | 5 . . |
| 8 . . | 2 . 3 | . . 9 |
| . . 5 | . 1 . | 3 . . |
+-------+-------+-------+
first row #
grid[0]
['.', '.', '3', '.', '2', '.', '6', '.', '.']
def get_row(grid, index):
return grid[index]
get_row(grid, 4)
['7', '.', '.', '.', '.', '.', '.', '.', '8']
def get_column(grid, index):
return [row[index] for row in grid]
get_column(grid, 2)
['3', '.', '1', '8', '.', '6', '2', '.', '5']
now lets make a dictionaries that will keep each of the blocks stored
block_range = {
0: [0, 1, 2],
1: [0, 1, 2],
2: [0, 1, 2],
3: [3, 4, 5],
4: [3, 4, 5],
5: [3, 4, 5],
6: [6, 7, 8],
7: [6, 7, 8],
8: [6, 7, 8],
}
def get_block(grid, row, column):
values = []
for r in block_range[row]:
for c in block_range[column]:
values.append(grid[r][c])
return values
print_grid(grid)
+-------+-------+-------+
| . . 3 | . 2 . | 6 . . |
| 9 . . | 3 . 5 | . . 1 |
| . . 1 | 8 . 6 | 4 . . |
+-------+-------+-------+
| . . 8 | 1 . 2 | 9 . . |
| 7 . . | . . . | . . 8 |
| . . 6 | 7 . 8 | 2 . . |
+-------+-------+-------+
| . . 2 | 6 . 9 | 5 . . |
| 8 . . | 2 . 3 | . . 9 |
| . . 5 | . 1 . | 3 . . |
+-------+-------+-------+
get_block(grid, 0, 4)
['.', '2', '.', '3', '.', '5', '8', '.', '6']
DIGITS = set("123456789")
def get_possible_values(grid, row, col):
existing = get_row(grid, row) + get_column(grid, col) + get_block(grid, row, col)
existing = set(existing)
remaining = DIGITS - existing
return list(remaining)
get_possible_values(grid, 0, 0)
{'4', '5'}
x = {1, 2, 3, 4}
x
{1, 2, 3, 4}
y = {2, 3, 5}
y
{2, 3, 5}
x - y
{1, 4}
{1, 2, 3, 4, 5}
def find_empty_slot(grid):
for i,row in enumerate(grid):
if "." in row:
j = row.index(".")
return i,j
return -1, -1
find_empty_slot(grid)
(0, 0)
values = get_possible_values(grid, 0, 0)
values
{'4', '5'}
grid[0][0] = '4'
find_empty_slot(grid)
(0, 1)
def solve(grid):
i, j = find_empty_slot(grid)
# no empty slot left. That means we solved the puzzle
if (i, j) == (-1, -1):
print("yay! solved!!")
return True
#print(f"({i}, {j}): solve")
values = get_possible_values(grid, i, j)
#print(f"({i}, {j}): possble values", values)
for v in values:
#print(f"({i}, {j}): trying {v}...")
grid[i][j] = v
#print_grid(grid)
if solve(grid):
return True
#print(f"({i}, {j}): no values found. Failed to solve the puzzle.")
grid[i][j] = "."
return False
grid = read_puzzle("sudoku.txt")
print_grid(grid)
solve(grid)
print_grid(grid)
+-------+-------+-------+
| . . 3 | . 2 . | 6 . . |
| 9 . . | 3 . 5 | . . 1 |
| . . 1 | 8 . 6 | 4 . . |
+-------+-------+-------+
| . . 8 | 1 . 2 | 9 . . |
| 7 . . | . . . | . . 8 |
| . . 6 | 7 . 8 | 2 . . |
+-------+-------+-------+
| . . 2 | 6 . 9 | 5 . . |
| 8 . . | 2 . 3 | . . 9 |
| . . 5 | . 1 . | 3 . . |
+-------+-------+-------+
yay! solved!!
+-------+-------+-------+
| 4 8 3 | 9 2 1 | 6 5 7 |
| 9 6 7 | 3 4 5 | 8 2 1 |
| 2 5 1 | 8 7 6 | 4 9 3 |
+-------+-------+-------+
| 5 4 8 | 1 3 2 | 9 7 6 |
| 7 2 9 | 5 6 4 | 1 3 8 |
| 1 3 6 | 7 9 8 | 2 4 5 |
+-------+-------+-------+
| 3 7 2 | 6 8 9 | 5 1 4 |
| 8 1 4 | 2 5 3 | 7 6 9 |
| 6 9 5 | 4 1 7 | 3 8 2 |
+-------+-------+-------+
!cat sudoku.txt
..3.2.6..
9..3.5..1
..18.64..
..81.29..
7.......8
..67.82..
..26.95..
8..2.3..9
..5.1.3..
%%file sudoku2.txt
....2..4.
..8.35...
....7.6.2
.31.4697.
2........
...5.12.3
.49...73.
.......1.
8....4...
Writing sudoku2.txt
%%time
grid = read_puzzle("sudoku2.txt")
print_grid(grid)
solve(grid)
print_grid(grid)
+-------+-------+-------+
| . . . | . 2 . | . 4 . |
| . . 8 | . 3 5 | . . . |
| . . . | . 7 . | 6 . 2 |
+-------+-------+-------+
| . 3 1 | . 4 6 | 9 7 . |
| 2 . . | . . . | . . . |
| . . . | 5 . 1 | 2 . 3 |
+-------+-------+-------+
| . 4 9 | . . . | 7 3 . |
| . . . | . . . | . 1 . |
| 8 . . | . . 4 | . . . |
+-------+-------+-------+
yay! solved!!
+-------+-------+-------+
| 6 9 7 | 1 2 8 | 3 4 5 |
| 4 2 8 | 6 3 5 | 1 9 7 |
| 3 1 5 | 4 7 9 | 6 8 2 |
+-------+-------+-------+
| 5 3 1 | 2 4 6 | 9 7 8 |
| 2 8 6 | 3 9 7 | 4 5 1 |
| 9 7 4 | 5 8 1 | 2 6 3 |
+-------+-------+-------+
| 1 4 9 | 8 5 2 | 7 3 6 |
| 7 5 2 | 9 6 3 | 8 1 4 |
| 8 6 3 | 7 1 4 | 5 2 9 |
+-------+-------+-------+
CPU times: user 8.4 ms, sys: 4.12 ms, total: 12.5 ms
Wall time: 12.1 ms