fun

Added a 25x25 example sudoku. Also, removed the initial 'optimization', because exactly that happens already in the optimized search algorithm.

Author
Vngngdn
Date
Aug. 28, 2016, 8:11 p.m.
Hash
c75851b16bd3c24e8795422e568800e863df55bb
Parent
ec0b82f601c829cf39a00c9f556a8594e12e3553
Modified file
sudoku-solver.py

sudoku-solver.py

31 additions and 20 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
9x9). 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 row:
48
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
61
61
62
62
63
63
# Given an empty sudoku, the solution is very simple.
64
64
# Although this is mainly a small optimization, as it is only usable when the
65
65
# root solution is possible.
66
66
def solve_empty_sudoku(sudoku): 
67
67
    n = sqrt(len(sudoku))
68
68
    
69
69
    for i in range(0, n*n):
70
70
        for j in range(0, n*n):
71
71
            sudoku[i][j] = (i*n + i/n + j) % (n*n) + 1;
72
72
    return sudoku
73
73
74
74
75
75
# Checks if the given sudoku qualifies as a root solution.
76
76
# This function mainly serves as a silly optimization to check beforehand
77
77
# whether we have to do the entire backtrack.
78
78
def is_possible_root_solution(sudoku):
79
79
    root_solution = solve_empty_sudoku()
80
80
    for x in range(0, len(root_solutxon)):
81
81
        for y in range(0, len(root_solution[x])):
82
82
            if sudoku[x][y] != root_solution[x][y] and sudoku[x][y] != EMPTY:
83
83
                return False
84
84
    # when here, all the sudoku can be filled as a root solution.
85
85
    return True
86
86
87
87
# Checks whether the given number already exists in the given array.
88
88
def exists_in_array(x, y, value, sudoku):
89
89
    if value == EMPTY:
90
90
        return False  # Just... of course.
91
91
92
92
    for i in range(0, len(sudoku)):
93
93
        if sudoku[i][y] == value:  # No need to check for empty
94
94
            return True
95
95
    return False
96
96
97
97
# Checks whether the number on the given location is unique in its column.
98
98
def exists_in_column(x, y, value, sudoku):
99
99
    if value == EMPTY:
100
100
        return False
101
101
102
102
    for i in range(0, len(sudoku[x])):
103
103
        if sudoku[x][i] == value:
104
104
            return True
105
105
    return False
106
106
107
107
# Checks whether the number on the given location is unique in its "root grid".
108
108
def exists_in_grid(x, y, value, sudoku):
109
109
    if value == EMPTY:
110
110
        return False
111
111
    
112
112
    # We're going to find out now in which part of the grid the (x,y) is put.
113
113
    # The idea I'm going for :
114
114
    # I'll first try to find out in which segment of the sudoku the value is in.
115
115
    # When I've found it, I trim the data to that segment, after I'll be
116
116
    # checking on that segment only.
117
117
    n = int(sqrt(len(sudoku)))  # Determining the square root of the sudoku's length.
118
118
119
119
    # The following algorithm is able to handle all square sudokus.
120
120
    A = x%n
121
121
    B = y%n
122
122
    for i in range(0, n):
123
123
        for j in range(0, n):
124
124
            C = x - A + i
125
125
            D = y - B + j
126
126
            if sudoku[C][D] == value and (C != x and D != y):
127
127
                return True
128
128
    return False
129
129
130
130
# Checks whether the sudoku still contains empty grids. Returns false if not,
131
131
# and vice versa.
132
132
def is_filled_sudoku(sudoku):
133
133
    for x in range(0, len(sudoku)):
134
134
        for y in range(0, len(sudoku[x])):
135
135
            if sudoku[x][y] == EMPTY:
136
136
                return False
137
137
    return True
138
138
139
139
# Looks from the upper left grid to the lower right grid of the sudoku to find
140
140
# an empty grid. If it encounters an empty grid, the respective (x,y)
141
141
# coordinates are returned.
142
142
# If no empty grid is being found, both returned values will be -1.
143
143
def find_first_empty_grid(sudoku):
144
144
    for x in range(0, len(sudoku)):
145
145
        for y in range(0, len(sudoku[x])):
