The standard Tower of Hanoi game is with 3 towers and we need to move all discs from one tower to another. This post provides a flavor of same puzzle but with more than 3 towers and given an initial configuration, we need to find the minimum moves required to go to a target configuration.
Problem
We will be given the discs with radius 1 to N, towers (K), an initial configuration and target configuration. We need to calculate the minimum number of moves we need to make to get to the target configuration starting from initial configuration.
Few rules:
- N discs – there are N discs each with radius of 1 to N
- K towers
- Disc with radius R can be added to the tower if and only if it is empty or the top disc’s radius is < R
- 1<= N<=8 and 3<= K<=5 – these constraints help us in building a more practical algorithm
- Read the input from STDIN – System.in and print the output to STDOUT – System.out
Input format
- First line consists of two integers N and K with space delimited
- 2nd line consists of initial configuration. It is provided as space delimited integers where index is the disc radius and the number at that index is the tower it contains
- 3rd line consists of target or desired configuration. It is provided in the same initial configuration.
Sample Input
6 4
4 2 4 3 1 1
1 1 1 1 1 1
Here,
- N=6 (discs) and K=4 (towers)
- Initial configuration is “4 2 4 3 1 1”
- Tower 1 have 6 and 5 discs
- Tower 2 have disc 2
- Tower 3 have disc 4
- tower 4 have 3 and 1 discs
- Target configuration is “1 1 1 1 1 1”
- all discs from 6 to 1 are on tower 1
Following diagram depicts the source and target Tower of Hanoi configurations. Note that the discs are not according to the radius, but they are color coded to represent appropriate radius for simplicity.
Output format
- 1st line should be the minimum number of moves required to get to target configuration from initial configuration
- From 2nd line, print from and to tower for a given move. “4 3” – means a disc is moved from 4th tower to 3rd tower
Sample output
Following is the output for above given sample input.
5
3 1
4 3
4 1
2 1
3 1
Here,
- 5 – minimum number of move to get to target configuration
- Then each line consists of from and to towers for each of those 5 moves. For example, “3 1” represents a disc is moved from tower 3 to 1
Solution
There are different ways to solve this problem. Here we will discuss a simple and object oriented approach. We can model this solution as follows.
- This can be solved using a Breadth-First-Search (BFS). Why BFS? It is the best way to travel a level by level and find the shortest path from a given node to target node
- Consider the initial configuration as the starting node
- Then get all of its neighboring nodes – all possible legal configuration we can get from current configuration and repeat this step until we reach target configuration or the graph is exhausts
- Towers can be easily represent as a Stack
- Node contains K towers – it represents a configuration
In Java
Following is the full java implementation of the above approach. Please leave your feedback in comments section.
package com.sada.puzzles;
import com.sada.puzzles.TOH.Node.Move;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;
/**
*
* @author Sada Kurapati <sadakurapati@gmail.com>
*/
public class TOH{
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
//towers initial config
Node source = readPegsConfiguration(k, n, sc);
//read target configuration
Node target = readPegsConfiguration(k, n, sc);
//To keep track what config we visited and avoid cycles
Set visited = new HashSet();
try {
minMovesToTarget(source, target, visited);
} catch (Exception ex) {
System.out.println("Exception = " + ex);
}
}
private static void minMovesToTarget(Node source, Node target, Set visited) throws CloneNotSupportedException {
//Perform BFS
//add source node to Queue
Queue q = new LinkedList();
q.add(source);
Node current = source;
while (!q.isEmpty()) {
current = q.poll();
if (current.equals(target)) { //found the target configuration
break;
}
List neighbors = current.neighbors();
if (neighbors.size() > 0) {
for (Node n : neighbors) {
if (!visited.contains(n)) {//if not visited, put it in queue
q.offer(n);
visited.add(n);
}
}
}
}
//Printing path and moves if target config found
if (current.equals(target)) {
printOutput(current);
}
}
private static Node readPegsConfiguration(int k, int n, Scanner sc) {
Stack[] initialState = new Stack[k];
for (int i = 0; i < k; i++) {
initialState[i] = new Stack();
}
//reading and reversing the line as we need to put the elements in decresing size
//disc is key and tower is value.
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(Collections.reverseOrder());
for (int i = 0; i < n; i++) {
map.put(i, sc.nextInt());
}
//prepare towers
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
initialState[entry.getValue() - 1].push(entry.getKey());
}
return new Node(initialState);
}
static void printOutput(Node target) {
Stack stack = new Stack<>(); //using stack as we need to print the trail from Source - target config
while (target.parent != null) {
stack.add(target.move);
target = target.parent;
}
System.out.println(stack.size());
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
static class Node implements Cloneable {
//towers
Stack[] state = null;
Node parent = null; //for backtracking trail
Move move = null; // The move we made to go to next neighbor config
public Node(Stack[] st) {
state = st;
}
@Override
protected Node clone() throws CloneNotSupportedException {
Stack[] cloneStacks = new Stack[state.length];
for (int i = 0; i < state.length; i++) {
cloneStacks[i] = (Stack) state[i].clone();
}
Node clone = new Node(cloneStacks);
return clone;
}
//returns the neghboring configurations.
//What all configurations we can get based on current config.
public List neighbors() throws CloneNotSupportedException {
List neighbors = new ArrayList<>();
int k = state.length;
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
if (i != j && !state[i].isEmpty()) {
//Need to clone to avoid change the parent node.
//Hint - in java, objects are not mutable and they are references
Node child = this.clone();
//make a move
if (canWeMove(child.state[i], child.state[j])) {
child.state[j].push(child.state[i].pop());
//this is required to backtrack the trail once we find the target config
child.parent = this;
//the move we made to get to this neighbor
child.move = new Move(i, j);
neighbors.add(child);
}
}
}
}
return neighbors;
}
public boolean canWeMove(Stack fromTower, Stack toTower) {
boolean answer = false;
if (toTower.isEmpty()) {// if destination tower is empty, then we can move any disc
return true;
}
int toDisc = toTower.peek();
int fromDisc = fromTower.peek();
if (fromDisc < toDisc) { //we can only place small disc on top
answer = true;
}
return answer;
}
@Override
public int hashCode() {
int hash = 7;
return hash;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final Node other = (Node) obj;
if (!Arrays.deepEquals(this.state, other.state)) {
return false;
}
return true;
}
class Move {
int towerFrom, towerTo;
public Move(int f, int t) {
towerFrom = f + 1;
towerTo = t + 1;
}
@Override
public String toString() {
return towerFrom + " " + towerTo;
}
}
}
}
Sada Kurapati 