I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Solve the Towers of Hanoi

04.19.2012
| 7295 views |
  • submit to reddit

Another Thursday, another puzzle. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you think is suitable. Last week we got some great answers with Fabie, Christian and Francesco giving pretty detailed answers - thanks for participating guys. 

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Towers of Hanoi 

Let's go for another classic computer science coding problem, the Towers of Hanoi.  The objective is to move the entire stack to any other rod, obeying these rules: 

  • Only one disk can be moved at a time
  • Each move consists of taking the upper disk from one rod, adding it onto another rod, on top of any disks that you may have already placed on that rod.
  • But no disk can be placed on top of a smaller disk

There's a few different ways to achieve this. If you wish, you can express the efficiency of the algorithm you come up with using Big O notation.

Tags:

Comments

Liam Knox replied on Thu, 2012/04/19 - 12:04pm

in SCALA it is 0.356 charaters lss

Mike P(Okidoky) replied on Thu, 2012/04/19 - 9:29pm

Ok, I couldn't help myself. I swear I have not researched or investigated or looked for anything written on this even once. There probably is a neat little trick that does it much easier than what I'm doing here. What I'm doing is a brute force mechanism that iterates through every possible move, with checks to prevent going in circles or going down redundant paths. Given that only smaller discs can sit on larger discs, it lends to an opportunity to represent a collection of discs on a peg in a binary form. Disc of size one is represented by bit 0. Disc of size 8 is represented by bit 7 (right to left starting at 0). Any combination stack of 0 to 8 discs fits in 8 bits. To find the smallest disc in a collection, I'm using a trick to find the LSB (least significant bit): lsb = i ^ i & i - 1. To consider moving the top disc from one peg to another peg, the source peg must be non-empty, and the destination peg can be either empty, or have a larger disc to move the disc on top of. Calculate the lsb of both before doing a comparison.

This isn't fully optimized. Maybe it could be more efficient by representing the discs in a reverse bit pattern. I'm just plunking down what I've hacked up.

public class Hanoi
{
	// Represent set of discs in binary form, where each disc is a bit, and the bit number represents the size of the disc (higher is larger disc).
	//
	private static final int
		N_PEGS = 3,		// 3 pegs by default
		N_DISCS = 8,		// 8 discs stacked on a peg by default
		DISC_SET = (1 << N_DISCS) - 1;		// full set of discs on a peg, 1 bit per disc, eg. 8 discs -> 255
	
	public static void main(String[] args)
	{
		System.out.println("Hanoi");
		
		new Hanoi().go();
	}
	
	private int _pegs[] = new int[N_PEGS];
	
	// A boolean for every disc combination, helping us prevent walking routes where we've already been.
	//
	private int _discCollections[] = new int[1 << N_PEGS * N_DISCS];
	
	// A trace of the moves we're making, so that we can report it when we see a full stack of discs on one of the other pegs
	//
	private int _moves[] = new int[1024], _move, _bestMoves[];
	
	public void reset()
	{
		_pegs[0] = DISC_SET;
		for (int x = 1; x < N_PEGS; x++)
		{
			_pegs[x] = 0;
		}
	}
	
	public void print()
	{
		int renderedPegs[][] = new int[N_PEGS][N_DISCS];
		for (int x = 0; x < N_PEGS; x++)
		{
//			System.out.print("\t" + _pegs[x]);
			for (int discs = _pegs[x], y = N_DISCS, n = N_DISCS; n > 0; n--)
			{
				if ((discs & 1 << n - 1) != 0)
				{
					renderedPegs[x][--y] = n;
				}
			}
		}
//		System.out.println("\n");
		for (int y = 0; y < N_DISCS; y++)
		{
			for (int x = 0; x < N_PEGS; x++)
			{
				int d = renderedPegs[x][y];
				if (d != 0)
					System.out.print("\t" + renderedPegs[x][y]);
				else
					System.out.print("\t|");
			}
			System.out.println();
		}
		System.out.println("----------------------------");
	}
	
