Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
A*, Empirically Improved Heuristic solution in Clear category for The Shortest Knight's Path by PositronicLlama
"""
Determine the most efficient knight's path.
"""
import collections
import heapq
import itertools
import re
RE_CHESS_COORD = re.compile('^([a-h])([1-8])$')
# The edge length of a chess board.
BOARD_LEN = 8
# The number of squares on a chess board.
BOARD_SIZE = BOARD_LEN * BOARD_LEN
# Store prev so we could reconstruct the path (even though it is not necessary)
Cell = collections.namedtuple('Cell', ['dist', 'prev'])
Move = collections.namedtuple('Move', ['dist', 'loc'])
def index(x, y):
"""The cell index into a chess board stored as an array."""
return x + BOARD_LEN * y
def chess_coordinate(loc):
"""
Convert a chess location into cartesian coordinates.
Examples: a1 -> (0, 0)
c2 -> (2, 1)
h8 -> (7, 7)
"""
m = RE_CHESS_COORD.match(loc)
if not m:
raise ValueError("Invalid chess location: {}".format(loc))
return (ord(m.group(1)) - ord('a'), ord(m.group(2)) - ord('1'))
def knight_moves_gen(x, y):
"""
Iterator of possible knight moves from (x, y).
"""
return itertools.chain(
itertools.product((x - 1, x + 1), (y + 2, y - 2)),
itertools.product((x - 2, x + 2), (y + 1, y - 1)))
def manhattan_distance(a, b):
"""Return the manhattan distance between coordinate tuples a and b."""
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def dist_heuristic(a, b):
"""Return a heuristic for knight move distance."""
# In order to be admissable, the heuristic must not overestimate the
# distance. This heuristic is inadmissable over long distances, but
# significantly reduces the number of moves that must be explored.
dist = manhattan_distance(a, b)
if dist == 0:
return 0 # At the goal
elif dist <= 2:
return 2 # Exactly two away
elif dist == 3 and a[0] != b[0] and a[1] != b[1]:
return 1 # Exactly three away and not in a line
else:
return dist
def push_location(open, board, dist, loc, prev, goal):
"""
Push a new location onto the open list.
open: The open list
board: The board so far
dist: The number of moves so far
loc: The current location
prev: The previous location
goal: The goal location
"""
if 0 <= loc[0] < BOARD_LEN and 0 <= loc[1] < BOARD_LEN:
ix = index(*loc)
if board[ix] is None or board[ix].dist > dist:
board[ix] = Cell(dist, prev)
estimated_remaining = dist_heuristic(loc, goal)
heapq.heappush(open, Move(dist + estimated_remaining, loc))
def shortest_knight_move_dist(begin, end):
"""
Return the shortest knight move length from begin to end.
"""
# Use A*
board = [None] * BOARD_SIZE
board[index(*begin)] = Cell(0, None)
# A heap of moves to try
open = [Move(dist_heuristic(begin, end), begin)]
while open:
move = heapq.heappop(open)
if move.loc == end:
return move.dist
ix = index(*move.loc)
dist = board[ix].dist
for next_loc in knight_moves_gen(*move.loc):
push_location(open, board, dist + 1, next_loc, move.loc, end)
raise RuntimeError("Could not find move from {} to {}".format(begin, end))
def checkio(move_string):
'''
Find a length of the shortest path of knight
'''
begin, end = move_string.split('-')
begin = chess_coordinate(begin)
end = chess_coordinate(end)
return shortest_knight_move_dist(begin, end)
if __name__ == "__main__":
assert checkio("b1-d5") == 2, "First"
assert checkio("a6-b8") == 1, "Second"
assert checkio("h1-g2") == 4, "Third"
assert checkio("h8-d7") == 3, "Fourth"
assert checkio("a1-h8") == 6, "Fifth"
"""
Determine the most efficient knight's path.
"""
import collections
import heapq
import itertools
import re
RE_CHESS_COORD = re.compile('^([a-h])([1-8])$')
# The edge length of a chess board.
BOARD_LEN = 8
# The number of squares on a chess board.
BOARD_SIZE = BOARD_LEN * BOARD_LEN
# Store prev so we could reconstruct the path (even though it is not necessary)
Cell = collections.namedtuple('Cell', ['dist', 'prev'])
Move = collections.namedtuple('Move', ['dist', 'loc'])
def index(x, y):
"""The cell index into a chess board stored as an array."""
return x + BOARD_LEN * y
def chess_coordinate(loc):
"""
Convert a chess location into cartesian coordinates.
Examples: a1 -> (0, 0)
c2 -> (2, 1)
h8 -> (7, 7)
"""
m = RE_CHESS_COORD.match(loc)
if not m:
raise ValueError("Invalid chess location: {}".format(loc))
return (ord(m.group(1)) - ord('a'), ord(m.group(2)) - ord('1'))
def knight_moves_gen(x, y):
"""
Iterator of possible knight moves from (x, y).
"""
return itertools.chain(
itertools.product((x - 1, x + 1), (y + 2, y - 2)),
itertools.product((x - 2, x + 2), (y + 1, y - 1)))
def manhattan_distance(a, b):
"""Return the manhattan distance between coordinate tuples a and b."""
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def dist_heuristic(a, b):
"""Return an admissable A* heuristic for knight move distance."""
# Must not overestimate the number of moves.
return manhattan_distance(a, b) / 4
def push_location(open, board, dist, loc, prev, goal):
"""
Push a new location onto the open list.
open: The open list
board: The board so far
dist: The number of moves so far
loc: The current location
prev: The previous location
goal: The goal location
"""
if 0 <= loc[0] < BOARD_LEN and 0 <= loc[1] < BOARD_LEN:
ix = index(*loc)
if board[ix] is None or board[ix].dist > dist:
board[ix] = Cell(dist, prev)
estimated_remaining = dist_heuristic(loc, goal)
heapq.heappush(open, Move(dist + estimated_remaining, loc))
def shortest_knight_move_dist(begin, end):
"""
Return the shortest knight move length from begin to end.
"""
# Use A*
board = [None] * BOARD_SIZE
board[index(*begin)] = Cell(0, None)
# A heap of moves to try
open = [Move(dist_heuristic(begin, end), begin)]
while open:
move = heapq.heappop(open)
if move.loc == end:
return move.dist
ix = index(*move.loc)
dist = board[ix].dist
for next_loc in knight_moves_gen(*move.loc):
push_location(open, board, dist + 1, next_loc, move.loc, end)
raise RuntimeError("Could not find move from {} to {}".format(begin, end))
def checkio(move_string):
'''
Find a length of the shortest path of knight
'''
begin, end = move_string.split('-')
begin = chess_coordinate(begin)
end = chess_coordinate(end)
return shortest_knight_move_dist(begin, end)
if __name__ == "__main__":
assert checkio("b1-d5") == 2, "First"
assert checkio("a6-b8") == 1, "Second"
assert checkio("h1-g2") == 4, "Third"
assert checkio("h8-d7") == 3, "Fourth"
assert checkio("a1-h8") == 6, "Fifth"
Dec. 9, 2012
Comments:
