Python Sudoku solver

Posted on August 22, 2011 by Daniel Veazey

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.

Code block

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

Working on the bike problem with Python

Posted on June 8, 2010 by Daniel Veazey

My bike is still chained to the rail on my balcony. If you recall, I said previously that I believed the combination to the lock had a 1 and a 4 in it. Continue reading →

Practical programming

Posted on May 22, 2010 by Daniel Veazey

I have a bicycle. It is currently attached to my balcony railing with a combination lock/cable. It has been there for a while. The weather is nice now and I want to go for a ride, but I have forgotten the combination to the lock. So today I was playing around with the lock, trying to remember the combination. I’m pretty sure it had a 1 and a 4 in it. The combination is four digits long, and the digits can be any number from 1 to 6. So I was thinking I might have to try new combinations one by one until I found the right one. How many combinations could there be? Well, I could do the math, 6*6*6*6 = 1296 possible combinations. But that doesn’t really illustrate to me the reality of fiddling around with that thing. “What a great opportunity to write a program,” I thought. So I wrote a Python program to show me a list of all the possible combinations. It was very simple. Here it is:

combos.py

x = 0
for a in range (0, 6):
    for b in range (0, 6):
        for c in range (0, 6):
            for d in range (0, 6):
                print a+1, b+1, c+1, d+1
                x = x+1
print "There are",x,"possible combinations."

How it works

First we give a value of 0 to the variable x. Then we set up 4 for loops, a through d, with each successive one inside the next. We let them run from 0 to 6. Inside the fourth loop, we tell Python to print the value that each loop is on in that particular cycle. We add 1 to the value of x to keep track of how many possible combinations there are. After all the loops are executed, we print a sentence telling us what the value of x is. That’s all there is to it! Now, write a comment in the comments section.

timestable.py

Posted on April 23, 2010 by Daniel Veazey

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.

timestable.py

# 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, 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.

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),

Line 3: The same thing happens here as in Line 2, and assigns this value to the variable “rows.”

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 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.

Python, in bitesize chunks

Posted on April 14, 2010 by Daniel Veazey

I am messing around a little bit more with Python. This is total beginner stuff. Let’s look at two kinds of loops in Python: The “for” loop and the “while” loop. We’re also going to learn a little bit about modules.

This program counts down from 30 to 0, and prints one number from that countdown every second. Here’s the whole program. It’s very short and sweet. We’ll go over it line by line.

countdown.py

import time
for count in range (30, -1, -1):
    time_a = time.time()
    time_b = time.time()
    while (time_b < time_a+1):
        time_b = time.time()
    print count
print “BOOM”

Line 1: This tells Python to import the module “time.” There are lots of modules that have been written for Python, and these modules contain lots of code that is commonly needed when writing programs. So with modules, you don’t have to write out long blocks of code to perform those functions. The module “time” has lots of functions that, surprisingly enough, deal with time.

Line 2: This is the beginning of our “for” loop. The word “count” is a variable that we define. We could just as easily call this variable “potato” or any other word. But we use the word “count” because that’s what the variable is for: to keep track of the count. The “in range” and the numbers in parentheses tell Python how many times we want it to go through this loop. The first number, 30, is the starting number. The loop assigns this value to the variable “count.” The second number, -1, is where we want the loop to stop. The reason that we don’t put a 0 here is because Python performs the “for” loop until the conditions of the second number is met. If the variable “count” has a value of -1, the loop will not go through another cycle. The last number, -1, is the amount we want to subtract from the variable “count” for each cycle of the loop. Finally, the colon at the end tells Python to follow the instructions in the succeeding lines during each cycle of the loop. So this line basically says to Python, “For the numbers 30 to -1, subtracting 1 for each cycle of this loop, assigned to the variable ‘count,’ perform the following instructions.”

Line 3: This line is indented 4 spaces. Every line that is indented 4 spaces after a loop is set up becomes part of that loop. Now what this line does is creates a variable called “time_a” and assigns a value to it, which is the current system time. It does this with the “time.time()” statement. The “time” before the period tells Python that you want something from the “time” module that it imported on the first line. The “time()” after the period tells Python what specific function you want from that “time” module, which is the current time on the system clock, expressed in seconds from the epoch. The epoch, in Linux, was midnight on January 1, 1970. If we didn’t have the “time” module to go fetch the system clock’s time, we’d have to write a lot more code to do that. But with the “time” module imported, it makes it a lot easier to tell Python to go grab it.

