fun

sudoku-solver.py - A simple program that can solve any (solvable) sudoku puzzle.

Copyright 2016 Maarten 'Vngngdn' Vangeneugden

Licensed under the Apache License, Version 2.0 (the "License");

you may not use this file except in compliance with the License.

You may obtain a copy of the License at

    https://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software

distributed under the License is distributed on an "AS IS" BASIS,

WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

See the License for the specific language governing permissions and

limitations under the License.

"""

"""

This sudoku solver takes a recursive approach to solve a given sudoku.

Although there are many different variations and types of sudokus, this program

only handles NxN sudokus (i.e. squares with root-subgrids, like the most common

9x9). So if you want hexadecimal plays, you can totally do that.

"""

# Imports:

from math import sqrt  # For the roots of the sudoku length.

# Constants:

EMPTY = 0

# Prints the given sudoku to the terminal in a readable way:

def print_sudoku(sudoku):

    # In order to print in a clean way, we first have to determine the length of

    # the biggest number:

    biggestNumber = 0

    for row in sudoku:

        for number in row:

            if number > biggestNumber:

                biggestNumber = number

    rootNumber = 10

    digits = 1

    while rootNumber**digits < biggestNumber:

        digits += 1

    # And now we've got the largest amount of digits.

    for row in sudoku:

        for number in row:

            # XXX: Even though the next line looks a bit dirty, it's a great way

            # to deduce the required amount of whitespace for readable output.

            # It takes the highest amount of digits, subtracted with the current

            # number's digits. so 10 in a sudoku with max. 3 digits: 3-2+1 = 2

            # whitespaces.

            spaces = " " * (digits-len(str(number)) + 1)

            print(str(number) + spaces, end="")

        for i in range(0, digits):

            # And after each row, a seperation whitespace.

            print()

# Given an empty sudoku, the solution is very simple.

# Although this is mainly a small optimization, as it is only usable when the

# root solution is possible.

def solve_empty_sudoku(sudoku): 

    n = sqrt(len(sudoku))

    for i in range(0, n*n):

        for j in range(0, n*n):

            sudoku[i][j] = (i*n + i/n + j) % (n*n) + 1;

    return sudoku

# Checks if the given sudoku qualifies as a root solution.

# This function mainly serves as a silly optimization to check beforehand

# whether we have to do the entire backtrack.

def is_possible_root_solution(sudoku):

    root_solution = solve_empty_sudoku()

    for x in range(0, len(root_solutxon)):

        for y in range(0, len(root_solution[x])):

            if sudoku[x][y] != root_solution[x][y] and sudoku[x][y] != EMPTY:

                return False

    # when here, all the sudoku can be filled as a root solution.

    return True

# Checks whether the given number already exists in the given array.

def exists_in_array(x, y, value, sudoku):

    if value == EMPTY:

        return False  # Just... of course.

    for i in range(0, len(sudoku)):

        if sudoku[i][y] == value:  # No need to check for empty

            return True

    return False

# Checks whether the number on the given location is unique in its column.

def exists_in_column(x, y, value, sudoku):

    if value == EMPTY:

        return False

    for i in range(0, len(sudoku[x])):

        if sudoku[x][i] == value:

            return True

    return False

# Checks whether the number on the given location is unique in its "root grid".

def exists_in_grid(x, y, value, sudoku):

    if value == EMPTY:

        return False

    # We're going to find out now in which part of the grid the (x,y) is put.

    # The idea I'm going for :

    # I'll first try to find out in which segment of the sudoku the value is in.

    # When I've found it, I trim the data to that segment, after I'll be

    # checking on that segment only.

    n = int(sqrt(len(sudoku)))  # Determining the square root of the sudoku's length.

    # The following algorithm is able to handle all square sudokus.

    A = x%n

    B = y%n

    for i in range(0, n):

        for j in range(0, n):

            C = x - A + i

            D = y - B + j

            if sudoku[C][D] == value and (C != x and D != y):

                return True

    return False

# Checks whether the sudoku still contains empty grids. Returns false if not,

# and vice versa.

def is_filled_sudoku(sudoku):

    for x in range(0, len(sudoku)):

        for y in range(0, len(sudoku[x])):

            if sudoku[x][y] == EMPTY:

                return False

    return True

# Looks from the upper left grid to the lower right grid of the sudoku to find

# an empty grid. If it encounters an empty grid, the respective (x,y)

# coordinates are returned.

# If no empty grid is being found, both returned values will be -1.

def find_first_empty_grid(sudoku):

    for x in range(0, len(sudoku)):

        for y in range(0, len(sudoku[x])):

            if sudoku[x][y] == EMPTY:

                return x, y

    # When we get to this point, there's no empty grid anymore in the sudoku.

    raise Exception("""

        The given sudoku does not feature any empty grids. Assert that you've

        given the sudoku to the is_filled_sudoku() function.

        """)

# Works identical to the other function, but looks for the first grid with the

# smallest amount of possibilities. So grids with 2 possibilities are returned,

# even if an empty grid was found already, having 5 possibilities.

def find_first_empty_grid_optimized(sudoku, possibilities):

    i = 0

    j = 0

    minimum = len(sudoku)+1 # +1 guarantees 1 will always be chosen.

    for x in range(0, len(sudoku)):

        for y in range(0, len(sudoku[x])):

            if sudoku[x][y] == EMPTY:

                if len(possibilities[x][y]) < minimum:

                    i, j = x, y

                    minimum = len(possibilities[x][y])

    return i, j

# Checks whether assigning the given value to the given coordinate in the sudoku

# still renders the sudoku valid.

def is_valid_assignment(x, y, value, sudoku):

    if exists_in_array(x, y, value, sudoku):

        return False

    if exists_in_column(x, y, value, sudoku):

        return False

    if exists_in_grid(x, y, value, sudoku):

        return False

    return True

# Collects all symbols that can be placed in the given place.

def collect_possible_entries(sudoku, x, y):

    # The strategy is simple: Iterate over all possibilities, and check whether

    # it's possible or not.

    possible_values = set()

    for value in range(1, len(sudoku)+1):

        if is_valid_assignment(x, y, value, sudoku):

            possible_values.add(value)

    return possible_values

# Updates the possibilities, in function of the given position.

def remove_possibility(sudoku, possibilities, x, y):

    for i in range(len(possibilities)):

        for j in range(len(possibilities[i])):

            # i==x XOR j==y

            if (i==x and j!=y) or (i!=x and j==y):

                # The next if-test is necessary to avoid a KeyErrro.

                if sudoku[x][y] in possibilities[i][j]:

                    #assert (i != x and j == y) or (

                    possibilities[i][j].remove(sudoku[x][y])

    # Removal of possibilities in grid:

    n = int(sqrt(len(sudoku)))  # Determining the square root of the sudoku's length.

    A = x%n

    B = y%n

    for i in range(0, n):

        for j in range(0, n):

            C = x - A + i

            D = y - B + j

            if C!=x and D!=y:

                if sudoku[x][y] in possibilities[C][D]:

                    assert C != x and D != y

                    possibilities[C][D].remove(sudoku[x][y])

def add_possibility(sudoku, possibilities, x, y, value):

    for i in range(len(possibilities)):

        for j in range(len(possibilities[i])):

            # i==x XOR j==y

            #if (i==x or j==y) and not (i==x and j==y):

            if (i==x and j!=y) or (i!=x and j==y):

                #assert i != x and j != y

                possibilities[i][j].add(value)

    # Addition of possibilities in grid:

    n = int(sqrt(len(sudoku)))  # Determining the square root of the sudoku's length.

    A = x%n

    B = y%n

    for i in range(0, n):

        for j in range(0, n):

            C = x - A + i

            D = y - B + j

            if C!=x and D!=y:

                assert C != x and D != y

                possibilities[C][D].add(value)

# TODO: For remove/add_possibility: Add √n*√n grid removal as well.

# Applies a recursive backtrack algorithm to the given sudoku, in an attempt to

# solve it.

def recursive_solution(sudoku, possibilities):

    if is_filled_sudoku(sudoku):

        return True  # The sudoku is solved.

    else:

        #x, y = find_first_empty_grid(sudoku)

        x, y = find_first_empty_grid_optimized(sudoku, possibilities)

        if len(possibilities[x][y]) == EMPTY:

            # With an empty grid, there must be a possible value to enter. If there

            # isn't, that means that somewhere earlier, a possibility was removed,

            # because the wrong value was added. Thus, this is an impossible

            # solution, and we must backtrack.

            return False

        for i in range(1, 1+len(sudoku)):

            if i in possibilities[x][y]:

            # We don't need to test if it's concerning a valid assignment, since

            # if it weren't a valid assignment, it wouldn't be listed as a

            # possibility in the first place.

                sudoku[x][y] = i

                remove_possibility(sudoku, possibilities, x, y)

                possibilities[x][y].remove(i)

                if recursive_solution(sudoku, possibilities) is False:

                    sudoku[x][y] = EMPTY

                    add_possibility(sudoku, possibilities, x, y, i)

                    i = 0 # Reloop over all posibilities (which may have updated

                    # Note how I don't add the tested possibility back, as I did

                    # remove the possibility. That is, because it's clear that

                    # this cannot be a solution if we want to solve the sudoku.

                    # Thus, it shouldn't be added back.

                else:

                    return True

        return False

# Assertion function. Checks whether the sudoku is a valid, and solved sudoku.

def test_solution(sudoku):

    discovered = []  # This list will be used to store discovered numbers.

    # Rows:

    for column in sudoku:

        for number in column:

            if number in discovered:

                return False

            else:

                discovered.append(number)

        discovered.clear()

    #Columns:

    for i in range(0, len(sudoku)):

        for y in range(0, len(sudoku[i])):

            if y in discovered:

                return False

            else:

                discovered.append(y)

        discovered.clear()

    #Grids:

    # Checking for grids requires us to collect the starting points of said

    # grids.

    n = int(sqrt(len(sudoku)))

    gridPoints = []

    for i in range(0, n):

        gridPoints.append(i*n)

    for k in gridPoints:

        for x in range(0,n):

            for y in range(0,n):

                if sudoku[x+k][y+k] in discovered:

                    return False

                else:

                    discovered.append(sudoku[x+k][y+k])

        discovered.clear()

    return True

# Prints an introduction paragraph to the user, explaining the details of the

# program, and how to operate it properly.

def print_introduction():

    introduction = """

        Welcome to Vngngdn's sudoku solver!

        I'll explain briefly what you have to do to use this program:

        After this paragraph, insert the first array of the sudoku, with each

        grid seperated by 1 space.

        If there are grids that are empty, use a 0 as placeholder for the empty

        space.

        When the row is complete, hit RETURN.

        The program will then ask for other arrays, until a square sudoku is

        formed.

        So, for example, if you enter 9 numbers, and hit RETURN, the program

        will ask for 8 more arrays, to create a 9x9 sudoku.

        When the last array has been entered, the program will stop asking for

        input, and immediately try to solve the sudoku.

        When the sudoku has been solved, it will print the solution in a

        readable way.

        If the sudoku could not be solved, it will print "Failed!", instead of a

        solution.

        This indicates the sudoku is most likely invalid, and can't be solved.

        Off you go now!

    """

    print(introduction)

# Asks the user for input.

def receive_input():

    sudoku = []  # This will be returned in the end.

    #integers = []  # A list which will be added to the sudoku after input.

    length = 1  # We know there will be at least 1 number.

    i = 0

    while i < length: 

        integers = []  # A list which will be added to the sudoku after input.

        integers.clear()

        # The amount of given numbers implies the remaining amount of rows,

        # because only square sudokus are handled.

        line = input()

        numbers = line.split()  # numbers now contains the given numbers.

        # XXX: Next addition might be redundant after the first one, but it's

        # still cleaner than having an entire redundant block.

        length = len(numbers)

        for number in numbers:

            integers.append(int(number))

        sudoku.append(integers)

        i += 1

    # Current state: The sudoku is completely filled in, including empty spots.

    # TODO: Add some defensive programming structure, to check for empty spots

    # in the sudoku. If so, ask the user where to insert the missing numbers.

    return sudoku

# MAIN (sort of)

print_introduction()

sudoku = receive_input()

"""

