fun

Sudoku solver: Major bugfixing. I also added some example sudokus for quick testing purposes, in comments.

Author
Vngngdn
Date
July 23, 2016, 2:07 p.m.
Hash
c49cecb41d43ff8fdd3be6e07d2aeae3a3a488ed
Parent
75a01245f2fc4d11735d7978a9d55b7fc4ddfaf4
Modified file
sudoku-solver.py

sudoku-solver.py

51 additions and 9 deletions.

View changes Hide changes
1
1
sudoku-solver.py - A simple program that can solve any (solvable) sudoku puzzle.
2
2
Copyright 2016 Maarten 'Vngngdn' Vangeneugden
3
3
4
4
Licensed under the Apache License, Version 2.0 (the "License");
5
5
you may not use this file except in compliance with the License.
6
6
You may obtain a copy of the License at
7
7
8
8
    https://www.apache.org/licenses/LICENSE-2.0
9
9
10
10
Unless required by applicable law or agreed to in writing, software
11
11
distributed under the License is distributed on an "AS IS" BASIS,
12
12
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13
13
See the License for the specific language governing permissions and
14
14
limitations under the License.
15
15
"""
16
16
17
17
"""
18
18
This sudoku solver takes a recursive approach to solve a given sudoku.
19
19
Although there are many different variations and types of sudokus, this program
20
20
only handles NxN sudokus (i.e. squares with root-subgrids, like the most common
21
21
3x3). So if you want hexadecimal plays, you can totally do that.
22
22
"""
23
23
24
24
# Imports:
25
25
from math import sqrt  # For the roots of the sudoku length.
26
26
27
27
# Constants:
28
28
EMPTY = 0
29
29
30
30
# Prints the given sudoku to the terminal in a readable way:
31
31
def print_sudoku(sudoku):
32
32
    # In order to print in a clean way, we first have to determine the length of
33
33
    # the biggest number:
34
34
    biggestNumber = 0
35
35
    for row in sudoku:
36
36
        for number in row:
37
37
            if number > biggestNumber:
38
38
                biggestNumber = number
39
39
40
40
    rootNumber = 10
41
41
    digits = 1
42
42
    while rootNumber**digits < biggestNumber:
43
43
        digits += 1
44
44
    # And now we've got the largest amount of digits.
45
45
46
46
    for row in sudoku:
47
47
        for number in sudoku:
48
-
            # XXX: Even though the next line looks a bit dirty, it's a great way
+
48
            # XXX: Even though the next line looks a bit dirty, it's a great way
49
49
            # to deduce the required amount of whitespace for readable output.
50
50
            # It takes the highest amount of digits, subtracted with the current
51
51
            # number's digits. so 10 in a sudoku with max. 3 digits: 3-2+1 = 2
52
52
            # whitespaces.
53
53
            spaces = " " * (digits-len(str(number)) + 1)
54
54
            print(str(number) + spaces, end="")
55
55
56
56
        for i in range(0, digits):
57
57
            # And after each row, a seperation whitespace.
58
58
            print()
59
59
60
60
# Given an empty sudoku, the solution is very simple.
61
61
# Although this is mainly a small optimization, as it is only usable when the
62
62
# root solution is possible.
63
63
def solve_empty_sudoku(sudoku): 
64
64
    n = sqrt(len(sudoku))
65
65
    
66
66
    for i in range(0, n*n):
67
67
        for j in range(0, n*n):
68
68
            sudoku[i][j] = (i*n + i/n + j) % (n*n) + 1;
69
69
    return sudoku
70
70
71
71
72
72
# Checks if the given sudoku qualifies as a root solution.
73
73
# This function mainly serves as a silly optimization to check beforehand
74
74
# whether we have to do the entire backtrack.
75
75
def is_possible_root_solution(sudoku):
76
76
    root_solution = solve_empty_sudoku()
77
77
    for x in range(0, len(root_solutxon)):
78
78
        for y in range(0, len(root_solution[x])):
79
79
            if sudoku[x][y] != root_solution[x][y] and sudoku[x][y] != EMPTY:
80
80
                return False
81
81
    # when here, all the sudoku can be filled as a root solution.
82
82
    return True
83
83
84
84
# Checks whether the given number already exists in the given array.
85
85
def exists_in_array(x, y, value, sudoku):
86
86
    if value == EMPTY:
87
87
        return False  # Just... of course.
88
88
89
89
    for i in range(0, len(sudoku)):
90
90
        if sudoku[i][y] == value:  # No need to check for empty
91
91
            return True
92
92
    return False
93
93
94
94
# Checks whether the number on the given location is unique in its column.
95
95
def exists_in_column(x, y, value, sudoku):
96
96
    if value == EMPTY:
97
97
        return False
98
98
99
99
    for i in range(0, len(sudoku[x])):
100
100
        if sudoku[x][i] == value:
101
101
            return True
102
102
    return False
103
103
104
104
# Checks whether the number on the given location is unique in its "root grid".
105
105
def exists_in_grid(x, y, value, sudoku):
106
106
    if value == EMPTY:
107
107
        return False
108
108
    
109
109
    # We're going to find out now in which part of the grid the (x,y) is put.
110
110
    # The idea I'm going for :
111
111
    # I'll first try to find out in which segment of the sudoku the value is in.
112
112
    # When I've found it, I trim the data to that segment, after I'll be
113
113
    # checking on that segment only.
114
114
    n = sqrt(len(sudoku))  # Determining the square root of the sudoku's length.
115
-
+
115
116
116
    # The following algorithm is able to handle all square sudokus.
117
117
    A = x%n
118
118
    B = y%n
119
119
    for i in range(0, n):
120
120
        for j in range(0, n):
121
121
            C = x - A + i
122
122
            D = y - B + j
123
123
            if sudoku[C][D] == value and (C != x and D != y):
124
124
                return True
125
125
    return False
126
126
127
127
# Checks whether the sudoku still contains empty grids. Returns false if not,
128
128
# and vice versa.
129
129
def is_filled_sudoku(sudoku):
130
130
    for x in range(0, len(sudoku)):
131
131
        for y in range(0, len(sudoku[x])):
132
132
            if sudoku[x][y] == EMPTY:
133
133
                return False
134
134
    return True
135
135
136
136
# Looks from the upper left grid to the lower right grid of the sudoku to find
137
137
# an empty grid. If it encounters an empty grid, the respective (x,y)
138
138
# coordinates are returned.
139
139
# If no empty grid is being found, both returned values will be -1.
140
140
def find_first_empty_grid(sudoku):
141
141
    for x in range(0, len(sudoku)):
142
142
        for y in range(0, len(sudoku[x])):
143
143
            if sudoku[x][y] == EMPTY:
144
144
                return x, y
145
145
146
146
    # When we get to this point, there's no empty grid anymore in the sudoku.
147
147
    raise Exception("""
