The five pillars puzzle

From Wikipedia, the free encyclopedia

This article may require cleanup to meet Wikipedia's quality standards.
Please discuss this issue on the talk page or replace this tag with a more specific message.
This article has been tagged since December 2006.

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:

[edit] 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; 


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); 
  }
}

[edit] 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