Attachment 'konj.py'

Download

   1 #!/usr/bin
   2 # coding: UTF8
   3 '''
   4 Решить следующую задачу методом рекурсивного перебора с возвратами. Найти путь (список координат полей), по которому шахматный конь, начав в левом верхнем углу доски (NxN полей, N > 5) обойдет ее всю, побывав на каждом поле всего один раз.
   5 '''
   6 
   7 Hod=((-1,-2),(-2,-1),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2))
   8 
   9 def konj(N):
  10     def check(x,y): return x>=0 and x<N and y>=0 and y<N
  11     def __konj(p):
  12         if len(p) == N*N: return p
  13         for dx, dy in Hod:
  14             x,y = p[-1][0]+dx,p[-1][1]+dy
  15             if check(x,y) and (x,y) not in p:
  16                 r = __konj(p+[(x,y)])
  17                 if r: return r
  18         return None
  19     def pokaz(p):
  20         Pole=[[0]*N for i in xrange(N)]
  21         for i in xrange(len(p)):
  22             Pole[p[i][0]][p[i][1]]=i
  23         print "="*4*N
  24         for x in xrange(N):
  25             print "".join(["{0:4}".format(Pole[x][y]) for y in xrange(N)])
  26     pokaz(__konj([(0,0)]))
  27 
  28 konj(input())

Attached Files

To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.

You are not allowed to attach a file to this page.