Sudoku solver in python :D

[Hot_Milo23]

So, this is my first try at this, actually the first time I've even had my code evaluated by anyone else, so here goes:
I'm going to try to show you how I made a program to solve sudoku puzzles in python. If you like you can probably just look at the attached source, im pretty sure it should be fairly self explanatory.
To test if its working i suggest the following:

from sudo2 import *
setpuzzle(actualpuzzle)

If this prints out a solved puzzle, it should be working ok.
Ok
So, where to start?
Some terms:
a PUZZLE-a nine by nine box, sudoku puzzle. Made up of nine BOXES
a BOX-a three by three square consisting of nine square
a SQUARE-part of a box, a socket for a number to fit in.
Each is a list, so numbering goes like this.


The first line in the code is:

import copy #used to deepcopy later

self explanatory?
continuing on:

def checkbox(box, num):  #checks if a number is in a box (num and box respectively)
	for check in box:
		if check==num:
			return False #if you find the number, return false
	return True  #if number is not found, return true

This function checks to see if a number is in a box (num and box). If it doesnt find the number it returns true, else-it returns false. Simple.

def checkrow(puzzle, box, square, num): #checks for a number in a row of a puzzle
	row=(box/3)*3+square/3          #finds row, based on box and square
	a=(row/3)*3                     #used later, put them here for readability
	b=(row%3)*3                     #as above
	check=[]
	for x in range(0, 3):
		for y in range(0,3):
			check.append(puzzle[a+x][b+y]) #makes a list of what is in the row
	for test in check:
		if test==num:
			return False      #if the number we want to place is in the list, return false
	return check                    # if we dont find it, return the list of numbers that are in the row (doesnt get used anymore, was for debugging)

This function is for checking if a certain number is in a certain row. It finds what row to check based on what box and square it is checking. As stated in the comments; the a and b variables are purely aestectic, made the code look neater in my interpreter.

def checkcol(puzzle, box, square, num): #same as check row, but checks collumns instead
	col=(box%3)*3+square%3          #finds what collum we are in
	a=col%3                         #for readability
	check=[]
	for x in range(0, 3):
		for y in range(0, 3):
			check.append(puzzle[(col/3)+x*3][a+y*3]) #numbers in column
	for test in check:
		if test==num:
			return False  #return false if number was in column
	return check                  #returns true (a list of numbers in column)

This function checks a column of numbers for a certain number. column is found by box and square again.

def checkspot(puzzle, box, square, num): #checks if a num is allowed in a square, in a box, in a puzzle
	if(checkbox(puzzle[box], num)):  #checks the box
			if(checkrow(puzzle,box, square, num)): #checks the row
				if(checkcol(puzzle, box, square, num)): #checks the column
					return True  #number may be placed here
	return False   #number cant be placed here

The function that ties all three together. Checking whether a certain number is allowed to be placed in a certain square in a certain box in a certain puzzle. Just does the three checks from above.
now, the next code is explained slightly out of order, just to make things a little clearer.

def showboard(puzzle): #converts the box/square coordinates to row/column (y,x) coordinates
	s=[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]] # a 9*9 grid
	for box in range(0,9):
		for square in range(0,9):
			row=(box/3)*3+square/3
			col=(box%3)*3+square%3
			s[row][col]=puzzle[box][square] #transfers numbers into new style (row/column)
	for x in s:
		print x    #printing the board
	return s           #was for debugging, isnt entirely nesassary any more i think

So, this code is used for showing what the board looks like. It makes a new puzzle, and converts the box/square coordinates to row/column coordinates, to make things easier to print. It still returns the new list but im not sure if im actually using that, because it only shows board once now.

def makeboxes(puzzle): #takes a puzzle with row/column coords and makes it box/square coords
	s=[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]]
	for row in range(0,9):
		for col in range(0,9):
			box=(row/3)*3+col/3
			square=(row%3)*3+col%3
			s[box][square]=puzzle[row][col]
	return s

makeboxes() does the opposite of showboard. converts row.column into box/square.

def solved(puzzle):  #checks if a puzzle is solved yet
	for box in range(0,9):
		for square in range(0,9):
			if(puzzle[square][box]==0):
				return False #if we find a box that isnt solved, we are not done. Return False
	return True #must be finished :D

solved does a check to see if the puzzle has been solved yet. if not, return false.

def preppuzzle(puzzle): #this is the function that finds what numbers can be placed at any given time.
	puzzlecopy=copy.deepcopy(puzzle) #to prevent editing the original puzzle
	for x in range(0,9):              #should be box, not x, but changed for readability
		for y in range(0,9):      #should be square not y, changed for readability
			if puzzlecopy[x][y]==0:  #if we dont know what the number is =>
				puzzlecopy[x][y]=[]  #create a list to possiblities
				for num in range(1,10):
					if checkspot(puzzle, x, y, num):
						puzzlecopy[x][y].append(num) #add possiblities to list
			else:
				puzzlecopy[x][y]=[puzzlecopy[x][y]] #if we know the answer, place it in the grid
	return puzzlecopy #returns the puzzle, but each number is now a list of possibilies

so, heres the major one. It takes a puzzle and returns the same puzzle but instead of numbers in squares, it returns lists of possible numbers. Combined with the next function it serves to find answers.

def sync(puzzle, puzzlecopy):  #get a puzzle, and a copy of the puzzle with possibilities instead of numbers, and transfer over new answers
	for box in range(0,9):
		for square in range(0,9):
			if len(puzzlecopy[box][square])==1: #if only one possibilty
				puzzle[box][square]=puzzlecopy[box][square][0] #transfer

sync takes a puzzle with possible answers and adds the new found answers to the puzzle we are working on. Basically it searches each list and if there is only one possibility in it, it must be a correct answer.

def setpuzzle(puzzle=0): #user may define a premade puzzle, which must be written in box/square format
	if(not puzzle):  #if they dont, ask to make one (with row/column format)
		puzzle=[]
		puzzle2=[] #three lists is a little clumsy, i know :(
		puzzle3=[]
		for x in range(0,9):
			puzzle2.append(raw_input("Row "+str(x+1)+" ")) #ask for next row.
		for row in range(0,len(puzzle2)):
			puzzle3.append([])
			for col in range(0,len(puzzle2[row])): #remove all strings and turn puzzle two into a list of numbers.
				puzzle3[row].append(int(puzzle2[row][col]))
		puzzle=makeboxes(puzzle3) #define our puzzle
	while(not solved(puzzle)): #if the puzzle isnt solved, keep going
		test=preppuzzle(puzzle) #find possibilities
		sync(puzzle, test)     #add new answers
	s=showboard(puzzle)  #when we finish: show the answer

The final function! The user can call the function with a puzzle preset, but it would have to be in the box/square style, used for debugging, but mite still be useful so i kept it. If a puzzle is not defined it asks the user to create one by asking for each row of the puzzle (so, the user gives the puzzle in the row/col style). The function takes what the user gives, translates it into a readable puzzle, and sets about solving it. It checks if the puzzle is solved, if not it finds more solutions. simple as that.

Now, ive tried to solve "The hardest sudoku puzzle in the world" and unfortunately it hung. So this wont solve EVERY puzzle, but it solved all the other ones i tried, so i think it does an ok job.

I'm very open to suggestions, improvements, etc. I can take criticism, i know the code isnt "elegant" and there are probably better ways to solve these puzzles. Hopefully this might even teach someone something?

[Turk4n]

Great tutorial !!!
+rep,

If you like to do algorithms in python, I will gladly give you this as a challenge
I have succeed in making a fully working one for such things as this !
*Shows what I meant...*

[marwex89]

Awesome, +rep!

[debtboy]

Great Tutorial +rep

[ZekeDragon]

I always like to see Python code. And now I must try and duplicate this, except with objects! I'll send it to you, see what you think.

+rep, man!

[Hot_Milo23]

thx everyone, and i really look forward to seeing what u do zekedragon.
@Turk4n, sure i'd love a challenge, i have a couple of other projects in mind first tho. first will be a GUI, next will be "The Towers of Hannoi" which i tried implementing in javascript aaaaaages ago, but never worked out.

[amrosama]

really nice
+rep

[Jordan]

Well done! +rep