hughdbrown/knight_move.py

## knight_move.py
#!/usr/bin/env python3
from collections import deque

def possible(pos, legal_pos):
    r, c = pos
    can = {
        (r + 2, c - 1), (r + 2, c + 1),
        (r + 1, c - 2), (r + 1, c + 2),
        (r - 1, c - 2), (r - 1, c + 2),
        (r - 2, c - 1), (r - 2, c + 1)
    }
    return can.intersection(legal_pos)

def print_path(path):
    letters = "abcdefgh"
    print(" ".join(f"{letters[pos[1]]}{pos[0] + 1}" for pos in path))

def main():
    queen_pos = (4, 3)
    lower_diag = (1, 0)
    upper_diag = (7, 0)
    # Squares the queen can visit
    illegal_pos = set(
        [(queen_pos[0], col) for col in range(8)] +
        [(row, queen_pos[1]) for row in range(8)] +
        [(lower_diag[0] + i, lower_diag[1] + i) for i in range(7)] +
        [(upper_diag[0] - i, upper_diag[1] + i) for i in range(8)]
    )
    # All the squares
    all_squares = {(x, y) for x in range(8) for y in range(8)}
    # All the legal squares for knight to visit
    legal_pos = all_squares - illegal_pos
    visits = sorted(legal_pos, reverse=True)
    # Squares visitable from a position
    hops = {pos: possible(pos, legal_pos) for pos in legal_pos}
    current_square = visits[0]
    for square in visits:
        queue = deque([[current_square]])
        while queue:
            path = queue.popleft()
            last_pos = path[-1]
            if last_pos == square:
                print_path(path)
                current_square = square
                break
            else:
                for p in hops[last_pos] - set(path):
                    new_path = path + [p]
                    queue.append(new_path)

if __name__ == '__main__':
    main()
	#!/usr/bin/env python3
	from collections import deque

	def possible(pos, legal_pos):
	r, c = pos
	can = {
	(r + 2, c - 1), (r + 2, c + 1),
	(r + 1, c - 2), (r + 1, c + 2),
	(r - 1, c - 2), (r - 1, c + 2),
	(r - 2, c - 1), (r - 2, c + 1)
	}
	return can.intersection(legal_pos)

	def print_path(path):
	letters = "abcdefgh"
	print(" ".join(f"{letters[pos[1]]}{pos[0] + 1}" for pos in path))

	def main():
	queen_pos = (4, 3)
	lower_diag = (1, 0)
	upper_diag = (7, 0)
	# Squares the queen can visit
	illegal_pos = set(
	[(queen_pos[0], col) for col in range(8)] +
	[(row, queen_pos[1]) for row in range(8)] +
	[(lower_diag[0] + i, lower_diag[1] + i) for i in range(7)] +
	[(upper_diag[0] - i, upper_diag[1] + i) for i in range(8)]
	)
	# All the squares
	all_squares = {(x, y) for x in range(8) for y in range(8)}
	# All the legal squares for knight to visit
	legal_pos = all_squares - illegal_pos
	visits = sorted(legal_pos, reverse=True)
	# Squares visitable from a position
	hops = {pos: possible(pos, legal_pos) for pos in legal_pos}
	current_square = visits[0]
	for square in visits:
	queue = deque([[current_square]])
	while queue:
	path = queue.popleft()
	last_pos = path[-1]
	if last_pos == square:
	print_path(path)
	current_square = square
	break
	else:
	for p in hops[last_pos] - set(path):
	new_path = path + [p]
	queue.append(new_path)

	if __name__ == '__main__':
	main()