Packages
inplace
0.7.12
0.7.12
0.7.11
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.8
0.6.7
0.6.6
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.4
0.4.3
0.4.2
0.4.1
0.4.0
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.2.0
0.1.9
0.1.8
0.1.7
0.1.6
0.1.5
0.1.4
0.1.3
0.1.2
0.1.1
0.1.0
Mutable data structures
Current section
Files
Jump to
Current section
Files
lib/examples/knight_tour.py
def knight_tour_stack(n, start=(0, 0)):
moves = [(2, 1), (1, 2), (-1, 2), (-2, 1),
(-2, -1), (-1, -2), (1, -2), (2, -1)]
def legal(r, c):
return 0 <= r < n and 0 <= c < n
stack = [(start, [start], {start})]
while stack:
(r, c), path, visited = stack.pop()
if len(visited) == n * n:
print("solution")
return path
next_moves = []
for dr, dc in moves:
nr, nc = r + dr, c + dc
if legal(nr, nc) and (nr, nc) not in visited:
next_moves.append((nr, nc))
for nxt in reversed(next_moves):
stack.append((nxt, path + [nxt], visited | {nxt}))
return None