sudoku = [

        [0, 0, 0, 0, 9, 0, 4, 2, 0],

        [0, 0, 0, 0, 0, 0, 0, 0, 8],

        [9, 0, 0, 1, 0, 0, 3, 0, 0],

        [0, 3, 0, 0, 5, 8, 9, 1, 0],

        [0, 0, 0, 9, 0, 3, 0, 0, 0],

        [0, 1, 9, 4, 2, 0, 0, 5, 0],

        [0, 0, 5, 0, 0, 6, 0, 0, 4],

        [6, 0, 0, 0, 0, 0, 0, 0, 0],

        [0, 2, 7, 0, 8, 0, 0, 0, 0]

        ]

"""

"""

sudoku = [

        [2, 0, 0, 0],

        [0, 0, 1, 0],

        [0, 3, 0, 0],

        [0, 0, 0, 4]

        ]

"""

        [0, 0, 0, 0, 1, 5, 8, 0, 6, 0, 0, 0, 7, 0, 0, 2],

        [1, 0, 0, 0, 4, 3, 0, 6, 0, 0, 10, 15, 0, 0, 0, 16],

        [0, 4, 8, 11, 0, 0, 10, 0, 0, 9, 0, 7, 0, 1, 0, 3],

        [9, 0, 5, 16, 2, 0, 0, 15, 0, 0, 8, 13, 10, 0, 0, 0],

        [0, 15, 0, 0, 0, 2, 0, 0, 0, 10, 0, 1, 4, 14, 6, 12],

        [0, 0, 12, 0, 5, 1, 0, 11, 14, 0, 0, 0, 8, 0, 7, 0],

        [0, 0, 0, 10, 0, 0, 6, 14, 0, 12, 0, 0, 0, 3, 0, 11],

        [13, 0, 7, 0, 0, 9, 0, 0, 0, 15, 0, 3, 0, 0, 16, 5],

        [15, 3, 0, 0, 11, 0, 12, 0, 0, 0, 1, 0, 0, 8, 0, 7],

        [5, 0, 10, 0, 0, 0, 1, 0, 7, 4, 0, 0, 15, 0, 0, 0],

        [0, 8, 0, 12, 0, 0, 0, 7, 16, 0, 11, 10, 0, 5, 0, 0],

        [7, 13, 16, 1, 3, 0, 5, 0, 0, 0, 15, 0, 0, 0, 11, 0],

        [0, 0, 0, 5, 9, 16, 0, 0, 10, 0, 0, 6, 11, 7, 0, 15],

        [10, 0, 15, 0, 8, 0, 2, 0, 0, 7, 0, 0, 14, 16, 1, 0],

        [8, 0, 0, 0, 7, 12, 0, 0, 9, 0, 5, 14, 0, 0, 0, 13],

        [14, 0, 0, 3, 0, 0, 0, 1, 0, 16, 13, 2, 0, 0, 0, 0]

        ]

print_sudoku(sudoku)

# OPTIMIZATION

possibilities = []

for x in range(len(sudoku)):

    row = []

    for y in range(len(sudoku[x])):

        entries = (collect_possible_entries(sudoku, x, y))

        row.append(entries)

        assert len(entries) != 0

    possibilities.append(row)

if recursive_solution(sudoku, possibilities):

    #if test_solution(sudoku):

    print("Sudoku solved!")

    print_sudoku(sudoku)

else:

    print("Failed!")

    print_sudoku(sudoku)