Line 4: This line is also indented 4 spaces, so we know it’s also a part of the loop set up in Line 2. This line does the exact same thing as Line 3, but it creates a variable called “time_b” instead of “time_a.”

Line 5: This line is also indented 4 spaces, so it’s part of the “for” loop. Here we create a “while” loop. The fundamental difference between this loop and the “for” loop that we started earlier, is that the “for” loop has a specific number of cycles we want it to go through, whereas the “while” loop doesn’t have that. We want Python to go through as many cycles as it takes until the condition of our “while” loop have been met. So how do we set the condition? It is defined in the parentheses. We want Python to go through this loop until the variable “time_b” is no longer less than the variable “time_a” plus 1. In Lines 3 and 4, we assigned the values of “time_a” and “time_b” to be those of the system clock at whatever time the program executed the instructions on those lines. Because computers work very quickly, the values of “time_a” and “time_b” are almost exactly the same. So we know that going into this loop, the condition of the loop have not been met. Once again, the colon at the end of the line tells Python to follow the instructions after this line as part of the loop.

Line 6: This line is indented an additional 4 spaces, which tells Python that it is part of the “while” loop set up in Line 5. What’s neat about Lines 5 and 6 is that they are a loop inside a loop. So this line just assigns the current system time to the variable “time_b” again. The previous value that was assigned to “time_b” gets thrown out, and the new value takes its place. This is done by the computer very quickly, and Python then looks at the condition of our “while” loop from Line 5 again. Is the value of “time_b” still less than the value of “time_a” plus one? If it is, then the program goes through another cycle of the loop. It just keeps assigning a new value to the variable “time_b” until it is no longer less than “time_a” plus one. Over and over and over again. The program may go through this loop thousands of times in one second.

Line 7: This line is indented only 4 spaces, so Python (and we) know that it is not part of the “while” loop, but it is still part of the “for” loop. This line just tells Python to print (on the screen) the value of the variable “count.” This is the last line that is indented, so Python knows that it has reached the end of the instructions that we want it to follow during each cycle of the “for” loop. It won’t go on to the next line until it goes through the loop the number of times we have defined.

Line 8: This line is not indented, so it’s not part of any loops. Once the program has gone through all the loops, we tell it to print the word “BOOM.” And that’s the end of the program.

It’s not much, but it’s a start. I want to learn more about Python.

Programming with Python

Posted on April 5, 2010 by Daniel Veazey

A few months ago, I was trying to learn the Python programming language. I learned a little bit, but lost interest. Today I came across a program I had written. The program prints 100 times the numbers 1 to 1,000,000, using two different methods: Range and Xrange. These are two different looping methods in Python (I think with the release of Python 3.0 that Xrange no longer exists). The program measures how long it takes to print those numbers and averages the 100 runs of each method to determine which is faster, Range or Xrange. The whole thing is kind of pointless, other than it was something I wanted to do, and it gave me a way to learn some Python. Anyway, here is the code:

###################
# averagetimecount.py
# a program to test the average speed of xrange loops vs. range loops in Python
# by Daniel Veazey
# 20 Oct 2009
# version 1.0
# released under the GNU General Public License v3 http://www.gnu.org/licenses/gpl.html
###################
import time
add_time_xrange = 0
for xrange_run in xrange(100):
    time_a = time.time()
    for x in xrange (1000000):
        print x
    time_b = time.time()
    add_time_xrange = add_time_xrange + (time_b - time_a)
average_time_xrange = add_time_xrange / 100
add_time_range = 0
for range_run in xrange(100):
    time_a = time.time()
    for x in range (1000000):
        print x
    time_b = time.time()
    add_time_range = add_time_range + (time_b - time_a)
average_time_range = add_time_range / 100
print "Average time for xrange: " + str(average_time_xrange)
print "Average time for range:  " + str(average_time_range)
if average_time_xrange < average_time_range:
    print "On average, xrange was faster by " + str(average_time_range - average_time_xrange) + " seconds."
if average_time_range < average_time_xrange:
    print "On average, range was faster by " + str(average_time_xrange - average_time_range) + " seconds."
if average_time_range == average_time_xrange:
    print "Xrange and range had equal average times."