Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
