ஹானொய் இன் கோபுரம் (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!

Published by

ezhillang

எழில் மொழி அறக்கட்டளை, தமிழில் திற மூல (opensource) கருவிகளை உருவாக்குவதும், அறிவியல், கணிமை துறைகளில் சிந்தனைகளை பகிர்வதும் இரண்டாவது குறிக்கோள்.

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