how to build puzzle parts



Definition

  • 'box' or 'cube' is used as smalest unit and exists in 2D and as 3D
  • Puzzle 'parts' are build of several boxes.
  • 'Puzzle' are build of several puzzle parts.
  • 2D
    parts do have a dimension in x and y direction.
    Flip bottom side to upper side does create another puzzle.
    Example:
    This means, we are in the 3D world and have a puzzle with 2 Dimensions only.

  • 1D
    parts do have a dimension in x and y direction.
    Flip bottom side to upper side does create another puzzle.
    Example:
    Only 2 red unique puzzles and more gray rotated puzzles exists.

  • 3D
    parts do have a dimension in x,y and zdirection.
    Example:

Basic

All we need to know are 3 basic rotations, wich can build 90 degree rotated puzzles:
rot Y Matrix
         0  0  1
         0  1  0
         -1  0  0
rot X Matrix
         1  0  0
         0  0  -1
         0  1  0
rotZ Matrix
         0 -1  0
         1  0  0
         0  0  1
Assume we have a Vector for 5 elements like this [0,0,0][0,1,0][0,2,0][0,3,0][1,3,0] .
If we want to rotate this puzzle with 90 degree around y axis then we use the given Y Matrix.
	x' = 0*x + 0*y + 1*z
	y' = y
	z' = -x

24 rotations

rot 0



[0,0,0]
[0,1,0]
[0,2,0]
[0,3,0]
[1,3,0]

rot 1



[0,3,0]
[0,0,1]
[0,1,1]
[0,2,1]
[0,3,1]

rot 2



[1,0,0]
[1,1,0]
[1,2,0]
[0,3,0]
[1,3,0]

rot 3



[0,0,0]
[0,1,0]
[0,2,0]
[0,3,0]
[0,3,1]

rot 4



[0,0,0]
[0,0,1]
[0,0,2]
[0,0,3]
[1,0,3]

rot 5



[3,0,0]
[0,0,1]
[1,0,1]
[2,0,1]
[3,0,1]

rot 6



[0,0,0]
[1,0,0]
[1,0,1]
[1,0,2]
[1,0,3]

rot 7



[0,0,0]
[1,0,0]
[2,0,0]
[3,0,0]
[0,0,1]
rotate X

rot 8



[0,0,0]
[0,0,1]
[0,0,2]
[0,0,3]
[0,1,3]

rot 9



[0,0,0]
[1,0,0]
[2,0,0]
[3,0,0]
[3,1,0]

rot 10



[0,0,0]
[0,1,0]
[0,0,1]
[0,0,2]
[0,0,3]

rot 11



[0,0,0]
[1,0,0]
[2,0,0]
[3,0,0]
[0,1,0]

rot 12



[0,0,0]
[0,1,0]
[0,2,0]
[0,3,0]
[0,0,1]

rot 13



[0,0,0]
[1,0,0]
[0,1,0]
[0,2,0]
[0,3,0]

rot 14



[0,0,0]
[0,0,1]
[0,1,1]
[0,2,1]
[0,3,1]

rot 15



[0,0,0]
[1,0,0]
[1,1,0]
[1,2,0]
[1,3,0]
rotate Z rotate X

rot 16



[0,0,0]
[1,0,0]
[2,0,0]
[3,0,0]
[3,0,1]

rot 17



[0,0,0]
[1,0,0]
[0,0,1]
[0,0,2]
[0,0,3]

rot 18



[0,0,0]
[0,0,1]
[1,0,1]
[2,0,1]
[3,0,1]

rot 19



[1,0,0]
[1,0,1]
[1,0,2]
[0,0,3]
[1,0,3]

rot 20



[3,0,0]
[0,1,0]
[1,1,0]
[2,1,0]
[3,1,0]

rot 21



[0,0,0]
[0,1,0]
[0,1,1]
[0,1,2]
[0,1,3]

rot 22



[0,0,0]
[0,1,0]
[1,1,0]
[2,1,0]
[3,1,0]

rot 23



[0,1,0]
[0,1,1]
[0,1,2]
[0,0,3]
[0,1,3]
rotate Z rotate X

How to build

