ஹானொய் இன் கோபுரம் (Tower of Hanoi)

ஹனோய் கோபுரம் அறிமுக கணினி அறிவியலில் ஒரு சிறந்த பிரச்சனை. (Tower of Hanoi is a classic introductory computer science problem) see: http://en.wikipedia.org /wiki/Tower_of_Hanoi

பிரச்சனை நோக்கம், பின்வரும் நிலைமைகளின் கீழ், அச்சு # 3 மது # 1, முதல் வட்டுகள் அனைத்து நகர்த்த உள்ளது

R1: ஒரு சிறிய வட்டு பெரிய வட்டு மேல் உட்கார முடியாது
R2: நீங்கள் தற்காலிக அச்சு இரண்டு அச்சு ஏதாவது பயன்படுத்தலாம்
R3: நீங்கள் செய்ய முடியும் நகர்வுகள் எண்ணிக்கை இல்லை

Goal of the problem is to move all of disks from peg #1, to peg #3, under the following conditions,

  1. R1: Only a smaller disk can sit on top of the larger disk
  2. R2: You may use any of two pegs as temporary store
  3. R3: There is no limit on number of moves you can make
Tower of Hanoi (Ref: http://en.wikipedia.org/wiki/Tower_of_Hanoi)
Tower of Hanoi
(Ref: http://en.wikipedia.org/wiki/Tower_of_Hanoi)

How can you solve this problem ?

  1.  Let us reduced the size of the problem to 1 disk on the peg #1.
  2. We can make a drawing like [1,0,0].
  3. We can simply move the disk 1 from peg #1 to peg #3, and we have completed the problem!
  4. That was easy. [0,0,1].
  1. For 2 disks how do you solve it?
  2. We initially have [1 2, 0, 0]. we want to get to [0,0,1 2]
  3. By moving smaller disk 1 from peg #1, to peg #2, we have [2, 1, 0].
  4. Now your situation is same as problem with 1-disk on peg #1, and 1-disk on peg #2 which we will ignore temporarily.
  5. Next we can move either of disks from peg #1 or peg #2 to peg #3. However the rule, R1, requires us to move the peg #1 disk as it is the larger disk and it should go at bottom.
  6. Now your configuration is like, [0,1,2]
  7. Clearly the final step is to move disk #1 from peg #2 to peg #3, on top of the existing disk #2. Now your configuration is [0,0,1 2]. Solved!

So what does the general solution look like, for n-disks? Well the problem has a dynamic-programming structure, where solving smaller problems, inductively, leads to solution of the larger problem.

  1. Here, you need to move all n-1 smaller disks from peg #1 to peg #2,  and to do that, you will use peg #3 as temporary.
  2. Once you have achieved this, you have to move disk-n from peg #1 to peg #3.
  3. Now move (1,2, … n-1) disks from peg #2 to peg #3 using the peg #1 as intermediate.

This is a recursive solution and harder to visualize at first reading, but you will eventually get the hang of it.

Move 1,2,3 disks from peg #1 to peg #2, with peg #3 as intermediate. Move disk 4 from peg #1 to peg #4. Then move all disks from peg #2 to peg #3 using peg #1 as intermediate.
Move 1,2,3 disks from peg #1 to peg #2, with peg #3 as intermediate. Move disk 4 from peg #1 to peg #4. Then move all disks from peg #2 to peg #3 using peg #1 as intermediate.

The follow program describes the Ezhil program solution to Tower of Hanoi problem,

# (C) 2013 Ezhil Language Project
# Tower of Hanoi – recursive solution

நிரல்பாகம் ஹோனாய்(வட்டுகள், முதல்அச்சு, இறுதிஅச்சு,வட்டு)

@(வட்டுகள் == 1 ) ஆனால்
பதிப்பி  “வட்டு ” + str(வட்டு) + “ஐ \t  (” + str(முதல்அச்சு) + ”  —> ” +  str(இறுதிஅச்சு)+ “) அச்சிற்கு நகர்த்துக.”
இல்லை

@( [“இ”, “அ”,  “ஆ”]  இல் அச்சு ) ஒவ்வொன்றாக
@( (முதல்அச்சு != அச்சு)  && (இறுதிஅச்சு  != அச்சு) ) ஆனால்
நடு = அச்சு
முடி

முடி

# solve problem for n-1 again between src and temp pegs                      ஹோனாய்(வட்டுகள்-1, முதல்அச்சு,நடு,வட்டுகள்-1)

# move largest disk from src to destination
ஹோனாய்(1, முதல்அச்சு, இறுதிஅச்சு,வட்டுகள்)

# solve problem for n-1 again between different pegs
ஹோனாய்(வட்டுகள்-1, நடு, இறுதிஅச்சு,வட்டுகள்-1)
முடி
முடி

ஹோனாய்(4,”அ”,”ஆ”,0)

Try this program online, at, ezhillang.org Alternative solution by @tshrinivasan can be found towers_of_hanoi.n

Solution is illustrated in Fig. 2, with following output,

வட்டு 1ஐ       (அ  —> இ) அச்சிற்கு நகர்த்துக.
வட்டு 2ஐ       (அ  —> ஆ) அச்சிற்கு நகர்த்துக.
வட்டு 1ஐ       (இ  —> ஆ) அச்சிற்கு நகர்த்துக.
வட்டு 3ஐ       (அ  —> இ) அச்சிற்கு நகர்த்துக.
வட்டு 1ஐ       (ஆ  —> அ) அச்சிற்கு நகர்த்துக.
வட்டு 2ஐ       (ஆ  —> இ) அச்சிற்கு நகர்த்துக.
வட்டு 1ஐ       (அ  —> இ) அச்சிற்கு நகர்த்துக.
வட்டு 4ஐ       (அ  —> ஆ) அச்சிற்கு நகர்த்துக.
வட்டு 1ஐ       (இ  —> ஆ) அச்சிற்கு நகர்த்துக.
வட்டு 2ஐ       (இ  —> அ) அச்சிற்கு நகர்த்துக.
வட்டு 1ஐ       (ஆ  —> அ) அச்சிற்கு நகர்த்துக.
வட்டு 3ஐ       (இ  —> ஆ) அச்சிற்கு நகர்த்துக.
வட்டு 1ஐ       (அ  —> இ) அச்சிற்கு நகர்த்துக.
வட்டு 2ஐ       (அ  —> ஆ) அச்சிற்கு நகர்த்துக.
வட்டு 1ஐ       (இ  —> ஆ) அச்சிற்கு நகர்த்துக.

I hope you had fun!

One thought on “ஹானொய் இன் கோபுரம் (Tower of Hanoi)”

  1. ஆஹா! இதுபோல நம் ஊர்ப் பல்லாங்குழி ஆட்டத்தை “எழில்” மொழியின்வழியே எழுதிப் பார்க்கலாமே 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s