cube files
Indexed Cube Lovers Archive
Efficient test for equivalence of bandaged 4x4x4s ?
Submitted by Andreas Nortmann on Sun, 01/27/2008 - 09:40.
I know that bandaged cube (regardless of their size) are often ignored, which gave me my niche to live in...
I tried to write a program to generate all valuable bandagings of a 4x4x4. Here valuable means:
1. No single gluing can be added without restricting at least one turn which was possible before.
2. From every set of equivalent bandagings, which are transformable into each other by turning and/or generating symmetries, at most one is in the final list.
3. No bandagings which could be realized by a 2x2x2 or a 3x3x3.
Only the 108 bondings between the surface cubies are considered.
Years before I wrote a similar program for the 3x3x3 and its 54 bondings (24 between corners and edges; 24 between edges and faces; 6 between faces and the invisible center). After several improvments this program now needs a mere 3 minutes to produce the final list of 7356 bandagings.
This first program had a test implemented which generated all aequivalent bandagings by turning the original successively. If one generated bandaging has a signature smaller than the original one, the original is in the same set like a bandaging already on the final list. This dull brute-force-approach worked well for the 3x3x3 because there are at most 90176 bandagings in one set.
My efforts were fruitless on the 4x4x4 because there are a lot of sets which exceed this size by far. I have already made use of symmetries and implemented a vector (=> every bandaging needs only 1 bit) to reduce memory consumption. I am run out of ideas and can't go any further with this turning-based test.
My question: Has anybody an idea for an algorithm which tells me wheater two bandagings are part of the same set without generating this set?
I tried to write a program to generate all valuable bandagings of a 4x4x4. Here valuable means:
1. No single gluing can be added without restricting at least one turn which was possible before.
2. From every set of equivalent bandagings, which are transformable into each other by turning and/or generating symmetries, at most one is in the final list.
3. No bandagings which could be realized by a 2x2x2 or a 3x3x3.
Only the 108 bondings between the surface cubies are considered.
Years before I wrote a similar program for the 3x3x3 and its 54 bondings (24 between corners and edges; 24 between edges and faces; 6 between faces and the invisible center). After several improvments this program now needs a mere 3 minutes to produce the final list of 7356 bandagings.
This first program had a test implemented which generated all aequivalent bandagings by turning the original successively. If one generated bandaging has a signature smaller than the original one, the original is in the same set like a bandaging already on the final list. This dull brute-force-approach worked well for the 3x3x3 because there are at most 90176 bandagings in one set.
My efforts were fruitless on the 4x4x4 because there are a lot of sets which exceed this size by far. I have already made use of symmetries and implemented a vector (=> every bandaging needs only 1 bit) to reduce memory consumption. I am run out of ideas and can't go any further with this turning-based test.
My question: Has anybody an idea for an algorithm which tells me wheater two bandagings are part of the same set without generating this set?
