sudoku-solver.py

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