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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
#!env python
"""
#===============================================================================
#
# FILE: ch-2.py
#
# USAGE: ./ch-2.py
#
# DESCRIPTION: Perl Weekly Challenge 086
# Task 2
# Sudoku Puzzle
#
# Uses backtrack algorithm
#
# AUTHOR: Lubos Kolouch
# CREATED: 11/15/2020 01:27:06 PM
#===============================================================================
"""
import re
from copy import deepcopy
def load_puzzle(puzzle_input):
""" load the puzzle from the input """
puzzle = []
for row in puzzle_input:
row = re.sub("_", "0", row)
puzzle.append(list(map(int, row.split(' '))))
return puzzle
def get_valid_options(puzzle, row, col):
""" eliminate numbers 1-9 that are already taken """
valid_options = {}
for i in range(10):
valid_options[i] = 1
# eliminate already taken numbers
for i in range(9):
try:
del valid_options[puzzle[row][i]]
except:
pass
for i in range(9):
try:
del valid_options[puzzle[i][col]]
except:
pass
if not valid_options:
return
# eliminate quadrant
for row_shift in range(3):
for col_shift in range(3):
row_pos = row // 3 * 3 + row_shift
col_pos = col // 3 * 3 + col_shift
try:
del valid_options[puzzle[row_pos][col_pos]]
except:
pass
return valid_options
def solve_position(puzzle_input):
# backtrack recursively to find the solution
next_puzzle = deepcopy(puzzle_input)
for row, row_data in enumerate(next_puzzle):
for col, item in enumerate(row_data):
if item != 0:
continue
valid_options = get_valid_options(puzzle=next_puzzle, row=row, col=col)
if not valid_options:
# nothing left to try, check if the solution is complete
for test_row in next_puzzle:
for test_item in test_row:
if item == 0:
return
return next_puzzle
for next_key in valid_options:
next_puzzle[row][col] = next_key
next_iteration = solve_position(deepcopy(next_puzzle))
if next_iteration:
return next_iteration
# great, we could fill all empty positions!
return next_puzzle
def print_puzzle(puzzle):
""" print the puzzle """
for row in puzzle:
print(' '.join(list(map(str, row))))
print()
def solve_sudoku(puzzle):
""" let's solve the puzzle! """
puzzle = load_puzzle(puzzle)
print_puzzle(puzzle)
solution = solve_position(puzzle)
print_puzzle(solution)
return solution
assert solve_sudoku(['_ _ _ 2 6 _ 7 _ 1',
'6 8 _ _ 7 _ _ 9 _',
'1 9 _ _ _ 4 5 _ _',
'8 2 _ 1 _ _ _ 4 _',
'_ _ 4 6 _ 2 9 _ _',
'_ 5 _ _ _ 3 _ 2 8',
'_ _ 9 3 _ _ _ 7 4',
'_ 4 _ _ 5 _ _ 3 6',
'7 _ 3 _ 1 8 _ _ _']) == [
[4, 3, 5, 2, 6, 9, 7, 8, 1],
[6, 8, 2, 5, 7, 1, 4, 9, 3],
[1, 9, 7, 8, 3, 4, 5, 6, 2],
[8, 2, 6, 1, 9, 5, 3, 4, 7],
[3, 7, 4, 6, 8, 2, 9, 1, 5],
[9, 5, 1, 7, 4, 3, 6, 2, 8],
[5, 1, 9, 3, 2, 6, 8, 7, 4],
[2, 4, 8, 9, 5, 7, 1, 3, 6],
[7, 6, 3, 4, 1, 8, 2, 5, 9], ]
|
