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