From: Timothy Byrd <byrd.timothy@...>
Date: 2005-04-13T03:29:37+09:00
Subject: Re: Knight's Travails (#27)

And here is an iterative, breadth-first search that can be used in
place of my find_path_recurse().


module Knight

    def self.find_path_bf(pStart, pEnd, forbidden)

        # Are we there yet?
        #
        return [pEnd.clone] if pStart == pEnd

        # You can't get there from here!
        #
        return nil if forbidden.include?(pEnd)

        position_list = Hash.new
        forbidden.each {|f| position_list[f] = 'forbidden' }
        position_list[pStart] = []

        moves_to_check = [pStart]

        until moves_to_check.empty? do
            pos = moves_to_check.shift
            possible_moves(pos).each do |m|
                next if position_list[m]
                position_list[m] = position_list[pos] + [m]
                return position_list[m] if m == pEnd
                moves_to_check.push(m)
            end
        end

        nil
    end
end

-- Timothy