8/15 Puzzle using A* (A Star) Algorithm

A* Algorithm

A* (“A Star”) algorithm is an informed search strategy – strategy that uses problem specific knowledge, deriving from the problem itself.

In other words, it is a best-first search algorithm that evaluates the next possible path based on the total estimated cost. It always looks for the cheapest path among the possible paths and tries to reach towards the goal.

So how does A* knows which one is the cheapest path? Let’s take an example to see this.

Given the below map, a person has to travel from Delhi to Hyderabad. We know the actual distance that a person has to cover from one city to another (numbers in green color).

So travel distance from Delhi -> Mumbai is 12, Delhi -> Lucknow is 7, Mumbai -> Hyderabad is 8, Lucknow -> Kolkata is 6, and Kolkata -> Hyderabad is 9.

In real world, probably you would know the total distance that you might have to travel to reach Hyderabad, from all possible paths and you will choose the one where you see the minimum distance you have to cover. This is pretty easy when person has information about all the sates – from start to the final destination.

The challenge comes into the picture when you have no idea about the next destination unless you actually reach there i.e. when you have to actually discover the path from one point to another point and you don’t know the state unless you are in the state. This type of search is known as uniformed search – there is no other information other than the problem definition itself.

For example, you don’t know that there is a path from Mumbai to Hyderabad unless you reach at Mumbai.

Now, say along with the actual distance between Delhi and Mumbai, we also know the straight line distance of each city to Hyderabad – shortest path: always less or equal to the actual distance from current city to Hyderabad (known as Heuristic for A* algorithm).

For easy notation – we will call actual distance from one city to another as g.

And straight line distance from that city to goad city as h.

As you have noticed, heuristic cost h is not overestimating the cost g (h <= g; a very important thing for A* to converge).

Now we will say distance of moving from one city to another city is sum of actual distance (g) and straight line distance (h):

f = g + h.

This distance (f) is used by the algorithm to determine the cheapest path. So, a path which has lower value of f would be preferred over the one with higher value of f.

Now, using the above distance formula, we can figure out how A* is going to search the optimal path from Delhi to Hyderabad.

Straight line distance to Hyderabad:

Delhi: 20
Mumbai: 12
Lucknow: 16
Kolkata: 8
Hyderabad: 0

f(Delhi -> Mumbai) = 20 + 12 = 32
f(Delhi -> Lucknow) = 20 + 7 = 27

Since Delhi to Lucknow has lower value of f, next path to expand is Lucknow to Kolkata.

f(Lucknow -> Kolkata) = 27 + 16 + 6 = 49.

Now we have two open states (Delhi -> Mumbai) and (Lucknow -> Kolkata). One with lowest value of f will be explored further (32 - Delhi -> Mumbai).

f(Mumbai -> Hyderabad) = 32 + 12 + 8 = 52

Next path to examine is (Delhi -> Lucknow -> Kolkata).

f(Kolkata -> Hyderabad): 49 + 8 + 9 = 66

Now that it has reached to the destination, and it has cheapest path among possible one is one from Delhi -> Mumbai -> Hyderabad. It will backtrack and declare this path as an optimal path.

One thing worth mentioning here is it does not expand all possible paths to the destination.

It always expands those one that seems optimal. For example, if there would have been a path from Kolkata -> Bhubaneswar -> Hyderabad and total cost reaching to Kolkata -> Bhubaneswar > 52, A* won’t even bother to examine the path at all. It knows that there exist a path to the final destination with f value = 52 and f value to Bhubaneswar is more than 52.

8/15 Puzzle

So how does 8/15 puzzle can be solved using this path finding algorithm?

Let's talk about 8 puzzle – simple sliding tiles on a 3x3 grid. You are allowed to move along with empty block, one step at a time. The puzzle is said to be solved, when it has sequential arrangement of the numbers.

So you have a start state (some random arrangement), and then a final state to reach.

This is how you start solving the puzzle:

1. Get the first state, which is your start sate.
2. Get all the possible states that the puzzle can be.
3. Add those new states in the open state list.
4. Add processed state in the closed list.
5. Pick the next state from the list which has the lowest cost
6. Start repeating the steps from 1 to 6 unless you reach to the final state or no more states to examine (in this case, no solution exists).
7. Once you have the final state, backtrack to the start node and that would be the optimal path to find the solution.

So what should be the g and h cost for this problem?

Since each time you just move one tile by one block – you can say actual move cost (g) is 1 from moving one state to another.

For 8 puzzle, total states that grid could be is !9/2 = 181,440. So you really need an optimal way to determine you are reaching towards the goal and without exploring unnecessary states.

There are 2 common h cost (it is known as Heuristic cost):

1. Number of misplaced tiles – you can count the number of tiles which are misplaced, for a particular sate. When you are into final sate, h = 0.
2. Sum of distances of the tiles from their actual positions (Manhattan distance) – sum of horizontal and vertical distances, for each tile.

2nd heuristic converges faster than the first one.

Implementation

1. You need to maintain the parent information to maintain the tree so that it can be backtracked.
2. Also, you need to maintain a list of open and closed nodes so that you won’t examine the one which have been examined earlier and avoid falling in loop.
3. You probably want to maintain the open nodes using Min Priority Queue data structure so that you can get the next state to examine quickly. It can be done without Min Priority Queue as well – but that would be too slow.
4. You also need Hash tables to quickly find closed / open nodes.

I have implemented this in C#. you need .Net 4.0 installed on your machine to run the application –

You can shuffle the arrangements and change the heuristic from the menu. On average, it’s taking ~44 seconds (using misplaced tiles heuristic) to tell if no solution exists for the arrangement (i.e. no way this puzzle can be solved).

One of my friends told me that it’s taking ~9 seconds to converge in this case, so I assume I have a pathetic system.

Code and executable can be downloaded from here – http://www.codeproject.com/Articles/616874/8-15-Puzzle-using-A-A-Star-Algorithm-Csharp

And last thing – I didn’t lie when I added 15 puzzle in the header. Same code can be used. In fact, you just need to change the grid from 3x3 to 4x4. But this is too slow for 15 puzzle.

15 puzzle can be in 10^13 states, which is too slow for A* algorithm to handle. There exists a better version of it; I will talk, when I have it.

Find sub-sequence within array with sum = 0

A few days ago, I have been given a problem to find the sub-sequence within an array with which has a total sum of 0. Within array A[1-N], you have to find i and j such that
 A[i] + A[i+1]... A[j] = 0; i <=j.

Ofcourse, the problem can be extended further to find the longest subsequence among all possible sub-sequences. Once you have the solution for first part, finding longest sub-sequence is no more a tricky job.


This is what I thought:

The idea is: If sum of elements from [i+1, j] is 0, then, after this subset, ith number would appear again at [j+1] position.



i.e. Sum(N[i] + N[i+1, j]) = N[j + 1], if N[i+1, j] = 0.


FindZeroSumSequence(Array):
{
   1. Sum elements such that ith index has sum up to [0 -i] elements
       For i = 1 to N
       Array[i] += Array[i -1]

   2. Find the first duplicate index from array
       EndIndex = FindFirstDuplicateIndex(Array)


   3. IF EndIndex > -1
       Find the First index with value equal to Array[EndIndex]
       For i = 0 to N
         IF(Array[i] == Array[EndIndex]
           StartIndex = i
           Break


   4. Return StartIndex and EndIndex as sub array indexes.
}


Running time of the algorithm is O(n) (though it slowly depends on the running time of FindFirstDuplicateIndex method which could be implemented in O(n) time).

Tail Recursion: Stack Optimization of Quick Sort

Following procedure implements QuickSort in recursive way –

QuickSort(Array, Left, Right)
{
If (Left >= Right)
{
Return
}
Else
{
Pivot <-- Partition(Array, Left, Right);

QuickSort(Array, Left, Pivot - 1);

QuickSort(Array, Pivot + 1, Right);
}
}

*Partition procedure mentioned above, rearranges the sub array Array[left..right]

Above procedure contains two recursive calls to itself. Once left sub array is recursively sorted and then right sub array is recursively sorted. This method demands for a stack space of ʘ(n).

To reduce the stack depth of the above method, second recursive call can be eliminated. This way we could get an optimization on stack depth without reducing the readability of the code.

QuickSort(Array, Left, Right)
{
If (Left >= Right)
{
Return;
}
Else
{
While(Left < Right)
{
Pivot <-- Partition(Array, Left, Right);

QuickSort(Array, Left, Pivot - 1);

Left <-- Pivot +1;
}
}
}

Stack depth of the modified version of QuickSort is ʘ(lgn).

Above optimization is called Tail recursion. Many compilers do this automatically for you. Unfortunately I could not see this optimization with C# compiler.

Using Types with same name and namespace from two different assemblies

Ocassionally, you may observe that one type is present in two different assemblies ( Say, MyClass is preseny in the assembes LibraryOne.dll and LibraryTwo.dll.). Using MyClass from both assemblies is not an issue as long as they belongs to two different name spaces i.e. if MyClass in LibraryOne.dll is in namespace LibraryOne.MyClass and MyClass in LibraryTwo.dll is in namespace LibraryTwo.MyClass, you can reference both assemblies together and use both classes in your project without any issues.

It becomes tricky (or may be ugly) when types from different assemblies share the same name and same namespaces. When you compile the application, your compiler gets confused and complains that type is found at two different places. Most of the tim,e this is not expected as it leads to a bad design. But sometimes you may find this situation unvoidable, for example, when you have to supoort backward compatibility in the application.
 Here are the steps to resolve the issue:
 1. Create Aliases for the assemblies:

• Open the references node in the visual studio and select the referenced assembly (LibraryOne.dll)
•  Right click and select properties
• In Aliases field, set an approprita aliase for the aseebmly.

 

 

• Similarly, set the alias for the second assembly

2. Use the Alias to specify the namepsace and type from a particular assembly:

• Refer the assembly alias on top of the class file using extern 

This way your compiler would know that it has to refer the Type which is defined in the assemlbly having alias LibVersion1 (i.e. LibraryOne.dll)

Deploying a Single EXE for the Application

Many applications consist of an EXE file that depends on many DLL files. When we deploy the application, all the files must be deployed on the client machine. If you want to deploy just a single EXE file instead of all depended DLL files, there is a way to achieve this. All the dependent DLLs can be embedded into the EXE file and then whole application can be deployed with a single EXE file.

For this, first you need to identify all the dependent DLLs which are not shipped with .Net framework. Add all the identified DLLs into your project and for each DLL file you add, open the properties page and change the its “Build Action” to “Embedded Resource”. This will instruct compiler to embed the DLLs into your EXE file, and you can deploy this one EXE file.

Structural Patterns - Adapter Pattern

Design Patterns help to make a system independent of how its objects are created, composed, and represented. These patterns become important when emphasis shifts away from
Hard-Coding a fixed set of behaviours toward defining a
smaller set of fundamental behaviours that can be composed in to any number of more complex ones. [GOF]

Pattern which defines the composition of classes and objects in the system to build the desired structure is known as Structural Pattern. Structural patterns define a way to combine two or more independent developed libraries. Developed libraries may differ in their implementation but can work for each other to produce the desired result without knowing the internal details.

For example, a particular Car model can make use of the cooling system to provide A/C feature though the cooling system is developed independent of the Car model.

One example of the structural pattern is Adapter pattern. Adapter pattern promotes the development of one interface to a particular implementation in order to provide uniform abstraction of different interfaces. Adapter pattern is particularly useful when you have two different classes with incompatible interfaces.

There are 3 entities to participate in the Adapter pattern. If a class wants to make use of an implementation, then these classes can be named as Target and Adaptee, respectively. The wrapper which provides the requested operations by the target using the implementation of the Adaptee is called Adapter. Below is the interaction diagram between Target, Adapter and Adaptee.

Implementation

Let’s take the example of Stack implementation.

Suppose Stack interface is exposed to the client to support stack data structure and operations. Now, there is a need to implement the Generic stack data structure. One possible approach is to use generic dictionary to implement generic stack. Generic dictionary is the class implemented in library to support generic and retrieval and storage of the items.

We can classify stack interface exposed to the client as Target and Dictionary class as an Adaptee. Create a wrapper class (GenericStack) which takes the responsibility to implement the stack operations using dictionary class. One of the possible implementation will follow the structure shown in the below image.

Code:

Stack Interface

internal interface IStack where T : IComparable { /// /// To Push Item in the Stack /// void Push(T item); /// /// Pop up the given item from the Stack /// T Pop(); /// To Pop up the item from the Stack T[] Pop(T item); } }

Generic Stack

/// This class defines Generic Stack. class GenericStack : IStack where T : IComparable { #region Fields private Dictionary<int, T> dicStackItemCollection; private Dictionary<int, int> dicItemKeyCollection; int iItemcount; #endregion Fields #region Properties #endregion Properties #region Methods public GenericStack() { iItemcount = 0; } /// /// To Push Item in the Stack /// /// public void Push(T item) { // Initialize Stack Item Collection - Deferred initialization if (dicStackItemCollection == null) { dicStackItemCollection = new Dictionary<int, T>(); dicItemKeyCollection = new Dictionary<int, int>(); } // Do Not Add Null items if (item != null) { dicStackItemCollection[iItemcount++] = item; dicItemKeyCollection[item.GetHashCode()] = iItemcount; } } /// /// To Pop up the item from the Stack public T Pop() { // Set Item to Its default value T item = default(T); // If Item exists, pop if (iItemcount > 0) { item = dicStackItemCollection[iItemcount - 1]; dicStackItemCollection.Remove(iItemcount - 1); iItemcount--; } return item; } /// /// Pop up the given item from the Stack /// Returns all removed items from the stack. /// /// /// public T[] Pop(T item) { T[] items = null; int itemKey; // If Item exists, pop if (iItemcount > 0 && IsItemExists(item, out itemKey)) { items = new T[itemKey - 1]; while (itemKey > 0) { // Get the Item from the Collection before removing it items[itemKey - 1] = dicStackItemCollection[itemKey]; // Remove item from the Collection dicStackItemCollection.Remove(itemKey--); } iItemcount = dicStackItemCollection.Count + 1; } return items; } /// /// To Get the Item from the collection /// private bool IsItemExists(T item, out int itemKey) { itemKey = -1; if (dicItemKeyCollection.ContainsKey(item.GetHashCode())) { itemKey = dicItemKeyCollection[item.GetHashCode()]; } return itemKey != -1; } #endregion Methods }

Client:

class Client { #region Fields private IStack<int> stack; #endregion Fields #region Properties #endregion Properties #region Methods public Client(IStack<int> stack) { this.stack = stack; } /// /// To Simulate Operations on Stack /// internal void DoSomeOperartions() { int item; Console.WriteLine("Push: 5"); stack.Push(5); Console.WriteLine("Push: 4"); stack.Push(4); item = stack.Pop(); Console.WriteLine("Pop: " + item); Console.WriteLine("Push: 3"); stack.Push(3); item = stack.Pop(); Console.WriteLine("Pop: " + item); item = stack.Pop(); Console.WriteLine("Pop: " + item); item = stack.Pop(); Console.WriteLine("Pop: " + item); } #endregion Methods }

Main Method:

class Program { static void Main(string[] args) { IStack<int> stack = new GenericStack<int>(); // Set Stack to the Client Client<int> client = new Client<int>(stack); // Ask client to do some operations client.DoSomeOperartions(); Console.ReadLine(); } }

** Please note that above implementation relies on the Hash code of the object in the stack. Results may be unpredictable if GetHashCode() method has been overridden in object’s type.