146
146
            if sudoku[x][y] == EMPTY:
147
147
                return x, y
148
148
    # When we get to this point, there's no empty grid anymore in the sudoku.
149
149
    raise Exception("""
150
150
        The given sudoku does not feature any empty grids. Assert that you've
151
151
        given the sudoku to the is_filled_sudoku() function.
152
152
        """)
153
153
154
154
# Works identical to the other function, but looks for the first grid with the
155
155
# smallest amount of possibilities. So grids with 2 possibilities are returned,
156
156
# even if an empty grid was found already, having 5 possibilities.
157
157
def find_first_empty_grid_optimized(sudoku, possibilities):
158
158
    i = 0
159
159
    j = 0
160
160
    minimum = len(sudoku)+1 # +1 guarantees 1 will always be chosen.
161
161
    for x in range(0, len(sudoku)):
162
162
        for y in range(0, len(sudoku[x])):
163
163
            if sudoku[x][y] == EMPTY:
164
164
                if len(possibilities[x][y]) < minimum:
165
165
                    i, j = x, y
166
166
                    minimum = len(possibilities[x][y])
167
167
    return i, j
168
168
169
169
170
170
171
171
# Checks whether assigning the given value to the given coordinate in the sudoku
172
172
# still renders the sudoku valid.
173
173
def is_valid_assignment(x, y, value, sudoku):
174
174
    if exists_in_array(x, y, value, sudoku):
175
175
        return False
176
176
    if exists_in_column(x, y, value, sudoku):
177
177
        return False
178
178
    if exists_in_grid(x, y, value, sudoku):
179
179
        return False
180
180
    return True
181
181
182
182
# Collects all symbols that can be placed in the given place.
183
183
def collect_possible_entries(sudoku, x, y):
184
184
    # The strategy is simple: Iterate over all possibilities, and check whether
185
185
    # it's possible or not.
186
186
    possible_values = set()
187
187
    for value in range(1, len(sudoku)+1):
188
188
        if is_valid_assignment(x, y, value, sudoku):
189
189
            possible_values.add(value)
190
190
    return possible_values
191
191
192
192
# Updates the possibilities, in function of the given position.
193
193
def remove_possibility(sudoku, possibilities, x, y):
194
194
    for i in range(len(possibilities)):
195
195
        for j in range(len(possibilities[i])):
196
196
            # i==x XOR j==y
197
197
            if (i==x and j!=y) or (i!=x and j==y):
198
198
                # The next if-test is necessary to avoid a KeyErrro.
199
199
                if sudoku[x][y] in possibilities[i][j]:
200
200
                    #assert (i != x and j == y) or (
201
201
                    possibilities[i][j].remove(sudoku[x][y])
202
202
    # Removal of possibilities in grid:
203
203
    n = int(sqrt(len(sudoku)))  # Determining the square root of the sudoku's length.
204
204
    A = x%n
205
205
    B = y%n
206
206
    for i in range(0, n):
207
207
        for j in range(0, n):
208
208
            C = x - A + i
209
209
            D = y - B + j
210
210
            if C!=x and D!=y:
211
211
                if sudoku[x][y] in possibilities[C][D]:
212
212
                    assert C != x and D != y
213
213
                    possibilities[C][D].remove(sudoku[x][y])
214
214
215
215
def add_possibility(sudoku, possibilities, x, y, value):
216
216
    for i in range(len(possibilities)):
217
217
        for j in range(len(possibilities[i])):
218
218
            # i==x XOR j==y
219
219
            #if (i==x or j==y) and not (i==x and j==y):
220
220
            if (i==x and j!=y) or (i!=x and j==y):
221
221
                #assert i != x and j != y
222
222
                possibilities[i][j].add(value)
223
223
    # Addition of possibilities in grid:
224
224
    n = int(sqrt(len(sudoku)))  # Determining the square root of the sudoku's length.
225
225
    A = x%n
226
226
    B = y%n
227
227
    for i in range(0, n):
228
228
        for j in range(0, n):
229
229
            C = x - A + i
230
230
            D = y - B + j
231
231
            if C!=x and D!=y:
232
232
                assert C != x and D != y
