AI Puzzle Program

Question

I have a puzzle with initial state

R R R G R 
R G G R R
R G G R G
R G G R R
R R R B R 

Where R = Red, G = Green and B = Moveable Blank

and Goal State

R R R R R
R G G G R
R G B G R
R G G G R 
R R R R R

I know in order to move the blank i must apply searching algorithms like DFS, BFS, A* etc

and i know i must create classes:

Node

class Node {
    char board[5][5];
    Node *parent;
};

Tree

class Tree {
     Node *root;
 };

Frontier like Hash Table to detect visited state in O(1) complexity.

So i am just confused how will i start implementing a solution to this puzzle. Can anyone guide me? The operators that i can apply on the blank are up, down, left, right.

Answer 1

The simplest idea would be to initialize the root node with the initial state. Then populate the next layer; write a procedure which generates the child nodes according to the blank space movement rules. You should be careful here; when the blank space is at the borders of the board, some movements would be invalid. In such a case, a sketch of A* algorithm can be drawn like that: Define your distance from the initial state as g(n). This may be the number of differently placed letters compared to the initial state, given the current state. Define a heuristic h(n), which gives your current distance from the goal state, which may be the number of differently placed letters compared to the goal state. Then in your current location in the tree, try to pick the next state, which minimizes f(n)=g(n)+h(n). I am not in a position to deeply analyze that right now, but I believe this approach may be much more efficient than brute force DFS or BFS approaches.