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