fun | Gitar

Sudoku solver: Biggest refactoring of the code, since it's now mostly finished. Added a lot of cleaner code, and extra comments. I may add some extra assertion code and docstrings in the future, as well as some defensive programming structures. But for now, this will do.

Author: Vngngdn
Date: July 22, 2016, 5:23 p.m.
Hash: 75a01245f2fc4d11735d7978a9d55b7fc4ddfaf4
Parent: fcf40fb6d89e9688f5d9ebfb919c35d9cfc8c7e2
Modified file: sudoku-solver.py

sudoku-solver.py ¶

103 additions and 70 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
3x3). So if you want hexadecimal plays, you can totally do that.
"""

# Prints the given sudoku to the terminal in a readable way:
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):
    for x in sudoku:
        for y in x:
            print(str(y) + " ", end="")
        print()  # Start a new line.

    # 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 sudoku:
            # 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.
def solve_empty_sudoku(sudoku): 
# root solution is possible.
def solve_empty_sudoku(sudoku): 
    n = 3
    for i in range(0, n*n):
    
    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

# Creates a table of 9x9 in the form of an array containing arrays.
"""
def create_sudoku():
    x = []
    for i in range(0,9):
        x.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
    return x

EMPTY = 0
"""

# 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 i in range(0, len(root_solution)):
        for j in range(0, len(root_solution[i])):
            if sudoku[i][j] != root_solution[i][j] and sudoku[i][j] != 0:
                return False
        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
    return True

# Checks whether the given number already exists in the given array.
def exists_in_array(x, y, value, sudoku):
    for i in range(0, len(sudoku)):
        return False  # Just... of course.

    for i in range(0, len(sudoku)):
        if sudoku[i][y] == value and sudoku[i][y] != EMPTY:
            return True
            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):
    for i in range(0, len(sudoku[x])):
        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 (3x3) grid.
def exists_in_grid(x, y, value, sudoku):
def exists_in_grid(x, y, value, sudoku):
    # We're going to find out now in which part of the grid the (x,y) is put.
        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 now:
    # I'll first try to find out in which segment of the sudoku the value is in.
    # 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.
    # Chart:
    n = len(sudoku)  # Determining the size of the sudoku 
    n = 3
    


    A = x%n
    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

def is_filled_sudoku(sudoku):
# and vice versa.
def is_filled_sudoku(sudoku):
    for i in range(0, len(sudoku)):
        for j in range(0, len(sudoku[i])):
            if sudoku[i][j] == 0:
                return False
        for y in range(0, len(sudoku[x])):
            if sudoku[x][y] == EMPTY:
                return False
    return True

def find_first_empty_grid(sudoku):
# 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 i in range(0, len(sudoku)):
        for j in range(0, len(sudoku[i])):
            if sudoku[i][j] == 0:
                return i, j

def is_valid_assignment(x, y, value, 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
# still renders the sudoku valid.
def is_valid_assignment(x, y, value, sudoku):
    #sudoku[x][y] = value
    if exists_in_array(x, y, value, sudoku):
        #print("Exists in array!")
        return False
    if exists_in_column(x, y, value, sudoku):
        #print("Exists in column!")
        return False
    if exists_in_grid(x, y, value, sudoku):
        #print("Exists in grid!")
        return False
    return True

# Makes a deep copy of the given sudoku, and returns that copy.
def make_copy(sudoku):
    newSudoku = []
    for array in sudoku:
        newSudoku.append(array.copy())
    return newSudoku


sudokuA = create_sudoku()

def recursive_solution(sudoku):
# solve it.
def recursive_solution(sudoku):
    if is_filled_sudoku(sudoku):
        return True  # The sudoku is solved.
    else:
        x, y = find_first_empty_grid(sudoku)
        #print(str(x) + "-" + str(y))
        for i in range(1, 10):
            # We're going to fill in numbers from 1 to 9, to find a solution
            # 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
                #oldSudoku = make_copy(sudoku)
                if recursive_solution(sudoku) is False:
                    sudoku[x][y] = EMPTY
                else:
                    return True
        return False

def test_solution(sudoku):
def test_solution(sudoku):
    discovered = []
    # Rows:
    # Rows:
    for column in sudoku:
        discovered.clear()
        for loc in column:
            if loc in discovered:
                return False
            if number in discovered:
                return False
            else:
                discovered.append(loc)

        discovered.clear()

    #Columns:
    for i in range(0, len(sudoku)):
        discovered.clear()
        for y in range(0, len(sudoku[i])):
            if y in discovered:
                return False
            else:
                discovered.append(y)

    discovered.clear()


    #Grids:
    for k in [0, 3, 6]:
        discovered.clear()
        for x in range(0,3):
            for y in range(0,3):
                if sudoku[x+k][y+k] in discovered:
    # grids.
    n = 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])


    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.

    for i in range(0, length):
        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)

    # 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()

if recursive_solution(sudokuA):
    if test_solution(sudokuA):
        print_sudoku(sudokuA)
else:
    if test_solution(sudoku):
        print_sudoku(sudoku)
else:
    print("Failed!")
    print_sudoku(sudokuA)
                
                


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	3x3). So if you want hexadecimal plays, you can totally do that.
22	22	"""
23	23
24	24	# Prints the given sudoku to the terminal in a readable way:
+	25	from math import sqrt # For the roots of the sudoku length.
+	26
+	27	# Constants:
+	28	EMPTY = 0
+	29
+	30	# Prints the given sudoku to the terminal in a readable way:
25	31	def print_sudoku(sudoku):
26	32	for x in sudoku:
27	-	for y in x:
28	-	print(str(y) + " ", end="")
29	-	print() # Start a new line.
30	-
+	33	# the biggest number:
+	34	biggestNumber = 0
+	35	for row in sudoku:
+	36	for number in row:
+	37	if number > biggestNumber:
+	38	biggestNumber = number
+	39
+	40	rootNumber = 10
+	41	digits = 1
+	42	while rootNumber**digits < biggestNumber:
+	43	digits += 1
+	44	# And now we've got the largest amount of digits.
+	45
+	46	for row in sudoku:
+	47	for number in sudoku:
+	48	# XXX: Even though the next line looks a bit dirty, it's a great way
+	49	# to deduce the required amount of whitespace for readable output.
+	50	# It takes the highest amount of digits, subtracted with the current
+	51	# number's digits. so 10 in a sudoku with max. 3 digits: 3-2+1 = 2
+	52	# whitespaces.
+	53	spaces = " " * (digits-len(str(number)) + 1)
+	54	print(str(number) + spaces, end="")
+	55
+	56	for i in range(0, digits):
+	57	# And after each row, a seperation whitespace.
+	58	print()
+	59
31	60	# Given an empty sudoku, the solution is very simple.
32	61	def solve_empty_sudoku(sudoku):
+	62	# root solution is possible.
+	63	def solve_empty_sudoku(sudoku):
33	64	n = 3
34	-	for i in range(0, n*n):
+	65
+	66	for i in range(0, n*n):
35	67	for j in range(0, n*n):
36	68	sudoku[i][j] = (in + i/n + j) % (nn) + 1;
37	69	return sudoku
38	70
39	71	# Creates a table of 9x9 in the form of an array containing arrays.
40	-	"""
41	-	def create_sudoku():
42	-	x = []
43	-	for i in range(0,9):
44	-	x.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
45	-	return x
46	-
47	-	EMPTY = 0
48	-	"""
49	-
50	72	# Checks if the given sudoku qualifies as a root solution.
51	73	# This function mainly serves as a silly optimization to check beforehand
52	74	# whether we have to do the entire backtrack.
53	75	def is_possible_root_solution(sudoku):
54	76	root_solution = solve_empty_sudoku()
55	77	for i in range(0, len(root_solution)):
56	-	for j in range(0, len(root_solution[i])):
57	-	if sudoku[i][j] != root_solution[i][j] and sudoku[i][j] != 0:
58	-	return False
+	78	for y in range(0, len(root_solution[x])):
+	79	if sudoku[x][y] != root_solution[x][y] and sudoku[x][y] != EMPTY:
+	80	return False
59	81	# When here, all the sudoku can be filled as a root solution.
60	-	return True
+	82	return True
61	83
62	84	# Checks whether the given number already exists in the given array.
63	85	def exists_in_array(x, y, value, sudoku):
64	86	for i in range(0, len(sudoku)):
+	87	return False # Just... of course.
+	88
+	89	for i in range(0, len(sudoku)):
65	90	if sudoku[i][y] == value and sudoku[i][y] != EMPTY:
66	-	return True
+	91	return True
67	92	return False
68	93
69	94	# Checks whether the number on the given location is unique in its column.
70	95	def exists_in_column(x, y, value, sudoku):
71	96	for i in range(0, len(sudoku[x])):
+	97	return False
+	98
+	99	for i in range(0, len(sudoku[x])):
72	100	if sudoku[x][i] == value:
73	101	return True
74	102	return False
75	103
76	104	# Checks whether the number on the given location is unique in its (3x3) grid.
77	-	def exists_in_grid(x, y, value, sudoku):
+	105	def exists_in_grid(x, y, value, sudoku):
78	106	# We're going to find out now in which part of the grid the (x,y) is put.
+	107	return False
+	108
+	109	# We're going to find out now in which part of the grid the (x,y) is put.
79	110	# The idea I'm going for now:
80	-	# I'll first try to find out in which segment of the sudoku the value is in.
+	111	# I'll first try to find out in which segment of the sudoku the value is in.
81	112	# When I've found it, I trim the data to that segment, after I'll be
82	113	# checking on that segment only.
83	114	# Chart:
84	-	n = len(sudoku) # Determining the size of the sudoku
85	-	n = 3
86	-
87	-
+	115
88	116	A = x%n
+	117	A = x%n
89	118	B = y%n
90	119	for i in range(0, n):
91	120	for j in range(0, n):
92	121	C = x - A + i
93	122	D = y - B + j
94	123	if sudoku[C][D] == value and (C != x and D != y):
95	124	return True
96	125	return False
97	126
98	127	def is_filled_sudoku(sudoku):
+	128	# and vice versa.
+	129	def is_filled_sudoku(sudoku):
99	130	for i in range(0, len(sudoku)):
100	-	for j in range(0, len(sudoku[i])):
101	-	if sudoku[i][j] == 0:
102	-	return False
+	131	for y in range(0, len(sudoku[x])):
+	132	if sudoku[x][y] == EMPTY:
+	133	return False
103	134	return True
104	135
105	136	def find_first_empty_grid(sudoku):
+	137	# an empty grid. If it encounters an empty grid, the respective (x,y)
+	138	# coordinates are returned.
+	139	# If no empty grid is being found, both returned values will be -1.
+	140	def find_first_empty_grid(sudoku):
106	141	for i in range(0, len(sudoku)):
107	-	for j in range(0, len(sudoku[i])):
108	-	if sudoku[i][j] == 0:
109	-	return i, j
110	-
111	-	def is_valid_assignment(x, y, value, sudoku):
+	142	for y in range(0, len(sudoku[x])):
+	143	if sudoku[x][y] == EMPTY:
+	144	return x, y
+	145
+	146	# When we get to this point, there's no empty grid anymore in the sudoku.
+	147	raise Exception("""
+	148	The given sudoku does not feature any empty grids. Assert that you've
+	149	given the sudoku to the is_filled_sudoku() function.
+	150	""")
+	151
+	152	# Checks whether assigning the given value to the given coordinate in the sudoku
+	153	# still renders the sudoku valid.
+	154	def is_valid_assignment(x, y, value, sudoku):
112	155	#sudoku[x][y] = value
113	-	if exists_in_array(x, y, value, sudoku):
114	156	#print("Exists in array!")
115	-	return False
116	157	if exists_in_column(x, y, value, sudoku):
117	158	#print("Exists in column!")
118	-	return False
119	159	if exists_in_grid(x, y, value, sudoku):
120	160	#print("Exists in grid!")
121	-	return False
122	161	return True
123	162
124	163	# Makes a deep copy of the given sudoku, and returns that copy.
125	-	def make_copy(sudoku):
126	-	newSudoku = []
127	-	for array in sudoku:
128	-	newSudoku.append(array.copy())
129	-	return newSudoku
130	-
131	-
132	-	sudokuA = create_sudoku()
133	-
134	-	def recursive_solution(sudoku):
+	164	# solve it.
+	165	def recursive_solution(sudoku):
135	166	if is_filled_sudoku(sudoku):
136	167	return True # The sudoku is solved.
137	168	else:
138	169	x, y = find_first_empty_grid(sudoku)
139	170	#print(str(x) + "-" + str(y))
140	-	for i in range(1, 10):
141	-	# We're going to fill in numbers from 1 to 9, to find a solution
+	171	# We're going to fill in numbers from 1 to 9, to find a solution
142	172	# that works.
143	173	if is_valid_assignment(x, y, i, sudoku):
144	174	sudoku[x][y] = i
145	175	#oldSudoku = make_copy(sudoku)
146	-	if recursive_solution(sudoku) is False:
147	176	sudoku[x][y] = EMPTY
148	177	else:
149	178	return True
150	179	return False
151	180
152	181	def test_solution(sudoku):
+	182	def test_solution(sudoku):
153	183	discovered = []
154	-	# Rows:
+	184	# Rows:
155	185	for column in sudoku:
156	186	discovered.clear()
157	-	for loc in column:
158	-	if loc in discovered:
159	-	return False
+	187	if number in discovered:
+	188	return False
160	189	else:
161	190	discovered.append(loc)
162	-
+	191	discovered.clear()
+	192
163	193	#Columns:
164	194	for i in range(0, len(sudoku)):
165	195	discovered.clear()
166	-	for y in range(0, len(sudoku[i])):
167	196	if y in discovered:
168	197	return False
169	198	else:
170	199	discovered.append(y)
171	200
172	-	discovered.clear()
173	-
+	201
174	202	#Grids:
175	203	for k in [0, 3, 6]:
176	-	discovered.clear()
177	-	for x in range(0,3):
178	-	for y in range(0,3):
179	-	if sudoku[x+k][y+k] in discovered:
+	204	# grids.
+	205	n = sqrt(len(sudoku))
+	206	gridPoints = []
+	207	for i in range(0, n):
+	208	gridPoints.append(i*n)
+	209
+	210	for k in gridPoints:
+	211	for x in range(0,n):
+	212	for y in range(0,n):
+	213	if sudoku[x+k][y+k] in discovered:
180	214	return False
181	215	else:
182	216	discovered.append(sudoku[x+k][y+k])
183	217
+	218
184	219	return True
185	220
186	221
187	-
188	-
189	-	# Prints an introduction paragraph to the user, explaining the details of the
190	222	# program, and how to operate it properly.
191	223	def print_introduction():
192	224	introduction = """
193	225	Welcome to Vngngdn's sudoku solver!
194	226	I'll explain briefly what you have to do to use this program:
195	227	After this paragraph, insert the first array of the sudoku, with each
196	228	grid seperated by 1 space.
197	229	If there are grids that are empty, use a 0 as placeholder for the empty
198	230	space.
199	231	When the row is complete, hit RETURN.
200	232	The program will then ask for other arrays, until a square sudoku is
201	233	formed.
202	234	So, for example, if you enter 9 numbers, and hit RETURN, the program
203	235	will ask for 8 more arrays, to create a 9x9 sudoku.
204	236	When the last array has been entered, the program will stop asking for
205	237	input, and immediately try to solve the sudoku.
206	238	When the sudoku has been solved, it will print the solution in a
207	239	readable way.
208	240	If the sudoku could not be solved, it will print "Failed!", instead of a
209	241	solution.
210	242	This indicates the sudoku is most likely invalid, and can't be solved.
211	243	Off you go now!
212	244	"""
+	245	"""
213	246	print(introduction)
214	247
215	248	# Asks the user for input.
216	249	def receive_input():
217	250	sudoku = [] # This will be returned in the end.
218	251	integers = [] # A list which will be added to the sudoku after input.
219	252	length = 1 # We know there will be at least 1 number.
220	253
221	254	for i in range(0, length):
222	255	integers.clear()
223	256	# The amount of given numbers implies the remaining amount of rows,
224	257	# because only square sudokus are handled.
225	258	line = input()
226	259	numbers = line.split() # numbers now contains the given numbers.
227	260	# XXX: Next addition might be redundant after the first one, but it's
228	261	# still cleaner than having an entire redundant block.
229	262	length = len(numbers)
230	263	for number in numbers:
231	264	integers.append(int(number))
232	265	sudoku.append(integers)
233	266
234	267	# Current state: The sudoku is completely filled in, including empty spots.
235	268	# TODO: Add some defensive programming structure, to check for empty spots
236	269	# in the sudoku. If so, ask the user where to insert the missing numbers.
237	270
238	271	return sudoku
239	272
240	273
241	274
242	275	# MAIN (sort of)
243	276
244	277	print_introduction()
245	278	sudoku = receive_input()
246	279
247	280	if recursive_solution(sudokuA):
248	-	if test_solution(sudokuA):
249	-	print_sudoku(sudokuA)
250	-	else:
+	281	if test_solution(sudoku):
+	282	print_sudoku(sudoku)
+	283	else:
251	284	print("Failed!")
252	285	print_sudoku(sudokuA)
253	-
+	286
254	287