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.- [get | view] (2011-09-26 08:35:13, 1.1 KB) [[attachment:konj.py]]
- [get | view] (2011-09-26 08:35:13, 1.7 KB) [[attachment:konjK.py]]
You are not allowed to attach a file to this page.