Tower of Hanoi solution using recursion in java

Tower of hanoi is one of the basic questions to learn recursion and very commonly asked interview question at beginner and intermediate level.

Section in this post:

1. Problem statement
2. Iterative solution
3. Alternate iterative solution
4. Recursive solution
5. Java Implementation

The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower, and sometimes pluralised) is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk.

 With three disks, the puzzle can be solved in seven moves. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2ⁿ - 1, where n is the number of disks.

Iterative solution

 

Alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it to the next position in the same direction (to the right if the starting number of pieces is even, to the left if the starting number of pieces is odd). If there is no tower position in the chosen direction, move the piece to the opposite end, but then continue to move in the correct direction. For example, if you started with three pieces, you would move the smallest piece to the opposite end, then continue in the left direction after that. When the turn is to move the non-smallest piece, there is only one legal move. Doing this will complete the puzzle in the fewest number of moves.

 

Simpler statement of iterative solution

 

Alternating between the smallest and the next-smallest disks, follow the steps for the appropriate case:
For an even number of disks:

• make the legal move between pegs A and B

• make the legal move between pegs A and C
• make the legal move between pegs B and C
• repeat until complete

For an odd number of disks:

• make the legal move between pegs A and C
• make the legal move between pegs A and B
• make the legal move between pegs C and B
• repeat until complete

In each case, a total of 2ⁿ-1 moves are made.

Equivalent iterative solution

 

Another way to generate the unique optimal iterative solution:

Number the disks 1 through n (largest to smallest).

• If n is odd, the first move is from the Start to the Finish peg.
• If n is even, the first move is from the Start to the Using peg.

Now, add these constraints:

• No odd disk may be placed directly on an odd disk.
• No even disk may be placed directly on an even disk.
• Never undo your previous move (that is, do not move a disk back to its immediate last peg).

Considering those constraints after the first move, there is only one legal move at every subsequent turn.

The sequence of these unique moves is an optimal solution to the problem equivalent to the iterative solution described above.

Recursive solution

 

A key to solving this puzzle is to recognize that it can be solved by breaking the problem down into a collection of smaller problems and further breaking those problems down into even smaller problems until a solution is reached. For example:

• label the pegs A, B, C — these labels may move at different steps
• let n be the total number of discs
• number the discs from 1 (smallest, topmost) to n (largest, bottommost)

To move n discs from peg A to peg C:

1. move n−1 discs from A to B. This leaves disc n alone on peg A
2. move disc n from A to C
3. move n−1 discs from B to C so they sit on disc n

The above is a recursive algorithm, to carry out steps 1 and 3, apply the same algorithm again for n−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. This step, moving a single disc from peg A to peg B, is trivial.

Below is my Java code to solve the problem recursively.

Class TowerOfHanoi:

public class TowerOfHanoi {

  public static void solveHanoi(int nTop, char fromTower, char midTower,
                              char toTower) {
    if (nTop == 1){
      System.out.println("Disk 1 from " + fromTower + " to " + toTower);
    }else {
      solveHanoi(nTop - 1, fromTower, toTower, midTower);
      System.out.println("Disk " + nTop + " from " + fromTower 
                 + " to " + midTower);
      solveHanoi(nTop - 1, midTower, fromTower, toTower);
    }
  }

  public static void main(String[] args) {
    int nDisks = 3;
    solveHanoi(nDisks, 'A', 'B', 'C');
  }
}

output :
===================================================================
Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C

Factorial of a number using recursion in Java

Java program to calculate factorial of integer using recursion


public class Factorial
{
     public int fact(int n) {
if(n==1) {
return 1;
}
else {
return  fact(n-1) * n;
}
    }

public static void main(String args[]){
       int number =4;
Factorial factorial = new factorial();
System.out.println("The factorial of the number is : " + factorial.fact(number);
     }
}

How to: Hard reset the NOKIA N900

Right now there is no direct way as with other Nokia mobile to hard rest Nokia N900

But it can be done following below mentioned steps. A word of caution, before hard resting your mobile don’t forget to back up all your mobile information like contacts, messages, notes etc. and also all the data from your 32 GB mobile storage  as after hard reset all data will be lost and your mobile will start as if it is starting first time.

I have tried the steps mentioned below on my Nokia N900 and it works fine, but there is absolutely no responsibility from my side if something goes wrong during hard reset process.  

That’s why it is highly advice to back up your data and finish all the steps mentioned below.

Although during my mobile’s hard reset I wasn’t able to finish all the steps myself as I downloaded wrong file ( :D happens many a times), and still no harm was made to my mobile. So just follow the steps and it will work fine J

                                                This tutorial is written to be used from a windows PC, but with slide changes it can be used from Linux based PC also. I will try to put one more tutorial on how to Hard reset NOKIA N900 using a Linux PC but for while it’s only indented for Windows PC

Step 1: Download flashing software

You need to download “Maemo Flasher”, it needs to be installed in computer to perform hard reset

http://tablets-dev.nokia.com/maemo-dev-env-downloads.php

The page will be somewhat like this.

From the list choose the appropriate version (In my first attempt I downloaded the wrong one and it gave me error when I used it)

The link is shown in Green rectangle box (Win Flasher_3.11.5.exe). Install the application after downloading.

Step 2: Image files for NOKIA N900

The file can be found here:

http://tablets-dev.nokia.com/nokia_N900.php

It will be something like this

In order to download the file, you will need to provide your device's 15-digit IMEI number and accept the end-user software agreement. How to find the IMEI number is given on top of the link itself.

There are two files  you need to download from there.

1.    eMMC content – This is the package to erase all data held on your 32GB storage.(For PR1.3 choose the one marked Latest)

2.    OS – This is your operating system.

There are multiple eMMC packages available, so download the Latest. At the time of writing this post it is PR1.3and It’s called:

RX-51_2009SE_10.2010.13-2.VANILLA_PR_EMMC_MR0_ARM.bin

The OS is a little more difficult to figure out which one you need.

The notes alongside the software lets you find the right package easier.

I found the best way to check is to do the following: (On the N900)

1.    Menu

2.    Settings

3.    About Product

This will show you this image (or similar)

Download the OS package that exactly matches your device. In my first attempt I downloaded the package for India region

RX-51_2009SE_20.2010.36-2.004_PR_COMBINED_004_ARM.bin (India)

Where I needed to use

RX-51_2009SE_20.2010.36-2.003_PR_COMBINED_003_ARM.bin (Middle East and North Africa)

Therefore just be a bit careful while downloading the exact file matching your device.

Step 3: Copy these to files in the installed “Maemo Flasher” folder.

If u have installed it in “c:\program files\maemo\flasher-3.5”, then put these two files in this folder

You should now have two .bin files in the directory above.

Step 4:Updating the NOKIA N900 OS

1.    Your battery should be as much as full as possible  to prevent any crashes which could leave your mobile dead.

2.    Turn your Nokia N900 off.

3.    Press and hold the U key on the keypad.

4.    Insert the USB cable, into a USB port, NOT a USB adapter. (A USB symbol should appear on the top right of your N900 screen, and also the Nokia logo in the centre).

5.    You can now let go of the U key.

6.    On your PC: Navigate to the Start Menu and select Maemo>Maemo Flasher 3.5>Maemo Flasher 3.5 or just go into the folder where “Maemo flasher” is install and run the exe directly.

7.    In the command window you should now see: C:\Program Files\maemo\flasher-3.5>

8.    Type: flasher-3.5 -F RX-51_2009SE_20.2010.36-2.002_PR_COMBINED_002_ARM.bin –f

The name of file might change according to region and version you downloaded. It’s a good practice to use tab for completing the name of file so u can get rid of trouble of writing name exactly

9.    You should see something like this on your terminal

10.   

Your personal data, such as Contacts, Images, SMS will still be on the device.
So if you want to remove these as well, follow the next steps.

10. Do not disconnect or reboot the device the device. Just leave as is for now.

Step 5: Resetting the Mass Memory

Type in the command window:

flasher-3.5 -F RX-51_2009SE_10.2010.13-2.VANILLA_PR_EMMC_MR0_ARM.bin -f –R

Again the name of file might change according to region and version you downloaded.

This image below shows the completed reset of the eMMC (32GB HDD), in the command prompt on your PC.

This would have now removed any data you had stored there. Including Music, Photos, Contacts, SMS.

This completes the hard reset procees of your N900. You will get the restart screen on your mobile. If it is not restarting then restart it manually and u will get configuration screen on your mobile which u get on first run

Congratulation!!!!!!!!! You have successfully hard reset your Nokia N900