### 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`