在这里详述 源码库/sudoku.py。

{{{#!python
# -*- coding: utf8 -*-
"""
    MoinMoin - sudoku

    This parser is used to show and resolve sudoku puzzles
    Improving is encouraged, but please send me a copy
    Email: znight@tom.com
    
    @copyright: 2009 by znight@tom.com
    @license: GNU GPL
"""

import random
from MoinMoin import wikiutil

Dependiencies=[]
sudoku_id=0

def sudoku_settings(gen=28):
  return locals()

class SudStack:
  _data=[]
  _cand=[]
  
  def __init__(self):
    self._data=[]
    self._cand=[]
  
  def push(self,x,y):
    self._data.append(x[:])
    self._cand.append(y[:])

  def pop(self):
    if len(self._data)>0:
      return self._data.pop(),self._cand.pop()
    return [],[]
  def clear(self):
    self._data=[]
    self._cand=[]

def pos2seq(x,y):
  return x+y*9
def blk2seq(b,s):
  return (b//3*3+s//3)*9+b%3*3+s%3
def seq2pos(p):
  return p%9,p//9
def seq2blk(p):
  return p%9//3+p//9//3*3,p%9%3+p//9%3*3

def remove(s,c):
  r=s
  s&=~c
  return 0 if r==s else 1,s

def count1(s):
  c=0
  for i in range (0,9):
    if s&1: c+=1
    s>>=1
  return c

def subset(s,c):
  return (s&c)==c

def find1(s,k):
  c=0
  for i in range(0,9):
    if s&1: c+=1
    if c>k: break
    s>>=1
  return i

def getcand(dt,cand):
  for i in range(0,81):
    if dt[i]!=0:
      cand[i]=(1<<(dt[i]-1))
      continue
    cc,cl=seq2pos(i)
    cb,bs=seq2blk(i)
    for j in range(0,9):
      d=dt[pos2seq(j,cl)]
      if d!=0: cand[i]&=~(1<<(d-1))
      d=dt[pos2seq(cc,j)]
      if d!=0: cand[i]&=~(1<<(d-1))
      d=dt[blk2seq(cb,j)]
      if d!=0: cand[i]&=~(1<<(d-1))
  cx=1
  while cx>0:
    cx=0
    for i in range(0,81):
      cs=count1(cand[i])
      if cs<2: continue
      cc,cl=seq2pos(i)
      cb,bs=seq2blk(i)
      k=0
      for k in range(0,9):
        if not (cand[i]&(1<<k)): continue;
        for j in range(0,9):
          if j!=cc and (cand[pos2seq(j,cl)]&(1<<k)): break
        else: j=9
        if j<9:
          for j in range(0,9):
            if j!=cl and (cand[pos2seq(cc,j)]&(1<<k)): break
          else: j=9
          if j<9:
            for j in range(0,9):
              if blk2seq(cb,j)!=i and (cand[blk2seq(cb,j)]&(1<<k)): break
            else: j=9
        if j>=9:
          cand[i]=(1<<k)
          cx+=1
          break
    """some other code will insert here"""
    
    for i in range(0,81):
      cc,cl=seq2pos(i)
      cb,bs=seq2blk(i)
      c=cand[i]
      cs=count1(cand[i])
      if cs==2:
        for j in range(0,9):
          if j!=cc and cand[pos2seq(j,cl)]==c: break
        else: j=9
        if j<9:
          for k in range(0,9):
            if k!=cc and k!=j:
              xx,cand[pos2seq(k,cl)]=remove(cand[pos2seq(k,cl)],c)
              cx+=xx
        for j in range(0,9):
          if j!=cl and cand[pos2seq(cc,j)]==c: break
        else: j=9
        if j<9:
          for k in range(0,9):
            if k!=cl and k!=j:
              xx,cand[pos2seq(cc,k)]=remove(cand[pos2seq(cc,k)],c)
              cx+=xx
        for j in range(0,9):
          if blk2seq(cb,j)!=i and cand[blk2seq(cb,j)]==c: break
        else: j=9
        if j<9:
          for k in range(0,9):
            if k!=j and k!=bs:
              xx,cand[blk2seq(cb,k)]=remove(cand[blk2seq(cb,k)],c)
              cx+=xx

      elif cs==3:
        j1=-1
        j2=-1
        for j in range(0,9):
          if j!=cc and subset(c,cand[pos2seq(j,cl)]): j1=j; break
        j+=1
        while j<9:
          if j!=cc and subset(c,cand[pos2seq(j,cl)]): j2=j; break
          j+=1
        if j1>=0 and j2>=0:
          for k in range(0,9):
            if k!=cc and k!=j1 and k!=j2:
              xx,cand[pos2seq(k,cl)]=remove(cand[pos2seq(k,cl)],c)
              cx+=xx

        j1=-1
        j2=-1
        for j in range(0,9):
          if j!=cl and subset(c,cand[pos2seq(cc,j)]): j1=j; break
        j+=1
        while j<9:
          if j!=cl and subset(c,cand[pos2seq(cc,j)]): j2=j; break
          j+=1
        if j1>=0 and j2>=0:
          for k in range(0,9):
            if k!=cl and k!=j1 and k!=j2:
              xx,cand[pos2seq(cc,k)]=remove(cand[pos2seq(cc,k)],c)
              cx+=xx

        j1=-1
        j2=-1
        for j in range(0,9):
          if blk2seq(cb,j)!=i and subset(c,cand[blk2seq(cb,j)]): j1=j; break
        j+=1
        while j<9:
          if blk2seq(cb,j)!=i and subset(c,cand[blk2seq(cb,j)]): j2=j; break
          j+=1
        if j1>=0 and j2>=0:
          for k in range(0,9):
            if k!=bs and k!=j1 and k!=j2:
              xx,cand[blk2seq(cb,k)]=remove(cand[blk2seq(cb,k)],c)
              cx+=xx
 

def check(dt,cd):
  #print """check""",cd
  x=0
  for i in range(0,81):
    if dt[i]==0:
      x=1
      continue
    cc,cl=seq2pos(i)
    cb,bs=seq2blk(i)
    for j in range(0,9):
      v=pos2seq(j,cl)
      d=dt[v]
      if v!=i and d==dt[i]: break
      v=pos2seq(cc,j)
      d=dt[v]
      if v!=i and d==dt[i]: break
      v=blk2seq(cb,j)
      d=dt[v]
      if v!=i and d==dt[i]: break
    else: j=9
    if j<9: break
  else: i=81
  #print "check result",i>=81,x
  if i>=81:
    if x: return 2
    #print "test ok"
    return 0
  return 1

def resolve(tab,gen=False):
  ss=SudStack()
  ss.clear()
  count_back=0
  count_step=0
  count_test=0
  tcc=0
  rtab=tab
  dt=[]
  cd=[]
  for i in range(0,81):
    dt.append(ord(tab[i])-48)
    cd.append((1<<9)-1)
  getcand(dt,cd)
  while 1:
    cc=1
    mv=-1
    mp=-1
    i=0
    while cc>0:
      cc=0
      mv=-1
      mp=-1
      for i in range(0,81):
        l=count1(cd[i])
        if l==0: break
        if l==1 and dt[i]==0:
          dt[i]=find1(cd[i],0)+1
          cc+=1
        elif l>=2 and (mv==-1 or l<mv):
          mv=l
          mp=i
      else: i=81
      if i<81: break
      getcand(dt,cd)
    if i<81 or check(dt,cd)==1:
      if tcc<=0: count_back+=1
      dt,cd=ss.pop()
      if len(dt)==0: break
    else:
      count_step+=1
      if (count_step>10000): """may break"""
      if mp>=0:
        cs=count1(cd[mp])
        if cs>1: count_test+=1
        sk=0
        if gen: sk=random.randint(0,cs-1)
        c=find1(cd[mp],sk)
        cd[mp]&=~(1<<c)
        ss.push(dt,cd)
        dt[mp]=c+1
        getcand(dt,cd)
      elif check(dt,cd)==0:
        tcc+=1
        #print "ssss...."
        if tcc<=1:
          rtab='';
          for i in range(0,81):
            """success"""
            rtab+=chr(dt[i]+48)
        if gen or tcc>1: break
        if tcc<=0: count_back+=1
        dt,cd=ss.pop()
        if len(dt)==0: break
      else:
        if tcc<=0: count_back+=1
        dt,cd=ss.pop()
        if len(dt)==0: break
  if tcc<=0:
    if count_step>10000: """more than 10000 steps"""
    else: """cann't resolve"""
  elif tcc==1: """resolved"""
  elif tcc>1: """more than one results"""
  else: """...results"""
  return tcc,rtab              
  
def genquest(nf):
  nd=81
  tt=[0]*81
  while nd>nf:
    xcd='0'*81
    tcc,rtab=resolve(xcd,True)
    xcd=rtab
    for i in range(0,81):
      tt[i]=i
    for i in range(0,81-1):
      v=random.randint(0,80-i)
      t=tt[v]
      tt[v]=tt[81-i-1]
      tt[81-i-1]=t
    nd=81
    for i in range(0,81):
      cc=xcd
      v=tt[i]
      cc=xcd[0:v]+'0'+xcd[v+1:]
      tcc,rtab=resolve(cc)
      if tcc==1:
        xcd=xcd[0:v]+'0'+xcd[v+1:]
        nd-=1
        if (nd<=nf):
          break
  return xcd 

class Parser:
  extensions='sud'
  Dependencies=[]
  
  def __init__(self,raw,request,**kw):
    self.raw=raw
    self.request=request
    args=kw.get('format_args','')
    try:
      settings=wikiutil.invoke_extension_function(request,sudoku_settings,args)
      for key,value in settings.items():
        setattr(self,key,value)
    except ValueError,err:
      msg=u"sudoku: %s"%err.args[0]
      setattr(self,"gen",0)

  def render(self,formatter):

    global sudoku_id
    sudoku_id+=1
    #text=(formatter.preformatted(1))
    #if not self.raw is str: return 'xxx'
    text=''
    k=0
    tab=''

    self.gen=0
    if self.gen==0:
      for i in range(0,9):
        for j in range(0,9):
          while k<len(self.raw) and self.raw[k].isspace(): k=k+1
          c='0'
          if k<len(self.raw): c=self.raw[k]
          if c<'1' or c>'9': c='0'
          tab+=c
          k+=1
    else:
      tab=genquest(self.gen)

    tcc,rtab=resolve(tab)
    #text+=rtab+"<br>"
    #text+=tab+"<br>"

    msgshowanswer=self.request.getText("Show Answer");
    msghideanswer=self.request.getText("Hide Answer");

    text+="""<script langauge=javascript>
<!--
  var rtab"""+str(sudoku_id)+"""='"""+rtab+"""';
  var tab"""+str(sudoku_id)+"""='"""+tab+"""';
  var showresolve"""+str(sudoku_id)+"""=false;
  function show_resolve"""+str(sudoku_id)+"""()
  {
    var showmsg;
    var f=document.getElementById('sudoku"""+str(sudoku_id)+"""')
    var t=f.getElementsByTagName('td');
    var i;
    showresolve"""+str(sudoku_id)+"""=!showresolve"""+str(sudoku_id)+""";
    if (showresolve"""+str(sudoku_id)+""")
      showmsg='"""+msghideanswer+"""';
    else
      showmsg='"""+msgshowanswer+"""';
    var sh=document.getElementById('showhide"""+str(sudoku_id)+"""')
    sh.innerText=showmsg;
 
    for(i=0;i<81;i++)
    {
      var c;
      if (showresolve"""+str(sudoku_id)+""")
        c=rtab"""+str(sudoku_id)+""".substr(i,1);
      else
        c=tab"""+str(sudoku_id)+""".substr(i,1);
      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; ">';
      t[i].innerHTML=c;
    }
  }
  //--></script>"""
    text+="<a href='javascript:show_resolve"+str(sudoku_id)+"()' id='showhide"+str(sudoku_id)+"'>"+msgshowanswer+"</a>"
    text+="<table id=sudoku"+str(sudoku_id)+" style=\"border:2pt solid black;\">"
    for i in range(0,9):
      text+="<tr>"
      for j in range(0,9):
        k=pos2seq(j,i)
        c=tab[k]
        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;">'
        text+="<td style=\"width:12px;height:20px;"
        if (tab[k]==rtab[k]):
          text+="font-weight:bold;"
        else:
          text+="color:gray;"
        #text+="border-left:1pt solid lightblue;";
        #text+="border-top:1pt solid light blye;";
        if j%3==2 and j!=8: text+="border-right: 2pt solid lightblue;"
        else: text+="border-right:1pt solid lightblue;"
        if i%3==2 and i!=8: text+="border-bottom: 2pt solid lightblue;"
        else: text+="border-bottom:1pt solid lightblue;"
        text+="margin:0pt;padding:0pt;padding-top:1pt;padding-bottom:1pt;width:22pt;height:20pt;\" valign=middle align=center>"+c+"</td>"
      text+="</tr>"
    text+="</table>"
    #self.request.write(formatter.preformatted(0))
    return text

  def format(self,formatter):
    self.request.write(self.render(formatter))

"""
class x:
  y=1  
  def write(self,str):
    print str
b=x()
a=Parser("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx",b)
a.format(b)   
"""
}}}