breathFirstSearch

8puzzle.scala

@tailrec
final def breathFirstSearch(queue: List[(State, List[Move])], explored: Set[State], sol: List[(State, List[Move])]): List[(State, List[Move])] =
  queue match {
    case Nil => sol
    case (state, history) :: xs =>
      if (!explored(state)) {
        breathFirstSearch(xs ++ Move.availableStates(state, moves, history, explored), explored + state, (state, history) :: sol)
      } else {
        breathFirstSearch(xs, explored, sol)
      }
  }