148
148
        The given sudoku does not feature any empty grids. Assert that you've
149
149
        given the sudoku to the is_filled_sudoku() function.
150
150
        """)
151
151
152
152
# Checks whether assigning the given value to the given coordinate in the sudoku
153
153
# still renders the sudoku valid.
154
154
def is_valid_assignment(x, y, value, sudoku):
155
155
    if exists_in_array(x, y, value, sudoku):
156
156
        return False
157
157
    if exists_in_column(x, y, value, sudoku):
158
158
        return False
159
159
    if exists_in_grid(x, y, value, sudoku):
160
160
        return False
161
161
    return True
162
162
163
163
# Applies a recursive backtrack algorithm to the given sudoku, in an attempt to
164
164
# solve it.
165
165
def recursive_solution(sudoku):
166
166
    if is_filled_sudoku(sudoku):
167
167
        return True  # The sudoku is solved.
168
168
    else:
169
169
        x, y = find_first_empty_grid(sudoku)
170
170
        for i in range(1, len(sudoku)):
171
-
            # We're going to fill in numbers from 1 to 9, to find a solution
+
171
            # We're going to fill in numbers from 1 to 9, to find a solution
172
172
            # that works.
173
173
            if is_valid_assignment(x, y, i, sudoku):
174
174
                sudoku[x][y] = i
175
175
                if recursive_solution(sudoku) is False:
176
176
                    sudoku[x][y] = EMPTY
177
177
                else:
178
178
                    return True
179
179
        return False
180
180
181
181
# Assertion function. Checks whether the sudoku is a valid, and solved sudoku.
182
182
def test_solution(sudoku):
183
183
    discovered = []  # This list will be used to store discovered numbers.
184
184
    # Rows:
185
185
    for column in sudoku:
186
186
        for number in column:
187
187
            if number in discovered:
188
188
                return False
189
189
            else:
190
190
                discovered.append(number)
191
191
        discovered.clear()
192
192
193
193
    #Columns:
194
194
    for i in range(0, len(sudoku)):
195
195
        for y in range(0, len(sudoku[i])):
196
196
            if y in discovered:
197
197
                return False
198
198
            else:
199
199
                discovered.append(y)
200
200
        discovered.clear()
201
201
202
202
    #Grids:
203
203
    # Checking for grids requires us to collect the starting points of said
204
204
    # grids.
205
205
    n = sqrt(len(sudoku))
206
-
    gridPoints = []
+
206
    gridPoints = []
207
207
    for i in range(0, n):
208
208
        gridPoints.append(i*n)
209
209
210
210
    for k in gridPoints:
211
211
        for x in range(0,n):
212
212
            for y in range(0,n):
213
213
                if sudoku[x+k][y+k] in discovered:
214
214
                    return False
215
215
                else:
216
216
                    discovered.append(sudoku[x+k][y+k])
217
217
        discovered.clear()
218
218
219
219
    return True
220
220
221
221
# Prints an introduction paragraph to the user, explaining the details of the
222
222
# program, and how to operate it properly.
223
223
def print_introduction():
224
224
    introduction = """
