Written by 
I spent the last couple of days thinking about and writing a program in Python to solve Sudoku puzzles. I know it has been done many times before, but I wanted to try anyway. I have been really excited about programming lately. It makes me feel like a kid again, when my dad had a TRS-80 and I was writing BASIC programs on it.
This Sudoku solver uses only a very basic method. I will add more advanced methods later. This was more about an exercise in programming than creating a robust Sudoku solver. Here it is. To get a usable copy of the code, click the little icon to the left of the printer icon, then copy and paste the code from the pop-up window.
# sudoku_solver_7.py
# version 0.1
#
# Copyright 2011 Daniel Veazey <danielveazey@gmail.com>
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
# MA 02110-1301, USA.
#
#
def quadfinder(find): # to figure out which quad to check for a position while solving
global quad_position
for quadcount in range(0, 9):
if find in quad_position[quadcount]:
return quadcount
print "Welcome to Daniel Veazey's Sudoku Solver 7."
print "http://www.danielveazey.com"
print "Please fill in the available numbers on the board,"
print "starting on the top row (Row 1), going left to right."
print "If a square is blank, put a 0 in its place."
print "Separate each position with a comma and a space."
print "Each position can be only one digit, 0 through 9."
print "Example:"
print "Row 1: 5, 6, 0, 0, 4, 1, 0, 0, 8"
print "Row 2: 1, 0, 0, 0, 0, 9, 0, 7, 0"
print "etc."
print
print "Let's get started."
print
print
## ask the user to populate the board by rows
row = [0, 1, 2, 3, 4, 5, 6, 7, 8]
for x in range(0, 9):
row[x] = list(input("Row " + str(x+1) + ": "))
print
print
print "Original board:"
for x in range (0, 9):
print row[x]
## define and populate the columns by referring to the rows
col = [0, 1, 2, 3, 4, 5, 6, 7, 8]
for x in range (0, 9):
col[x] = [row[0][x], row[1][x], row[2][x], row[3][x], row[4][x], row[5][x], row[6][x], row[7][x], row[8][x]]
## define and populate quads by referring to slices of rows
quad = [0, 1, 2, 3, 4, 5, 6, 7, 8]
quad[0] = row[0][0:3] + row[1][0:3] + row[2][0:3]
quad[1] = row[0][3:6] + row[1][3:6] + row[2][3:6]
quad[2] = row[0][6:] + row[1][6:] + row[2][6:]
quad[3] = row[3][0:3] + row[4][0:3] + row[5][0:3]
quad[4] = row[3][3:6] + row[4][3:6] + row[5][3:6]
quad[5] = row[3][6:] + row[4][6:] + row[5][6:]
quad[6] = row[6][0:3] + row[7][0:3] + row[8][0:3]
quad[7] = row[6][3:6] + row[7][3:6] + row[8][3:6]
quad[8] = row[6][6:] + row[7][6:] + row[8][6:]
## populate list of single positions
position = list()
for z in range(0, 81):
for x in range(0, 9):
for y in range(0, 9):
position.append(row[x][y])
## put list of possible answers in unsolved single positions
for x in range(0, 81):
if position[x] == 0:
position[x] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
## define which positions are in which quads
quad_position = [0, 1, 2, 3, 4, 5, 6, 7, 8]
quad_position[0] = [0, 1, 2, 9, 10, 11, 18, 19, 20]
quad_position[1] = [3, 4, 5, 12, 13, 14, 21, 22, 23]
quad_position[2] = [6, 7, 8, 15, 16, 17, 24, 25, 26]
quad_position[3] = [27, 28, 29, 36, 37, 38, 45, 46, 47]
quad_position[4] = [30, 31, 32, 39, 40, 41, 48, 49, 50]
quad_position[5] = [33, 34, 35, 42, 43, 44, 51, 52, 53]
quad_position[6] = [54, 55, 56, 63, 64, 65, 72, 73, 74]
quad_position[7] = [57, 58, 59, 66, 67, 68, 75, 76, 77]
quad_position[8] = [60, 61, 62, 69, 70, 71, 78, 79, 80]
################# SOLVING ######################################
## this program uses only a very simple method to solve the puzzle,
## just checking to see if a possible answer for a position
## is already in its row, column or quad. if so, the possible answer
## is eliminated from the list of possible answers.
did_change = True
while did_change == True:
did_change = False
for x in range(0, 81):
if type(position[x]) == list:
y = 0
while type(position[x]) == list and y < len(position[x]): # to only keep checking if there are more items in the list of possible answers
# check to see if the possible answer is already in a position in the row, column or quad
if position[x][y] in row[x/9] or position[x][y] in col[x%9] or position[x][y] in quad[quadfinder(x)]: # quadfinder tells us which quad to check
del position[x][y] ## delete the possible answer if it's found elsewhere
did_change = True ## to keep the loop going
if len(position[x]) == 1: ## if list of possible answers is only one item long,
position[x] = position[x][0] ## remove the nested list
row[x/9][x%9] = position[x] ## and copy the answer to the rows,
col[x%9][x/9] = position[x] ## columns,
for quad_count in range(0, 9): ## and quads
if x in quad_position[quad_count]: ## similar to function quadfinder(), but used on its own here
for z in range(0, 9):
if x == quad_position[quad_count][z]:
quad[quad_count][z] = position[x]
else: y = y + 1 # to check the next item in the list of possible answers
## additional methods will go here in the future
## find out if the puzzle was solved:
solved = True
for x in range(0, 81):
if type(position[x]) == list:
solved = False
if solved == False:
print
print
print "Here is a list of positions with either"
print "the correct answers or"
print "a list of possible correct answers:"
for x in range(0, 81):
print str(x+1) + ': ' + str(position[x])
## also print board by rows
print
print
print "This is as far as I got using the simple method Scroll up"
print "to see a list of possible answers for each position on the board."
for x in range (0, 9):
print row[x]
else:
print
print
print "I SOLVED IT!!!"
for x in range (0, 9):
print row[x]Plans for future versions
- Add more advanced methods for solving puzzles
- Add a timer to tell the user how long it took to solve the puzzle
Any more ideas? Leave a comment.
timestable.py
2010 2 Comments
I think I’m going to stick with this theme for now. It accommodates my WP-SynHighlight plugin rather well, and it’s easy to read. It’s rather plain, but that’s a sacrifice I’m willing to make.
Since I have jumbled up the appearance of my website for the sake of displaying programming code, let’s have a look at a small Python program I wrote and break it down.
Line 1: We begin the program with a comment. Comments in Python are set off by the # symbol. Python will ignore everything on a line after the # appears. I have been taught that adding comments and notations is important when programming. It makes the program easier to read by someone else who might be having a look, and it also helps you remember why you wrote a particular piece of code. So I am going to try to add comments and notations where appropriate. As you can see from the comment in Line 1, this program creates a multiplication table as defined by the user.
Line 2: Here we ask the user how many columns how many columns we want to appear in the multiplication table, and we assign that value to the variable “columns.” The int() means we want what’s in the following set of parentheses to be an integer. raw_input() is supposedly better than just input() because of some rare bugs. I’ve been told to use raw_input() over input() as standard practice, so that’s what I’m doing. raw_input() prints what’s in the quotes in the next set of parentheses and waits for the user to input something. If the user inputs something other than a number, the program produces and error and terminates, because of the int() function. For example, if the user inputs “ABC,” int() can’t return an integer, thus causing the error. But for now we’ll just pretend that the only thing the user would enter is a number. So because the raw_input() is inside the int(), columns ends up being an integer of whatever the user inputs.
Line 3: The same thing happens here as in Line 2, and assigns this value to the variable “rows.”
Line 4: Now we want to find out how many digits the largest number in the program will be, so we can space the table out evenly. The len() function returns the length of the string inside the parentheses. But columns * rows doesn’t produce a string, so we have to put the str() function inside the len() function. So str() returns a string representation of columns * rows, and len() returns the length of that string, and assigns it the the variable “longest.”
Line 5: Now we have all the information we need to create our table. We make a for loop called table, and give it a range of 1 through the value of “rows” + 1. We add the + 1 because the range in a for loop is exclusive on the back end, meaning it doesn’t include the actual last value of that loop.
Line 6: Inside the first loop called “table,” we make another for loop called “table2,” with the values of 1 through the value of “columns” + 1.
Line 7: Inside the table2 loop, we get the results for each cell of our multiplication table by multiplying the values of table and table2. As the program goes through the cycles of the two loops, the values of table and table2 change and give a different result for each cycle. We assign this value to the variable “result.”
Line 8: Now we print a string representation of the value of the “result” variable, and we add “.rjust(longest)” to tell Python we want it to print the result right-justified to the number of spaces in parentheses, which we get by plugging in the “longest” variable we got in Line 4. We put a comma at the end of this line to keep Python from adding a carriage return after printing the result.
Line 9: This line is moved back 4 spaces, so it’s not part of the “table2” loop, but it is still part of the “table” loop. We just add a print statement here so Python now adds the carriage return after finishing a line of the multiplication table.
Now there are a couple of improvements I want to make to this program. One improvement I want to make is to have a contingency plan for when the user inputs something other than a usable number for rows or columns. That shouldn’t be too hard. Another improvement I want to make is instead of printing the multiplication table to the screen, the program will output the results to a text file, because if you make a very large multiplication table, you run out of space and the lines break over before it gets to the end.
I think I’m going to stick with this theme for now. It accommodates my WP-SynHighlight plugin rather well, and it’s easy to read. It’s rather plain, but that’s a sacrifice I’m willing to make.
Since I have jumbled up the appearance of my website for the sake of displaying programming code, let’s have a look at a small Python program I wrote and break it down.
# produce a multiplication table with the number of rows and columns defined by the user
columns = int(raw_input(“Input the number of columns: “))
rows = int(raw_input(“Input the number of rows: “))
longest = len(str(columns * rows)) # find out how many digits are needed for rjust() to format table evenly
for table in range (1, rows+1):
for table2 in range (1, columns+1):
result = table * table2
print str(result).rjust(longest),
print
Line 1: We begin the program with a comment. Comments in Python are set off by the # symbol. Python will ignore everything on a line after the # appears. I have been taught that adding comments and notations is important when programming. It makes the program easier to read by someone else who might be having a look, and it also helps you remember why you wrote a particular piece of code. So I am going to try to add comments and notations where appropriate. As you can see from the comment in Line 1, this program creates a multiplication table as defined by the user.
Line 2: Here we ask the user how many columns how many columns we want to appear in the multiplication table, and we assign that value to the variable “columns.” The int() means we want what’s in the following set of parentheses to be an integer. raw_input() is supposedly better than just input() because of some rare bugs. I’ve been told to use raw_input() over input() as standard practice, so that’s what I’m doing. raw_input() prints what’s in the quotes in the next set of parentheses and waits for the user to input something. If the user inputs something other than a number, the program produces and error and terminates, because of the int() function. For example, if the user inputs “ABC,” int() can’t return an integer, thus causing the error. But for now we’ll just pretend that the only thing the user would enter is a number. So because the raw_input() is inside the int(), columns ends up being an integer of whatever the user inputs.
Line 3: The same thing happens here as in Line 2, and assigns this value to the variable “rows.”
Line 4: Now we want to find out how many digits the largest number in the program will be, so we can space the table out evenly. The len() function returns the length of the string inside the parentheses. But columns * rows doesn’t produce a string, so we have to put the str() function inside the len() function. So str() returns a string representation of columns * rows, and len() returns the length of that string, and assigns it the the variable “longest.”
Line 5: Now we have all the information we need to create our table. We make a for loop called table, and give it a range of 1 through the value of “rows” + 1. We add the + 1 because the range in a for loop is exclusive on the back end, meaning it doesn’t include the actual last value of that loop.
Line 6: Inside the first loop called “table,” we make another for loop called “table2,” with the values of 1 through the value of “columns” + 1.
Line 7: Inside the table2 loop, we get the results for each cell of our multiplication table by multiplying the values of table and table2. As the program goes through the cycles of the two loops, the values of table and table2 change and give a different result for each cycle. We assign this value to the variable “result.”
Line 8: Now we print a string representation of the value of the “result” variable, and we add “.rjust(longest)” to tell Python we want it to print the result right-justified to the number of spaces in parentheses, which we get by plugging in the “longest” variable we got in Line 4. We put a comma at the end of this line to keep Python from adding a carriage return after printing the result.
Line 9: This line is moved back 4 spaces, so it’s not part of the “table2” loop. We just add a print statement here so Python now adds the carriage return after finishing a line of the multiplication table.
Now there are a couple of improvements I want to make to this program. One improvement I want to make is to have a contingency plan for when the user inputs something other than a usable number for rows or columns. That shouldn’t be too hard. Another improvement I want to make is instead of printing the multiplication table to the screen, the program will output the results to a text file, because if you make a very large multiplication table, you run out of space and the lines break over before it gets to the end.