прикреплённый файл:konjK.py к странице LecturesVMSH/2010-11-24

   1 #!/usr/bin
   2 # coding: UTF8
   3 '''
   4 Решить следующую задачу методом рекурсивного перебора с возвратами. Найти путь (список координат полей), по которому шахматный конь, начав в левом верхнем углу доски (NxN полей, N > 5) обойдет ее всю, побывав на каждом поле всего один раз.
   5       вариант: Дополнительно дано K > 0, найти K различных путей коня.
   6 '''
   7 
   8 Hod=((-1,-2),(-2,-1),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2))
   9 LHod=len(Hod)
  10 
  11 def konj(N,K):
  12     def check(x,y): return x>=0 and x<N and y>=0 and y<N
  13     def __konj():
  14         Pole=[[-1]*N for i in xrange(N)]
  15         Pole[0][0]=1
  16         Putj=[[0,0,0]]  # координаты и шаг поиска
  17         while len(Putj):
  18             if len(Putj) == N*N: yield Pole
  19             for i in xrange(Putj[-1][2],LHod):
  20                 x,y=Putj[-1][0]+Hod[i][0],Putj[-1][1]+Hod[i][1]
  21                 if check(x,y) and Pole[x][y] == -1:
  22                     Putj[-1][2]=i+1     # Откуда продолжать поиск
  23                     Putj.append([x,y,0])
  24                     Pole[x][y]=len(Putj)
  25                     break
  26             else:   # больше вариантов не найдено
  27                 Pole[Putj[-1][0]][Putj[-1][1]]=-1
  28                 Putj.pop()
  29     def pokaz(Pole):
  30         for x in xrange(N):
  31             print "".join(["{0:4}".format(Pole[x][y]) for y in xrange(N)])
  32 
  33     n=0
  34     for p in __konj():
  35         print n+1, "="*4*N
  36         pokaz(p)
  37         n+=1
  38         if n==K: break
  39     else:
  40         print "No more solutions"
  41 
  42 konj(*input())