225
225
        Welcome to Vngngdn's sudoku solver!
226
226
        I'll explain briefly what you have to do to use this program:
227
227
        After this paragraph, insert the first array of the sudoku, with each
228
228
        grid seperated by 1 space.
229
229
        If there are grids that are empty, use a 0 as placeholder for the empty
230
230
        space.
231
231
        When the row is complete, hit RETURN.
232
232
        The program will then ask for other arrays, until a square sudoku is
233
233
        formed.
234
234
        So, for example, if you enter 9 numbers, and hit RETURN, the program
235
235
        will ask for 8 more arrays, to create a 9x9 sudoku.
236
236
        When the last array has been entered, the program will stop asking for
237
237
        input, and immediately try to solve the sudoku.
238
238
        When the sudoku has been solved, it will print the solution in a
239
239
        readable way.
240
240
        If the sudoku could not be solved, it will print "Failed!", instead of a
241
241
        solution.
242
242
        This indicates the sudoku is most likely invalid, and can't be solved.
243
243
        Off you go now!
244
244
245
245
    """
246
246
    print(introduction)
247
247
248
248
# Asks the user for input.
249
249
def receive_input():
250
250
    sudoku = []  # This will be returned in the end.
251
251
    integers = []  # A list which will be added to the sudoku after input.
252
252
    length = 1  # We know there will be at least 1 number.
253
253
254
-
    for i in range(0, length):
255
-
        integers.clear()
+
254
    while i < length: 
+
255
        integers.clear()
256
256
        # The amount of given numbers implies the remaining amount of rows,
257
257
        # because only square sudokus are handled.
258
258
        line = input()
259
259
        numbers = line.split()  # numbers now contains the given numbers.
260
260
        # XXX: Next addition might be redundant after the first one, but it's
261
261
        # still cleaner than having an entire redundant block.
262
262
        length = len(numbers)
263
263
        for number in numbers:
264
264
            integers.append(int(number))
265
265
        sudoku.append(integers)
266
266
+
267
        i += 1
+
268
267
269
    # Current state: The sudoku is completely filled in, including empty spots.
268
270
    # TODO: Add some defensive programming structure, to check for empty spots
269
271
    # in the sudoku. If so, ask the user where to insert the missing numbers.
270
272
    
271
273
    return sudoku
272
274
        
273
275
274
276
275
277
# MAIN (sort of)
276
278
277
279
print_introduction()
278
280
sudoku = receive_input()
279
281
280
-
if recursive_solution(sudoku):
+
282
sudoku = [
+
283
        [0, 0, 0, 0, 9, 0, 4, 2, 0],
+
284
        [0, 0, 0, 0, 0, 0, 0, 0, 8],
+
285
        [9, 0, 0, 1, 0, 0, 3, 0, 0],
+
286
        [0, 3, 0, 0, 5, 8, 9, 1, 0],
+
287
        [0, 0, 0, 9, 0, 3, 0, 0, 0],
+
288
        [0, 1, 9, 4, 2, 0, 0, 5, 0],
+
289
        [0, 0, 5, 0, 0, 6, 0, 0, 4],
+
290
        [6, 0, 0, 0, 0, 0, 0, 0, 0],
+
291
        [0, 2, 7, 0, 8, 0, 0, 0, 0]
+
292
        ]
+
293
"""
+
294
"""
+
295
sudoku = [
+
296
        [2, 0, 0, 0],
+
297
        [0, 0, 1, 0],
+
298
        [0, 3, 0, 0],
+
299
        [0, 0, 0, 4]
+
300
        ]
+
301
"""
+
302
"""
+
303
sudoku = [
+
304
        [0, 0, 0, 0, 1, 5, 8, 0, 6, 0, 0, 0, 7, 0, 0, 2],
+
305
        [1, 0, 0, 0, 4, 3, 0, 6, 0, 0, 10, 15, 0, 0, 0, 16],
+
306
        [0, 4, 8, 11, 0, 0, 10, 0, 0, 9, 0, 7, 0, 1, 0, 3],
+
307
        [9, 0, 5, 16, 2, 0, 0, 15, 0, 0, 8, 13, 10, 0, 0, 0],
+
308
        [0, 15, 0, 0, 0, 2, 0, 0, 0, 10, 0, 1, 4, 14, 6, 12],
+
309
        [0, 0, 12, 0, 5, 1, 0, 11, 14, 0, 0, 0, 8, 0, 7, 0],
+
310
        [0, 0, 0, 10, 0, 0, 6, 14, 0, 12, 0, 0, 0, 3, 0, 11],
+
311
        [13, 0, 7, 0, 0, 9, 0, 0, 0, 15, 0, 3, 0, 0, 16, 5],
+
312
        [15, 3, 0, 0, 11, 0, 12, 0, 0, 0, 1, 0, 0, 8, 0, 7],
+
313
        [5, 0, 10, 0, 0, 0, 1, 0, 7, 4, 0, 0, 15, 0, 0, 0],
+
314
        [0, 8, 0, 12, 0, 0, 0, 7, 16, 0, 11, 10, 0, 5, 0, 0],
+
315
        [7, 13, 16, 1, 3, 0, 5, 0, 0, 0, 15, 0, 0, 0, 11, 0],
+
316
        [0, 0, 0, 5, 9, 16, 0, 0, 10, 0, 0, 6, 11, 7, 0, 15],
+
317
        [10, 0, 15, 0, 8, 0, 2, 0, 0, 7, 0, 0, 14, 16, 1, 0],
+
318
        [8, 0, 0, 0, 7, 12, 0, 0, 9, 0, 5, 14, 0, 0, 0, 13],
+
319
        [14, 0, 0, 3, 0, 0, 0, 1, 0, 16, 13, 2, 0, 0, 0, 0]
+
320
        ]
+
321
"""
+
322
if recursive_solution(sudoku):
281
323
    if test_solution(sudoku):
282
-
        print_sudoku(sudoku)
283
-
else:
+
324
    print_sudoku(sudoku)
+
325
else:
284
326
    print("Failed!")
285
327
    print_sudoku(sudoku)
286
328
                
287
329