I'm off on a tanget at the moment and I have a question. We know there are 11 ways to unfold a cube as seen here:



These are a subset of the hexominos. I'm now curious about the number of ways to unfold the dicube. Its the n-polycube with n=2. Think of it as two cubes joined at a face.

So how many of the 4655 decominos can be folded to form a dicube? I was hoping this was a solved problem and I could find a list on them on-line but I didn't have much luck. Has anyone seen this set of decominos before? Ultimately I'm after an image like the one for the cube above. I think I have an "interesting" use for them if the complete set isn't too big.

I'm trying to think of the best way to generate this set and I'm sort of stuck and looking for help.

Thanks,
Carl

You could have a look at http://www.asahi-net.or.jp/~uy7t-isn/Puzzle/Polyominoes/Decomino.html I don't think that this is what you want, but if you click on "menu" there is a lot more on this site.

Also, this pagelists all the n-ominos, and there sees to be 9189 decominos

Thanks... that site has this too but I was looking here:
http://en.wikipedia.org/wiki/Polyomino
There are 4,655 free decominos. There are 9189 (what wikipedia calls) one-sided decominos. Your link has these numbers too but it calls the free ones "1-sided" and the one-sided ones "2-sided". Either way you look at it the shorter list allows the pieces to be flipped so the flipped version is not counted as part of the list. The other list in longer as it doesn't allow the pieces to be flipped so flipped versions are counted as a seperate decomino. I'm after the subset of the 4655 which can be folded into a dicube. I'm hoping its much much smaller.

Thanks,
Carl

The first thought that I got was to look at the dicube as two halves, as in two joined cubes with one face missing. 13 pentominoes (incl. mirror versions) can be folded to make a cube with one face missing, a box. Then "simply" test all combinations of these boxes together, and try to unfold. Then check for duplicates.

Maybe this idea is useless, maybe it leads to something. Who knows

From Coaster's idea, you could take the 13 pentominos that are nets of a open cube, highlight their open edges, and find the combinations that place open edges together without over lap. However, there are cross-shaped decominos that cannot be divided into pentominos, but can be folded into a dicube.

I had that same idea last night, but didn't realize I was missing some folds



I marked the free edges of the pentominoes with red on that picture. You can join any red edge(s) to another and fold a dicube. But those would still be missing some folds, as Jeffery pointed...

The rest of the unfolds (which surely are numerous) could be searched for by attaching 5 squares to the free edges of each pentomino. But that would surely take long,

So, if you strictly need the complete set for your use, this isn't much use yet, but if you don't, then you can just mix and match those for many interesting unfolds.

There are 723 nets for a dicube, not including rotations, reflections, or identical nets with different cut patterns.
I have attached a text file of all of them, in a rather odd (but unambiguous!) order

Anything else you need?

Peace,
Matt Galla

PS: This one is my favorite

_O __
_O __
_OOO
OOO _
__O _
__O_

Nice!!! Have you edited this post since you first put this up. I checked on my cell phone earlier and I was thinking I had seen a count of 2000+ which really surprised me. 723 sounds more reasonable put probably still more then I can put to use in my plan. I notice a few with 1x1 holes. How many of those are there in this set? Any 1x2 holes?

And since you have a program could you create a text file that lists the pieces in the format used by Gerard's Polyomino Solver? Maybe put the ones with holes at the end of this list. Even if I choose to ignore those I suspect this is still too many pieces to expect any solver to be able to handle in a resonable time but I can give it a try.

Oh and just to be clear... what do you consider identical nets with different cut patterns? I'm guessing its a decomino which can be folded into a dicube in two (or more) different ways... correct?

THANKS!!!
Carl

