Tackling the 8-puzzle problem via BFS

Question

I've heard that the 8-puzzle problem can be tackled via BFS, but I don't understand how. I wanna know the intermediate steps that I need to get from a board like this:

3 1 2
6 4 5
0 7 8

to

1 2 3
4 5 6
7 8 0

Are the intermediate steps "levels" on a BFS search?

By the way, this is basic homework, I don't care about optimality.

Answer 1

this is pretty much a template for any BFS search

function next_boards(board)
   yields a set of reachable in one move from the current board

queue = [start_board]

while true:
   current = queue.pop()
   if current = goal: break

   queue.push for all next_boards(current)

note we're not doing anything fancy like checking for cycles or anything. if we were, change queue to a stack, and you get DFS.