sudoku solver problem

[Ri0o]

hi, i have to make a sudoku solver using python quickdraw,
i've started on it and this is what i got so far
here is the link to the assignment
http://pages.cpsc.ucal gary.ca/~zongpeng/CPSC231/assignments/A4/a4.pdf

def solveRows():
    """eliminates solved numbers by row"""
    for x in range(0, 81, 9):
        row = puzzle[x : x+9]#loops through each row
        for space in row: #loops through each space
            if len(space) == 1: #space is solved
                for space2 in row: #loops through spaces again
                    if len(space2) != 1: #space isnt already solved
                        if space[0] in space2: #the solved number is a possibility
                            del space2[space2.index(space[0])] #deletes the number as a possiblbitly                
def solveColumns():
    """eliminates solved numbers by column"""
    rows = []#splits up the puzzle into rows
    for x in range(0, 81, 9):
        rows.append(puzzle[x:x+9])
    for n in range(0, 9):
        column = [x[n] for x in rows] #loops through each column
        #the next part is taken from solveRows()
        for space in column: #loops through each space
            if len(space) == 1: #space is solved
                for space2 in column: #loops through spaces again
                    if len(space2) != 1: #space isnt already solved
                        if space[0] in space2: #the solved number is a possibility
                            del space2[space2.index(space[0])] #deletes the number as a possiblbitly

def solveBoxes():
    """eliminates solved numbers by box"""
    rows = []#splits up the puzzle into rows
    for x in range(0, 81, 9):
        rows.append(puzzle[x:x+9])
    #this next part just splits the puzzle into boxes
    for x in range(0, 9, 3):
        for y in range(0, 9, 3):
            tempRows = rows[x:x+3]
            tempBox = [row[y:y+3] for row in tempRows]
            #the next part just formats the box
            #basically it was a list of lists of lists
            #and i need it as a list of lists
            box = []
            for row in tempBox:
                for space in row:
                    box.append(space)
            #the next part is taken from solveRows()
            for space in box: #loops through each space
                if len(space) == 1: #space is solved
                    for space2 in box: #loops through spaces again
                        if len(space2) != 1: #space isnt already solved
                            if space[0] in space2: #the solved number is a possibility
                                del space2[space2.index(space[0])] #deletes the number as a possiblbitly
                                
def isSolved():
    """Checks to see if the puzzle is solved"""
    for x in puzzle:
        if len(x) != 1:
            return False
    else:
        return True
    
def main():
    while True:
        temp = puzzle #used to see when puzzle is solved
        solveBoxes()
        solveRows()
        solveColumns()
        if isSolved():#puzzle is solved
            return

def display():
    """ displays the puzzle"""
    copy = puzzle #copy of the puzzle
    copy = map(str, [x[0] for x in copy]) #makes the ints strs so i can use S.join()
    #next part just displays the puzzle all nice and pretty
    for x in range(0, 9):
        print ', '.join(copy[x:x+9])

def getInput():
    """gets a puzzle to be solved from the user"""
    puzzle = []
    for x in range(1, 10): #1 for each line of the puzzle
        puzzle.append(raw_input('enter one line of the puzzle '))
    puzStr = '\n'.join(puzzle)
    puzzle = []#a soon to be matrix holding possibilities for each space
    for letter in puzStr:
        if letter == 'x':
            puzzle.append(range(1, 10)) #adds all possibilities if square is blank
        elif letter == '\n' or letter ==' ':
            continue
        else:
            puzzle.append([int(letter)]) #adds the already given number
    return puzzle

print """This program will solve some suDoku puzzles
If it can't it will just hang indefinately so give it a little
while then if nothing happens assume that either you entered
the puzzle incorrectly, it is not solvable, or this program
can't solve it.

Begin by entering the puzzle in line by line.
Represent empty spaces by an 'x'. So a line
migh look like '6x12x897x'. This program as of now
will not catch your errors so try not to make mistakes.
You can but do not have to add any spaces when entering the puzzle.

Enjoy!
"""
puzzle = getInput()
main()
print 'The answer is:'
print
display()

