1
$\begingroup$

Recently, I was given a puzzle by a friend of mine, which has 6 pieces. Giddy to try it out, I took it apart without batting an eye to follow what I was removing or moving or sliding.

I've been struggling with this puzzle for over a year and a half now, and so thought I would write an algorithm that would list all the possible orientations or possibilities of pieces.

To make it more general, I numbered each piece 1 though 6. But, each piece can be rotated and placed, so I extended this to 1 through 12. So now each piece has two numbers, 1 and 12 is one piece, 2 and 11, 3 and 10, etc... Now to the root of my question:

Is it even possible to write a recursive algorithm to display all possible permutations of the 12 (6) pieces such that if piece 1 is used, 12 cannot, and so forth. Reason I ask is because if this were recursive, we wont know what we picked above (unless we keep running down in the recursion tree our last picked items) so that we can skip others.

Or, even better, would it be better to write a non recursive function?

Just as a note: I am not looking for code, per se. Pseudo code or concepts, or pointers would be so grateful and helpful.

Relevant References :

The Math behind Combinations with Restrictions

The Math behind Permutations with Restrictions

Just as a note: Seeing as this may come up; I know the number to this solution is massive, but I've already written functions that tell me if a said permutation can even be played on the board (do certain blocks collide), if at least one block is moveable (we won't want gridlock), and if the placement of blocks conforms to the size of the puzzle enclosure. All this will, hopefully, eliminate quite a bunch, and let me try by hand the remaining games.

|cite|improve this question
$\endgroup$
1
$\begingroup$

Generate all permutations of 1,...,6 all binary numbers of length 6, then combine a pair of each:

for π in permutations(1,...,6):
    for x in 000000,...,111111:
        output C(π[1],x[1]),...,C(π[6],x[6])

where $C(n,0) = n$, $C(n,1) = 13 - n$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ So by this, you suggest there are only 6 * 64 = 384 possible permuted arrangements? This seems incorrect as if I just used the first six pieces I would be getting 6! = 720... Thoughts? $\endgroup$ – dovedevic Jan 30 '17 at 3:11
  • 1
    $\begingroup$ I'm suggesting there are $6!\cdot 2^6$ possible permutations. Take a look at the pseudocode of my English isn't clear enough. $\endgroup$ – Yuval Filmus Jan 30 '17 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.