```[Ruby Quiz <james / grayproductions.net>, 2005-04-08 20.38 CEST]
> Return an array indicating the shortest path that the knight must travel to get
> to the end position without landing on one of the forbidden squares. If there is
> no valid path to the destination return nil.

Here is a solution. I'm having a hard time trying to explain it in English,
I hope the code is clear enough (it's very simple).

Thanks.

# code:

class String
def to_coords
return [self[0] - ?a, self[1] - ?1]
end
end

class Array
def to_algebraic
return (self[0] + ?a).chr + (self[1] + ?1).chr
end
end

def where_can_jump_from (here, visited)
col, row = here
[
[col+2, row+1], [col+2, row-1], [col+1, row-2], [col-1, row-2],
[col-2, row-1], [col-2, row+1], [col-1, row+2], [col+1, row+2]
].select { |c,r|
r >= 0 && r < 8 && c >= 0 && c < 8 && !visited[c][r]
}
end

def knight_path (start_pos, finish_pos, forbidden)
visited = Array.new(8) { Array.new(8) }
forbidden.each do |col,row| visited[col][row] = true end

# special cases:
# shortest path: no movement at all
return [] if start_pos == finish_pos
return nil if forbidden.include? finish_pos

# setup...
paths = [[start_pos]]
visited[start_pos[0]][start_pos[1]] = true

while !paths.empty?
# pp paths.map {|p| p.map {|c| c.to_algebraic } }
new_paths = []
paths.each do |path|
where_next = where_can_jump_from(path.last, visited)
where_next.each do |coord|
newpath = path.dup << coord
if coord == finish_pos
# clear first cell (start position)
newpath.shift
return newpath
end
c, r = coord
visited[c][r] = true
new_paths.push newpath
end
end
paths = new_paths
end

return nil
end

start_pos = ARGV.shift.to_coords
finish_pos = ARGV.shift.to_coords
forbidden = ARGV.map {|arg| arg.to_coords }

result = knight_path start_pos, finish_pos, forbidden

if (result)
result.map! { |coord| coord.to_algebraic }
puts "[ " + result.join(" , ") + " ]"
else
p nil
end

```