8 Puzzle - WPF

• Download source - 1.18 MB

Introduction

75% of the focus of this article is on state space searching algorithms. The other 25% shows how animation can be used in Windows Presentation Foundation (aka WPF). I wanted to visually represent a computer (A.I.) solving an 8-puzzle using different search algorithms. Different search algorithms being: Depth-First search; Iterative Depth-First search and A*.

Background

159.302 Artificial Intelligence - Assignment 1! Need I say more? This is just an assignment I was doing while I was taking the A.I. paper. The assignment itself was supposed to be done in C/C++ but I did it using C# as it’s implementing the search algorithms that are important, not what language you choose to implement it in. And I was pretty hyped about WPF's animation support and wanted to use it to have a better visual representation of how each algorithm affects how the 8-puzzle is solved. I thought the solution I came up with was pretty neat so what better way to share it than put it up on CodeProject =).

Do keep in mind though that like most students if not all, most of the work I did on this assignment was a short time before the due date. I'm going to blame the lack of commenting and possibly not the best way to have organised the code...

Brief Introduction to Search Algorithms

Search algorithms are very important in AI. They are the backbone of systematic exploration of alternatives you could say. A problem is represented as a graph consisting of at least one node and several paths, like the one below:

There are states (Auckland, Hamilton, etc.) and edges (lines) that connect the different states. This is the problem domain and it contains a set of possible solutions. Given the task of finding a way to get from Auckland to Raglan, using a search algorithm you can systematically work through all possible paths by searching and examining node by node. There are many different algorithms all with their pros and cons, but all of them are more alike than different. Anyhow if you're reading this article, I'm already assuming you know about graphs and trees and have a basic concept of search algorithms, but I'll just refresh your memory anyhow.

Depth-First Search

This is the most basic of the search algorithms also categorised as Any-path uninformed algorithm. So DFS might not find the most optimal solution if one is found. It examines all possible nodes till it finds the goal. It can be optimised using Visited List (Note: Visited not Expanded) to avoid loops in a uni-directional graph.

Implementing DFS is pretty straight forward using a stack. As you examine a node for any child nodes, add the child nodes to the stack, pop the stack and examine the node on the top of the stack. It doesn't get much simpler than this =). DFS doesn't guarantee a shallowest solutions or any solution if it gets stuck in an infinite loop if a visited list is not used.

Iterative Depth-First Search

IDFS, also an Any-path uniformed algorithm, expands nodes or finds its way to the solution almost exactly like Breadth-First search. But BFS memory requirements increase at an exponential rate as it searches deeper. BFS is implemented using a queue (FILO). IDFS has the same memory requirements as DFS but unlike DFS, it will find the goal at the shallowest depth like the BFS algorithm.

A* (Pronounced A Star)

Accepted as one of the best search algorithms, it is categorised as an Optimal Informed algorithm. The algorithm uses a heuristic which is an estimate of the straight line distance to the goal in a search space. It has to be a straight line distance because A* will only find the optimal path to the goal if the heuristic (estimate) is admissible; admissible meaning less than or equal to the actual distance to the goal.

Using the Code

All the algorithms are programmed quite similarly, I'll just explain the first and easiest one: DFS. As you may already know, DFS is implemented using a stack. A state is examined and all possible states that can lead on to from that state get added on to the stack. The stack is then popped to retrieve the top most state that was pushed on top, examined to see if it is the goal state if not examine any paths than lead to other states and so on.

//I store a state as a 2-dimensional double array. Each element can be thought of as
//a square on the 8 puzzle. 
class State
{
    public Double[][] xPuzzle = new Double[3][];    
    public Double[][] yPuzzle = new Double[3][];    
}

static public void initializeArray()
{
    for (int i = 0; i < 3; i++)
    {
        xPuzzle[i] = new Double[3];
        yPuzzle[i] = new Double[3];
    }
}

The WPF canvas (container for the 8-puzzle images) is 300px square. Each square is 100px. So each element in the array xPuzzle and yPuzzle stores the x and y values of the position of the squares. Possible values can only be from the set {0, 100, 200} so each square can only be in 1 out of the 9 possible positions on the canvas. This forms the basis of storing each representing a particular state for the 8-puzzle. I hope I have explained this properly.

You should now know how DFS is supposed to work and how I have implemented an 8-puzzle state in C#.

The way I animated the squares is using the DoubleAnimation class found in System.Windows.Media.Animation namespace.

