fun | Gitar

Solving the sudoku takes an enourmous amount of time, especially on bigger sudokus with few hints. To resolve this, I did some code tuning. It works very simple: It first finds out what the possibilities are for each grid. In the previous version, the program would simply iterate over all numbers, which was a total waste of time. Now, it only tries the actual possibilities.

But it didn't stop there. I also added a new search algorithm, that finds the first empty grid, with the least amount of possibilities. That way, the grids with, for example, 2 possibilities, gets backtracked, even if there's an earlier grid with say, 10 possibilities. The result, is that the program now runs exponentially faster. Run some clock software or something on it if you will, but if you just try the 16x16 example, you can see it already.

Author: Vngngdn
Date: Aug. 28, 2016, 3:19 p.m.
Hash: ec0b82f601c829cf39a00c9f556a8594e12e3553
Parent: 0e0070b075fc4533b50a8ef3b99ea8d2ee4ebdde
Modified file: sudoku-solver.py

sudoku-solver.py ¶

130 additions and 10 deletions.

View changes Hide changes

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.


# 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.
        """)

# Checks whether assigning the given value to the given coordinate in the sudoku
# 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

# Applies a recursive backtrack algorithm to the given sudoku, in an attempt to
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):
    if is_filled_sudoku(sudoku):
    if is_filled_sudoku(sudoku):
        return True  # The sudoku is solved.
    else:
        x, y = find_first_empty_grid(sudoku)
        for i in range(1, 1+len(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)):
            # We're going to fill in numbers from 1 to 9, to find a solution
            # that works.
            if is_valid_assignment(x, y, i, sudoku):
                sudoku[x][y] = i
            # 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
                if recursive_solution(sudoku) is False:
                    sudoku[x][y] = EMPTY
                possibilities[x][y].remove(i)
                if recursive_solution(sudoku, possibilities) is False:
                    sudoku[x][y] = EMPTY
                else:
                    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]
        ]
"""
"""
sudoku = [
sudoku = [
        [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("You entered the following sudoku:")
print("You entered the following sudoku:")
print_sudoku(sudoku)

if recursive_solution(sudoku):
    #if test_solution(sudoku):
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)

# We can already add trivial solutions:
"""print("Adding trivial solutions...")
solutions_count = 0
for x in range(len(sudoku)):
    for y in range(len(sudoku[x])):
        if len(possibilities[x][y]) == 1 and sudoku[x][y] == EMPTY:
            sudoku[x][y] = possibilities[x][y].pop()
            remove_possibility(sudoku, possibilities, x, y)
            solutions_count += 1
print("All trivial solutions added! ("+ str(solutions_count) +")")
print("Testing if still solveable...")
for x in range(len(sudoku)):
    for y in range(len(sudoku[x])):
        if sudoku[x][y] == EMPTY:
            assert len(possibilities[x][y]) != 0
print("Still solveable!")
"""

if recursive_solution(sudoku, possibilities):
    #if test_solution(sudoku):
    print("Sudoku solved!")
    print_sudoku(sudoku)
else:
    print("Failed!")
    print_sudoku(sudoku)
                


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