Misplaced Pages

Five pillars puzzle: Difference between revisions

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editContent deleted Content addedVisualWikitext
Revision as of 14:41, 31 December 2006 editHex (talk | contribs)Autopatrolled, Administrators25,371 edits {{cleanup-date|December 2006}}← Previous edit Latest revision as of 14:39, 5 March 2022 edit undoSahaib (talk | contribs)Extended confirmed users, New page reviewers151,157 editsNo edit summary 
(15 intermediate revisions by 7 users not shown)
Line 1: Line 1:
#REDIRECT ]
{{cleanup-date|December 2006}}


{{Redirect category shell|1=
'''The five pillars puzzle''' is a ] in which one is to try to remove a string from a structure of five threaded pillars.
{{R from alternative name}}
The following image illustrates this structure:
{{R with history}}

}}
<center>]</center>

<!-- == Origin ==-->

<!--==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;

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

== Execution example ==
<pre>
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

</pre>

== Notes ==
* Actually, the code can solve any intermediate stage by invoking the proper relaese_(...)/insert_(...) function.

]

Latest revision as of 14:39, 5 March 2022

Redirect to:

This page is a redirect. The following categories are used to track and monitor this redirect:
  • From an alternative name: This is a redirect from a title that is another name or identity such as an alter ego, a nickname, or a synonym of the target, or of a name associated with the target.
    • This redirect leads to the title in accordance with the naming conventions for common names to aid searches and writing. It is not necessary to replace these redirected links with a piped link.
    • If this redirect is an incorrect name for the target, then {{R from incorrect name}} should be used instead.
  • With history: This is a redirect from a page containing substantive page history. This page is kept as a redirect to preserve its former content and attributions. Please do not remove the tag that generates this text (unless the need to recreate content on this page has been demonstrated), nor delete this page.
    • This template should not be used for redirects having some edit history but no meaningful content in their previous versions, nor for redirects created as a result of a page merge (use {{R from merge}} instead), nor for redirects from a title that forms a historic part of Misplaced Pages (use {{R with old history}} instead).
When appropriate, protection levels are automatically sensed, described and categorized.
Five pillars puzzle: Difference between revisions Add topic