Yes, you caught me I thought 2769 sounded too high as well and was double checking and sure enough, I found one error that was producing alot of redundant nets. Since no one had responded, I thought it would be ok to edit without saying anything (the website doesn't say "last edited by..." if the edited post is the most recent post). I believe 723 is the right number though.
That's correct. There are exactly 40 nets with one hole.
Nope.
Ok I have attached two files. One of just nets without a hole and one of just nets with a hole. There are no nets with more than one hole (if it were two holes as opposed to a 1x2 hole, that would require at least 11 squares). They are numbered in the same order as in my first post, so you can see where the holed nets go in the progression (although I started the numbering at 0. Is that ok? ). Each line lists the squares in the same order you read: top to bottom, then left to right. If a different order would optimize the system, let me know. I wasn't sure what parameters you wanted at the beginning and end so I only provided the piece lines.
Not quite, and since you are only interested in the decomino shape it porbably doesn't matter, but for example this net:

O
OOOO
OOOO
O

could be cut up in many different ways and still fold into a dicube the same way. For example:

O
|
O-O-O-O
|
O-O-O-O
|
O

or

O
|
O-O-O-O
spaces do not work here, so I had to be creative|
O-O-O-O
|
O

will both fold into a dicube, but the shape only appears once in my list. I did not consider the same net folding into a dicube two different ways. If such a net exists, it would only appear once in my list though.
No problem It was fun Don't expect me to do too much though, because I really didn't have time to do that (I just really wanted to)

Peace,
Matt Galla

It was ok. Just checking that I hadn't been seeing things.
So that makes for 7270 squares which need to be packed and as 727 is prime I think that means the only rectangle worth trying is 10x727. And if we leave out the ones with holes we have 683 which is also prime so there I could try 10x683. Odd...
Yes, these are perfect. Thanks!!!
Interesting... though this particular decomino can simply be folded up as is into a dicube. Why this need to "cut" it up? Makes me wonder... are there decominos which need to be cut before they can be folded into a dicube on your list? I believe all the foldings of a cube can be turned into a cube with just folding. Here with the dicube it appears there may be two types of unfoldings.
I'm not sure such a thing exists either to be honest. The ends of the dicube are clearly different then the other 8 squares so I could assume there may be a net where a particular square in one folding is an end square and in another folding of the same net a "side" square. Maybe there is some reason which keeps this from occuring. I just can't prove they don't and I haven't spend much time looking for an example.
Still it was very appreciated. How is your cubing related problem coming along? I haven't heard much about it in a while but I assume its still in the works. Being vague but I think you'll know what I'm talking about.

Carl

I have to ask, do the ones that can be divided into two of the pentominoes that can be folded into open cubes, and the ones without this property form interesting subsets?

Are there any other interesting properties that can be used to divide these into subsets?

Wouldn't filling in the holes be considered cheating? I suppose I was tackling this problem from a more topological point of view. Imagine we had a paper cut out of each net and we consider two squares to be connected if and only if they are connected by an edge (conrners don't count!). Then all 11 cube unfoldings are topologically equivalent to a filled-disc. I used this as a starting point to bring the analogy up to a dicube. That means every dicube net would require a starting square with 9 other squares attached by one side to a growing net. That means there are 9 connections between the 10 squares on the net; 9 places in the paper where the edge has not been cut away, but rather creased.

(In fact this is how I performed the search: I considered all the ways to choose 11 of the 20 edges of a dicube to cut away, and examined the resulting net. After collecting all the nets that were in one piece and did not overlap themselves, I created rotations and reflections and made an ordered list and removed duplicates. I technically never searched for nets that were formed by choosing less than 11 edges to cut, but these are a subset of the list I did find, since every net that has more than 9 remaining edges can have some cut away to form another legal net that is identical for your purposes)

However, whenever a 2x2 box of squares appears, the analogy creates 4 shapes which essentially make the letter C rotated 4 times. Clearly there is a place where two squares could have been fused together completing an O-shape. However, this changes the topology! The net is now topologically equivalent to the shadow of a donut. From your point of view, you do not care about how many "extra" cuts there are in the shape, so this argument doesn't really apply - I'm just pointing out that there are more ways of looking at this than just as a decomino No.
Proof:
Any decomino that could be cut without forming two disjoint shapes has at least 10 edges that have not been cut. Therefore it has at least one closed path. If this closed path is a 2x2 box, then no square of that 2x2 box can be one of the ends of the dicube. They all therefore must belong to two long faces, which does not require cutting. If this closed path is a 3x3 box with the 1x1 center missing (which I don't believe exists... but I haven't confirmed), then without loss of generality, the top left square will be cut from the top middle square. Then:
If the top left square is an end of the dicube, it coincides with the top right square.
If the bottom left square is an end of the dicube, then the top left and right square coincide.
If the bottom right square is an end of the dicube, then the left square and the top right square coincide.
If the top right square is an end of the dicube, it coincides with the top left square.
If any edge is an end of the dicube, then the opposite edge in the 3x3 box is the same end... that doesn't work...
Finally, if none of these squares are an end, then the bottom 1x3 must wrap around the long faces of the dicube, which means either the middle left AND middle right square are both the same end, or the top left AND top right are both the same end, so those each have a sort of double contradiction. In any case, no such closed path can form a dicube.
If this closed path is a 4x3 box with the 1x2 center missing, then all 10 squares must be used in making this shape, so this net is unique and since this net does not give a dicube (proof of that: check the list ), such a closed path cannot form a dicube. FINALLY, if this closed path is any other shape, it uses more than 10 squares and the dicube net may only have 10 squares. QED
Correct. Topological reasons force all cube nets to have exactly 5 uncut edges which is the minimum required to keep the net in one piece. Yes. I suppose this is exactly my point. You can consider at least these two types of unfoldings. One where you just look at the shape of the net and one where you consider additional cuts made into the net. For a cube, the results are the same. For the dicube, the second gives many more nets than the first. Understanding this was also pretty crucial to the way I implemented my search as well.
I thought the same thing here too, but BOTH of our intuitions are WRONG! Take a look at the following net and see if you can tell me why

