Solved

Cube Puzzle solver

Posted on 2004-09-23
8
537 Views
Last Modified: 2013-11-16
I have a cube puzzle, where there are 8 wooden blocks, each with a coloured ring on each face, making up a large cube, inside an open-topped clear plastic container.
The puzzle is solved by getting all of the same colour on every side of the large cube. There are 6 colours, one for each face of the cube. There is never 2 of the same coloured rings on one cube. No two faces of the large cube can be the same colour.

This puzzle is not unlike a Rubik's cube, except you do not have 9 cubes and have the freedom to move and/or rotate any cube that you like.

I am planning to make a program in VB (don't be put off this question if you don't know VB) to solve this puzzle. The 'bruteforce' method could be useful, as I have deduced that there are several ways to solve it.

First, I would like to know how many possible ways there are for the cubes to go in, given that there are 8 cubes, which can be in 8 different spaces, with 6 different directions for each cube.

Secondly, I would like to know how to go about designing an efficient program to solve this puzzle. I have great knowledge of VB, and some knowledge of C++, so I should be able to translate any C++ snippets into VB.

Thanks in advance,
Graham Sutherland.
0
Comment
Question by:burningmace
  • 3
  • 3
8 Comments
 

Expert Comment

by:dan-g
ID: 12138886
Hello M. Sutherland.

If I understand correctly, your ultimate goal is to find out how to stack 8 individual, colored cubes in a 2 x 2 x 2 array so that each face of the larger, assembled cube shows a different, single color.

Also, please correct any of the following statements if they are wrong:

   - In the total puzzle, there are only 6 colors, c1 to c6
   - each individual cube uses all 6 colors, one per face

