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.
So, where to start?
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 laterself explanatory?
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 trueThis 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 hereThe 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 thinkSo, 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 smakeboxes() 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 :Dsolved 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 possibiliesso, 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] #transfersync 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 answerThe 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?