The S U P E R C U B E 10x10 is puzzle where you have to create 10x10x10 cube from 82 small parts. In order to solve it, first you will need to print it, all parts available at www.myminifactory.com/object/3d-print-65009

 

resize-img-6259.jpg

 

Co-worker printed it and brought it to work, I tried to solve it... After 30min, started to wonder, is it possible to write application that would solve it ?

 

Parsing all peaces

All pieces are in STL files, this only contains vertices and normals. For STL manipulations I'm using https://github.com/QuantumConcepts/STLdotNET 

To simplify process we need to make few adjustments to our pieces:

  1. Move piece to X=0, Y=0, Z=0 
  2. Scale down. Originally, all pieces are made from small rectangles that are 5mm size, scale down to 1mm.
  3. Convert all vertices (triangles) into rectangles. Simply by taking smallest bounding rectangle.

Now the hardes part is to find all points that are inside 3d object. To make algorithm demonstration easier, we will use simple L shaped piece (77.stl).

L_shape.PNG

 

 

 

We are checking if blue point is inside this object (in this case it's, just bear with me, I only have paint). Currently we are cheking if point has walls on x axis. Just take all walls that are vertical lines looking from this perspective.

 

Z_Y.png

Rotate object and only keep rectangles which encapsulates our point.

Z_Y.png

 

 

Now we are left with only two walls, if there is at least one wall which has larger X and at least one wall with smaller X, that means point has walls on X axis.

Z_Y.png 

 

 

Repeat same process for Y and Z axis. If point has wall in all of them, we can assume point is inside object. 

This algorithm is not perfect, but in this case it works perfectly fine even with complex objects.

Points for this L shaped piece would be:

x,y,z

0,0,0

0,1,0

0,2,0

0,3,0

1,0,0

2,0,0

 

Problem description

Since we are working in 3D space, each piece can be rotated around. If we want to put our L shaped piece at x=4,y=4,z=4 there are 24 different possibilities.

 

Created input file with following format:

First line containes numbe of pieces: N

Next there are N pieces description, each containing:

M (piece id, same as stl file name) and  P (number of points in object) separated by space.

Next 24 lines contains all possible different rotations for this object. Each line has P number of points, separated by spaces:

x[0] y[0] z[0] x[1] y[1] z[1] ... x[P - 1] y[P - 1] z[P - 1]  

 

Input data 

 

Solution guide

This puzzle has solution guid, it's outer walls of the cube. Parsing it is too complicated, instead I wrote small app that lets me color pieces on cube walls and try to identify which piece it is. If only one piece fits in colored pattern, we found correct piece. Using solution guide, it's possible to identify ~38 pieces. Sorry fo the colors, some of them are almost identical, didn't want to spend time picking 82 different colors, so I'm just using random colors.

Highilighted two points that are unsolvable, all pieces that are left unused at this point can't fit at any of these spots.

unsolvable.png

Even solution guide is dead end at this point. Will take break from this puzzle and write part 2 if by any accident I manage to solve it.

 

Comments


Comments are closed