прикреплённый файл:queens.py к странице LecturesVMSH/2012-03-21

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Расставить на стандартной N²-клеточной шахматной доске N ферзей так, чтобы ни один из них не находился под боем другого. Посчитать количество расстановок.
   5 '''
   6 
   7 import sys
   8 
   9 def dumb(N):
  10     '«Тупой» метод: расставляем как попало, потом проверяем'
  11     global Count
  12 
  13     def check2((x1,y1), (x2,y2)):
  14         global Actions
  15         Actions+=1
  16         return x1!=x2 and y1<y2 and x1+y1!=x2+y2 and x1-y1!=x2-y2
  17 
  18     def check():
  19         for k in xrange(1,N):
  20             for i in xrange(k):
  21                 if not check2(Pos[Queens[i]],Pos[Queens[k]]):
  22                     return False
  23         return True
  24 
  25     def out():
  26         for i in Queens:
  27             print "  "+"[]"*Pos[i][0]+"##"+"[]"*(N-Pos[i][0]-1)
  28         print "-"*(N+4)
  29 
  30     Pos=[(x,y) for x in xrange(N) for y in xrange(N)]
  31     Queens=[0]*N
  32     while Queens != [N*N-1]*N:
  33         if check(): 
  34             out()
  35             Count+=1
  36         for i in xrange(N):
  37             if Queens[i]<N*N-1:
  38                 Queens[i]+=1
  39                 break
  40             else:
  41                 Queens[i]=0
  42 
  43 def linear(N):
  44     '«Простой» метод: каждый ферзь на своей горизонтали'
  45     global Count
  46 
  47     def check2((x1,y1), (x2,y2)):
  48         global Actions
  49         Actions+=1
  50         return x1!=x2 and x1+y1!=x2+y2 and x1-y1!=x2-y2
  51 
  52     def check():
  53         for k in xrange(1,N):
  54             for i in xrange(k):
  55                 if not check2((Queens[i],i),(Queens[k],k)):
  56                     return False
  57         return True
  58 
  59     def out():
  60         for i in Queens:
  61             print "  "+"[]"*i+"##"+"[]"*(N-i-1)
  62         print "-"*(N+4)
  63 
  64     Queens=[0]*N
  65     while True:
  66         if check():
  67             #out()
  68             Count+=1
  69         for i in xrange(N):
  70             if Queens[i]<N-1:
  71                 Queens[i]+=1
  72                 break
  73             else:
  74                 Queens[i]=0
  75         else:
  76             break
  77 
  78 def adaptive(N):
  79     "Алгоритм с проверкой, можно ли выставить очередного ферзя в данную клетку"
  80     global Count
  81 
  82     def check2((x1,y1), (x2,y2)):
  83         global Actions
  84         Actions+=1
  85         return x1!=x2 and x1+y1!=x2+y2 and x1-y1!=x2-y2
  86 
  87     def check(M):
  88         for k in xrange(1,M):
  89             for i in xrange(k):
  90                 if not check2((Queens[i],i),(Queens[k],k)):
  91                     return False
  92         return True
  93 
  94     def out():
  95         for i in Queens:
  96             print "  "+"[]"*i+"##"+"[]"*(N-i-1)
  97         print "-"*(N+4)
  98 
  99     Queens=[0]
 100     while Queens:   # Пока первый ферзь ещё стоит
 101         if(len(Queens)==N): # Если ферзей восемь -- напечатать
 102             #out()
 103             Count+=1
 104         else: # если меньше -- добавить очередного ферзя на -1 поле
 105             Queens.append(-1)
 106         while Queens:
 107             if Queens[-1]==N-1: # если двигать некуда -- выбросить текущего ферзя
 108                 Queens.pop()
 109                 continue
 110             Queens[-1]+=1 # подвинуть текущего ферзя
 111             if check(len(Queens)): break
 112 
 113 def tagged(N):
 114     "Алгоритм с запоминанием полей под боем"
 115     Table=[[-1]*N for i in xrange(N)]
 116     global Count, Free
 117 
 118     def outtable():
 119         c="".join((str(i) for i in xrange(N)))+" "
 120         return "\n".join(("".join((c[i] for i in t)) for t in Table))+"\n"+"-"*(N+1)
 121 
 122     def out():
 123         for i in Queens:
 124             print "  "+"[]"*i+"##"+"[]"*(N-i-1)
 125         print "-"*(N+4)
 126 
 127     def _tag(y, x, From, To):
 128         global Actions
 129         #print outtable()
 130         c=0
 131         for i in xrange(N):
 132             for X,Y in ((y,i), (i,x), (y+i,x+i), (y-i,x-i), (y-i,x+i), (y+i,x-i)):
 133                 if 0<=Y<N and 0<=X<N:
 134                     Actions+=1
 135                     if Table[X][Y]==From: 
 136                         Table[X][Y]=To
 137                         c+=1
 138         return c
 139 
 140     def tag(y,x):
 141         global Free
 142         Free-=_tag(y,x,-1,y)
 143 
 144     def untag(y,x): 
 145         global Free
 146         Free+=_tag(y,x,y,-1)
 147 
 148     Queens=[0]
 149     tag(0,0)
 150     while Queens:
 151         if(len(Queens)==N):
 152             #out()
 153             Count+=1
 154         elif Free>=N-len(Queens):
 155             Queens.append(-1)
 156         while Queens:
 157             if Queens[-1]>=N-1:
 158                 untag(len(Queens)-1,Queens[-1])
 159                 Queens.pop()
 160                 continue
 161             untag(len(Queens)-1,Queens[-1])
 162             Queens[-1]+=1
 163             if Table[len(Queens)-1][Queens[-1]]==-1:
 164                 tag(len(Queens)-1,Queens[-1])
 165                 break
 166 
 167 N=8
 168 if(len(sys.argv)>1): N=int(sys.argv[1])
 169 Actions,Count,Free=0,0,N*N
 170 fun=tagged
 171 if len(sys.argv)>2:
 172     fun=eval(sys.argv[2])
 173 
 174 fun(N)
 175 print Count, Actions, Actions/N, Actions/N/N/N, Actions*1000/(6**N)