Misplaced Pages

This is an old revision of this page, as edited by SmackBot (talk | contribs) at 22:27, 5 January 2007 (Date the maintenance tags using AWB). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

You must add a |reason= parameter to this Cleanup template – replace it with {{Cleanup|December 2006|reason=<Fill reason here>}}, or remove the Cleanup template.

The five pillars puzzle 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:

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.

 
#include <iostream> 
using namespace std; 
// By Ori Mosenzon 
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); 
  }
}

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 relaese_(...)/insert_(...) function.

• Mechanical puzzles