tower of Hanoi

[ycsim]

Does anybody have any source code for this mathematical question...

it can be in any programming languages (preferably Java, C or C++)....

[Fox]

mhm... what IS this mathematical question?

[Sam Finch]

What do You Mean The Source Code?

I Can Give You The Answer, For N disks on 3 Pegs the minimum number of moves is (2^N)-1

If you need to Proove that look up Proof By Induction.

for 1 Disk it Requires 1 Move (2^1)-1 = 1

consider the Formula holds true For K disks, we try to move K+1 Disks

First we Must move K disks to the Middle Post, then we must move the Final disk to the Last Post then move the K disks on top of the Final Disk

Hence we Need
((2^K)-1)+ 1 + ((2^K)-1)

= ((2^K)+(2^K)) +1 - 2

= (2^K+1) - 1

so If is Holds for K disks it must hold for K+1 disks.

as it holds for 1 it must hold for 2, therefore must hold for 3 etc.

ThereFore The Formula ((2^N)-1) holds for any Integer N


If you use More than 3 Pegs it gets Much Much Harder.

[ycsim]

i want to solve the tower of hanoi programmatically....

sorry for the unclear explanation....

thx

thank you sam!!
I have tower of hanoi game and I could get to about 5 disks, then I couldnt do it anymore...
well I could but I was too lazy to try to figure out

I didnt make the game, but if anybody wants it, I wiill be glad to email it or post in on my website(it was freeware, so this is legal).

[Sam Finch]

This is a Visual Basic Forum, So you'll get a Visual Basic answer.

You need a Form, With one Commandbutton, called cmdNext
and a Controll array of Listboxes, Called lstPeg, you need 3, with indexes 1 to 3.

then add this Code

Option Explicit

Dim collPegs(1 To 3) As New Collection

Dim boolContinue As Boolean

Private Const DISKS = 4


'This Handles Moving a Disk Between Collections
Private Sub MoveDisk(FromPeg As Integer, ToPeg As Integer)
Call AddDisk(ToPeg, GetDisk(FromPeg))
Call RefreshPegs 'RefreshPegs lists and wait
End Sub


Private Function GetDisk(FromPeg As Integer) As Integer

    GetDisk = collPegs(FromPeg).Item(collPegs(FromPeg).Count)
    collPegs(FromPeg).Remove (collPegs(FromPeg).Count)

End Function

Private Sub AddDisk(ToPeg As Integer, DiskNo As Integer)

    collPegs(ToPeg).Add DiskNo

End Sub



Private Sub cmdNext_Click()
boolContinue = True
End Sub

'This Fills The Listboxes with the Collections
'and waits for the user to hit the next button
Private Sub RefreshPegs()
Dim v As Variant
Dim i As Integer

'Fill out the ListBoxes with the Current Pegs
For i = 1 To 3

    lstPeg(i).Clear
    
    For Each v In collPegs(i)
    
        lstPeg(i).AddItem v
        
    Next v
    
Next i

'Wait until The User Clicks the Next Button
Do Until boolContinue
    DoEvents
Loop
boolContinue = False
End Sub

Public Function OtherPeg(Peg1 As Integer, Peg2 As Integer)
Dim i As Integer

For i = 1 To 3

    If Not (Peg1 = i Or Peg2 = i) Then
    
        OtherPeg = i
        Exit Function
        
    End If
    
Next i
    
End Function

Public Sub MoveDisks(FromPeg As Integer, ToPeg As Integer, NoOfDisks As Integer)

'If we're moving just 1 disk
If NoOfDisks = 1 Then

    Call MoveDisk(FromPeg, ToPeg)
    Exit Sub
    
End If


'move all disks except 1 to the peg we're not moving to
Call MoveDisks(FromPeg, OtherPeg(FromPeg, ToPeg), NoOfDisks - 1)

'move one Disk to the Peg We Want to move it to
Call MoveDisk(FromPeg, ToPeg)

'move the rest of the Disks  to the target peg
Call MoveDisks(OtherPeg(FromPeg, ToPeg), ToPeg, NoOfDisks - 1)

End Sub



Private Sub Form_Load()
Dim i As Integer

'stack some disks onto peg 1
For i = DISKS To 1 Step -1

    Call AddDisk(1, i)

Next i

Me.Show

Call RefreshPegs

Call MoveDisks(1, 3, DISKS)
MsgBox "Finished"

End Sub

This is a Demonstration of the logic, so It only does it once, the MoveDisks Sub is Where the Majic Happens, the MoveDisk sub waits for you to press the Command button.

The Recursive Idea of the Lojic is what's important, So I don't know how you'd do it without something like DoEvents, but I'm sure there's a way round it.

[RohanWest]

Hi there, i made a solution in Pascal, it could very easily made in to C++, i could send it to you if you want....

Rohan

[ycsim]

rohan,

i would be very glad if you could send me that too...