1
$\begingroup$

I see so many 8 Puzzle Solvers use a stack instead of a queue. Why is that? If you are looking for the solution with the fewest number of moves, wouldn't the solution be at a shallower point in the tree, meaning that BFS would find it much quicker? Is there some subtlety to the problem that I'm forgetting that makes DFS a better approach?

I've been comparing performance times myself and it seems like BFS is consistently and significantly faster.

$\endgroup$
1
$\begingroup$

If the goal is to find the shortest solution to the 8-puzzle, DFS is indeed a very poor method. It's not a matter of faster or slower; DFS is not correct (it finds a solution, but it's not guaranteed to be the shortest solution). You could use BFS and that will work fine. Even better is to use A* or some related algorithm; it will find the shortest solution even faster than BFS.

If the goal is to find any solution to the 8-puzzle, without regard to how many moves the solution takes, DFS is a fine method. Actually, you could use either DFS or BFS for that. The 8-puzzle has only 181440 reachable states, so the data structures won't grow too large.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.