Finding Permutations with Exclusions

Question

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.

Answer 1

Generate all permutations of 1,...,6 (outer loop below), and all binary numbers of length 6 (inner loop below), then combine each permutation in the first set with each one from the second set:

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$.

• dovedevic: 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?
• Yuval Filmus: I'm suggesting there are 6ドル!\cdot 2^6$ possible permutations. Take a look at the pseudocode of my English isn't clear enough.