_O___O_
OOOOOO
_O___O_
(approximating the best I can here, the O and the _ are different widths... -_- ... it's supposed to be two plus-shapes fused together)


Pretty fantastic actually At least as good as I could hope for at this point. (and actually you're not the only one who is curious) I'm not done, and I can't guarantee that my idea will work or will be complete by the time my thesis is due in May, but I give myself probably a 30% success probability at this point, and considering what it is, I'll definitely take that for now. Must keep at it....


Good questions! I have no idea Maybe you should look into and tell us what you find I don't have time to look into it more, but I can get you started: I have attached the files DicubeNetsPents and DicubeNetsOther. The -Pents file contains only those dicube nets that cut up exactly 3 of the 4 edges "fusing" the two cubes of a dicube together, thereby dividing the dicube into two open cubes at the remaining edge. Remembering that I am including additional cuts, this DOES include two open-cube nets fused along an edge more than one cube long, for example two L-shapes fused along the long sides. The -Others file includes all the nets not included in the -Pents file. Is this equal to the set of all nets that can be formed by cutting up less than 3 of the 4 edges fusing the two cubes of a dicube? NO! That is because there are some nets that can be folded into a dicube in more than one way! One such way is given above. I do not know how many of these exist, but I have found at least a subset of these. The -Doubles file contains every net that could have come from cutting up 3 of the 4 fusing edges OR from cutting up less than 3 of the 4 fusing edges. Two such methods give clearly different folds, but identical nets in some cases... In any case, I can now say that yes, there are at least 42 dicube nets that can be folded into a dicube in more than one way: the 42 given in DicubeNetsDoubles. (it really is the answer to everything.... )

Peace,
Matt Galla

I think Carl is more "in the know" than I am on the subject but good luck. Even incomplete or unsuccessful work is worth sharing at some point. Hopefully it doesn't come to that though .

You wouldn't have to fill them in. Just add 40 1x1 voids to the piece list before you start the solver. Actually since you know where those voids would go... yes you in effect just fill them in. Not really cheating... you know they can't be filled with any of the other dicube foldings.
I think I followed that. May need to read it a few more times.
The second gives you many more nets, but no new decominos if I understand everything correctly so far.
Hmmm... I guess you could say this folds into a dicube in 2 ways. Either way the end squares are the same. One way just gives you the inside-out version of the other. You can do the same with the foldings of a cube though. And I think I see where you are going. The end squares have no diagonal neighbors. The side squares do. So I think this proves a dicube end square can't ever be unfolded and then re-folded to become a side square. Did I come up with the same why you did?
Nice... and thanks SO much for the link. I had missed that post before now. I'm sorry to hear about the award, since I hadn't heard anything that was what I had assumed happened. I figured I would have heard the jumping for joy had it happened. And I'm glad to here things are progressing well with the thesis. Even if you haven't completely solved the problem by May I hope you keep it on the back burner. I'd love to see you solve this one.
Now I'm confused. The only other folding of the net above I see produces an inside-out version of the original dicube. But then don't all folding allow for the possibility of being refolded into the inside-out state. Here you say "some nets". Which makes me think I'm missing something. Off to take a second look...

Ok... ignore what I said above. I see how this can be refolded several different ways.

Depending on how this is folded the blue squares are at the ends of the dicube. So now I'm wondering what was wrong about our intuitions? These cases clearly do exist.

Carl

Yes, I know what he's working on but everyone will have to wait on Matt to tell them. I have no plans of taking any of the thunder away from him.

Carl