233
233
                possibilities[C][D].add(value)
234
234
235
235
# TODO: For remove/add_possibility: Add √n*√n grid removal as well.
236
236
237
237
238
238
# Applies a recursive backtrack algorithm to the given sudoku, in an attempt to
239
239
# solve it.
240
240
def recursive_solution(sudoku, possibilities):
241
241
    if is_filled_sudoku(sudoku):
242
242
        return True  # The sudoku is solved.
243
243
    else:
244
244
        #x, y = find_first_empty_grid(sudoku)
245
245
        x, y = find_first_empty_grid_optimized(sudoku, possibilities)
246
246
        if len(possibilities[x][y]) == EMPTY:
247
247
            # With an empty grid, there must be a possible value to enter. If there
248
248
            # isn't, that means that somewhere earlier, a possibility was removed,
249
249
            # because the wrong value was added. Thus, this is an impossible
250
250
            # solution, and we must backtrack.
251
251
            return False
252
252
253
253
        for i in range(1, 1+len(sudoku)):
254
254
            if i in possibilities[x][y]:
255
255
            # We don't need to test if it's concerning a valid assignment, since
256
256
            # if it weren't a valid assignment, it wouldn't be listed as a
257
257
            # possibility in the first place.
258
258
                sudoku[x][y] = i
259
259
                remove_possibility(sudoku, possibilities, x, y)
260
260
                possibilities[x][y].remove(i)
261
261
                if recursive_solution(sudoku, possibilities) is False:
262
262
                    sudoku[x][y] = EMPTY
263
263
                    add_possibility(sudoku, possibilities, x, y, i)
264
264
                    i = 0 # Reloop over all posibilities (which may have updated
265
265
                    # Note how I don't add the tested possibility back, as I did
266
266
                    # remove the possibility. That is, because it's clear that
267
267
                    # this cannot be a solution if we want to solve the sudoku.
268
268
                    # Thus, it shouldn't be added back.
269
269
                else:
270
270
                    return True
271
271
        return False
272
272
273
273
# Assertion function. Checks whether the sudoku is a valid, and solved sudoku.
274
274
def test_solution(sudoku):
275
275
    discovered = []  # This list will be used to store discovered numbers.
276
276
    # Rows:
277
277
    for column in sudoku:
278
278
        for number in column:
279
279
            if number in discovered:
280
280
                return False
281
281
            else:
282
282
                discovered.append(number)
283
283
        discovered.clear()
284
284
285
285
    #Columns:
286
286
    for i in range(0, len(sudoku)):
287
287
        for y in range(0, len(sudoku[i])):
288
288
            if y in discovered:
289
289
                return False
290
290
            else:
291
291
                discovered.append(y)
292
292
        discovered.clear()
293
293
294
294
    #Grids:
295
295
    # Checking for grids requires us to collect the starting points of said
296
296
    # grids.
297
297
    n = int(sqrt(len(sudoku)))
298
298
    gridPoints = []
299
299
    for i in range(0, n):
300
300
        gridPoints.append(i*n)
301
301
302
302
    for k in gridPoints:
303
303
        for x in range(0,n):
304
304
            for y in range(0,n):
305
305
                if sudoku[x+k][y+k] in discovered:
306
306
                    return False
307
307
                else:
308
308
                    discovered.append(sudoku[x+k][y+k])
309
309
        discovered.clear()
310
310
311
311
    return True
312
312
313
313
# Prints an introduction paragraph to the user, explaining the details of the
314
314
# program, and how to operate it properly.
315
315
def print_introduction():
316
316
    introduction = """
317
317
        Welcome to Vngngdn's sudoku solver!
318
318
        I'll explain briefly what you have to do to use this program:
319
319
        After this paragraph, insert the first array of the sudoku, with each
320
320
        grid seperated by 1 space.
321
321
        If there are grids that are empty, use a 0 as placeholder for the empty
322
322
        space.
323
323
        When the row is complete, hit RETURN.
324
324
        The program will then ask for other arrays, until a square sudoku is
325
325
        formed.
326
326
        So, for example, if you enter 9 numbers, and hit RETURN, the program
327
327
        will ask for 8 more arrays, to create a 9x9 sudoku.
328
328
        When the last array has been entered, the program will stop asking for
329
329
        input, and immediately try to solve the sudoku.
330
330
        When the sudoku has been solved, it will print the solution in a
331
331
        readable way.
332
332
        If the sudoku could not be solved, it will print "Failed!", instead of a
333
333
        solution.
334
334
        This indicates the sudoku is most likely invalid, and can't be solved.
335
335
        Off you go now!
336
336
337
337
    """