Now, I ASSUME that the disposition of the 6 colors on a cube is NOT the same for each cube, otherwise it is very simple to assemble a larger cube so that all faces show a unique, distinct color.  All you have to do is orient the cubes in the same direction as you put them in a 2x2x2 arrangement (I've done it using 8 dices (dies?) (check that each dice has the same number disposition!))

So, to answer the first part of your question, how many possible ways there are for the cubes to go in:

- A single cube can be placed in 24 different positions, not 6 (A specific face can be placed on any of the 6 side, but then you can rotate the cube in 4 positions while keeping the specific face on the same side)

Therefore, the first cube can be placed in 8 locations, in one of the 24 orientations
The 2nd cube can be placed in one of the 7 remaining locations, in one of the 24 orientations
...
The 7th cube can be placed in one of the 2 remaining locations, in one of the 24 orientations
The 8th cube can be placed in the last remaining location, in one of the 24 orientations

Total:  (8 * 24) * (7 * 24) * ... * (2 * 24) * (1 * 24) = 8*7*6*5*4*3*2*1 * 24^8 = 8! * 24^8 = 40320 * 1.1x10^11

= 4.438 x 10^15 (approx)

This is the "pure" brute force result, it includes all rotations of the same global arrangements, but taking that into account would only divide the total number by 24, which doesn't really help that much....

Before moving on to the second part of your question, I'd like confirmation that my understanding and assumptions are correct and if I have answered your first part to your satisfaction.

If you want to document the color disposition of your cubes, you could use the following notation:

1 - yellow, 2 - blue, 3 - red, ..., 6 - purple

where the numbers are the side of the cube with "1" on top, "2", "3", "4" and "5" each of the sides in sequence, and "6" on the bottom

Viewed from top:
   __4__
   |       |
5 |   1   | 3
   |____|
       2

Hope this makes sense....

Dan.
0
 
LVL 84

Expert Comment

by:ozo
ID: 12140426
= 4.438 x 10^15 (approx)
many of these configurations can be eliminated immedetely on checking the first few cubes without need to examine all possible configurations of the other cubes.
0
 
LVL 5

Author Comment

by:burningmace
ID: 12140539
Dan-q, I think you may have got it completely right the first time!

http://images.google.com/images?q=tbn:0k67QKe_FUcJ:www.pentangle-puzzles.co.uk/Minis/mp8cc.jpg

For now, that should show you a small thumbnail of the picture.
I can't guarantee it'll stay there, as it's a google images search cached picture.

Thanks so far...
0
What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 

Expert Comment

by:dan-g
ID: 12141640
Hello M. Sutherland.

Thanks for the approval!  I take it then that there are only 6 colors total (I'm not sure by looking at the picture...), and that the disposition of colors is not the same for each cube.

Is the disposition different for EACH cube, or are some cubes identical?  If some are identical, then the total brute force number would be less, since you could have permutations of identical cubes.

Of course, as ozo pointed out, some basic checks can quickly rule out the start of a combination, but that's entering into the second phase of your question.  I was only looking at the first part so far and getting some confirmations.

In fact, for the second part, once a first cube is placed, the next cube placed beside it can only go in one orientation (if at all).  So with only 192 starting positions (8 cubes * 24 positions), and for each about 5040 cube selections(7*6*5*4*3*2*1), that makes it to 967,680 combinations.  A program should be able to check that rather quickly.  

A general structure of the program could be like this:

- Define a structure to represent the color arrangement of each cube, and if it is "used" or not

- Mark all cubes as "unused"

- For each of the 8 cubes
    - Mark the cube as "used" in position (0,0,0)
    - For each of the 24 possible positions

        - For each of the "unused" cubes
            - If the cube can be put at (0,0,1) while respecting color restrictions
                - Mark the cube as "used" in position (0,0,1)
       
                - For each of the "unused" cubes
                    - If the cube can be put at (0,1,0) while respecting color restrictions
                        - Mark the cube as "used" in position (0,1,0)
       
                        - For each of the "unused" cubes
                            - If the cube can be put at (0,1,1) while respecting color restrictions
                                - Mark the cube as "used" in position (0,1,1)
       
                                - For each of the "unused" cubes
                                    - If the cube can be put at (1,0,0) while respecting color restrictions
                                        - Mark the cube as "used" in position (1,0,0)
       
                                        - For each of the "unused" cubes
                                            - If the cube can be put at (1,0,1) while respecting color restrictions
                                                - Mark the cube as "used" in position (1,0,1)
       
                                                - For each of the "unused" cubes
                                                    - If the cube can be put at (1,1,0) while respecting color restrictions
                                                        - Mark the cube as "used" in position (1,1,0)
       
                                                        - For each of the "unused" cubes
                                                            - If the cube can be put at (1,1,1) while respecting color restrictions
                                                                - PRINT OUT THE SOLUTION!!!!        
                                                            - Mark the cube as "unused"
                                                        - Next cube

                                                    - Mark the cube as "unused"
                                                - Next cube

                                            - Mark the cube as "unused"
                                        - Next cube

                                    - Mark the cube as "unused"
                                - Next cube

                            - Mark the cube as "unused"
                        - Next cube

                    - Mark the cube as "unused"
                - Next cube

            - Mark the cube as "unused"
        - Next cube

    - Next position
    - Mark the cube as "unused"

- Next cube

We can try to get fancy and use some recursivity, but a quick & dirty solution would be as above.  There remain some detail work with "If the cube can be put at (x,y,z) while respecting color restrictions", which would obviously be a function that takes a cube pointer and a position, looks at side colors already defined by cubes already placed and can return the orientation to use, but overall that's the general structure I would use.

Does this closes your question?

Dan.
0
 
LVL 5

Author Comment

by:burningmace
ID: 12142005
All cubes are different. Because there are about 24 solutions, the brute-force shouldn't take too long. Also, I wanted the result to be printed as:

Cube 1: X, Y, Z, Rotation (Green Left, Red Right, Grey Up, Gold Down, Purple Front, Blue Back)
Cube 2...
Cube 3...
.......
Cube 8...

I would like a method of putting what you wrote above into code, whether it be C++ or VB.
0
 

Accepted Solution

by:
dan-g earned 200 total points
ID: 12148910
Hello!

Here's a program that should compute solutions.  When I run it, it generate LOTS of solutions.  Maybe my definitions of the cube is too easy to assemble.  Just put the definition of your cubes and let it rip!  Run it in within the Visual environement, the output is done using Console.WriteLine, so it appears in the Output window.

The overall class hierarchy is really bad, I've really concentrated on the algorithm.  It's rather tortuous in some places, but I think it works.

--------------------------------------------------------------------

Public Class Form1
    Inherits System.Windows.Forms.Form

#Region " Windows Form Designer generated code "

    Public Sub New()
        MyBase.New()

        'This call is required by the Windows Form Designer.
        InitializeComponent()

        'Add any initialization after the InitializeComponent() call

    End Sub

    'Form overrides dispose to clean up the component list.
    Protected Overloads Overrides Sub Dispose(ByVal disposing As Boolean)
        If disposing Then
            If Not (components Is Nothing) Then
                components.Dispose()
            End If
        End If
        MyBase.Dispose(disposing)
    End Sub

    'Required by the Windows Form Designer
    Private components As System.ComponentModel.IContainer

    'NOTE: The following procedure is required by the Windows Form Designer
    'It can be modified using the Windows Form Designer.  
    'Do not modify it using the code editor.
    Friend WithEvents Button1 As System.Windows.Forms.Button
    <System.Diagnostics.DebuggerStepThrough()> Private Sub InitializeComponent()
        Me.Button1 = New System.Windows.Forms.Button
        Me.SuspendLayout()
        '
        'Button1
        '
        Me.Button1.Location = New System.Drawing.Point(40, 32)
        Me.Button1.Name = "Button1"
        Me.Button1.TabIndex = 0
        Me.Button1.Text = "GO!"
        '
        'Form1
        '
        Me.AutoScaleBaseSize = New System.Drawing.Size(5, 13)
        Me.ClientSize = New System.Drawing.Size(176, 118)
        Me.Controls.Add(Me.Button1)
        Me.Name = "Form1"
        Me.Text = "Form1"
        Me.ResumeLayout(False)

    End Sub

#End Region


    ' The 6 colors in the set  ********** Change the name of your colors if required ********
    Public Enum Color
        Red
        Green
        Blue
        Yellow
        Cyan
        Magenta
    End Enum

    ' The sides of cubes, indexes into the cube's Colors array
    Public Enum Side
        Top = 0
        Front = 1
        Right = 2
        Back = 3
        Left = 4
        Bottom = 5
    End Enum

    ' This is the hard conceptual part, representing the different orientations of a cube
    ' and be able to know which color is where.  This is probably not the most efficient or
    ' elegant way, but I hope it will be simple to understand and debug.
    '
    ' The Orientation enum lists all the valid places where the cube's top and front face can
    ' be placed in front of someone (try to think of where the cube's top & front faces would show
    ' in a slightly larger glass cube

    Public Enum Orientation
        TopFront = 0        ' Put top on top, rotate front face
        TopRight = 1
        TopBack = 2
        TopLeft = 3
        FrontBottom = 4     ' Now put top in front, rotate front face
        FrontRight = 5
        FrontTop = 6
        FrontLeft = 7
        BottomBack = 8      ' Now put top on the bottom, rotate front face
        BottomLeft = 9
        BottomFront = 10
        BottomRight = 11
        BackTop = 12        ' Now put top in back, rotate front face
        BackLeft = 13
        BackBottom = 14
        BackRight = 15
        RightTop = 16       ' Now put top at right, rotate front face
        RightFront = 17
        RightBottom = 18
        RightBack = 19
        LeftTop = 20        ' Now put top at left, rotate front face
        LeftFront = 21
        LeftBottom = 22
        LeftBack = 23
    End Enum

    ' This is where it gets even harder...  This class tells what side of the cube is seen where,
    ' when the cube is in a specific orientation.  If the top of the cube is to the left (one of
    ' the Left... orientations), then ShownSides(Side.Left) will return Side.Top because the Top
    ' side is the one that's on the left.
    Public Class OrientationTransformation

        Public ShownSides(6) As Side

        Public Sub New(ByVal TopSide As Side, ByVal FrontSide As Side, _
                       ByVal RightSide As Side, ByVal BackSide As Side, _
                       ByVal LeftSide As Side, ByVal BottomSide As Side)
            ShownSides(Side.Top) = TopSide
            ShownSides(Side.Front) = FrontSide
            ShownSides(Side.Right) = RightSide
            ShownSides(Side.Back) = BackSide
            ShownSides(Side.Left) = LeftSide
            ShownSides(Side.Top) = TopSide
        End Sub
    End Class


    ' This will contain the side correspondances for all 24 orientations of a cube
    Public Shared OrientationLookup(24) As OrientationTransformation


    ' Data about a single cube
    Public Class cube

        Public Sub New(ByVal TopColor As Color, ByVal FrontColor As Color, _
                       ByVal RightColor As Color, ByVal BackColor As Color, _
                       ByVal LeftColor As Color, ByVal BottomColor As Color, _
                       ByVal CubeID As Integer)
            ID = CubeID
            Colors(Side.Top) = TopColor
            Colors(Side.Front) = FrontColor
            Colors(Side.Right) = RightColor
            Colors(Side.Back) = BackColor
            Colors(Side.Left) = LeftColor
            Colors(Side.Bottom) = BottomColor
            Used = False
        End Sub

        Public ID As Integer           ' Cube ID, to be used when printing solution
        Public Colors(6) As Integer    ' Repartition of the colors around the cube
        Public Used As Boolean         ' Is this cube already placed?
        Public X, Y, Z As Integer      ' If cube is placed, where is it in larger cube (X to the right, Y to the back, Z upwards)
        Public Orient As Orientation   ' Orientation of the cube in the larger referential

        ' This function will return the color shown on the larger referential's side by the
        ' cube, taking into consideration it's orientation.
        '
        ' For example, if a cube has Red on its bottom and is oriented "RightFront", meaning
        ' the cube's top face is at right and it's front face is at front, then
        ' Orient(Side.Left) will return Red because it is the bottom face that is on the left.
        Public Function OrientedColor(ByVal s As Side)
            Return Colors(OrientationLookup(Orient).ShownSides(s))
        End Function

    End Class

    ' This will contain the data for all the individual cubes
    Public Shared AllCubes As New Collection

    ' We will also use a "cube" to note the known colors of the overall cube.
    Public Shared LargeCube As New cube(Nothing, Nothing, Nothing, Nothing, Nothing, Nothing, 0)

    Public Class Search

        Public Sub start()

            ' This is the real ugly part, couldn't think of an easy way to generate
            ' the side correspondance table automatically.  Let's hope there is no error.
            ' You need a good 3d visualisation mind here!  Had to make a little cube and
            ' mark it, then rotate it...
            ' The order of constructor is Top, Front, Right, Back, Left, Bottom.

            ' top on top, rotate front face

            ' First one is straigthforward, they match one-to-one
            OrientationLookup(Orientation.TopFront) = New OrientationTransformation(Side.Top, Side.Front, Side.Right, Side.Back, Side.Left, Side.Bottom)
            ' Second one: Top on top, bottom on bottom.  In a TopRight orientation,
            ' what's the side shown on front? left side.  Then on Right?  Front side.  And so on....
            OrientationLookup(Orientation.TopRight) = New OrientationTransformation(Side.Top, Side.Left, Side.Front, Side.Right, Side.Back, Side.Bottom)
            OrientationLookup(Orientation.TopBack) = New OrientationTransformation(Side.Top, Side.Back, Side.Left, Side.Front, Side.Right, Side.Bottom)
            OrientationLookup(Orientation.TopLeft) = New OrientationTransformation(Side.Top, Side.Right, Side.Back, Side.Left, Side.Front, Side.Bottom)
            'top is now in front, rotate front face
            OrientationLookup(Orientation.FrontBottom) = New OrientationTransformation(Side.Back, Side.Top, Side.Right, Side.Bottom, Side.Left, Side.Front)
            OrientationLookup(Orientation.FrontRight) = New OrientationTransformation(Side.Right, Side.Top, Side.Front, Side.Bottom, Side.Back, Side.Left)
            OrientationLookup(Orientation.FrontTop) = New OrientationTransformation(Side.Front, Side.Top, Side.Left, Side.Bottom, Side.Right, Side.Back)
            OrientationLookup(Orientation.FrontLeft) = New OrientationTransformation(Side.Left, Side.Top, Side.Back, Side.Bottom, Side.Front, Side.Right)
            'top is now on the bottom, rotate front face
            OrientationLookup(Orientation.BottomBack) = New OrientationTransformation(Side.Bottom, Side.Back, Side.Right, Side.Front, Side.Left, Side.Top)
            OrientationLookup(Orientation.BottomLeft) = New OrientationTransformation(Side.Bottom, Side.Left, Side.Back, Side.Right, Side.Front, Side.Top)
            OrientationLookup(Orientation.BottomFront) = New OrientationTransformation(Side.Bottom, Side.Front, Side.Left, Side.Back, Side.Right, Side.Top)
            OrientationLookup(Orientation.BottomRight) = New OrientationTransformation(Side.Bottom, Side.Right, Side.Front, Side.Left, Side.Back, Side.Top)
            'Top is now in back, rotate front face
            OrientationLookup(Orientation.BackTop) = New OrientationTransformation(Side.Front, Side.Bottom, Side.Right, Side.Top, Side.Left, Side.Back)
            OrientationLookup(Orientation.BackLeft) = New OrientationTransformation(Side.Right, Side.Bottom, Side.Back, Side.Top, Side.Front, Side.Left)
            OrientationLookup(Orientation.BackBottom) = New OrientationTransformation(Side.Back, Side.Bottom, Side.Left, Side.Top, Side.Right, Side.Front)
            OrientationLookup(Orientation.BackRight) = New OrientationTransformation(Side.Left, Side.Bottom, Side.Front, Side.Top, Side.Back, Side.Right)
            ' Top is at right, rotate front face
            OrientationLookup(Orientation.RightTop) = New OrientationTransformation(Side.Front, Side.Right, Side.Top, Side.Left, Side.Bottom, Side.Back)
            OrientationLookup(Orientation.RightFront) = New OrientationTransformation(Side.Left, Side.Front, Side.Top, Side.Back, Side.Bottom, Side.Right)
            OrientationLookup(Orientation.RightBottom) = New OrientationTransformation(Side.Back, Side.Left, Side.Top, Side.Right, Side.Bottom, Side.Front)
            OrientationLookup(Orientation.RightBack) = New OrientationTransformation(Side.Right, Side.Back, Side.Top, Side.Front, Side.Bottom, Side.Left)
            ' Top is at left, rotate front face
            OrientationLookup(Orientation.LeftTop) = New OrientationTransformation(Side.Front, Side.Left, Side.Bottom, Side.Right, Side.Top, Side.Back)
            OrientationLookup(Orientation.LeftFront) = New OrientationTransformation(Side.Right, Side.Front, Side.Bottom, Side.Back, Side.Top, Side.Left)
            OrientationLookup(Orientation.LeftBottom) = New OrientationTransformation(Side.Back, Side.Right, Side.Bottom, Side.Left, Side.Top, Side.Front)
            OrientationLookup(Orientation.LeftBack) = New OrientationTransformation(Side.Left, Side.Back, Side.Bottom, Side.Front, Side.Top, Side.Right)



            ' Create the cubes (they will all be marked "unused" by the constructor)
            '
            '  ********** Specify the color disposition of your cubes here *********
            '            
            ' Order of colors: Top, Front, Right, Back, Left, Bottom
            '
            AllCubes.Add(New cube(Color.Red, Color.Green, Color.Cyan, Color.Blue, Color.Magenta, Color.Yellow, 1))
            AllCubes.Add(New cube(Color.Red, Color.Green, Color.Magenta, Color.Blue, Color.Cyan, Color.Yellow, 2))
            AllCubes.Add(New cube(Color.Red, Color.Green, Color.Yellow, Color.Cyan, Color.Magenta, Color.Blue, 3))
            AllCubes.Add(New cube(Color.Red, Color.Green, Color.Magenta, Color.Cyan, Color.Yellow, Color.Blue, 4))
            AllCubes.Add(New cube(Color.Red, Color.Green, Color.Blue, Color.Magenta, Color.Yellow, Color.Cyan, 5))
            AllCubes.Add(New cube(Color.Red, Color.Green, Color.Blue, Color.Yellow, Color.Magenta, Color.Cyan, 6))
            AllCubes.Add(New cube(Color.Red, Color.Green, Color.Blue, Color.Yellow, Color.Cyan, Color.Magenta, 7))
            AllCubes.Add(New cube(Color.Red, Color.Blue, Color.Cyan, Color.Magenta, Color.Yellow, Color.Green, 8))

            FindFirstCube()

        End Sub

        Public Sub FindFirstCube()

            ' Try all the cubes in the first bottom, front left corner
            For Each firstCube As cube In AllCubes
                firstCube.Used = True

                Console.WriteLine("")
                Console.WriteLine("Trying cube ID {0}", firstCube.ID)
                Console.WriteLine("")

                ' Try all the possible orientations
                For orient As Orientation = Orientation.TopFront To Orientation.LeftBack

                    firstCube.Orient = orient
                    firstCube.X = 0
                    firstCube.Y = 0
                    firstCube.Z = 0

                    ' This already decides the color of three sides of the larger cube
                    LargeCube.Colors(Side.Bottom) = firstCube.OrientedColor(Side.Bottom)
                    LargeCube.Colors(Side.Front) = firstCube.OrientedColor(Side.Front)
                    LargeCube.Colors(Side.Left) = firstCube.OrientedColor(Side.Left)

                    FindSecondCube()

                Next

                firstCube.Used = False
            Next

            Console.WriteLine("")
            Console.WriteLine("Finished!")

        End Sub

        Public Sub FindSecondCube()

            ' Try all the cubes in the first bottom, back left corner
            For Each secondCube As cube In AllCubes

                ' Cube must not already be used....
                If Not secondCube.Used Then

                    ' Try all the possible orientations
                    For orient As Orientation = Orientation.TopFront To Orientation.LeftBack

                        secondCube.Orient = orient

                        ' Check that in this orientation, left & bottom face are the right color
                        ' and that what will be the back color is not already used in front
                        If (secondCube.OrientedColor(Side.Left) = LargeCube.Colors(Side.Left) AndAlso _
                            secondCube.OrientedColor(Side.Bottom) = LargeCube.Colors(Side.Bottom) AndAlso _
                            secondCube.OrientedColor(Side.Back) <> LargeCube.Colors(Side.Front)) Then

                            secondCube.Used = True

                            secondCube.X = 0
                            secondCube.Y = 1
                            secondCube.Z = 0

                            ' This decides the color of back side of the larger cube
                            LargeCube.Colors(Side.Back) = secondCube.OrientedColor(Side.Back)

                            FindThirdCube()
                            secondCube.Used = False

                        End If

                    Next
                End If

            Next

        End Sub

        Public Sub FindThirdCube()

            ' Try all the cubes in the bottom, front right corner
            For Each thirdCube As cube In AllCubes

                ' Cube must not already be used....
                If Not thirdCube.Used Then

                    ' Try all the possible orientations
                    For orient As Orientation = Orientation.TopFront To Orientation.LeftBack

                        thirdCube.Orient = orient

                        ' Check that in this orientation, front & bottom face are the right color
                        ' and that what will be the right color is not already used in left or back
                        If (thirdCube.OrientedColor(Side.Front) = LargeCube.Colors(Side.Front) AndAlso _
                            thirdCube.OrientedColor(Side.Bottom) = LargeCube.Colors(Side.Bottom) AndAlso _
                            thirdCube.OrientedColor(Side.Right) <> LargeCube.Colors(Side.Left) AndAlso _
                            thirdCube.OrientedColor(Side.Right) <> LargeCube.Colors(Side.Back)) Then

                            thirdCube.Used = True

                            thirdCube.X = 1
                            thirdCube.Y = 0
                            thirdCube.Z = 0


                            ' This decides the color of right side of the larger cube
                            LargeCube.Colors(Side.Right) = thirdCube.OrientedColor(Side.Right)

                            FindFourthCube()
                            thirdCube.Used = False

                        End If

                    Next
                End If

            Next

        End Sub

        Public Sub FindFourthCube()

            ' Try all the cubes in the bottom, back right corner
            For Each fourthCube As cube In AllCubes

                ' Cube must not already be used....
                If Not fourthCube.Used Then

                    ' Try all the possible orientations
                    For orient As Orientation = Orientation.TopFront To Orientation.LeftBack

                        fourthCube.Orient = orient

                        ' Check that in this orientation, right, back & bottom face are the right color
                        If (fourthCube.OrientedColor(Side.Back) = LargeCube.Colors(Side.Back) AndAlso _
                            fourthCube.OrientedColor(Side.Bottom) = LargeCube.Colors(Side.Bottom) AndAlso _
                            fourthCube.OrientedColor(Side.Right) = LargeCube.Colors(Side.Right)) Then

                            fourthCube.Used = True

                            fourthCube.X = 1
                            fourthCube.Y = 1
                            fourthCube.Z = 0

                            FindFifthCube()
                            fourthCube.Used = False

                        End If

                    Next
                End If

            Next

        End Sub

        Public Sub FindFifthCube()

            ' Try all the cubes in the top, front left corner
            For Each fifthCube As cube In AllCubes

                ' Cube must not already be used....
                If Not fifthCube.Used Then

                    ' Try all the possible orientations
                    For orient As Orientation = Orientation.TopFront To Orientation.LeftBack

                        fifthCube.Orient = orient

                        ' Check that in this orientation, front and left face are the right color
                        ' and that what will be the top color is not already used in right, back or bottom
                        If (fifthCube.OrientedColor(Side.Front) = LargeCube.Colors(Side.Front) AndAlso _
                            fifthCube.OrientedColor(Side.Left) = LargeCube.Colors(Side.Left) AndAlso _
                            fifthCube.OrientedColor(Side.Top) <> LargeCube.Colors(Side.Right) AndAlso _
                            fifthCube.OrientedColor(Side.Top) <> LargeCube.Colors(Side.Back) AndAlso _
                            fifthCube.OrientedColor(Side.Top) <> LargeCube.Colors(Side.Bottom)) Then

                            fifthCube.Used = True

                            fifthCube.X = 0
                            fifthCube.Y = 0
                            fifthCube.Z = 1


                            ' This decides the color of right side of the larger cube
                            LargeCube.Colors(Side.Top) = fifthCube.OrientedColor(Side.Top)

                            FindSixthCube()
                            fifthCube.Used = False

                        End If

                    Next
                End If

            Next

        End Sub

        Public Sub FindSixthCube()

            ' Try all the cubes in the top, back left corner
            For Each sixthCube As cube In AllCubes

                ' Cube must not already be used....
                If Not sixthCube.Used Then

                    ' Try all the possible orientations
                    For orient As Orientation = Orientation.TopFront To Orientation.LeftBack

                        sixthCube.Orient = orient

                        ' Check that in this orientation, left, back and top face are the right color
                        If (sixthCube.OrientedColor(Side.Back) = LargeCube.Colors(Side.Back) AndAlso _
                            sixthCube.OrientedColor(Side.Left) = LargeCube.Colors(Side.Left) AndAlso _
                            sixthCube.OrientedColor(Side.Top) = LargeCube.Colors(Side.Top)) Then

                            sixthCube.Used = True

                            sixthCube.X = 0
                            sixthCube.Y = 1
                            sixthCube.Z = 1

                            FindSeventhCube()
                            sixthCube.Used = False

                        End If

                    Next
                End If

            Next

        End Sub

        Public Sub FindSeventhCube()

            ' Try all the cubes in the top, front right corner
            For Each seventhCube As cube In AllCubes

                ' Cube must not already be used....
                If Not seventhCube.Used Then

                    ' Try all the possible orientations
                    For orient As Orientation = Orientation.TopFront To Orientation.LeftBack

                        seventhCube.Orient = orient

                        ' Check that in this orientation, front, right and top face are the right color
                        If (seventhCube.OrientedColor(Side.Front) = LargeCube.Colors(Side.Front) AndAlso _
                            seventhCube.OrientedColor(Side.Right) = LargeCube.Colors(Side.Right) AndAlso _
                            seventhCube.OrientedColor(Side.Top) = LargeCube.Colors(Side.Top)) Then

                            seventhCube.Used = True

                            seventhCube.X = 1
                            seventhCube.Y = 0
                            seventhCube.Z = 1

                            FindEighthCube()
                            seventhCube.Used = False

                        End If

                    Next
                End If

            Next

        End Sub

        Public Sub FindEighthCube()

            ' Try all the cubes in the top, front right corner
            For Each eighthCube As cube In AllCubes

                ' Cube must not already be used....
                If Not eighthCube.Used Then

                    ' Try all the possible orientations
                    For orient As Orientation = Orientation.TopFront To Orientation.LeftBack

                        eighthCube.Orient = orient

                        ' Check that in this orientation, back, right and top face are the right color
                        If (eighthCube.OrientedColor(Side.Back) = LargeCube.Colors(Side.Back) AndAlso _
                            eighthCube.OrientedColor(Side.Right) = LargeCube.Colors(Side.Right) AndAlso _
                            eighthCube.OrientedColor(Side.Top) = LargeCube.Colors(Side.Top)) Then

                            eighthCube.Used = True

                            eighthCube.X = 1
                            eighthCube.Y = 1
                            eighthCube.Z = 1

                            printsolution()

                            eighthCube.Used = False

                        End If

                    Next
                End If

            Next

        End Sub

        Public Sub printsolution()

            Console.WriteLine("")
            Console.WriteLine("Here's a solution!")
            Console.WriteLine("")
            For Each cube As cube In AllCubes
                Console.WriteLine("   Cube ID {0} at ({1},{2},{3}) with {4} on top and {5} towards you", _
                                  cube.ID, cube.X, cube.Y, cube.Z, _
                                  cube.OrientedColor(Side.Top), cube.OrientedColor(Side.Front))
            Next
            Console.WriteLine("")
        End Sub

    End Class

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        Dim s As New Search
        s.start()
    End Sub
End Class

--------------------------------------------------------------------
0
 
LVL 5

Author Comment

by:burningmace
ID: 12370122
Thanks a lot dan-q
Worked great!

Sorry about the lack of comments, it's hard to find time to read solutions with college.
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

This article explains all about SQL Server Piecemeal Restore with examples in step by step manner.
Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now