1 # -*- coding: utf8 -*-
   2 """
   3     MoinMoin - sudoku
   4 
   5     This parser is used to show and resolve sudoku puzzles
   6     Improving is encouraged, but please send me a copy
   7     Email: znight@tom.com
   8     
   9     @copyright: 2009 by znight@tom.com
  10     @license: GNU GPL
  11 """
  12 
  13 import random
  14 from MoinMoin import wikiutil
  15 
  16 Dependiencies=[]
  17 sudoku_id=0
  18 
  19 def sudoku_settings(gen=28):
  20   return locals()
  21 
  22 class SudStack:
  23   _data=[]
  24   _cand=[]
  25   
  26   def __init__(self):
  27     self._data=[]
  28     self._cand=[]
  29   
  30   def push(self,x,y):
  31     self._data.append(x[:])
  32     self._cand.append(y[:])
  33 
  34   def pop(self):
  35     if len(self._data)>0:
  36       return self._data.pop(),self._cand.pop()
  37     return [],[]
  38   def clear(self):
  39     self._data=[]
  40     self._cand=[]
  41 
  42 def pos2seq(x,y):
  43   return x+y*9
  44 def blk2seq(b,s):
  45   return (b//3*3+s//3)*9+b%3*3+s%3
  46 def seq2pos(p):
  47   return p%9,p//9
  48 def seq2blk(p):
  49   return p%9//3+p//9//3*3,p%9%3+p//9%3*3
  50 
  51 def remove(s,c):
  52   r=s
  53   s&=~c
  54   return 0 if r==s else 1,s
  55 
  56 def count1(s):
  57   c=0
  58   for i in range (0,9):
  59     if s&1: c+=1
  60     s>>=1
  61   return c
  62 
  63 def subset(s,c):
  64   return (s&c)==c
  65 
  66 def find1(s,k):
  67   c=0
  68   for i in range(0,9):
  69     if s&1: c+=1
  70     if c>k: break
  71     s>>=1
  72   return i
  73 
  74 def getcand(dt,cand):
  75   for i in range(0,81):
  76     if dt[i]!=0:
  77       cand[i]=(1<<(dt[i]-1))
  78       continue
  79     cc,cl=seq2pos(i)
  80     cb,bs=seq2blk(i)
  81     for j in range(0,9):
  82       d=dt[pos2seq(j,cl)]
  83       if d!=0: cand[i]&=~(1<<(d-1))
  84       d=dt[pos2seq(cc,j)]
  85       if d!=0: cand[i]&=~(1<<(d-1))
  86       d=dt[blk2seq(cb,j)]
  87       if d!=0: cand[i]&=~(1<<(d-1))
  88   cx=1
  89   while cx>0:
  90     cx=0
  91     for i in range(0,81):
  92       cs=count1(cand[i])
  93       if cs<2: continue
  94       cc,cl=seq2pos(i)
  95       cb,bs=seq2blk(i)
  96       k=0
  97       for k in range(0,9):
  98         if not (cand[i]&(1<<k)): continue;
  99         for j in range(0,9):
 100           if j!=cc and (cand[pos2seq(j,cl)]&(1<<k)): break
 101         else: j=9
 102         if j<9:
 103           for j in range(0,9):
 104             if j!=cl and (cand[pos2seq(cc,j)]&(1<<k)): break
 105           else: j=9
 106           if j<9:
 107             for j in range(0,9):
 108               if blk2seq(cb,j)!=i and (cand[blk2seq(cb,j)]&(1<<k)): break
 109             else: j=9
 110         if j>=9:
 111           cand[i]=(1<<k)
 112           cx+=1
 113           break
 114     """some other code will insert here"""
 115     
 116     for i in range(0,81):
 117       cc,cl=seq2pos(i)
 118       cb,bs=seq2blk(i)
 119       c=cand[i]
 120       cs=count1(cand[i])
 121       if cs==2:
 122         for j in range(0,9):
 123           if j!=cc and cand[pos2seq(j,cl)]==c: break
 124         else: j=9
 125         if j<9:
 126           for k in range(0,9):
 127             if k!=cc and k!=j:
 128               xx,cand[pos2seq(k,cl)]=remove(cand[pos2seq(k,cl)],c)
 129               cx+=xx
 130         for j in range(0,9):
 131           if j!=cl and cand[pos2seq(cc,j)]==c: break
 132         else: j=9
 133         if j<9:
 134           for k in range(0,9):
 135             if k!=cl and k!=j:
 136               xx,cand[pos2seq(cc,k)]=remove(cand[pos2seq(cc,k)],c)
 137               cx+=xx
 138         for j in range(0,9):
 139           if blk2seq(cb,j)!=i and cand[blk2seq(cb,j)]==c: break
 140         else: j=9
 141         if j<9:
 142           for k in range(0,9):
 143             if k!=j and k!=bs:
 144               xx,cand[blk2seq(cb,k)]=remove(cand[blk2seq(cb,k)],c)
 145               cx+=xx
 146 
 147       elif cs==3:
 148         j1=-1
 149         j2=-1
 150         for j in range(0,9):
 151           if j!=cc and subset(c,cand[pos2seq(j,cl)]): j1=j; break
 152         j+=1
 153         while j<9:
 154           if j!=cc and subset(c,cand[pos2seq(j,cl)]): j2=j; break
 155           j+=1
 156         if j1>=0 and j2>=0:
 157           for k in range(0,9):
 158             if k!=cc and k!=j1 and k!=j2:
 159               xx,cand[pos2seq(k,cl)]=remove(cand[pos2seq(k,cl)],c)
 160               cx+=xx
 161 
 162         j1=-1
 163         j2=-1
 164         for j in range(0,9):
 165           if j!=cl and subset(c,cand[pos2seq(cc,j)]): j1=j; break
 166         j+=1
 167         while j<9:
 168           if j!=cl and subset(c,cand[pos2seq(cc,j)]): j2=j; break
 169           j+=1
 170         if j1>=0 and j2>=0:
 171           for k in range(0,9):
 172             if k!=cl and k!=j1 and k!=j2:
 173               xx,cand[pos2seq(cc,k)]=remove(cand[pos2seq(cc,k)],c)
 174               cx+=xx
 175 
 176         j1=-1
 177         j2=-1
 178         for j in range(0,9):
 179           if blk2seq(cb,j)!=i and subset(c,cand[blk2seq(cb,j)]): j1=j; break
 180         j+=1
 181         while j<9:
 182           if blk2seq(cb,j)!=i and subset(c,cand[blk2seq(cb,j)]): j2=j; break
 183           j+=1
 184         if j1>=0 and j2>=0:
 185           for k in range(0,9):
 186             if k!=bs and k!=j1 and k!=j2:
 187               xx,cand[blk2seq(cb,k)]=remove(cand[blk2seq(cb,k)],c)
 188               cx+=xx
 189  
 190 
 191 def check(dt,cd):
 192   #print """check""",cd
 193   x=0
 194   for i in range(0,81):
 195     if dt[i]==0:
 196       x=1
 197       continue
 198     cc,cl=seq2pos(i)
 199     cb,bs=seq2blk(i)
 200     for j in range(0,9):
 201       v=pos2seq(j,cl)
 202       d=dt[v]
 203       if v!=i and d==dt[i]: break
 204       v=pos2seq(cc,j)
 205       d=dt[v]
 206       if v!=i and d==dt[i]: break
 207       v=blk2seq(cb,j)
 208       d=dt[v]
 209       if v!=i and d==dt[i]: break
 210     else: j=9
 211     if j<9: break
 212   else: i=81
 213   #print "check result",i>=81,x
 214   if i>=81:
 215     if x: return 2
 216     #print "test ok"
 217     return 0
 218   return 1
 219 
 220 def resolve(tab,gen=False):
 221   ss=SudStack()
 222   ss.clear()
 223   count_back=0
 224   count_step=0
 225   count_test=0
 226   tcc=0
 227   rtab=tab
 228   dt=[]
 229   cd=[]
 230   for i in range(0,81):
 231     dt.append(ord(tab[i])-48)
 232     cd.append((1<<9)-1)
 233   getcand(dt,cd)
 234   while 1:
 235     cc=1
 236     mv=-1
 237     mp=-1
 238     i=0
 239     while cc>0:
 240       cc=0
 241       mv=-1
 242       mp=-1
 243       for i in range(0,81):
 244         l=count1(cd[i])
 245         if l==0: break
 246         if l==1 and dt[i]==0:
 247           dt[i]=find1(cd[i],0)+1
 248           cc+=1
 249         elif l>=2 and (mv==-1 or l<mv):
 250           mv=l
 251           mp=i
 252       else: i=81
 253       if i<81: break
 254       getcand(dt,cd)
 255     if i<81 or check(dt,cd)==1:
 256       if tcc<=0: count_back+=1
 257       dt,cd=ss.pop()
 258       if len(dt)==0: break
 259     else:
 260       count_step+=1
 261       if (count_step>10000): """may break"""
 262       if mp>=0:
 263         cs=count1(cd[mp])
 264         if cs>1: count_test+=1
 265         sk=0
 266         if gen: sk=random.randint(0,cs-1)
 267         c=find1(cd[mp],sk)
 268         cd[mp]&=~(1<<c)
 269         ss.push(dt,cd)
 270         dt[mp]=c+1
 271         getcand(dt,cd)
 272       elif check(dt,cd)==0:
 273         tcc+=1
 274         #print "ssss...."
 275         if tcc<=1:
 276           rtab='';
 277           for i in range(0,81):
 278             """success"""
 279             rtab+=chr(dt[i]+48)
 280         if gen or tcc>1: break
 281         if tcc<=0: count_back+=1
 282         dt,cd=ss.pop()
 283         if len(dt)==0: break
 284       else:
 285         if tcc<=0: count_back+=1
 286         dt,cd=ss.pop()
 287         if len(dt)==0: break
 288   if tcc<=0:
 289     if count_step>10000: """more than 10000 steps"""
 290     else: """cann't resolve"""
 291   elif tcc==1: """resolved"""
 292   elif tcc>1: """more than one results"""
 293   else: """...results"""
 294   return tcc,rtab              
 295   
 296 def genquest(nf):
 297   nd=81
 298   tt=[0]*81
 299   while nd>nf:
 300     xcd='0'*81
 301     tcc,rtab=resolve(xcd,True)
 302     xcd=rtab
 303     for i in range(0,81):
 304       tt[i]=i
 305     for i in range(0,81-1):
 306       v=random.randint(0,80-i)
 307       t=tt[v]
 308       tt[v]=tt[81-i-1]
 309       tt[81-i-1]=t
 310     nd=81
 311     for i in range(0,81):
 312       cc=xcd
 313       v=tt[i]
 314       cc=xcd[0:v]+'0'+xcd[v+1:]
 315       tcc,rtab=resolve(cc)
 316       if tcc==1:
 317         xcd=xcd[0:v]+'0'+xcd[v+1:]
 318         nd-=1
 319         if (nd<=nf):
 320           break
 321   return xcd 
 322 
 323 class Parser:
 324   extensions='sud'
 325   Dependencies=[]
 326   
 327   def __init__(self,raw,request,**kw):
 328     self.raw=raw
 329     self.request=request
 330     args=kw.get('format_args','')
 331     try:
 332       settings=wikiutil.invoke_extension_function(request,sudoku_settings,args)
 333       for key,value in settings.items():
 334         setattr(self,key,value)
 335     except ValueError,err:
 336       msg=u"sudoku: %s"%err.args[0]
 337       setattr(self,"gen",0)
 338 
 339   def render(self,formatter):
 340 
 341     global sudoku_id
 342     sudoku_id+=1
 343     #text=(formatter.preformatted(1))
 344     #if not self.raw is str: return 'xxx'
 345     text=''
 346     k=0
 347     tab=''
 348 
 349     self.gen=0
 350     if self.gen==0:
 351       for i in range(0,9):
 352         for j in range(0,9):
 353           while k<len(self.raw) and self.raw[k].isspace(): k=k+1
 354           c='0'
 355           if k<len(self.raw): c=self.raw[k]
 356           if c<'1' or c>'9': c='0'
 357           tab+=c
 358           k+=1
 359     else:
 360       tab=genquest(self.gen)
 361 
 362     tcc,rtab=resolve(tab)
 363     #text+=rtab+"<br>"
 364     #text+=tab+"<br>"
 365 
 366     msgshowanswer=self.request.getText("Show Answer");
 367     msghideanswer=self.request.getText("Hide Answer");
 368 
 369     text+="""<script langauge=javascript>
 370 <!--
 371   var rtab"""+str(sudoku_id)+"""='"""+rtab+"""';
 372   var tab"""+str(sudoku_id)+"""='"""+tab+"""';
 373   var showresolve"""+str(sudoku_id)+"""=false;
 374   function show_resolve"""+str(sudoku_id)+"""()
 375   {
 376     var showmsg;
 377     var f=document.getElementById('sudoku"""+str(sudoku_id)+"""')
 378     var t=f.getElementsByTagName('td');
 379     var i;
 380     showresolve"""+str(sudoku_id)+"""=!showresolve"""+str(sudoku_id)+""";
 381     if (showresolve"""+str(sudoku_id)+""")
 382       showmsg='"""+msghideanswer+"""';
 383     else
 384       showmsg='"""+msgshowanswer+"""';
 385     var sh=document.getElementById('showhide"""+str(sudoku_id)+"""')
 386     sh.innerText=showmsg;
 387  
 388     for(i=0;i<81;i++)
 389     {
 390       var c;
 391       if (showresolve"""+str(sudoku_id)+""")
 392         c=rtab"""+str(sudoku_id)+""".substr(i,1);
 393       else
 394         c=tab"""+str(sudoku_id)+""".substr(i,1);
 395       if (c=='0') c='<INPUT SIZE=2 AUTOCOMPLETE=off NAME=n"""+str(sudoku_id)+'_'+str(i)+' MAXLENGTH=1 ID=d'+str(sudoku_id)+'_'+str(i)+""" style="border:0pt solid; COLOR: #7777dd; FONT-SIZE: 12pt;TEXT-ALIGN: center;MARGIN: 0pt; WIDTH: 20pt; ">';
 396       t[i].innerHTML=c;
 397     }
 398   }
 399   //--></script>"""
 400     text+="<a href='javascript:show_resolve"+str(sudoku_id)+"()' id='showhide"+str(sudoku_id)+"'>"+msgshowanswer+"</a>"
 401     text+="<table id=sudoku"+str(sudoku_id)+" style=\"border:2pt solid black;\">"
 402     for i in range(0,9):
 403       text+="<tr>"
 404       for j in range(0,9):
 405         k=pos2seq(j,i)
 406         c=tab[k]
 407         if c<'1' or c>'9': c='<INPUT SIZE=2 AUTOCOMPLETE=off NAME=n'+str(sudoku_id)+'_'+str(i*9+j)+' MAXLENGTH=1 ID=d'+str(sudoku_id)+'_'+str(i*9+j)+' style="border:0pt solid; COLOR: #7777dd; FONT-SIZE: 12pt;TEXT-ALIGN: center;vertical-align:middle;MARGIN: 0pt; WIDTH: 20pt;">'
 408         text+="<td style=\"width:12px;height:20px;"
 409         if (tab[k]==rtab[k]):
 410           text+="font-weight:bold;"
 411         else:
 412           text+="color:gray;"
 413         #text+="border-left:1pt solid lightblue;";
 414         #text+="border-top:1pt solid light blye;";
 415         if j%3==2 and j!=8: text+="border-right: 2pt solid lightblue;"
 416         else: text+="border-right:1pt solid lightblue;"
 417         if i%3==2 and i!=8: text+="border-bottom: 2pt solid lightblue;"
 418         else: text+="border-bottom:1pt solid lightblue;"
 419         text+="margin:0pt;padding:0pt;padding-top:1pt;padding-bottom:1pt;width:22pt;height:20pt;\" valign=middle align=center>"+c+"</td>"
 420       text+="</tr>"
 421     text+="</table>"
 422     #self.request.write(formatter.preformatted(0))
 423     return text
 424 
 425   def format(self,formatter):
 426     self.request.write(self.render(formatter))
 427 
 428 """
 429 class x:
 430   y=1  
 431   def write(self,str):
 432     print str
 433 b=x()
 434 a=Parser("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx",b)
 435 a.format(b)   
 436 """