Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
breadth-first search solution in Clear category for Chess Knight by David_Jones
from collections import deque
from itertools import product
COLUMNS = 'abcdefgh'
ROWS = '12345678'
GRADIENTS = tuple((dx,dy) for (dx,dy) in product(range(-2,3), repeat=2)
if abs(dx) + abs(dy) == 3)
def neighbors(cell):
letter, digit = cell
(x,y) = (COLUMNS.index(letter), ROWS.index(digit))
for (dx,dy) in GRADIENTS:
if 0 <= x+dx < 8 and 0 <= y+dy < 8:
yield COLUMNS[x+dx] + ROWS[y+dy]
def chess_knight(start, moves):
possible_cells = set()
queue = deque([(start,0)])
while queue:
cell, length = queue.popleft()
if length:
possible_cells.add(cell)
if length < moves:
for neighbor in neighbors(cell):
queue.append((neighbor, length+1))
return sorted(possible_cells)
June 11, 2019
Comments:
