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 - 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
3 3367
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.
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()
-
-
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
Sign in to post your reply or Sign up for a free account.
Similar topics
by: ago |
last post by:
Inspired by some recent readings on LinuxJournal and an ASPN recipe, I
decided to revamp my old python hack... The new code is a combination
of (2) reduction methods and brute force and it is quite...
|
by: engsolnorm |
last post by:
A co-worker and I want to increase our knowledge of Python. I have a tiny bit of exposure to python. He has none, but
has wide experience with C, C++, NET, C#, etc. We agreed we'd do a Sudoku...
|
by: kalinga1234 |
last post by:
hy guys
i am having a problem with my sudoku program which i coded using c++.;
currently in my program if a duplicate number exist in either
row/column/block i would make the particualr square...
|
by: avinash1990 |
last post by:
hi
can you tell me how to make a sudoku solver program ..i really need it for my project
|
by: JosAH |
last post by:
Greetings,
a couple of years ago a large part of the world went totally mad. Not because
of global climate changes, not because of terrible wars that were started in
the Middle East, nor because...
|
by: blux |
last post by:
I am working on a function to check the validity of a sudoku puzzle.
It must check the 9x9 matrix to make sure it follows the rules and is
a valid sudoku puzzle.
this is what I have come up with...
|
by: Thekid |
last post by:
Hi, I found this sudoku solver online and it works good but I was wondering how I could get the answer that's in matrix form, to also print out in a single comma-delimited line, instead of 9 rows of...
|
by: Boon |
last post by:
Hello group,
I've been toying with a simple sudoku solver. I meant for the code to
be short and easy to understand. I figured "brute force is simple" --
who needs finesse, when you've got...
|
by: jkmyoung |
last post by:
Does anyone have some super, super hard Sudoku puzzles?
Back in February this year, I had enough time to finally program a Sudoku solver in Java. Right now, I'm looking for solvable puzzles, but...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |