Thursday Code Puzzler: Solve the Towers of Hanoi

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--;
				}
			}
		}
	}
}

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.

 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]);
    }
}

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("");
		}
	}
}