4/25/2023 0 Comments Hanoi towers big oh proof![]() The WebMonks maintain it is true and will refine the proof to convince the non-believers. This has been rejected (or rather non-accepted) by the mathematical guardians of the tower. The proposed proof depends critically on the statement highlighted in blue below. The number of moves, based on structural arguments, and then show that this is achievable. The approach is to develop a formula for a lower bound for This section develops and proposes a proof for a formula for the number of moves required to solve the general Towers of Hanoi problem. įor those interested in the maths related to the Towers of Hanoi, an excellent tome discussing all facets of the topic is. Application of this paper in a physics context is discussed in. Symmetry arguments show that it does (as assumed by the 'presumed optimal' solution). However,įor the less-generalised (normal) problem, In the context of 3 pegs, he stated in that the solution does not always require that the base disc only moves once. Hinz (a prolific contributor to the Towers of Hanoi problem) introduced an interesting input to the 'even more generalised' Towers of Hanoi where the initial ![]() This is is not explored further, though its consequences can be seen on the 'Animate' pageĪ. 'off' the base disc is not necessarily the partition used to move 'on' the destination disc. The Frame-Stewart solution acknowledges that there are (generally) a number of partitions that are minimal thus the partition used for moving To achieve it is probably more interesting to most people.Ī hint when checking references/links is to verify whether the document is addressing 'the solution' or commenting on 'the presumed solution'.īecause of the looseness of definitions and assumptions, a useful link which ties things down is The problem as stated is to find the number of moves, though the algorithm used Note that the original paper uses 'washers' for what we denote as 'discs'. This missing lemma, ie that the assumption generates an optimal solution, was noted by the journal editor and has not been proved since - hence the 'presumed' bit. Is obtainable by moving the top n k discs to a new disc (for a suitable value of n k) then optimally moving the remaining discs to the destination peg and moving The solutions depend on the assumption that an optimal solution It addresses broadly equivalent solutions by Frame and Stewart. The 'presumed optimal' solution was given in a paperīack in 1941 addressing the problem posed in 1939. Than our favourite value of p, which is 5. The particular case where p = 4 is called the Reve's puzzle, but is no more special The generalised Towers of Hanoi problem concerns moving multiple discs using p ≥ 3 pegs. This is currently predicted to be early in 2038. When the animation is complete, the epoch of the internet will end. Here, Urban Legend has it that a number of WebMonks are watching (in shifts) theĪnimation you can see on the 'Animate' tab but with 32 discs on 3 pegs going really, really fast. However, of more relevance to the current generation is the e-Towers of Hanoi legend. Legend has it that a bunch of monks are moving a physical tower of 64 discs from one of three pegs to another when they finish, the world will end. Move everything else from the swap to the goalīecause it's bottom-up, you have to give the list starting with the bottom-most disc.The basic Towers of Hanoi problem is moving multiple discs on three pegs - there are more than enough discussions about this (eg see ).Move everything on top of the bottom disc to the swap (which is the recursive step).The trick here is that this is a bottom-up algorithm. you will get results like this: Move disk smallest from left to center When you run move(, left, center, right). Consider something like this: move(,X,Y,_) :. ![]() I strongly recommend SWI-Prolog, which gives the correct results.Īs to naming the discs, yes you can do it. First of all, what Prolog are you using to get those results? That looks like you have a debugger enabled or something.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |