Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much

Challenge: "Insanity" Cube Puzzle

by liverpole (Monsignor)
on Jul 04, 2006 at 22:47 UTC ( #559228=perlmeditation: print w/replies, xml ) Need Help??

Last weekend during our annual family reunion it rained the whole time, so we played a lot of indoor games.

One game which my niece was trying to solve was called Insanity.  It consisted simply of a set of 4 cubes with differently colored faces.  The colors were green, purple, red and yellow, and the object was to stack the cubes on top of one another in such a way as to have no duplicate colors in any of the 4 columns.

I thought it would be fun to write a Perl script to solve it using "brute force", but didn't get it finished until after we returned Sunday night.  I was mostly interested in seeing whether there was only a single solution, or multiple solutions -- in addition, of course, to the enjoyment of writing a fun Perl script.  I'm presenting this as a challenge in case other monks would like to try it for themselves.  I'm fairly sure someone can come up with a more elegant solution than my "brute force" method, or at least improve on its readability and/or speed.

The following represents the 4 cubes:

my $cube1 = 'pgpygr'; my $cube2 = 'rprrgy'; my $cube3 = 'ppryyg'; my $cube4 = 'rrygpy';
where 'g', 'p', 'r' and 'y' represent the colors 'green', 'purple', 'red' and 'yellow' respectively, and the colors in each string are, in order, the left, front, right, back, top and bottom faces.  Thus, cube1 'pgpygr' represents the cube:
+-------+ | g | | green | | | +-------+-------+-------+-------+ | p | g | p | y | |purple | green |purple |yellow | | | | | | +-------+-------+-------+-------+ | r | | red | | | +-------+

For those not interested in trying to solve it themselves, my program is behind the following spoiler tags.


Replies are listed 'Best First'.
Re: Challenge: "Insanity" Cube Puzzle
by bobf (Monsignor) on Jul 05, 2006 at 03:52 UTC

    Interesting puzzle, and a nice challenge. Thanks for the diversion. :-)

    I don't know if my solution is any more elegant, readable, or speedy*, but here it is:

    *Update: After downloading and running your code, my solution appears to be a bit faster. The short-circuiting that I used meant that I only checked 12,480 4-block combinations for the given input data, whereas your solution checks 331,776 combinations. I didn't run extensive benchmarks (which might be more interesting once other solutions are posted), but on my box your code took about 50 sec to run and mine took less than 1 sec. Your code has more error checking and output capability, though, so speed isn't everything. :-)

Re: Challenge: "Insanity" Cube Puzzle (tye's)
by tye (Sage) on Jul 05, 2006 at 08:02 UTC

    The following runs in a fraction of second. I haven't looked at the other code contributions so I won't try to compare code complexity. (:

    - tye        

Re: Challenge: "Insanity" Cube Puzzle
by Ieronim (Friar) on Jul 05, 2006 at 13:27 UTC
    Regexp-based solution (finds only unique solutions for the puzzle and is very fast :))

    The solution posted 5 days ago wasn't a solution at all :)
    I just realised that it solved a bit another puzzle :)

    The updated pure rexep-based version is here:</p

Re: Challenge: "Insanity" Cube Puzzle
by Limbic~Region (Chancellor) on Jul 05, 2006 at 15:53 UTC
    The following is also a brute-force attack. I am only posting per our conversation in the CB.

    Update (2006-07-06):
    Here is a smarter brute-force approach. It reduces the number of loops from 331,776 to 65,536:

    Final Update (2006-07-06):
    This is an even smarter brute-force approach. The number of total loops is less than 8,048 and It is quite fast.

    #!/usr/bin/perl use strict; use warnings; my @cube = map rotations($_), qw/pgpygr rprrgy ppryyg rrygpy/; my @used; for my $c1 (@{$cube[0]}) { @used = map {{$_ => 1}} @$c1; CUBE2: for my $c2 (@{$cube[1]}) { $used[$_]{$c2->[$_]} && next CUBE2 for 0 .. 3; $used[$_]{$c2->[$_]} = 1 for 0 .. 3; CUBE3: for my $c3 (@{$cube[2]}) { $used[$_]{$c3->[$_]} && next CUBE3 for 0 .. 3; $used[$_]{$c3->[$_]} = 1 for 0 .. 3; CUBE4: for my $c4 (@{$cube[3]}) { $used[$_]{$c4->[$_]} && next CUBE4 for 0 .. 3; print "@$c1\n@$c2\n@$c3\n@$c4\n\n"; } $used[$_]{$c3->[$_]} = 0 for 0 .. 3; } $used[$_]{$c2->[$_]} = 0 for 0 .. 3; } } sub rotations { my (%seen, @rot); my @cube = split //, shift @_; for ([0 .. 3], [1, 4, 3, 5], [4, 0, 5, 2]) { my @col = @cube[@$_]; push @rot, map {push @col, shift @col; $seen{"@col"}++ ? () : +[@col]} 1..4; @col = reverse @{$rot[-1]}; push @rot, map {push @col, shift @col; $seen{"@col"}++ ? () : +[@col]} 1..4; } return \@rot; }

    Cheers - L~R

      The total number of iterations needed to find all unique solutions is ((3*4)^4)/8 == 2592, as the unique solution does not depend on the cubes' order :) And all 8 solutions can be built using simple permutation of an array representing the unique one.

      My regexp solution really uses the smallest possible number of loops, i think. Be stricter, it does not use loops at all to find the solution only during the pre-processing :)))

      It's difficult to make a good benchmark, as all presented scripts print their output directly to STDOUT and need to be a bit modified to become comparable by cmpthese(). But i'll try to do it today, if i have enough time.

        I told liverpole in the CB that I didn't really have time to play with this but since he indicated I was the reason he posted it as a Challenge (see some of my previous posts), I felt obligated to do so. Without thinking about it too much, I decided just to brute-force it and then see if there were any obvious optimizations on that. I do not expect it to be the fastest but it is fast enough.

        With regards to benchmarking, it is almost never a good idea to include IO. Basically, the routines should be verified to produce essentially the same results first and then the output should be omitted. In other words, doing any preparation IO work before the bench, run the bench, and omit any IO output.

        Update: Depending on how you count, the following only loops 1,152 times and still finds duplicates.

        And the following performs even fewer (< 500):

        Cheers - L~R

Re: Challenge: "Insanity" Cube Puzzle
by reasonablekeith (Deacon) on Jul 06, 2006 at 15:39 UTC
    Not much more to see here, mainly posted because it worked :). Generates the solutions as in the OPs original post.

    my name's not Keith, and I'm not reasonable.
Re: Challenge: "Insanity" Cube Puzzle
by herby1620 (Monk) on Jul 11, 2006 at 00:53 UTC
    While I have not solved this problem, I remember a friend who worked on it back in the 60's/70's (I don't recall which). He had worked out a program for the IBM 1130 (in the language of the day: Fortran!) that went thru and found combinations of the cubes that would NOT work. It seems as though if you put the faces on correctly you can make it an insane puzzle. Now, I don't know the result of this musing, but given a set of cubes, and their available colors, making an "impossible" set might be a more difficult task. As I remember it they pryed apart the cubes and snapped them back to give the set to the math teacher or something like that. Good luck!
Re: Challenge: "Insanity" Cube Puzzle
by ambrus (Abbot) on Aug 06, 2008 at 18:39 UTC

    Here's my solution in the J programming language. The cubes in the example are defined near the beginning, but you can use any other cube colorings you wish. My solution uses brute force and is unoptimized, but on a modern machine it still runs within a few seconds so I don't care.

    The output lists all the solutions and then gives the number of solutions just in case there are so many they scrolled out of the screen. Each solution is the list of four rotated cubes each given as six colors like in the input. The output is in spoiler tags.

    Update: Let's compare the output with that of some of the other solutions posted in this thread.

    Update: I cross-posted a description of the puzzle and my solution to the J wiki: Essays/InsanityCube.

    Update 2010-11-29: has anyone linked to the description of this puzzle (called Instant Insanity there) on Jaap's puzzle page?

Re: Challenge: "Insanity" Cube Puzzle
by ambrus (Abbot) on Apr 13, 2009 at 11:10 UTC

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://559228]
Approved by Paladin
Front-paged by Old_Gray_Bear
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (7)
As of 2017-02-22 19:55 GMT
Find Nodes?
    Voting Booth?
    Before electricity was invented, what was the Electric Eel called?

    Results (335 votes). Check out past polls.