Connecting Tech Pros Worldwide Forums | Help | Site Map
bytes > topic > python > answers

sudoku solver problem

Newbie
  
Join Date: Nov 2009
Posts: 8
#1: 3 Weeks Ago
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.ucalgary.ca/~zongpeng/CPSC231/assignments/A4/a4.pdf
Expand|Select|Wrap|Line Numbers
  1. def solveRows():
  2.     """eliminates solved numbers by row"""
  3.     for x in range(0, 81, 9):
  4.         row = puzzle[x : x+9]#loops through each row
  5.         for space in row: #loops through each space
  6.             if len(space) == 1: #space is solved
  7.                 for space2 in row: #loops through spaces again
  8.                     if len(space2) != 1: #space isnt already solved
  9.                         if space[0] in space2: #the solved number is a possibility
  10.                             del space2[space2.index(space[0])] #deletes the number as a possiblbitly                
  11. def solveColumns():
  12.     """eliminates solved numbers by column"""
  13.     rows = []#splits up the puzzle into rows
  14.     for x in range(0, 81, 9):
  15.         rows.append(puzzle[x:x+9])
  16.     for n in range(0, 9):
  17.         column = [x[n] for x in rows] #loops through each column
  18.         #the next part is taken from solveRows()
  19.         for space in column: #loops through each space
  20.             if len(space) == 1: #space is solved
  21.                 for space2 in column: #loops through spaces again
  22.                     if len(space2) != 1: #space isnt already solved
  23.                         if space[0] in space2: #the solved number is a possibility
  24.                             del space2[space2.index(space[0])] #deletes the number as a possiblbitly
  25.  
  26. def solveBoxes():
  27.     """eliminates solved numbers by box"""
  28.     rows = []#splits up the puzzle into rows
  29.     for x in range(0, 81, 9):
  30.         rows.append(puzzle[x:x+9])
  31.     #this next part just splits the puzzle into boxes
  32.     for x in range(0, 9, 3):
  33.         for y in range(0, 9, 3):
  34.             tempRows = rows[x:x+3]
  35.             tempBox = [row[y:y+3] for row in tempRows]
  36.             #the next part just formats the box
  37.             #basically it was a list of lists of lists
  38.             #and i need it as a list of lists
  39.             box = []
  40.             for row in tempBox:
  41.                 for space in row:
  42.                     box.append(space)
  43.             #the next part is taken from solveRows()
  44.             for space in box: #loops through each space
  45.                 if len(space) == 1: #space is solved
  46.                     for space2 in box: #loops through spaces again
  47.                         if len(space2) != 1: #space isnt already solved
  48.                             if space[0] in space2: #the solved number is a possibility
  49.                                 del space2[space2.index(space[0])] #deletes the number as a possiblbitly
  50.  
  51. def isSolved():
  52.     """Checks to see if the puzzle is solved"""
  53.     for x in puzzle:
  54.         if len(x) != 1:
  55.             return False
  56.     else:
  57.         return True
  58.  
  59. def main():
  60.     while True:
  61.         temp = puzzle #used to see when puzzle is solved
  62.         solveBoxes()
  63.         solveRows()
  64.         solveColumns()
  65.         if isSolved():#puzzle is solved
  66.             return
  67.  
  68. def display():
  69.     """ displays the puzzle"""
  70.     copy = puzzle #copy of the puzzle
  71.     copy = map(str, [x[0] for x in copy]) #makes the ints strs so i can use S.join()
  72.     #next part just displays the puzzle all nice and pretty
  73.     for x in range(0, 9):
  74.         print ', '.join(copy[x:x+9])
  75.  
  76. def getInput():
  77.     """gets a puzzle to be solved from the user"""
  78.     puzzle = []
  79.     for x in range(1, 10): #1 for each line of the puzzle
  80.         puzzle.append(raw_input('enter one line of the puzzle '))
  81.     puzStr = '\n'.join(puzzle)
  82.     puzzle = []#a soon to be matrix holding possibilities for each space
  83.     for letter in puzStr:
  84.         if letter == 'x':
  85.             puzzle.append(range(1, 10)) #adds all possibilities if square is blank
  86.         elif letter == '\n' or letter ==' ':
  87.             continue
  88.         else:
  89.             puzzle.append([int(letter)]) #adds the already given number
  90.     return puzzle
  91.  
  92. print """This program will solve some suDoku puzzles
  93. If it can't it will just hang indefinately so give it a little
  94. while then if nothing happens assume that either you entered
  95. the puzzle incorrectly, it is not solvable, or this program
  96. can't solve it.
  97.  
  98. Begin by entering the puzzle in line by line.
  99. Represent empty spaces by an 'x'. So a line
  100. migh look like '6x12x897x'. This program as of now
  101. will not catch your errors so try not to make mistakes.
  102. You can but do not have to add any spaces when entering the puzzle.
  103.  
  104. Enjoy!
  105. """
  106. puzzle = getInput()
  107. main()
  108. print 'The answer is:'
  109. print
  110. display()
  111.  
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

