main.rb
def knight_moves(from, to)
  distances = Array.new(64, nil)

  # Search
  step = 0
  distances[pair_to_index(*from)] = step
  
  (0...64).cycle do |i|
    if distances[i] == step
      found = false
      possible_moves = moves_from(*index_to_pair(i))
      possible_moves.each do |file, rank|
        pm_index = pair_to_index(file, rank)
        distances[pm_index] = step + 1 if distances[pm_index].nil?  # if not nil, it's already been visited
        found = true if [file, rank] == to # we reached target square
      end

      break if found
    end

    step += 1 if i == 63 # increment step count after whole cycle
  end

  # Backtrack  
  path = [to]
  step = distances[pair_to_index(*to)] - 1

  until step < 0 do
    next_square = moves_from(*path.first).find { |file, rank| distances[pair_to_index(file, rank)] == step }
    path.unshift next_square

    step -= 1
  end

  path
end
# Returns (one) shortest path between starting and ending square on the chess board
Returns (one) shortest path between starting and ending square on the chess board
Returns ( one ) shortest path between starting and ending square on the chess board
def knight_moves(from, to)
  distances = Array.new(64, nil)
  step = 0
  distances[pair_to_index(*from)] = step
  (0...64).cycle do |i|
    if distances[i] == step
      found = false
      possible_moves = moves_from(*index_to_pair(i))
      possible_moves.each do |file, rank|
        pm_index = pair_to_index(file, rank)
        distances[pm_index] = step + 1 if distances[pm_index].nil?  
        found = true if [file, rank] == to 
      end
      break if found
    end
    step += 1 if i == 63 
  end
  path = [to]
  step = distances[pair_to_index(*to)] - 1
  until step < 0 do
    next_square = moves_from(*path.first).find { |file, rank| distances[pair_to_index(file, rank)] == step }
    path.unshift next_square
    step -= 1
  end
  path
end
def knight_moves ( from , to ) distances = Array . new ( 64 , nil ) step = 0 distances [ pair_to_index ( * from ) ] = step ( 0 ... 64 ) . cycle do | i | if distances [ i ] == step found = false possible_moves = moves_from ( * index_to_pair ( i ) ) possible_moves . each do | file , rank | pm_index = pair_to_index ( file , rank ) distances [ pm_index ] = step + 1 if distances [ pm_index ] . nil? found = true if [ file , rank ] == to end break if found end step += 1 if i == 63 end path = [ to ] step = distances [ pair_to_index ( * to ) ] - 1 until step < 0 do next_square = moves_from ( * path . first ) . find { | file , rank | distances [ pair_to_index ( file , rank ) ] == step } path . unshift next_square step -= 1 end path end
Returns (one) shortest path between starting and ending square on the chess board
Returns ( one ) shortest path between starting and ending square on the chess board
# Search # if not nil, it's already been visited # we reached target square # increment step count after whole cycle # Backtrack  
from
to