	public void go()
	{
		System.out.println("Number of pegs is " + N_PEGS);
		System.out.println("Number of discs on the first peg to start is " + N_DISCS);
		reset();
		play();
		System.out.println("Best number of moves found was " + _bestMoves.length);
		
		reset();
		print();
		
		for (int i = 0; i < _bestMoves.length; i++)
		{
			int x = _bestMoves[i] & DISC_SET, x2 = _bestMoves[i] >> N_DISCS;
			int discs = _pegs[x];
			int disc = discs ^ discs & discs - 1;	// least significant bit is the smallest, top, disc
			_pegs[x] &= ~disc;
			_pegs[x2] |= disc;
			print();
		}
	}
	
	private void play()
	{
		// going to try to move disc of each peg
		//
		for (int x = 0; x < N_PEGS; x++)
		{
			int discs = _pegs[x];
			
			// if no disc on peg, then skip
			//
			if (discs == 0)
				continue;
			
			// if full set of discs on peg other than the first one, we've completed the move
			//
			if (x > 0 && discs == DISC_SET)
			{
				// report the results
				//
//				System.out.println(_move + " moves");
//				print(_pegs);
				
				// These are the best moves if this is the first successful solution, or if this solution is better than the recorded one.
				//
				if (_bestMoves == null || _move < _bestMoves.length)
				{
					_bestMoves = new int[_move];
					System.arraycopy(_moves, 0, _bestMoves, 0, _move);
				}
				
				// this route is done
				//
				return;
			}
			
			if (_bestMoves != null && _move >= _bestMoves.length)
			{
				// If we're doing worse than the current best number of moves, then give up this route
				//
				return;
			}
			
			// find peg to move disc to
			//
			for (int x2 = 0; x2 < N_PEGS; x2++)
			{
				// don't move disc to same peg
				//
				if (x2 == x)
					continue;
					
				int discs2 = _pegs[x2];
				
				// trick to get least most significant bit, which happens to represent the bit of the top most disc on the stack
				//
				int disc = discs ^ discs & discs - 1, disc2 = discs2 ^ discs2 & discs2 - 1;
				
				// move to peg if it has no discs or has a larger top disc
				//
				if (discs2 == 0 || disc < disc2)
				{
					// move disc to other peg
					//
					_pegs[x] &= ~disc;
					_pegs[x2] |= disc;
					
					// track move
					//
					// make room if needed
					//
					if (_move == _moves.length)
					{
						int moves[] = new int[_move * 2];
						System.arraycopy(_moves, 0, moves, 0, _move);
						_moves = moves;
					}
					_moves[_move++] = x | x2 << N_DISCS;
					
					// Prevent going in circles, only go where no disc collection has gone before.
					// This prevents continuing on a path we're already handling further up the stack.
					// Calculate a signature that's unique to the current disc positions.
					//
					int discCollection = _pegs[0];
					for (int z = 1; z < N_PEGS; z++)
					{
						discCollection = discCollection << N_DISCS | _pegs[z];
					}

					// Continue searching this path if we haven't seen this disc collection before, or if the number of moves is better than when we've recorded this disc collection before
					//
					if (_discCollections[discCollection] == 0 || _move < _discCollections[discCollection])
					{
						_discCollections[discCollection] = _move;
						play();
					}
					
					// Move disc back.
					// This in favor of making copies.
					//
					_pegs[x] |= disc;
					_pegs[x2] &= ~disc;
					
					// roll back trace of moves
					//
					_move--;
				}
			}
		}
	}
}

Mike P(Okidoky) replied on Thu, 2012/04/19 - 9:34pm

ps. could someone finally tell me what is the best way to copy-paste code? I'm using the code and pre tags. Isn't there a custom source tag that makes it format nicely?

Mitch Pronschinske replied on Fri, 2012/04/20 - 6:48am in response to: Mike P(Okidoky)

Sure.  Just copy your code.  Hit the little icon in the rich text tools above where you're typing the comment (should appear in FF and Chrome) and then paste the code into the window that pops up.  Before you hit insert, make sure you change the dropdown at the top of the little window to the language that you're pasting.

Mike P(Okidoky) replied on Fri, 2012/04/20 - 8:54am in response to: Mitch Pronschinske

Hi Mitch, I'm using Chromium on Linux. The text area is a normal html text area and not a rich text editor. All I'm seeing for options is the "Allowed HTML tags" below the text area. If only one of those would make a block format source code nicely...

Thierry Bodhuin replied on Sat, 2012/04/21 - 10:41am

 The best way to solve this problem is to use recursion.

My program use a supporting class (that could be better done also with a Java interface with an implementing class) to visulaize the move and state of the hanoi towers.

The Towers class does the algorithm, where the constructor takes the number of disks in the first tower (usually 7).

 

Hope it helps.

 

package it.atechsense.hanoi;
/**
*
* @author Thierry BODHUIN (bodhuin@gmail.com)
*/
public class Towers { private int nDisks;
private TowerDisplay td; public Towers(int nDisks) {
this.nDisks = nDisks;
td = new TowerDisplay(nDisks, 1);
} public void solveIt() {
solveIt(nDisks, 1, 3);
} private void solveIt(int nDisks, int source, int target) {
if (nDisks <= 0) {
return;
}
int holdingTower = getHoldingTower(source, target);
solveIt(nDisks - 1, source, holdingTower);
td.displayMove(source, target);
solveIt(nDisks - 1, holdingTower, target);
} private int getHoldingTower(int source, int target) {
return (6 - source - target);
} public static void main(String argv[]) {
Towers t = new Towers(7);
t.solveIt();
}
--------------------
package it.atechsense.hanoi;

/**
 *
 * @author Thierry BODHUIN (bodhuin@gmail.com)
 */
public class TowerDisplay {

    private String[] tower;
    private int count = 0;

    public TowerDisplay(int nDisks, int source) {
        if (nDisks > 9) {
            nDisks = 9;
        }
        tower = new String[4];
        tower[1] = "";
        tower[2] = "";
        tower[3] = "";
        tower[source] = "123456789".substring(0, nDisks);
    }

    public void displayMove(int from, int to) {
        count++;
        System.out.println("MOVE(" + count + ") from " + from + " to " + to);
        int fromLast = tower[from].length() - 1;
        tower[to] = tower[to].concat(tower[from].substring(fromLast));
        tower[from] = tower[from].substring(0, fromLast);
        System.out.println("   tower 1:" + tower[1]);
        System.out.println("   tower 2:" + tower[2]);
        System.out.println("   tower 3:" + tower[3]);
    }
}

Mike P(Okidoky) replied on Mon, 2012/04/23 - 10:19am in response to: Thierry Bodhuin

Thierry, "@author", really?

http://www.google.ca/search?q=%22towers.java%22+hanoi

Quite an off-the-shelf algorithm, I'd say.

Manuel Lima replied on Fri, 2012/06/01 - 11:13pm in response to: Mike P(Okidoky)

My solution: 
 
public class TowersOfHanoiSolver {

	private static String[] buildPositions(int sticks) {
		String[] positions = new String[sticks*2];
		for(int i = 0, j = sticks*2-1; i < sticks; i++, j--) {
			positions[i] = positions[j] = "" + (i + 1);
		}
		return positions;
	}

	public static void main(String[] args) {
		int sticks = 3;
		int discs = 6;

		String[] positions = buildPositions(sticks);

		int cycles = (int) Math.pow(sticks, discs);
		int[] divisors = new int[discs];

		for (int i = 0; i < discs; i++) {
			divisors[i] = (int) Math.pow(sticks, i);
		}

		for (int i = 0; i < cycles; i++) {
			System.out.printf("%d: ", i);
			for (int j = 0; j < discs; j++) {
				System.out.printf("d%d-%s ", j + 1, positions[i / divisors[j] % (sticks * 2)]);
			}
			System.out.println("");
		}
	}
}

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.