Member
  
Join Date: Nov 2008
Posts: 51
#2: 2 Weeks Ago

re: sudoku solver problem

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 "contradictory 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.
Member
  
Join Date: Nov 2008
Posts: 51
#3: 2 Weeks Ago

re: sudoku solver problem

Here's a sudoku solver along the above lines:
Expand|Select|Wrap|Line Numbers
  1. #!/usr/bin/env python
  2. #This is meant to solve a sudoku.  It will eventually become a test for GUI etc.
  3.  
  4.  
  5. class Sudoku(object):
  6.     """A sudoku puzzle solver"""
  7.     #define startposition, currentposition, possibilities
  8.     def __init__(self,puzzle):
  9.         """Takes the puzzle in format of
  10.         a string of 81 characters of x913xx12x1"""
  11.         self.startposition=puzzle
  12.         self.currentposition=puzzle
  13.         self.possibilities=[]
  14.         for i in range(81):
  15.             self.possibilities.append("123456789")
  16.         self.impossible=False
  17.         self.finish=False
  18.     def progress(self):
  19.         pos=0
  20.         for i in self.possibilities:
  21.              pos+=len(i)
  22.         return pos
  23.  
  24.     def basiccrunch(self):
  25.         """does the basic elimination"""
  26.         #eliminate possibilities from the current position
  27.         for n,i in enumerate(self.currentposition):
  28.             if i<>"x":
  29.                 #ensure current positional possibility is set
  30.                 row=n/9 #0-8
  31.                 col=n%9 #0-8
  32.                 sqrow=row/3 #0-2
  33.                 sqcol=col/3
  34.                 #eliminate from rows
  35.                 for j in range(9*row,9*(row+1)):
  36.                     self.possibilities[j]=self.possibilities[j].replace(i,"")
  37.                 #eliminate from cols
  38.                 for j in range(col,col+81,9):
  39.                     self.possibilities[j]=self.possibilities[j].replace(i,"")
  40.                 #eliminate from squares
  41.                     for j in range(3):
  42.                         for k in range(3):
  43.                             self.possibilities[sqcol*3+k+9*(3*sqrow+j)]=self.possibilities[sqcol*3+k+9*(3*sqrow+j)].replace(i,"")
  44.                 self.possibilities[n]=i
  45.         #find possibilities that can only be in a given position
  46.         #ROWS
  47.         for row in range(9):
  48.             for i in range(1,10):
  49.                 myCount=0
  50.                 for element in range(9):
  51.                     if str(i) in self.possibilities[9*row+element]:
  52.                         myCount+=1
  53.                         myLast=element
  54.                 if myCount==1:
  55.                     self.possibilities[9*row+myLast]=str(i)
  56.                 if myCount==0:
  57.                     self.impossible=True
  58.         #COLUMNS
  59.         for col in range(9):
  60.             for i in range(1,10):
  61.                 myCount=0
  62.                 for element in range(9):
  63.                     if str(i) in self.possibilities[col+9*element]:
  64.                         myCount+=1
  65.                         myLast=element
  66.                 if myCount==1:
  67.                     self.possibilities[col+9*myLast]=str(i)
  68.                 if myCount==0:
  69.                     self.impossible=True
  70.         #SQUARES
  71.         for sqr in range(9):
  72.             sqrx=sqr/3
  73.             sqry=sqr%3
  74.             for i in range(1,10):
  75.                 myCount=0
  76.                 for element in range(9):
  77.                     elx=element/3
  78.                     ely=element%3
  79.                     if str(i) in self.possibilities[sqrx*3+elx+9*(3*sqry+ely)]:
  80.                         myCount+=1
  81.                         myLastx=elx
  82.                         myLasty=ely
  83.                 if myCount==1:
  84.                     self.possibilities[sqrx*3+myLastx+9*(3*sqry+myLasty)]=str(i)
  85.                 if myCount==0:
  86.                     self.impossible=True
  87.         #Put back into currentposition
  88.         for n,i in enumerate(self.possibilities):
  89.             if len(i)==1:
  90.                 self.currentposition=self.currentposition[:n]+i+self.currentposition[n+1:]
  91.             if len(i)==0:
  92.                 self.impossible=True
  93.  
  94.     def basiccrunchmanager(self):
  95.         """returns solved, not progressing, impossible"""
  96.         while True:
  97.             prog1=self.progress()
  98.             self.basiccrunch()
  99.             prog2=self.progress()
  100.             if "x" not in self.currentposition:
  101.                 return "solved"
  102.             if self.impossible:
  103.                 return "impossible"
  104.             if prog2==prog1:
  105.                 return "not progressing"
  106.     def solve(self):
  107.         """solves the sudoku"""
  108.         res=self.basiccrunchmanager() #solved, not progressing, impossible
  109.         if res=="solved":
  110.             print "solved!"
  111.             self.printresult()
  112.         elif res=="not progressing":
  113.             #implement advanced solver here
  114.             print "no further progress possible.  Calling advanced solver..."
  115.             self.advancedsolver(2)
  116.             if not self.finish:
  117.                 self.solve()
  118.         elif res=="impossible":
  119.             print "not possible to solve"
  120.             for n,i in enumerate(self.possibilities):
  121.                 print n,i
  122.             self.printresult()
  123.     def savepos(self):
  124.         self.savedposition=self.currentposition
  125.         self.savedpossibilities=[]
  126.         for i in self.possibilities:
  127.             self.savedpossibilities.append(i)
  128.         #self.savedpossibilities=self.possibilities
  129.         return
  130.     def restorepos(self):
  131.         self.currentposition=self.savedposition
  132.         self.possibilities=[]
  133.         for i in self.savedpossibilities:
  134.             self.possibilities.append(i)
  135.         #self.possibilities=self.savedpossibilities
  136.         return
  137.     def advancedsolver(self,level=2):
  138.         """eliminates one result and then does basic solver"""
  139.         #save current situation
  140.         self.savepos()
  141.         for n in range(81):
  142.             i=self.possibilities[n]
  143.             if len(i)==level:
  144.                 for guess in i:
  145.                     self.currentposition=self.currentposition[:n]+guess+self.currentposition[n+1:]
  146.                     res=self.basiccrunchmanager()
  147.                     if res=="impossible":
  148.                         self.restorepos()
  149.                         self.impossible=False
  150.                         self.possibilities[n]=self.possibilities[n].replace(guess,"")
  151.                         if len(self.possibilities[n])==1:
  152.                             self.currentposition=self.currentposition[:n]+self.possibilities[n]+self.currentposition[n+1:]
  153.                         print "Advanced solver has made some progress. Continuing with basic solver"
  154.                         return
  155.                     elif res=="solved":
  156.                         print "A solution is found.  May not be unique."
  157.                         self.printresult()
  158.                         print "Continuing to check"
  159.                         self.restorepos()
  160.                     elif res=="not progressing":
  161.                         self.restorepos()
  162.         print "Advanced solver failed at level ",level
  163.         if level>3:
  164.             print "Advanced solver failed.  Probably insufficient information."
  165.             self.finish=True
  166.             return
  167.         self.advancedsolver(level+1)
  168.  
  169.  
  170.     def printresult(self):
  171.         """Prints result so far"""
  172.         for n,i in enumerate(self.currentposition):
  173.             if n%27==0: print "-------------------------------------------------------"
  174.             if n%3==0: print "| ",
  175.             print i,"  ",
  176.             if n%9==8: print "|"
  177.         print "-------------------------------------------------------"
  178.  
  179. def main():
  180.     puz="6x12xxx7xx8x6x5x2xxxxxxxxx14xx7xxxxxx9xxxxx1xxxx182xxxxxxxxx75xx7x3x9x4xx285x41x3"
  181.     #UNCOMMENT THESE LINES TO ENTER PUZZLE MANUALLY
  182.     #puz=""
  183.     #for i in range(9):
  184.     #    puz+=raw_input("Enter line "+str(i+1)+":")
  185.     sud=Sudoku(puz)
  186.     sud.solve()
  187.  
  188. if __name__=="__main__": main()
  189.  
  190.  
Newbie
  
Join Date: Nov 2009
Posts: 8
#4: 1 Week Ago

re: sudoku solver problem

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
Expand|Select|Wrap|Line Numbers
  1. import copy
  2.  
  3. def display(A):
  4.     if A:
  5.         for i in range(9):
  6.             for j in range(9):
  7.                 if type(A[i][j]) == type([]): print A[i][j][0],
  8.                 else: print A[i][j],
  9.             print
  10.         print
  11.     else: print A
  12.  
  13. def has_conflict(A):
  14.     for i in range(9):
  15.         for j in range(9):
  16.             for (x,y) in get_neighbors(i,j):
  17.                 if len(A[i][j])==1 and A[i][j]==A[x][y]: return True
  18.     return False
  19.  
  20. def get_neighbors(x,y):    # no idea how to get it or do it
  21.     return []
  22.  
  23. def update(A, i, j, value):  # no idea how to do it
  24.     return []
  25.  
  26. def solve(A):   # not sure if it's coorect
  27.     return []          
  28.  
  29.  
  30.  
  31.  
  32. A = []
  33. infile = open('puzzle1.txt', 'r')
  34.  
  35. for i in range(9):
  36.     A += [[]] 
  37.     for j in range(9):
  38.         num = int(infile.read(2))
  39.         if num: A[i] += [[num]]
  40.         else: A[i] += [[1,2,3,4,5,6,7,8,9]]
  41.  
  42. for i in range(9):
  43.     for j in range(9):
  44.         if len(A[i][j])==1: A = update(A, i,j, A[i][j][0])
  45.         if A==[]: break
  46.     if A==[]: break
  47.  
  48. if A<>[]: A = solve(A)
  49. display(A)
  50.  
  51.  
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
Reply

« previous question | next question »

Similar Python bytes

/bytes/development

/bytes/it

Forums
Visit our community forums for general discussions and latest on Bytes

Our staff and community areas have moved to bytes.com/forums/

/bytes/about

We are a network of experts and professionals in IT and software development that help one another with answers to tough questions and share insights. Get the best answers to your questions from over 226,510 network members.

dev questions:
algorithms | asp | asp.net | c/c++ | coldfusion | c# | flash | html/css | java | javascript |
mobile dev | .net | perl | php | python | ruby | software dev | vb.net | visual basic | xml
it questions:
access | apache | careers | db2 | iis | macosx | mysql | networking | oracle | postgresql | sql server | unix | windows

About Bytes | Copyright 1995-2009 BYTES. All rights Reserved