don't know what to do next,i'[ve tried putting like
6x12x897x, x8x6x5x2x, x54xxxxx1, 4xx796xxx, x9xxxxx1x
xxx182xx7, 3xxxxx75x, x7x3x9x4x, x285x41x3
didn't work and it said errno #22 close failed
so, am i doing the assignment right
any help pls

[Glenton]

I think you'll need to do some more debugging. I'd recommend checking your individual functions to make sure they're doing what you think they are. It would help us to help you. E.g. if you told us what each function was meant to do, and give an example of it working then we'd know we don't need to trawl through those.

It's just a bit difficult to engage with what you've given us so far, which is probably why you haven't received many replies!

One thing, that I may or may not be correct about, is that maybe you need to pass puzzle over explicitly to your functions? Or make puzzle a global variable.

In terms of overall technique, working with a class may be easier.

In terms of actually solving the sudoku (and I admit I haven't understood your method entirely so perhaps I'm not helping here), I'd consider creating a list of the possible answers in each of the 81 squares ("123456789" ). Then have an algorithm as follows:
(A) update the possible answers with the input variables (e.g. change square 1 to "6" and 3 to "1" etc in the example you gave).
(B1) Eliminate all new answers from the rows, columns and blocks (flag if there's been a change).
(B2) Check whether each number (1-9) appears only once in each row. If so set that square equal to the number. (flag if there's been a change).
(B3) Ditto for columns
(B4) Ditto for blocks.
(B5) Check for any squares that have no possibilities. If there is one then exit with a "contradict ory set up" message.
(B6) Check if it's been solved. If so then exit with the solution.
(B5) If there's been a change then return to B1. If not go on to C.
(hint: if you keep track of the sum of the lengths of the possibilities strings you'll know if there's been a change, and if it's been solved).
(C) Now you're in a situation where the straightforward stuff didn't work. You can give up and exit, or you can do the following:
(C1) Find the square with the least number of possibilities (chances are there'll be one with 2 or 3 possibilities only).
(C2) Assume it's the first of these possibilities and try to solve with the algorithm in B.
(C2.1) If you get a contradictory set up message, then you know you can eliminate the possibility you tried in C2. Do so, and go back to B again. (This is really what you want from C).
(C2.2) If this solves it, then save the solution, but don't yet exit, as you haven't discovered uniqueness. Continue to C3
(C2.3) If you get to somewhere where you are not progressing (cf B5), then continue to C3
(C3) Go back to C1 but check the next possibility.

Hope this helps. Post back to let us know how it's going.

[Glenton]

Here's a sudoku solver along the above lines:

#!/usr/bin/env python
#This is meant to solve a sudoku.  It will eventually become a test for GUI etc.


class Sudoku(object):
    """A sudoku puzzle solver"""
    #define startposition, currentposition, possibilities
    def __init__(self,puzzle):
        """Takes the puzzle in format of
        a string of 81 characters of x913xx12x1"""
        self.startposition=puzzle
        self.currentposition=puzzle
        self.possibilities=[]
        for i in range(81):
            self.possibilities.append("123456789")
        self.impossible=False
        self.finish=False
    def progress(self):
        pos=0
        for i in self.possibilities:
             pos+=len(i)
        return pos
        
    def basiccrunch(self):
        """does the basic elimination"""
        #eliminate possibilities from the current position
        for n,i in enumerate(self.currentposition):
            if i<>"x":
                #ensure current positional possibility is set
                row=n/9 #0-8
                col=n%9 #0-8
                sqrow=row/3 #0-2
                sqcol=col/3
                #eliminate from rows
                for j in range(9*row,9*(row+1)):
                    self.possibilities[j]=self.possibilities[j].replace(i,"")
                #eliminate from cols
                for j in range(col,col+81,9):
                    self.possibilities[j]=self.possibilities[j].replace(i,"")
                #eliminate from squares
                    for j in range(3):
                        for k in range(3):
                            self.possibilities[sqcol*3+k+9*(3*sqrow+j)]=self.possibilities[sqcol*3+k+9*(3*sqrow+j)].replace(i,"")
                self.possibilities[n]=i
        #find possibilities that can only be in a given position
        #ROWS
        for row in range(9):
            for i in range(1,10):
                myCount=0
                for element in range(9):
                    if str(i) in self.possibilities[9*row+element]:
                        myCount+=1
                        myLast=element
                if myCount==1:
                    self.possibilities[9*row+myLast]=str(i)
                if myCount==0:
                    self.impossible=True
        #COLUMNS
        for col in range(9):
            for i in range(1,10):
                myCount=0
                for element in range(9):
                    if str(i) in self.possibilities[col+9*element]:
                        myCount+=1
                        myLast=element
                if myCount==1:
                    self.possibilities[col+9*myLast]=str(i)
                if myCount==0:
                    self.impossible=True
        #SQUARES
        for sqr in range(9):
            sqrx=sqr/3
            sqry=sqr%3
            for i in range(1,10):
                myCount=0
                for element in range(9):
                    elx=element/3
                    ely=element%3
                    if str(i) in self.possibilities[sqrx*3+elx+9*(3*sqry+ely)]:
                        myCount+=1
                        myLastx=elx
                        myLasty=ely
                if myCount==1:
                    self.possibilities[sqrx*3+myLastx+9*(3*sqry+myLasty)]=str(i)
                if myCount==0:
                    self.impossible=True
        #Put back into currentposition
        for n,i in enumerate(self.possibilities):
            if len(i)==1:
                self.currentposition=self.currentposition[:n]+i+self.currentposition[n+1:]
            if len(i)==0:
                self.impossible=True
        
    def basiccrunchmanager(self):
        """returns solved, not progressing, impossible"""
        while True:
            prog1=self.progress()
            self.basiccrunch()
            prog2=self.progress()
            if "x" not in self.currentposition:
                return "solved"
            if self.impossible:
                return "impossible"
            if prog2==prog1:
                return "not progressing"
    def solve(self):
        """solves the sudoku"""
        res=self.basiccrunchmanager() #solved, not progressing, impossible
        if res=="solved":
            print "solved!"
            self.printresult()
        elif res=="not progressing":
            #implement advanced solver here
            print "no further progress possible.  Calling advanced solver..."
            self.advancedsolver(2)
            if not self.finish:
                self.solve()
        elif res=="impossible":
            print "not possible to solve"
            for n,i in enumerate(self.possibilities):
                print n,i
            self.printresult()
    def savepos(self):
        self.savedposition=self.currentposition
        self.savedpossibilities=[]
        for i in self.possibilities:
            self.savedpossibilities.append(i)
        #self.savedpossibilities=self.possibilities
        return
    def restorepos(self):
        self.currentposition=self.savedposition
        self.possibilities=[]
        for i in self.savedpossibilities:
            self.possibilities.append(i)
        #self.possibilities=self.savedpossibilities
        return
    def advancedsolver(self,level=2):
        """eliminates one result and then does basic solver"""
        #save current situation
        self.savepos()
        for n in range(81):
            i=self.possibilities[n]
            if len(i)==level:
                for guess in i:
                    self.currentposition=self.currentposition[:n]+guess+self.currentposition[n+1:]
                    res=self.basiccrunchmanager()
                    if res=="impossible":
                        self.restorepos()
                        self.impossible=False
                        self.possibilities[n]=self.possibilities[n].replace(guess,"")
                        if len(self.possibilities[n])==1:
                            self.currentposition=self.currentposition[:n]+self.possibilities[n]+self.currentposition[n+1:]
                        print "Advanced solver has made some progress. Continuing with basic solver"
                        return
                    elif res=="solved":
                        print "A solution is found.  May not be unique."
                        self.printresult()
                        print "Continuing to check"
                        self.restorepos()
                    elif res=="not progressing":
                        self.restorepos()
        print "Advanced solver failed at level ",level
        if level>3:
            print "Advanced solver failed.  Probably insufficient information."
            self.finish=True
            return
        self.advancedsolver(level+1)
                        
                        
    def printresult(self):
        """Prints result so far"""
        for n,i in enumerate(self.currentposition):
            if n%27==0: print "-------------------------------------------------------"
            if n%3==0: print "| ",
            print i,"  ",
            if n%9==8: print "|"
        print "-------------------------------------------------------"

def main():
    puz="6x12xxx7xx8x6x5x2xxxxxxxxx14xx7xxxxxx9xxxxx1xxxx182xxxxxxxxx75xx7x3x9x4xx285x41x3"
    #UNCOMMENT THESE LINES TO ENTER PUZZLE MANUALLY
    #puz=""
    #for i in range(9):
    #    puz+=raw_input("Enter line "+str(i+1)+":")
    sud=Sudoku(puz)
    sud.solve()

if __name__=="__main__": main()

[Ri0o]

thx alot now the only thing is left is this
I tried doing it before posting but i just can't so this is the partial solution

import copy

def display(A):
    if A:
        for i in range(9):
            for j in range(9):
                if type(A[i][j]) == type([]): print A[i][j][0],
                else: print A[i][j],
            print
        print
    else: print A

def has_conflict(A):
    for i in range(9):
        for j in range(9):
            for (x,y) in get_neighbors(i,j):
                if len(A[i][j])==1 and A[i][j]==A[x][y]: return True
    return False

def get_neighbors(x,y):    # no idea how to get it or do it
    return []

def update(A, i, j, value):  # no idea how to do it
    return []

def solve(A):   # not sure if it's coorect
    return []          
 



A = []
infile = open('puzzle1.txt', 'r')

for i in range(9):
    A += [[]] 
    for j in range(9):
        num = int(infile.read(2))
        if num: A[i] += [[num]]
        else: A[i] += [[1,2,3,4,5,6,7,8,9]]

for i in range(9):
    for j in range(9):
        if len(A[i][j])==1: A = update(A, i,j, A[i][j][0])
        if A==[]: break
    if A==[]: break

if A<>[]: A = solve(A)
display(A)

So as u can see it has to deal with A
now what i need is the def update part, get neighbours, and solve. I worked all the other stufff now i just need this so if anyone pls help me out, any help would be really apperciated
BTW the link of my assignment is top of the page