338
338
    print(introduction)
339
339
340
340
# Asks the user for input.
341
341
def receive_input():
342
342
    sudoku = []  # This will be returned in the end.
343
343
    #integers = []  # A list which will be added to the sudoku after input.
344
344
    length = 1  # We know there will be at least 1 number.
345
345
    i = 0
346
346
    while i < length: 
347
347
        integers = []  # A list which will be added to the sudoku after input.
348
348
        integers.clear()
349
349
        # The amount of given numbers implies the remaining amount of rows,
350
350
        # because only square sudokus are handled.
351
351
        line = input()
352
352
        numbers = line.split()  # numbers now contains the given numbers.
353
353
        # XXX: Next addition might be redundant after the first one, but it's
354
354
        # still cleaner than having an entire redundant block.
355
355
        length = len(numbers)
356
356
        for number in numbers:
357
357
            integers.append(int(number))
358
358
        sudoku.append(integers)
359
359
         
360
360
        i += 1
361
361
362
362
    # Current state: The sudoku is completely filled in, including empty spots.
363
363
    # TODO: Add some defensive programming structure, to check for empty spots
364
364
    # in the sudoku. If so, ask the user where to insert the missing numbers.
365
365
    
366
366
    return sudoku
367
367
        
368
368
369
369
370
370
# MAIN (sort of)
371
371
372
372
print_introduction()
373
373
sudoku = receive_input()
374
374
"""
375
375
sudoku = [
376
376
        [0, 0, 0, 0, 9, 0, 4, 2, 0],
377
377
        [0, 0, 0, 0, 0, 0, 0, 0, 8],
378
378
        [9, 0, 0, 1, 0, 0, 3, 0, 0],
379
379
        [0, 3, 0, 0, 5, 8, 9, 1, 0],
380
380
        [0, 0, 0, 9, 0, 3, 0, 0, 0],
381
381
        [0, 1, 9, 4, 2, 0, 0, 5, 0],
382
382
        [0, 0, 5, 0, 0, 6, 0, 0, 4],
383
383
        [6, 0, 0, 0, 0, 0, 0, 0, 0],
384
384
        [0, 2, 7, 0, 8, 0, 0, 0, 0]
385
385
        ]
386
386
"""
387
387
"""
388
388
sudoku = [
389
389
        [2, 0, 0, 0],
390
390
        [0, 0, 1, 0],
391
391
        [0, 3, 0, 0],
392
392
        [0, 0, 0, 4]
393
393
        ]
394
394
"""
395
395
396
-
sudoku = [
+
396
sudoku = [
397
397
        [0, 0, 0, 0, 1, 5, 8, 0, 6, 0, 0, 0, 7, 0, 0, 2],
398
398
        [1, 0, 0, 0, 4, 3, 0, 6, 0, 0, 10, 15, 0, 0, 0, 16],
399
399
        [0, 4, 8, 11, 0, 0, 10, 0, 0, 9, 0, 7, 0, 1, 0, 3],
400
400
        [9, 0, 5, 16, 2, 0, 0, 15, 0, 0, 8, 13, 10, 0, 0, 0],
401
401
        [0, 15, 0, 0, 0, 2, 0, 0, 0, 10, 0, 1, 4, 14, 6, 12],
402
402
        [0, 0, 12, 0, 5, 1, 0, 11, 14, 0, 0, 0, 8, 0, 7, 0],
403
403
        [0, 0, 0, 10, 0, 0, 6, 14, 0, 12, 0, 0, 0, 3, 0, 11],
404
404
        [13, 0, 7, 0, 0, 9, 0, 0, 0, 15, 0, 3, 0, 0, 16, 5],
405
405
        [15, 3, 0, 0, 11, 0, 12, 0, 0, 0, 1, 0, 0, 8, 0, 7],
406
406
        [5, 0, 10, 0, 0, 0, 1, 0, 7, 4, 0, 0, 15, 0, 0, 0],
407
407
        [0, 8, 0, 12, 0, 0, 0, 7, 16, 0, 11, 10, 0, 5, 0, 0],
408
408
        [7, 13, 16, 1, 3, 0, 5, 0, 0, 0, 15, 0, 0, 0, 11, 0],
409
409
        [0, 0, 0, 5, 9, 16, 0, 0, 10, 0, 0, 6, 11, 7, 0, 15],
410
410
        [10, 0, 15, 0, 8, 0, 2, 0, 0, 7, 0, 0, 14, 16, 1, 0],
411
411
        [8, 0, 0, 0, 7, 12, 0, 0, 9, 0, 5, 14, 0, 0, 0, 13],
412
412
        [14, 0, 0, 3, 0, 0, 0, 1, 0, 16, 13, 2, 0, 0, 0, 0]
413
413
        ]
414
414
415
-
print("You entered the following sudoku:")
+
415
sudoku = [
+
416
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 19, 0, 0, 0, 20, 0],
+
417
        [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 0],
+
418
        [0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+
419
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+
420
        [0, 0, 23, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 0, 0, 18, 0, 0, 0, 0, 0, 0],
+
421
        [0, 0, 0, 7, 0, 0, 0, 23, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+
422
        [0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0],
+
423
        [0, 0, 0, 0, 0, 0, 0, 12, 0, 0, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 0],
+
424
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+
425
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+
426
        [0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 0, 0, 0, 0, 0, 12, 0, 0, 0],
+
427
        [0, 0, 12, 0, 15, 0, 0, 0, 0, 0, 14, 0, 0, 0, 5, 0, 0, 24, 3, 0, 0, 0, 0, 0, 0],
+
428
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 13, 0, 0, 5, 0, 0, 24, 3, 0],
+
429
        [0, 0, 8, 0, 0, 11, 0, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+
430
        [0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+
431
        [0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+
432
        [0, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 0, 0, 0],
+
433
        [0, 0, 0, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+
434
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+
435
        [0, 5, 0, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1],
+
436
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10],
+
437
        [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+
438
        [0, 0, 0, 0, 0, 0, 0, 0, 20, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+
439
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+
440
        [0, 23, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
+
441
        ]
+
442
print("You entered the following sudoku:")
416
443
print_sudoku(sudoku)
417
444
418
445
# OPTIMIZATION
419
446
possibilities = []
+
447
possibilities = []
420
448
for x in range(len(sudoku)):
421
449
    row = []
422
450
    for y in range(len(sudoku[x])):
423
451
        entries = (collect_possible_entries(sudoku, x, y))
424
452
        row.append(entries)
425
453
        assert len(entries) != 0
426
454
    possibilities.append(row)
427
455
428
-
# We can already add trivial solutions:
429
-
"""print("Adding trivial solutions...")
430
-
solutions_count = 0
431
-
for x in range(len(sudoku)):
432
-
    for y in range(len(sudoku[x])):
433
-
        if len(possibilities[x][y]) == 1 and sudoku[x][y] == EMPTY:
434
-
            sudoku[x][y] = possibilities[x][y].pop()
435
-
            remove_possibility(sudoku, possibilities, x, y)
436
-
            solutions_count += 1
437
-
print("All trivial solutions added! ("+ str(solutions_count) +")")
438
-
print("Testing if still solveable...")
439
-
for x in range(len(sudoku)):
440
-
    for y in range(len(sudoku[x])):
441
-
        if sudoku[x][y] == EMPTY:
442
-
            assert len(possibilities[x][y]) != 0
443
-
print("Still solveable!")
444
-
"""
445
-
+
456
446
457
if recursive_solution(sudoku, possibilities):
447
458
    #if test_solution(sudoku):
448
459
    print("Sudoku solved!")
449
460
    print_sudoku(sudoku)
450
461
else:
451
462
    print("Failed!")
452
463
    print_sudoku(sudoku)
453
464
                
454
465