Skip to content

Instantly share code, notes, and snippets.

@sofoklis
Created February 21, 2013 21:23
Show Gist options
  • Save sofoklis/5008374 to your computer and use it in GitHub Desktop.
Save sofoklis/5008374 to your computer and use it in GitHub Desktop.
BFS loop 8-puzzle
@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)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment