8 puzzle Solution whit RBFS

You should be doing your own homework, but I will give you some pointers.

What you first need to do is define a board state. Lets say the number 0 represents the empty space and numbers 1-8 represent the tiles.

So, we will have a 3x3 2D array of integers.

typedef struct {
	int Board[3][3];
} BoardState;

Now we need to define valid moves. Lets call these Up, Down, Left and Right, which are the respective directions that we will move the hole.

typedef enum {
	Up,
	Down,
	Left,
	Right,
} Moves;

You will then need to define functions to apply each move to the board and to check if a move is valid. You can do this.

bool IsMoveValid(const BoardState &Board, Moves move);
void MoveUp(const BoardState &OrigBoard, BoardState *pNewBoard);
void MoveDown(const BoardState &OrigBoard, BoardState *pNewBoard);
void MoveLeft(const BoardState &OrigBoard, BoardState *pNewBoard);
void MoveRight(const BoardState &OrigBoard, BoardState *pNewBoard);

Now what you need is a starting board.

BoardState board = {
	{ 0, 1, 2 },
	{ 3, 4, 5 },
	{ 6, 7, 8 },
};
MyTreeNode<boardstate> TreeRoot(board); //MyTree is a tree structure class that you have to write. This one is templated, and takes 1 parameter, which is the value stored at the root node.
</boardstate>

From this we now need to build a tree of all the possible moves we can make.
For the first case on my example board, these moves would be Right and Down. We will use a generic approach tho.

void GenerateChildren(const MyTreeNode &node) {
	BoardState temp;
	if (IsValidMove(node.board, Left)) {
		MoveLeft(node.board, temp);
		node.AddChild(new MyTreeNode(temp));
	}
	//Do the same for other directions
}

Once we have a tree made, we can use a Recursive Breadth First Search (RBFS) to search it for the path to the solution. RBFS goes across the tree first, then into children.
To do this you will need to (you have to figure out the order):
a. Check the current node to see if it the solution
b. Check all child nodes to see if they are the solution


Hopefully I have given you enough so you can do it on your own now without giving you all the answers. Give it a try (Wikipedia helps). If you are still having trouble come back with code WHEN YOU HAVE TRIED SOMETHING.