First, we start with one single red box.
Now we expand this, using the following steps:
We start to add a new box on each possible side of the base box.
There are max 4 positions in the 2D world
and additional 2 positions in the 3D world.
We use a vector notation [x,y,z] or [x,y] for a box.repeated
Example: [0,0,0] [1,0,0] [2,0,0] [3,0,0] [3,1,0]
Each box is saved in a 64Bit long integer = x + 32*y + 32²*z
and the list of boxes is saved as array, sorted in ascending order.
Now we build up to 24 rotations for 3D parts
After rotate we need to standardize the part by moving to origin and sort the box sequence
For each rotation we check, if we already know it.
If all rotations are not found, we save it in a parts list. So the list will contain only unique puzzles.
We use hashing to get fast access.
The hash.key is build
If all positions are expanded, we increase to number of boxes.

Speed

These are some criterias to speed up the process:
  1. large hash table
    To store all valid parts, the hash table needs to be realy big.
    Assume we have a partslist for all parts with 5 boxes.
    Next we walk in sequence for all parts, expand it and store as partslist with 6 boxes.
    To save space, we release the current parts If more then 2GB in size, then speed goes down, but collisions in hash tables are reduced.
  2. Reduce collisions in hash table
    Use double hashing to avoid clustering.

How to display SVG

Most SVG Images are created on the fly.
A php program is used, to call the PuzzleShow.jar program with some arguments.
The java program will report all generated SVG to stdout.
Some valid examples:
argsSVG
-string 1 1 1 0








		
		
		
		
		
		
		
		
		






















-vector [0,0]








		
		
		
		
		
		
		
		
		






















-pdef [0,1][1,1]








		
		
		
		
		
		
		
		
		
























-scale 3 -vector [0,0]








		
		
		
		
		
		
		
		
		






















-3D -vector [0,0,0]










		
		
		
		
		
		
		
		
		





























-string 2 1 1 0 1








		
		
		
		
		
		
		
		
		































-scale 2 -3D -vector [0,0,0][1,0,0][0,0,1]










		
		
		
		
		
		
		
		
		










































-title A -vector [0,0]

A







		
		
		
		
		
		
		
		
		






















-label -3D -scale 3 -string 3 1 1 1 2 3










		
		
		
		
		
		
		
		
		






 1	 1	 1	





 2	 2	 2	





 3	 3	 3	










































-noFatLines -scale 3 -vector [0,0]








		
		
		
		
		
		
		
		
		


















-string 11 1 1 0 1 2 3 4 5 6 7 8 9 10








		
		
		
		
		
		
		
		
		
















































































































-2D -vector [0,0][1,0][2,0]








		
		
		
		
		
		
		
		
		




























-gray -vector [0,0][1,0][1,1]








		
		
		
		
		
		
		
		
		




























-gray -rot -vector [0,0][1,0][1,1]

rot_1







		
		
		
		
		
		
		
		
		





























rot_2







		
		
		
		
		
		
		
		
		





























rot_3







		
		
		
		
		
		
		
		
		





























rot_4







		
		
		
		
		
		
		
		
		



























-usage
---------------------------------------------------------------------------------
Welcome to my puzzle svg creator
---------------------------------------------------------------------------------
-string      maxX maxY maxZ      solutionString
                                 _ whole
                                 +,@ free position, not set
                                 1 2 3 4 ... positions set
-vector      vector              [x,y,z]
-pdef        vector              [x,y,z] puzzle definition
-3D                              show 3D puzzle                       default: false
-2D                              show 2D puzzle                       default: true
-1D                              show 2D puzzle with flip option      default: false
-axis                            show axis x,y,z                      default: true
-no          vector              not used puzzles
-rot                             create all rotations                 default: false

-scale       <0.3 .. 10>         for smaller or bigger cubes,         default: 1.0
-ani         <0..9>              AnimationNbr, just try;              default: 0
-noFatLines                      hide fat lines for puzzle            default: false
-label                           add abc char on each side of box;    default: false
-gray                            create a gray box only;              default: false
-title                           use this String on puzzle
-part                       create multipe SVGs for all parts;   default: false 
-layer                      create multipe SVGs for all y layers default: false 

e.g.: java -jar PuzzleShow.jar -vector [0,0,0][1,0,0][2,0,0][0,1,0]
      java -jar PuzzleShow.jar -scale 10 -string 5 1 1 0 _ 1 + 2

Programs