protected void UpdatePuzzle()
{
    DoubleAnimation xBox1 = new DoubleAnimation(PuzzleData.xPuzzle[0][0],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox2 = new DoubleAnimation(PuzzleData.xPuzzle[0][1],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox3 = new DoubleAnimation(PuzzleData.xPuzzle[0][2],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox4 = new DoubleAnimation(PuzzleData.xPuzzle[1][0],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox5 = new DoubleAnimation(PuzzleData.xPuzzle[1][1],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox6 = new DoubleAnimation(PuzzleData.xPuzzle[1][2],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox7 = new DoubleAnimation(PuzzleData.xPuzzle[2][0],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox8 = new DoubleAnimation(PuzzleData.xPuzzle[2][1],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox9 = new DoubleAnimation(PuzzleData.xPuzzle[2][2],
        TimeSpan.FromMilliseconds(AnmSpeed));
                
    DoubleAnimation yBox1 = new DoubleAnimation(PuzzleData.yPuzzle[0][0],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox2 = new DoubleAnimation(PuzzleData.yPuzzle[0][1],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox3 = new DoubleAnimation(PuzzleData.yPuzzle[0][2],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox4 = new DoubleAnimation(PuzzleData.yPuzzle[1][0],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox5 = new DoubleAnimation(PuzzleData.yPuzzle[1][1],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox6 = new DoubleAnimation(PuzzleData.yPuzzle[1][2],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox7 = new DoubleAnimation(PuzzleData.yPuzzle[2][0],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox8 = new DoubleAnimation(PuzzleData.yPuzzle[2][1],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox9 = new DoubleAnimation(PuzzleData.yPuzzle[2][2],
        TimeSpan.FromMilliseconds(AnmSpeed));
    
    //The statement below is basically an eventhandler for when the blank square's
    //animation stops. The Event handler is called the method Shuffle_Complete is
    //ShuffleDonw flag is not set and shuffleOn flag is set. This is how it loops
    //however many number of times defined in the Shuffle class. Look at Shuffle
    //Class for more info.
    if ((!Shuffle.shuffleDone)&&(Shuffle.shuffleOn)) {
        xBox9.Completed += new EventHandler(Shuffle_Completed); }

    //The statements below start the horizontal animation for each box.
    Box1.BeginAnimation(Canvas.LeftProperty, xBox1);
    Box2.BeginAnimation(Canvas.LeftProperty, xBox2);
    Box3.BeginAnimation(Canvas.LeftProperty, xBox3);
    Box4.BeginAnimation(Canvas.LeftProperty, xBox4);
    Box5.BeginAnimation(Canvas.LeftProperty, xBox5);
    Box6.BeginAnimation(Canvas.LeftProperty, xBox6);
    Box7.BeginAnimation(Canvas.LeftProperty, xBox7);
    Box8.BeginAnimation(Canvas.LeftProperty, xBox8);
    Box9.BeginAnimation(Canvas.LeftProperty, xBox9);
    
    //The statements below start the vertical animation for each box.
    Box1.BeginAnimation(Canvas.TopProperty, yBox1);
    Box2.BeginAnimation(Canvas.TopProperty, yBox2);
    Box3.BeginAnimation(Canvas.TopProperty, yBox3);
    Box4.BeginAnimation(Canvas.TopProperty, yBox4);
    Box5.BeginAnimation(Canvas.TopProperty, yBox5);
    Box6.BeginAnimation(Canvas.TopProperty, yBox6);
    Box7.BeginAnimation(Canvas.TopProperty, yBox7);
    Box8.BeginAnimation(Canvas.TopProperty, yBox8);
    Box9.BeginAnimation(Canvas.TopProperty, yBox9);
}

This is how I animate the squares. They x and y positions for each of the squares are stored in an array and I animate all of them every iteration. So if a square hasn't moved it's position then it won't obviously animate. I have attached an animation complete event handler to just one of the squares. This event starts the next iteration of the particular algorithm being used and so on.

How I Implemented a Search Algorithm

Let's take the DFS algorithm for example. Solving an algorithm requires using certain data structures such as a queue, stack list ,etc. For DFS, we will be using a stack as we need a first in first out (FIFO) data structure to store our states.

Taking our previous graph example: If we were trying to find a path from Auckland to Tauranga, we would look at the start at the Auckland node. We can see there is path connecting to Hamilton and Raglan. So we add Hamilton and Raglan nodes to our stack. Next we pop a node of our stack to examine it closely. We find that there is a path connecting Hamilton to the Raglan node. So we add Raglan on to our stack. *VERY IMPORTANT: But we DO NOT stop here. We don't stop searching just because we have visited our goal state. We stop searching once we have pulled our goal node off our stack. So in the next few iterations, Raglan will eventually get pulled off our stack. If you keep track of the nodes you are pulling off the stack by just adding them to a list as you pull them off, you will eventually end up with a path from Auckland to Tauranga via Hamilton if you just iterate through your list from start to finish. Remember you finish iterating through the algorithm only once you pulled the goal node off the stack not once you've placed it on the stack. So, to summarise again:

1. Place start node on stack
2. Pop node of stack to examine and append node to list
3. If node popped off stack is the goal node, then the list from start to finish represents a path from start to goal
4. Examine node and push any connecting nodes to the stack
5. Go to step 2

You probably picked up that there could be the algorithm as it is now doesn't cater for infinite loops. You can modify the algorithm slightly by using an expanded list to keep track of all the nodes you have examined. This is what I have done in this application.

A node or a state in my application is the combination of two 2-d arrays storing the position of the 8 squares.

So yea, just download the application and play around with it. You will probably get a much better understanding that way to see what's actually going on.

Points of Interest

WPF is the coolest thing ever for leveraging your video card capabilities in everyday apps, don't you think..? I lost all my updates with A* algorithm (darn crappy source code management) so it doesn't work like it should at all... If you can fix it before I can restore it to how it was, please do so and post an update. Cheers.

Also like I mentioned before, I wanted to show how different algorithms solve the puzzle in different ways. And I think I've done that really well. If you try out both DFS and progressive DFS, you can really see the difference of how using different algorithms impact the steps taken to reach the goal. I use an expanded list for DFS by the way as 8-puzzle can have infinite loops in its search space.

Signing off

This is my first article and I just wanted to share something that I thought was pretty cool, and I hope someone finds it useful. I realize it's pretty summarized but just wanted to get something out there. You may use the ideas however you like and do whatever you want with the source, only thing I ask is please give credit where it's due. If you really like this article, please do vote and leave comments for me (it doesn't take much you know =P ). Thanks heaps...

History

Corrected a few spelling mistakes and semantic errors. Thanks to Manuel & Ravi. Cheers for pointing out the errors =).