Cherrypy sudoku
Tilbage
Hent filen
Licens GPL
Implementation off sudoku in cherrypy Copyright Bauer Data.
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
#
import sys
sys.path.append("/opt/share/cherry")
import random
import cherrypy
import sets
"""
+-------+-------+-------+
| | | |
| 1 | 2 | 3 |
| | | |
+-------+-------+-------+
| | | |
| 4 | 5 | 6 |
| | | |
+-------+-------+-------+
| | | |
| 7 | 8 | 9 |
| | | |
+-------+-------+-------+
En maengde pr square
+-------+-------+-------+
| 1 2 3 | 4 5 6 | 7 8 9 | row 1 = [1,2,3,4,5,6,7,8,9] en maengde pr. raekke
| 5 2 9 | 8 4 1 | 3 6 7 | row 2 = [1,2,3,4,5,6,7,8,9]
| 4 1 7 | 6 3 9 | 2 5 8 | row 3 = [1,2,3,4,5,6,7,8,9]
+-------+-------+-------+
| 8 4 2 | 5 9 7 | 6 1 3 | row 4 = [1,2,3,4,5,6,7,8,9]
| 7 3 5 | 4 1 6 | 2 9 8 | row 5 = [1,2,3,4,5,6,7,8,9]
| 9 6 1 | 8 2 3 | 5 4 7 | row 6 = [1,2,3,4,5,6,7,8,9]
+-------+-------+-------+
| 3 6 7 | 2 8 9 | 5 1 4 | row 7 = [1,2,3,4,5,6,7,8,9]
| 4 8 5 | 6 1 7 | 2 3 9 | row 8 = [1,2,3,4,5,6,7,8,9]
| 2 9 1 | 5 4 3 | 8 6 7 | row 0 = [1,2,3,4,5,6,7,8,9]
+-------+-------+-------+
En maengde pr colonne
1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6 6
7 7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9
All squares must contain the ciffers 1 through 9
All rows may contain 1 throug 9
All columns may contain 1 throug 9
create a "def square():" who produce at legal square.
"""
sqfields=(
( 0, 1, 2, 9,10,11, 18,19,20 ),
( 3, 4, 5, 12,13,14, 21,22,23 ),
( 6, 7, 8, 15,16,17, 24,25,26 ),
(27,28,29, 36,37,38, 45,46,47 ),
(30,31,32, 39,40,41, 48,49,50 ),
(33,34,35, 42,43,44, 51,52,53 ),
(54,55,56, 63,64,65, 72,73,74 ),
(57,58,59, 66,67,68, 75,76,77 ),
(60,61,62, 69,70,71, 78,79,80 ),
)
class sudokusqr:
"""returns a random generated sudoku square"""
def __init__(self,size=9,safe=True,debug=True):
self.debug=debug
self.sqsize=int(pow(size, 0.5))
self.size=size
self.squ={}
self.row={}
self.safe=True
self.col={}
self.generate_sudoku()
self.f=open("sudoku_solutions_squares.txt","a")
def init_sets(self):
for i in range(self.size):
self.squ[i]=[1,2,3,4,5,6,7,8,9]
self.row[i]=[1,2,3,4,5,6,7,8,9]
self.col[i]=[1,2,3,4,5,6,7,8,9]
# square hold size*size fields.
self.fields={}
for i in range(self.size*self.size):
rowno=i/self.size
colno=i%self.size
squno=i/self.sqsize%self.sqsize+i/27*3
data=[self.row[rowno],self.col[colno],self.squ[squno]]
# print i,rowno,colno,squno,data
self.fields[i]=data
self.square=["0"]*self.size*self.size
def make_square(self,squareno):
fields=sqfields[squareno]
# print squareno,fields
rollback=True
rbcount=3
while rollback:
rollback=False
for field in fields:
# Fetch a random number from col and check if it is in squ and col.
# if so remove number from row, col and squ set
# and then place it in square[field]
row,col,squ=self.fields[field]
trail=0
while True:
trail+=1
number=random.choice(squ)
if number in row and number in col:
row.remove(number)
col.remove(number)
squ.remove(number)
self.square[field]=str(number)
break
# print "trail > 20"
# print row,col,squ, number
# self.Print()
if trail > 10:
break
if trail > 10:
rollback=True
# print "#"*40
# print "# No God",field
# print "#"*40
# print field, row,col,squ, number
# self.Print()
break
if rollback:
self.rollback(squareno)
rbcount-=1
if rbcount == 0:
return False
return True
def rollback(self,squareno):
fields=sqfields[squareno]
if self.debug: print "k%s" % squareno,
for field in fields:
number=int(self.square[field])
if self.debug : print number,
row,col,squ=self.fields[field]
if number:
self.square[field]=0
row.append(number)
col.append(number)
squ.append(number)
if self.debug : print
def generate_sudoku(self):
self.init_sets()
sqrnumbers =[0,4,8,3,6,7,1,2,5]
# print
i=0
while True:
if self.make_square(sqrnumbers[i]): i+=1
else:
i-=1
self.rollback(sqrnumbers[i])
if i >= len(sqrnumbers):
break
def save(self):
self.f.write("".join(self.square))
self.f.write("\n")
def prt_strg(self):
return "".join(self.square)
def Print(self):
if self.safe:
self.save()
return
for i in range(self.size*self.size):
if i % (self.size*3)==0:
print"\n+-------+-------+-------+\n|",
else:
if i % (self.size)==0:
print"\n|",
print "%s" % self.square[i],
if i%self.sqsize==2:
print"|",
print"\n+-------+-------+-------+"
class Sudoku(list):
"""read solution square 9*9 and eleminate 9*9 - 16 fields and write i on stdout"""
def __init__(self, strg):
list.__init__(self, [d[i*9:(i+1)*9] for i in range(9) for d in [[int(e) for e in strg ]]])
def __repr__(self):
return "\n".join([" ".join([str(c) for c in r]) for r in self])
def prt_strg(self):
return "".join(["".join([str(c) for c in r]) for r in self])
def prt_html(self):
strg=self.prt_strg()
htm=['<html><body><h1>Free Sudoku<h2><form action="checkplate" method="POST"><table border="1" cellpadding="4" cellspacing="6">']
for sqr in range(9):
if sqr % 3 ==0:
htm.append('<tr>')
sq='<td><table border="1" cellspacing="2"><tr> %s %s %s</tr><tr>%s %s %s</tr><tr>%s %s %s</tr></table></td>' % \
tuple(['<td width=25> '+strg[field]+' </td>' for field in sqfields[sqr]])
htm.append(sq.replace(' 0 ','<input type=text name="%s_%s" value="" size=1 maxlength=2> </input>' % (sqr,field)))
if sqr % 3 ==2:
htm.append('</tr>')
htm.append('</table>')
htm.append('<table><td valign="top">')
# htm.append('<input type="submit" value="Check">')
htm.append('<input type="reset"></form></td>')
htm.append('<td valign="top"><form method="POST" action="index"><input type=submit value="Ny plade"></form>')
htm.append('</td></table>')
htm.append(self.footer())
htm.append("""<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "UA-541320-6";
urchinTracker();
</script>""")
htm.append('</body></html>')
return '\n'.join(htm)
def footer(self):
return """
<p><a href="http://www.databassen.dk:8090/bauerdata/diverse-filer-til-download-mm/cherrypy-sudoku">Kildetekst til dette program</a>
</p>
<span>Denne hjemmeside er sponseret af <a href="http://www.bauerdata.dk">Bauer Data.<br></a></span>
<script type="text/javascript"><!--
google_ad_client = "pub-6987251328342779";
google_ad_width = 728;
google_ad_height = 90;
google_ad_format = "728x90_as";
google_ad_type = "text_image";
google_ad_channel ="";
google_color_border = "DDB7BA";
google_color_bg = "FFF5F6";
google_color_link = "0000CC";
google_color_url = "008000";
google_color_text = "6F6F6F";
//--></script>
<script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js">
</script>
"""
def save(self,filename="sudoku_plates.txt"):
f=open(filename,"a")
f.write("%s\n"%self.prt_strg())
f.close()
def grp(self, i, j):
return sets.Set(
( self[i][:]
+ [self[k][j] for k in range(9)]
+ [self[k][l] for k in range(i/3*3, i/3*3+3) for l in range(j/3*3, j/3*3+3)]
)
)
def next(self, i, j): return (i*9+j+1)/9, (i*9+j+1)%9
def loop(self, i, j):
if i<9: yield i, j
while True:
i, j = self.next(i, j)
if i>=9: break
yield i, j
def solve(s, k=0, l=0):
"""Backtracking solver"""
for i, j in s.loop(k, l):
if s[i][j] is 0:
for val in sets.Set(range(1, 10)).difference(s.grp(i, j)):
s[i][j]=val
if solve(s,*s.next(i, j)): return s
s[i][j]=0
return
return s
def get_random_pattern(n=9*9,p=20):
sqsets={}
for i in range(9):
sqsets[i]=list(sqfields[i])
# create solutions containing at least all 9 squares
# first get a field from each square
comb=[]
for i in range(9):
field=random.choice(sqsets[i])
sqsets[i].remove(field)
comb.append(field)
# then get last p-9 fields random
antal=0
iset=range(9)
# put square 4 raise the possibility to get more squares there
iset.append(4)
while antal <= p-9:
antal+=1
i=random.choice(iset)
field=random.choice(sqsets[i])
sqsets[i].remove(field)
comb.append(field)
return comb
def produce(square_solution):
"""return a resolution as a class Sudoku"""
# print square_solution
size=9
rlist=["0"]*size*size
fset=[x for x in range(81)]
for field in get_random_pattern(p=27):
rlist[field]=square_solution[field]
fset.remove(field)
orig_square=Sudoku(square_solution)
# print Sudoku("".join(rlist)).prt_strg()
solution=""
while solution != orig_square:
fnum=random.choice(fset)
fset.remove(fnum)
rlist[fnum]=str(orig_square[fnum/9][fnum%9])
# print Sudoku("".join(rlist)).prt_strg()
solution=solve(Sudoku("".join(rlist)))
if solution:
# print "found"
break
else:
# print "not found"
return
# print '<a>size=',81-rlist.count('0'),'</a>'
return Sudoku("".join(rlist))
def main_solver(filename="sudoku_solutions_squares.txt"):
f=open(filename,"r")
for square_solution in f.xreadlines():
# test
# print square_solution
produce(square_solution)
class SudokuPage:
def initial_square(self,safe=True,debug=False):
kvadrat=sudokusqr(safe=safe,debug=debug)
# print kvadrat.prt_strg()
self.solution=produce(kvadrat.prt_strg())
# print solution
self.solution.save()
return self.solution.prt_html()
def index(self):
# make new sudoku
return self.initial_square()
index.exposed = True
def set_parameters(self,pargs):
args=[(x,pargs[x]) for x in pargs.keys()]
self.parameters={}
for key,value in args:
self.parameters[key]=value
def checkplate(self, komando = None,**kargs):
self.set_parameters(kargs)
return self.solution.prt_html()
checkplate.exposed = True
cherrypy.root = SudokuPage()
if __name__ == '__main__':
cherrypy.config.update(file = 'sudoku.conf')
cherrypy.server.start()
Forskelligt nyt fra Open Source miljøet.