| Revision as of 14:50, 27 May 2007 edit58.169.126.183 (talk)No edit summary← Previous edit | Revision as of 20:13, 9 June 2007 edit undoLendorien (talk | contribs)Extended confirmed users4,394 edits →A software solution: removed the software solution. Is Orig Research. A link to a site containing it would be more appropriate.Next edit → | ||
| Line 10: | Line 10: | ||
| <!--==Description ==--> | <!--==Description ==--> | ||
| == A software solution == | |||
| Apparently, there a general solution for this problem using a mutual recursion (Please note the number of each pillar in the image). The implementation is in C++ but it can be easly converted to any programming language. | |||
| <pre> | |||
| #include <iostream> | |||
| using namespace std; | |||
| void printRange(int n) { | |||
| if (n==1) | |||
| cout << 1 << "\n"; | |||
| else | |||
| cout << n << ".." << 1 <<"\n"; | |||
| } | |||
| void insert(int n); | |||
| void release_(int c) { | |||
| if(c==1) | |||
| return; | |||
| cout << "Thread through (upwards) ring number " << c << " (stick to the right)\n"; | |||
| insert(c-1); | |||
| release_(c-1); | |||
| } | |||
| void release(int n) { | |||
| release_(n); | |||
| cout << "Remove from "; | |||
| printRange(n); | |||
| } | |||
| void insert_(int c, int n) { | |||
| if(c==n) | |||
| return; | |||
| cout << "Thread through (upwards) ring number " << c+1 << " (stick to the left)\n"; | |||
| release(c); | |||
| insert_(c+1,n); | |||
| } | |||
| void insert(int n) { | |||
| cout << "Put over "; | |||
| printRange(n); | |||
| insert_(1,n); | |||
| } | |||
| int main() { | |||
| int n; | |||
| while(true) { | |||
| cout << "\nnumber of pillars? (0 = quit) "; | |||
| cin >> n ; | |||
| if(n<1) | |||
| break; | |||
| cout << "insert "<<n<<":\n-------\n"; | |||
| insert(n); | |||
| cout << "\n\nrelease "<<n<<":\n-------\n"; | |||
| release(n); | |||
| } | |||
| } | |||
| </pre> | |||
| == Execution example == | == Execution example == | ||
Revision as of 20:13, 9 June 2007
 | This article may require cleanup to meet Misplaced Pages's quality standards. No cleanup reason has been specified. Please help improve this article if you can. (December 2006) (Learn how and when to remove this message) |
The five pillars puzzle (also known as The Devil's Staircase, Devil's Halo and Impossible Staircase; another similar puzzle is the Giant's Causeway which uses a separate pillar with an embedded ring) is a mechanical puzzle in which one is to try to remove a string from a structure of five threaded pillars. The following image illustrates this structure:
Execution example
number of pillars? (0 = quit) 3 3 insert 3: ------- Put over 3..1 Thread through (upwards) ring number 2 (stick to the left) Remove from 1 Thread through (upwards) ring number 3 (stick to the left) Thread through (upwards) ring number 2 (stick to the right) Put over 1 Remove from 2..1 release 3: ------- Thread through (upwards) ring number 3 (stick to the right) Put over 2..1 Thread through (upwards) ring number 2 (stick to the left) Remove from 1 Thread through (upwards) ring number 2 (stick to the right) Put over 1 Remove from 3..1 number of pillars? (0 = quit) 5 5 insert 5: ------- Put over 5..1 Thread through (upwards) ring number 2 (stick to the left) Remove from 1 Thread through (upwards) ring number 3 (stick to the left) Thread through (upwards) ring number 2 (stick to the right) Put over 1 Remove from 2..1 Thread through (upwards) ring number 4 (stick to the left) Thread through (upwards) ring number 3 (stick to the right) Put over 2..1 Thread through (upwards) ring number 2 (stick to the left) Remove from 1 Thread through (upwards) ring number 2 (stick to the right) Put over 1 Remove from 3..1 Thread through (upwards) ring number 5 (stick to the left) Thread through (upwards) ring number 4 (stick to the right) Put over 3..1 Thread through (upwards) ring number 2 (stick to the left) Remove from 1 Thread through (upwards) ring number 3 (stick to the left) Thread through (upwards) ring number 2 (stick to the right) Put over 1 Remove from 2..1 Thread through (upwards) ring number 3 (stick to the right) Put over 2..1 Thread through (upwards) ring number 2 (stick to the left) Remove from 1 Thread through (upwards) ring number 2 (stick to the right) Put over 1 Remove from 4..1 release 5: ------- Thread through (upwards) ring number 5 (stick to the right) Put over 4..1 Thread through (upwards) ring number 2 (stick to the left) Remove from 1 Thread through (upwards) ring number 3 (stick to the left) Thread through (upwards) ring number 2 (stick to the right) Put over 1 Remove from 2..1 Thread through (upwards) ring number 4 (stick to the left) Thread through (upwards) ring number 3 (stick to the right) Put over 2..1 Thread through (upwards) ring number 2 (stick to the left) Remove from 1 Thread through (upwards) ring number 2 (stick to the right) Put over 1 Remove from 3..1 Thread through (upwards) ring number 4 (stick to the right) Put over 3..1 Thread through (upwards) ring number 2 (stick to the left) Remove from 1 Thread through (upwards) ring number 3 (stick to the left) Thread through (upwards) ring number 2 (stick to the right) Put over 1 Remove from 2..1 Thread through (upwards) ring number 3 (stick to the right) Put over 2..1 Thread through (upwards) ring number 2 (stick to the left) Remove from 1 Thread through (upwards) ring number 2 (stick to the right) Put over 1 Remove from 5..1 number of pillars? (0 = quit) 0
Notes
- Actually, the code can solve any intermediate stage by invoking the proper release_(...)/insert_(...) function.