I recently had to do a project for my AI class that could solve an 8 puzzle using an A* search in C++. I have to admit that I wish I could have spent more time cleaning up my code. What’s good is my linked list structure. What’s a little sloppy are my computational methods. Regardless, I thought that this code could still be useful for people who are new or rusty on how to use classes and setting up a search tree.

This is an empty console project, with one source file (main.cpp), one input file (in.txt), and one output file (out.txt). This code has been tested, compiled, and executed under Visual Studio 2008 Professional Edition.

My Algorithm

I created a tree class that could handle linked lists. Every linked node could have up to 4 children. I would simply build the tree structure out. Using the first heuristic, I would build the tree according to which node had the lowest distance from the root node. This is pretty much creating a tree by a breadth depth search. My second heuristic added in a cost for how similar the current node’s state was to the goal state. This allowed the tree to be built smartly and not continue to expand down bad branches.

I also added a constraint that wouldn’t allow a node to be created if it was trying to make a bad move. A bad move is when the puzzle is backtracking. Backtracking is a sure sign that that branch is not an optimal solution.

My Results

I ran my program using two different heuristics. One was many times more efficient than the other. My first heuristic was simply just using the distance from the root node. It took 6.63 minutes to complete.

/**************OUTPUT******************/
Success!
n = 12
time: 663801 msecs
Press any key to continue . . .
/**************************************/

My second heuristic was adding a cost to the distance for how many numbers in the current state were in the same position as the numbers in the goal state. The output was significantly faster. It computed the the same path in under 1 second.

/**************OUTPUT******************/
Success!
n = 12
time: 858 msecs
Press any key to continue . . .
/**************************************/

Using this Code

If you are working on a similar assignment, feel free to use this code and expand on it. I would really appreciate it if someone could polish the code for me and send me an updated copy. It could use a better class structure, better name conventions, prettier computational methods, and some relevant comments. I simply didn’t have time. Feel free to leave a comment if you have any questions trying to get this to work on your computer. I hope this helps!