Generalized Tower of Hanoi - K Pegs, N Disks

I recently found online that Facebook is giving a fast track job opportunity for those who would solve a specific problem which may be a little more complex than a simple interview question. The process happens online - you login with your Facebook id and have a specific amount of time to write a solution in the language you desire. Here's the url in case you want to try it. They also provide a sample problem and an allotted 45 minutes to solve it. The problem is the well known Tower of Hanoi puzzle but generalized to k pegs and n disks. Given an initial and final configuration of the pegs you have to output the minimal number of steps needed to reach the final configuration. To make it easier they bound the k and n to 1 <= n <= 8, 3 <= k <= 5 and let you assume that there's a solution that takes at least 7 steps.

One basic approach here is brute forcing all possible configurations which results in an undirected graph. And how do you find something in a graph ? Using a search strategy - in my case I chose Breath-First Search.

Before going into the details of this approach let's see what other approaches we can find. Brute forcing will generate in the worst case 5^8 (390625) different configurations and then we'll have to search through them. Is there any other way where we wouldn't do a brute force, but go through the minimal path the first time? It seems like we could use different strategies of navigating through the pegs of a Hanoi Tower. There's basically 3 configuration cases that will take different approaches in navigation. Those are n < k, n=k and n > k. The point is there's a specific move pattern for each of these cases, that you could do to achieve the desired configuration. This article goes into much detail on that. There's also the way of multi-threading - we could parallelize this in some way - for example we could start from both ends.

I chose the brute force this time. While coding this approach a few problems may arise; mainly the problem of how would you represent the pegs. I chose to use a byte array, where each cell represents a peg and each bit of a peg represents a disk (if set).


Code looks like this:

Note:
The findLowestBitSet method basically returns the number of trailing zeros. In Java there's a util method for that:

The method could be optimized to look like this: