CODEWITHSUNDEEP
language-agnosticbreadth-first-searchsliding-tile-puzzle
andandandand
andandandand

Reputation: 22270

Tackling the 8-puzzle via BFS

I've heard that the 8-puzzle problem can be tackled via BFS, but I don't understand how. I want to 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.

Upvotes: 1

Views: 5921

Answers (1)

Jimmy
Jimmy

Reputation: 91462

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.

Upvotes: 4

Related Questions