From: stadler@math.ohio-state.edu (Jonathan Stadler)
Newsgroups: sci.math
Subject: Re: Combinatorial problem with cubes
Date: 20 Oct 1995 23:35:29 -0400
The puzzle that Jason is talking about is called "Instant
Insanity." If you want a good discussion about it, check
out the book by Grimaldi called (I think) "Discrete and
Combinatorial Mathematics."
Idea of puzzle (again): You have four cubes and each has
one of four colors on each side. Your goal is to stack the
cubes so that each side of the stack has ALL four colors
represented.
One way to solve: Draw four vertices, labeled for the colors.
(R,B,G,W) For each cube, connect two vertices with an edge
if colors are on opposite faces and label the edge according
to which cube the pair was on. For instance, if you are going
through the first cube and one side is green and the side
opposite is red, draw an edge from R to G and label it (1).
Each cube will have three such edges, for a total of 12 edges.
Loops (an edge going from one vertex to itself) are permissible.
Now, look for two cycles C1 and C2 which each use all of the cubes
(1-4) and the edges between the same two colors come from
different cubes. For example, on one cycle, if the edge
connecting R and G is (1), the label connecting R and G
on the other cylce must be different than (1).
Now that you have these two cycles, look for the edge in the
first labelled (1). Look at the endpoints of this edge.
Suppose we go from color X to color Y by travelling clockwise
along this edge. Stack your first cube so that X is in front
and Y is in back. Now, look at the second cylce and find
edge (1) and note its endpoints S and T, so that we travel
from S, clockwise across edge (1) to T. Put color S at the
left and T on the right. Now, proceed in the same fashion
with cubes 2-4.
Here is an example. Suppose we end up with the following
cycles:
(1) (3)
R----------B R----------B
| | | |
| | | |
(2)| |(3) (4)| |(2)
| | | |
| | | |
W----------G W----------G
(4) (1)
So we have:
Front Left Right Back Cube number:
G W R W (4)
B R B G (3)
W B G R (2)
R G W B (1)
Hope that helps! If not, try the reference I gave above.
Jon Stadler
stadler@math.ohio-state.edu
From dcromley@wyoming.com Thu Oct 26 09:36:17 CDT 1995
Article: 46659 of sci.math
Path: muir.math.niu.edu!mp.cs.niu.edu!vixen.cso.uiuc.edu!news.ecn.bgu.edu!ixc.ixc.net!news.sprintlink.net!news.wyoming.com!usenet
From: dcromley@wyoming.com (Dave Cromley)
Newsgroups: sci.math
Subject: Re: Combinatorial problem with cubes
Date: 26 Oct 1995 04:42:16 GMT
Organization: wyoming.com LLC
Lines: 110
Message-ID: <46n3j8$817@horn.wyoming.com>
References: <4674ce$1at@homer.alpha.net> <469pq1$7ic@math.mps.ohio-state.edu>
NNTP-Posting-Host: cys-cap-7.wyoming.com
Mime-Version: 1.0
X-Newsreader: WinVN 0.99.2
>> Recently I saw a puzzle ..
>>
>> It involves taking 4 cubes where each face is painted using one
>> of 4 possible colors and lining the cubes in a row such that
>> each outer row has every color in the row only once. ..
>>
>> Is there a way that you can figure out if there is a solution
>> (and what it is) or if the coloring configuration given yields
>> no solution? Any help on this (especially from a programming
>> standpoint) would be greatly appreciated. ..
> The puzzle .. is called "Instant Insanity." If you want a
> good discussion about it, check out the book by Grimaldi
> called (I think) "Discrete and Combinatorial Mathematics."
As I remember it, the object was to stack the cubes so that
each side of the stack has all four faces the color.
There are fewer solutions for this rule.
At any rate, here is a (MSDOS) QBASIC program to solve my
version of the puzzle. It finds (the) one solution in a second
or so. I have changed it for the stated version, and it finds
(the) 76 solutions in a minute or so.
Program follows:
' 4 cube tower puzzle
' Each cube face is painted in one of four colors.
' The object is to stack the cubes so that each side
' of the stack has all four faces the same color.
' Program by David A. Cromley
DEFINT A-Z: CLS : blanks$ = STRING$(40, " "): num = 0
DIM b1(6), b2(6), b3(6), b4(6), b5(6) ' the 4 blocks
' red = 1, white = 2, blue = 4, green = 8
' place blocks in front of you and fill in table:
PRINT "Top---Front-Right-Left--Back--Bot--"
DATA 2, 1, 1, 8, 4, 4
DATA 2, 2, 8, 1, 4, 8
DATA 2, 4, 1, 8, 1, 4
DATA 2, 8, 1, 8, 2, 4
READ b1(1), b1(2), b1(3), b1(4), b1(5), b1(6) ' block 1
READ b2(1), b2(2), b2(3), b2(4), b2(5), b2(6) ' block 2
READ b3(1), b3(2), b3(3), b3(4), b3(5), b3(6) ' block 3
READ b4(1), b4(2), b4(3), b4(4), b4(5), b4(6) ' block 4
DIM c$(8): DATA "red ","white","","blue ","","","","green"
READ c$(1), c$(2), q$, c$(4), q$, q$, q$, c$(8)
' top = 1, front = 2, right = 3, left = 4, back = 5, bottom = 6
DIM f(24, 6) ' blockface(orientation, face)
DATA 1,2,3, 2,3,1, 3,1,2, 4,5,6, 5,6,4, 6,4,5
' make faceblock table: 24 orientations
i24 = 1: FOR i6 = 1 TO 6 ' six possible tops
READ top, front, right
bot = 7 - top: back = 7 - front: left = 7 - right
FOR i4 = 1 TO 4 ' rotate around 4 sides
f(i24, 1) = top: f(i24, 6) = bot
f(i24, 2) = front: f(i24, 5) = back
f(i24, 3) = right: f(i24, 4) = left
t = front: front = right: right = back: back = left: left = t
i24 = i24 + 1: NEXT i4
NEXT i6
'--end of initialization--start of mainline--
FOR o1 = 1 TO 12 STEP 4 ' block 1 orientation
' (only need 3 tops on first block, and
' don't have to rotate first block)
LOCATE 2, 1: FOR i6 = 1 TO 6
PRINT USING "\ \ "; c$(b1(f(o1, i6))); : NEXT i6: PRINT
' check one of each color on side faces
t = b1(f(o1, 2)) + b1(f(o1, 3)) + b1(f(o1, 4)) + b1(f(o1, 5))
IF t <> 15 THEN GOTO nexto1
' set colors of base block
c2 = b1(f(o1, 2)): c3 = b1(f(o1, 3))
c4 = b1(f(o1, 4)): c5 = b1(f(o1, 5))
FOR o2 = 1 TO 24 ' block 2 orientation
LOCATE 3, 1: FOR i6 = 1 TO 6
PRINT USING "\ \ "; c$(b2(f(o2, i6))); : NEXT i6: PRINT
t = b2(f(o2, 2)) + b2(f(o2, 3)) + b2(f(o2, 4)) + b2(f(o2, 5))
IF t <> 15 THEN GOTO nexto2
' check colors against base block
IF b2(f(o2, 2)) <> c2 THEN GOTO nexto2
IF b2(f(o2, 3)) <> c3 THEN GOTO nexto2
IF b2(f(o2, 4)) <> c4 THEN GOTO nexto2
IF b2(f(o2, 5)) <> c5 THEN GOTO nexto2
FOR o3 = 1 TO 24 ' block 3 orientation
LOCATE 4, 1: FOR i6 = 1 TO 6
PRINT USING "\ \ "; c$(b3(f(o3, i6))); : NEXT i6: PRINT
t = b3(f(o3, 2)) + b3(f(o3, 3)) + b3(f(o3, 4)) + b3(f(o3, 5))
IF t <> 15 THEN GOTO nexto3
IF b3(f(o3, 2)) <> c2 THEN GOTO nexto3
IF b3(f(o3, 3)) <> c3 THEN GOTO nexto3
IF b3(f(o3, 4)) <> c4 THEN GOTO nexto3
IF b3(f(o3, 5)) <> c5 THEN GOTO nexto3
FOR o4 = 1 TO 24 ' block 4 orientation
LOCATE 5, 1: FOR i6 = 1 TO 6
PRINT USING "\ \ "; c$(b4(f(o4, i6))); : NEXT i6: PRINT
t = b4(f(o4, 2)) + b4(f(o4, 3)) + b4(f(o4, 4)) + b4(f(o4, 5))
IF t <> 15 THEN GOTO nexto4
IF b4(f(o4, 2)) <> c2 THEN GOTO nexto4
IF b4(f(o4, 3)) <> c3 THEN GOTO nexto4
IF b4(f(o4, 4)) <> c4 THEN GOTO nexto4
IF b4(f(o4, 5)) <> c5 THEN GOTO nexto4
PRINT "--SOLUTION!--": num = num + 1
BEEP: WHILE INKEY$ = "": WEND
LOCATE 6, 1: PRINT blanks$
nexto4: LOCATE 5, 1: PRINT blanks$: NEXT o4
nexto3: LOCATE 4, 1: PRINT blanks$: NEXT o3
nexto2: LOCATE 3, 1: PRINT blanks$: NEXT o2
nexto1: LOCATE 2, 1: PRINT blanks$: NEXT o1
PRINT num; "solution(s)": END