class BfsBruteForce::Solver
Lazy breadth first puzzle solver
Public Instance Methods
solve(initial_state, status = [])
click to toggle source
Find a list of moves from the starting state of the puzzle to a solution state.
@param initial_state [State] Initial state of your puzzle @param status [#<<] IO object to receive status messages
@raise [NoSolution] No solution is found @return [Context] Solved Context
object has the final {State} and list of moves
# File lib/bfs_brute_force.rb, line 103 def solve(initial_state, status = []) status << "Looking for solution for:\n#{initial_state}\n\n" initial_context = Context.new(initial_state) if initial_context.solved? status << "Good news, its already solved\n" return initial_context end tries = 0 contexts = [initial_context] until contexts.empty? status << ("Checking for solutions that take %4d moves ... " % [ contexts.first.moves.size + 1 ]) new_contexts = [] contexts.each do |current_context| current_context.next_contexts do |context| tries += 1 if context.solved? status << "solved in #{tries} tries\n\nMoves:\n" context.moves.each {|m| status << " #{m}\n"} status << "\nFinal state:\n #{context.state}\n" return context end new_contexts << context end end contexts = new_contexts status << ("none in %9d new states\n" % contexts.size) end raise NoSolution.new(tries) end