These programs are used:
  • puzzle.c
    a C program to build all the basic puzzles. The Source Code could be compiled with gcc.
  • JPuzzle.jar
    this progam find a solution for puzzles.
    java -jar JPuzzle.jar
    ---------------------------------------------------------------------------------
    Welcome to my puzzle solver
    ---------------------------------------------------------------------------------
    reading args:
    mandatory arguments, either by file or cmd line:
                    -box X Y Z              put puzzles into a box with X,Y,Z size
                    -pdef [0,0,0]..         puzzle definition as multipe vector[x][y][z] or vector[x][y]
    optional arguments:
                    -conf filename          read args from filename
                    -title a title          a short title for this puzzle
                    -desc more txt          a description for this puzzle
                    -stop                   stop after first solution
                    -stop n                 stop after n solutions, where n>1
                    -kill n                 stop after n seconds
                    -thread            define max  running threads
                    -pinc         include file with -pdef puzzle Definitions
    special optional arguments:
                    -disp                   report exeTime & thread
                    -sql                    insert solution in MySQL database
                    -unique                 report unique puzzles only
                    -groupBy                common name for same group of puzzles
                    -verbose                more output for debugging
                    -dispThread             show start/finish of running threads
                    -sortAsc                sort puzzle sequence based on number of sets asc
                    -sortDesc               sort puzzle sequence based on number of sets desc
                    -single                 use only a single puzzle many times
                    -3D                     puzzle is in 3D
                    -2D                     puzzle is in 2D
                    -1D                     puzzle is in 1D
                    -keyGen            define x,y,z sequence, where 0....5
                    -opt                    use optimized fill up sequence
                    -wholeChk               chk for isolated wholes
                    -twinWholeChk           chk for isolated twin wholes
    example:
                    java -jar JPuzzle.jar -box 3 2 1 -2D -single -pdef [0,0][0,1][0,2][1,0] -pdef [0,0][0,1]
    ...terminating
    
    By default there are 2 files created during the run
    • a log file with with puzzlenumber, max rotation and a vector List and 3D indicator. It contains a lot of lines like
      p_6918  rot 24  [1,1,0][0,2,0][1,2,0][2,0,1][1,1,1][2,1,1][0,2,1][2,0,2]        3D
                  
    • A solution file with a SVG filename;dimension x,y,z; char position. e.g.
      8_3D_2592_24.svg        3 3 3 _AA__A_AA_A_______AA_______
                  
      and a solution section for all puzzles filled into the box definition.

  • puzzleRun.jar
    this program automates the process.
  • PuzzleShow.jar
    this program creates SVG files.
    ---------------------------------------------------------------------------------
    Welcome to my puzzle svg creator
    ---------------------------------------------------------------------------------
    -string      maxX maxY maxZ      solutionString
                                     _ whole
                                     + free position, not set
                                     1 2 3 4 ... positions set
    -vector      vector              [x,y,z]
    -pdef        vector              [x,y,z] puzzle definition
    -3D                              show 3D puzzle                       default: false
    -2D                              show 2D puzzle                       default: true
    -no          vector              not used puzzles
    
    -scale       <0.3 .. 10>         for smaller or bigger cubes,         default: 1.0
    -ani         <0..9>              AnimationNbr, just try;              default: 0
    -noFatLines                      hide fat lines for puzzle            default: false
    -label                           add abc char on each side of box;    default: false
    -gray                            create a gray box only;              default: false
    -title                           use this String on puzzle
    -part        <nbr>               create multipe SVGs for all parts;   default: false 
    -layer       <nbr>               create multipe SVGs for all y layers default: false 
    
    e.g.: java -jar PuzzleShow.jar -vector [0,0,0][1,0,0][2,0,0][0,1,0]
          java -jar PuzzleShow.jar -scale 10 -string 5 1 1 0 _ 1 + 2
    	  
    Examples:
    java -jar PuzzleShow.jar -vector [0,0,0][1,0,0][2,0,0][0,1,0]
    java -jar PuzzleShow.jar -vector [0,0,0][1,0,0][2,0,0][0,1,0] -3D
    java -jar PuzzleShow.jar -scale 2 -string 5 1 1 0 _ 1 + 2 -3D
    java -jar PuzzleShow.jar -scale 2 -string 5 1 1 0 _ 1 + 2 -3D -label -title demo-titel

Rolf LANG - Remsstr. 39 - 71384 Weinstadt | 07:36:32 up 29 days, 10:03, 1 user, load average: 0.23, 0.12, 0.10