fun | Gitar

Added an introduction to the program, removed the example sudoku, and an input handler for the sudoku solver.

Author: Vngngdn
Date: July 22, 2016, 4:16 p.m.
Hash: fcf40fb6d89e9688f5d9ebfb919c35d9cfc8c7e2
Parent: 306409c3d126fdff16a950a002086c145771267a
Modified file: sudoku-solver.py

sudoku-solver.py ¶

69 additions and 34 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.
"""

# I don't think I need to explain this, do I? Although I will explain how the
# program works:
# One is supposed to give an array of arrays, which will each contain a series
# of integer values in range [1,9]. Some of them may be 0, these will then stand
# for an empty value.
# This program's goal is to remove all 0's (blank spaces) and fill them so, that
# the sudoku is considered solved. After that, it prints the sudoku to the
# terminal.

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:
def print_sudoku(sudoku):
    for x in sudoku:
        #print(sudoku[x])
        for y in x:
            print(str(y) + " ", end="")
            #print(str(sudoku[x][y]) + " ", end="")
        print()  # Start a new line.

# Given an empty sudoku, the solution is very simple.
def solve_empty_sudoku(sudoku): 
    n = 3
    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():
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.
def is_possible_root_solution(sudoku):
# 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
    # 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):
    #value = sudoku[x][y]
    for i in range(0, len(sudoku)):
        if sudoku[i][y] == value and sudoku[i][y] != 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):
    #value = sudoku[x][y]
    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):
    #value = sudoku[x][y]
    # We're going to find out now in which part of the grid the (x,y) is put.
    # We'll increment x and y by 1 in order to have some 1-indexed math:

    # The idea I'm going for now:
    # 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:
    """
    +-----+
    |A B C|
    |D E F|
    |G H I|
    +-----+
    """
    n = 3
    n = 3
    

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

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):
    #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):
    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
            # 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):
    discovered = []
    # Rows:
    for column in sudoku:
        discovered.clear()
        for loc in column:
            if loc in discovered:
                return False
            else:
                discovered.append(loc)

    #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:
                    return False
                else:
                    discovered.append(sudoku[x+k][y+k])

    return True



# MAIN
sudokuA = [
        [8, 4, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 5, 7, 0, 1, 0, 3, 4],
        [9, 0, 7, 0, 0, 0, 0, 0, 0],
        [5, 9, 0, 2, 0, 0, 0, 0, 0],
        [0, 0, 0, 3, 8, 6, 0, 0, 0],
        [0, 0, 0, 0, 0, 4, 0, 8, 2],
        [0, 0, 0, 0, 0, 0, 3, 0, 1],
        [7, 3, 0, 5, 0, 9, 6, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 7, 5]
        ]

# 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:
    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	# I don't think I need to explain this, do I? Although I will explain how the
18	-	# program works:
19	-	# One is supposed to give an array of arrays, which will each contain a series
20	-	# of integer values in range [1,9]. Some of them may be 0, these will then stand
21	-	# for an empty value.
22	-	# This program's goal is to remove all 0's (blank spaces) and fill them so, that
23	-	# the sudoku is considered solved. After that, it prints the sudoku to the
24	-	# terminal.
25	-
+	18	This sudoku solver takes a recursive approach to solve a given sudoku.
+	19	Although there are many different variations and types of sudokus, this program
+	20	only handles NxN sudokus (i.e. squares with root-subgrids, like the most common
+	21	3x3). So if you want hexadecimal plays, you can totally do that.
+	22	"""
+	23
26	24	# Prints the given sudoku to the terminal in a readable way:
27	25	def print_sudoku(sudoku):
28	26	for x in sudoku:
29	27	#print(sudoku[x])
30	-	for y in x:
31	28	print(str(y) + " ", end="")
32	29	#print(str(sudoku[x][y]) + " ", end="")
33	-	print() # Start a new line.
34	30
35	31	# Given an empty sudoku, the solution is very simple.
36	32	def solve_empty_sudoku(sudoku):
37	33	n = 3
38	34	for i in range(0, n*n):
39	35	for j in range(0, n*n):
40	36	sudoku[i][j] = (in + i/n + j) % (nn) + 1;
41	37	return sudoku
42	38
43	39	# Creates a table of 9x9 in the form of an array containing arrays.
44	40	def create_sudoku():
+	41	def create_sudoku():
45	42	x = []
46	43	for i in range(0,9):
47	44	x.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
48	45	return x
49	46
50	47	EMPTY = 0
51	48
+	49
52	50	# Checks if the given sudoku qualifies as a root solution.
53	51	def is_possible_root_solution(sudoku):
+	52	# whether we have to do the entire backtrack.
+	53	def is_possible_root_solution(sudoku):
54	54	root_solution = solve_empty_sudoku()
55	55	for i in range(0, len(root_solution)):
56	56	for j in range(0, len(root_solution[i])):
57	57	if sudoku[i][j] != root_solution[i][j] and sudoku[i][j] != 0:
58	58	return False
59	59	# When here, all the sudoku can be filled as a root solution.
60	60	return True
61	61
62	62	# Checks whether the given number already exists in the given array.
63	63	def exists_in_array(x, y, value, sudoku):
64	64	#value = sudoku[x][y]
65	-	for i in range(0, len(sudoku)):
66	65	if sudoku[i][y] == value and sudoku[i][y] != EMPTY:
67	66	return True
68	67	return False
69	68
70	69	# Checks whether the number on the given location is unique in its column.
71	70	def exists_in_column(x, y, value, sudoku):
72	71	#value = sudoku[x][y]
73	-	for i in range(0, len(sudoku[x])):
74	72	if sudoku[x][i] == value:
75	73	return True
76	74	return False
77	75
78	76	# Checks whether the number on the given location is unique in its (3x3) grid.
79	77	def exists_in_grid(x, y, value, sudoku):
80	78	#value = sudoku[x][y]
81	-	# We're going to find out now in which part of the grid the (x,y) is put.
82	79	# We'll increment x and y by 1 in order to have some 1-indexed math:
83	-
84	-	# The idea I'm going for now:
85	80	# I'll first try to find out in which segment of the sudoku the value is in.
86	81	# When I've found it, I trim the data to that segment, after I'll be
87	82	# checking on that segment only.
88	83	# Chart:
89	84	"""
90	-	+-----+
91	-	\|A B C\|
92	-	\|D E F\|
93	-	\|G H I\|
94	-	+-----+
95	-	"""
96	-	n = 3
+	85	n = 3
97	86
98	87
99	88	A = x%n
100	89	B = y%n
101	90	for i in range(0, n):
102	91	for j in range(0, n):
103	92	C = x - A + i
104	93	D = y - B + j
105	94	if sudoku[C][D] == value and (C != x and D != y):
106	95	return True
107	96	return False
108	97
109	98	def is_filled_sudoku(sudoku):
110	99	for i in range(0, len(sudoku)):
111	100	for j in range(0, len(sudoku[i])):
112	101	if sudoku[i][j] == 0:
113	102	return False
114	103	return True
115	104
116	105	def find_first_empty_grid(sudoku):
117	106	for i in range(0, len(sudoku)):
118	107	for j in range(0, len(sudoku[i])):
119	108	if sudoku[i][j] == 0:
120	109	return i, j
121	110
122	111	def is_valid_assignment(x, y, value, sudoku):
123	112	#sudoku[x][y] = value
124	113	if exists_in_array(x, y, value, sudoku):
125	114	#print("Exists in array!")
126	115	return False
127	116	if exists_in_column(x, y, value, sudoku):
128	117	#print("Exists in column!")
129	118	return False
130	119	if exists_in_grid(x, y, value, sudoku):
131	120	#print("Exists in grid!")
132	121	return False
133	122	return True
134	123
135	124	# Makes a deep copy of the given sudoku, and returns that copy.
136	125	def make_copy(sudoku):
137	126	newSudoku = []
138	127	for array in sudoku:
139	128	newSudoku.append(array.copy())
140	129	return newSudoku
141	130
142	131
143	132	sudokuA = create_sudoku()
144	133
145	134	def recursive_solution(sudoku):
146	135	if is_filled_sudoku(sudoku):
147	136	return True # The sudoku is solved.
148	137	else:
149	138	x, y = find_first_empty_grid(sudoku)
150	139	#print(str(x) + "-" + str(y))
151	140	for i in range(1, 10):
152	141	# We're going to fill in numbers from 1 to 9, to find a solution
153	142	# that works.
154	143	if is_valid_assignment(x, y, i, sudoku):
155	144	sudoku[x][y] = i
156	145	#oldSudoku = make_copy(sudoku)
157	146	if recursive_solution(sudoku) is False:
158	147	sudoku[x][y] = EMPTY
159	148	else:
160	149	return True
161	150	return False
162	151
163	152	def test_solution(sudoku):
164	153	discovered = []
165	154	# Rows:
166	155	for column in sudoku:
167	156	discovered.clear()
168	157	for loc in column:
169	158	if loc in discovered:
170	159	return False
171	160	else:
172	161	discovered.append(loc)
173	162
174	163	#Columns:
175	164	for i in range(0, len(sudoku)):
176	165	discovered.clear()
177	166	for y in range(0, len(sudoku[i])):
178	167	if y in discovered:
179	168	return False
180	169	else:
181	170	discovered.append(y)
182	171
183	172	discovered.clear()
184	173
185	174	#Grids:
186	175	for k in [0, 3, 6]:
187	176	discovered.clear()
188	177	for x in range(0,3):
189	178	for y in range(0,3):
190	179	if sudoku[x+k][y+k] in discovered:
191	180	return False
192	181	else:
193	182	discovered.append(sudoku[x+k][y+k])
194	183
195	184	return True
196	185
197	186
198	187
199	188	# MAIN
200	-	sudokuA = [
201	-	[8, 4, 0, 0, 0, 0, 0, 0, 0],
202	-	[0, 0, 5, 7, 0, 1, 0, 3, 4],
203	-	[9, 0, 7, 0, 0, 0, 0, 0, 0],
204	-	[5, 9, 0, 2, 0, 0, 0, 0, 0],
205	-	[0, 0, 0, 3, 8, 6, 0, 0, 0],
206	-	[0, 0, 0, 0, 0, 4, 0, 8, 2],
207	-	[0, 0, 0, 0, 0, 0, 3, 0, 1],
208	-	[7, 3, 0, 5, 0, 9, 6, 0, 0],
209	-	[0, 0, 0, 0, 0, 0, 0, 7, 5]
210	-	]
211	-
+	189	# Prints an introduction paragraph to the user, explaining the details of the
+	190	# program, and how to operate it properly.
+	191	def print_introduction():
+	192	introduction = """
+	193	Welcome to Vngngdn's sudoku solver!
+	194	I'll explain briefly what you have to do to use this program:
+	195	After this paragraph, insert the first array of the sudoku, with each
+	196	grid seperated by 1 space.
+	197	If there are grids that are empty, use a 0 as placeholder for the empty
+	198	space.
+	199	When the row is complete, hit RETURN.
+	200	The program will then ask for other arrays, until a square sudoku is
+	201	formed.
+	202	So, for example, if you enter 9 numbers, and hit RETURN, the program
+	203	will ask for 8 more arrays, to create a 9x9 sudoku.
+	204	When the last array has been entered, the program will stop asking for
+	205	input, and immediately try to solve the sudoku.
+	206	When the sudoku has been solved, it will print the solution in a
+	207	readable way.
+	208	If the sudoku could not be solved, it will print "Failed!", instead of a
+	209	solution.
+	210	This indicates the sudoku is most likely invalid, and can't be solved.
+	211	Off you go now!
+	212	"""
+	213	print(introduction)
+	214
+	215	# Asks the user for input.
+	216	def receive_input():
+	217	sudoku = [] # This will be returned in the end.
+	218	integers = [] # A list which will be added to the sudoku after input.
+	219	length = 1 # We know there will be at least 1 number.
+	220
+	221	for i in range(0, length):
+	222	integers.clear()
+	223	# The amount of given numbers implies the remaining amount of rows,
+	224	# because only square sudokus are handled.
+	225	line = input()
+	226	numbers = line.split() # numbers now contains the given numbers.
+	227	# XXX: Next addition might be redundant after the first one, but it's
+	228	# still cleaner than having an entire redundant block.
+	229	length = len(numbers)
+	230	for number in numbers:
+	231	integers.append(int(number))
+	232	sudoku.append(integers)
+	233
+	234	# Current state: The sudoku is completely filled in, including empty spots.
+	235	# TODO: Add some defensive programming structure, to check for empty spots
+	236	# in the sudoku. If so, ask the user where to insert the missing numbers.
+	237
+	238	return sudoku
+	239
+	240
+	241
+	242	# MAIN (sort of)
+	243
+	244	print_introduction()
+	245	sudoku = receive_input()
+	246
212	247	if recursive_solution(sudokuA):
213	248	if test_solution(sudokuA):
214	249	print_sudoku(sudokuA)
215	250	else:
216	251	print("Failed!")
217	252	print_sudoku(sudokuA)
218	253
219	254