how to build and solve puzzles

Definition

'box' is used as smalest cube unit.
Puzzle 'parts' are build of several boxes.
Typically with the same amount of boxes.
'Puzzle' are build of several puzzle parts.

How to rotate

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 green box on each possible side of the base puzzle.
There are max 4 positions in the 2D world
and max 6 positions in the 3D world.
Note: not each tested position will result in a new unique puzzle.
We add only real new unique puzzles into a List.

This list contains only unique puzzles without any rotated view. To check, if a new puzzle is unique, we create first all up to 24 rotation products and check for equal entries in the list.

Now we can build the next puzzle with 3 boxes, exapanding once more. This is done in a recursive way using a 3 dimensional test array:

create(level) {
    while findFreePosAtStone {
        set position
        if addThis		// is a new unique puzzle
            create(next level)
        rset position
    }
}

Example #puzzle=4 in 2D World

Level1:	create single Box
	X
Level2:	add box
	XX
Level3:	add box
	XXX

Level4:	add box
	XXXX

	XXX
	X..
	
	XXX
	.X.

Level3:	add box continue
	XX
	X.

Level4: add box continue
	.XX
	XX.

	XX
	X.

Speed

These are some criterias to speed up the process:

Environment
Testing with MinGW, Windows Visual Studio, Debian@Windows, Debian@VMware
it seems that the fastest results are possible with g++ and Debian@Windows
Compiler option
unsing gnu compiler with -g -O1 for g++ (seems to get best results!)
Also tested -O2 -O3 -Ofast and without -g
large hash table
If more then 2GB in size, then speed goes down, but collisions in hash tables are reduced.
Reduce collisions in hash table
Use double hashing to avoid clustering.
Algoryhtm
Another try was, to save aswell the rotations in the list. But this will increase storage needs for the list and slowdown the process.

1D, 2D or 3D

There are 2D puzzles with dimension in x and y direction.
If we assume, it is a flat puzzle and the puzzle could only rotated in x/y, then we call it 1D.
Example:

Only 2 red unique puzzles and more gray rotated puzzles exists.

If we think we could flip the 2D puzzle (bottom side will flip to upper side), then we call it 2D.
Example:

This means, we are in the 3D world and have a puzzle with 2 Dimensions only.

If we have a puzzle in 3 Dimensions, then we call it 3D.
Example:

How to display SVG

Most SVG Images are created on the fly. A php program is used, to call the javaShow program with some arguments.

-string maxX maxY maxZ      solutionString
-vector vector
-file   solution_file nbr

-scale       <0.3 .. 10>         for smaller or bigger cubes,        default: 1.0
-ani         <0..9>              AnimationNbr, just try;             default: 8
-label                           add abc char on each side of box;   default: false
-gray                            create a gray box only;             default: false
-all                             option for -file
-title                           use this String on puzzle
-parts                           create multipe SVGs for all parts;  default: false
-opt                             optimize SVG output;                default: false

The java program will report all generated SVG to stdout. Some valid examples:

java -jar PuzzleShow.jar -string 3 1 1 ABC
	creates a ABC puzzle in one line
java -jar PuzzleShow.jar -vector [0,0,0][1,0,0][2,0,0]
	another 3 element puzzle in on line
java -jar PuzzleShow.jar -file puzzle.lsg 7
	read a file called puzzle.lsg and use solution number 7 for SVG creation

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

Results

See also online encyclopedia integer sequences.
The following table lists the calculation results and provides some links to created puzzle images.

Notes:

Calculated on Intel(R) Core(TM) i5-8400 CPU @ 2,80 GHz
Now rewritten in Java with some improvemets for speed.

using HashMap from JAVA
building a more efficent hash key
use Memory -Xms12G for big results

provide reduced and a full list of puzzles

1D A000988				2D A000105				3D A000162
# parts	SVG	calc time	# puzzles download	# parts	SVG	calc time	# puzzles download	# parts	SVG	calc time	# puzzles download
1	SVG	00:00:00,0	1	1	SVG	00:00:00,0	1	1	SVG	00:00:00,0	1
2	SVG	00:00:00,0	1	2	SVG	00:00:00,0	1	2	SVG	00:00:00,0	1
3	SVG	00:00:00,0	2	3	SVG	00:00:00,0	2	3	SVG	00:00:00,0	2
4	SVG	00:00:00,0	7	4	SVG	00:00:00,0	5	4	SVG	00:00:00,0	8
5	SVG	00:00:00,0	18	5	SVG	00:00:00,0	12	5	SVG	00:00:00,0	29
6	SVG	00:00:00,0	60	6	SVG	00:00:00,0	35	6	SVG	00:00:00,0	166
7	SVG	00:00:00,0	196	7	SVG	00:00:00,0	108	7	SVG	00:00:00,0	1 023
8	SVG	00:00:00,0	704	8	SVG	00:00:00,0	369	8	SVG	00:00:00,1	6 922
9	SVG	00:00:00,0	2 500	9	SVG	00:00:00,0	1 285	9	SVG	00:00:00,9	48 311
10	SVG	00:00:00,1	9 189	10	SVG	00:00:00,1	4 655	10	SVG	00:00:06,4	346 543
11	SVG	00:00:00,2	33 896	11	SVG	00:00:00,2	17 073	11	SVG	00:01:03,9	2 522 522
12	SVG	00:00:00,8	126 759	12	SVG	00:00:00,7	63 600	12	SVG	00:09:10,2	18 598 427
13	SVG	00:00:03,3	476 270	13	SVG	00:00:02,6	238 591	13	SVG	01:39:02,2	138 462 649
14	SVG	00:00:14,1	1 802 312	14	SVG	00:00:11,3	901 971
15	SVG	00:01:02,2	6 849 777	15	SVG	00:00:51,5	3 426 576
16	SVG	00:04:27,5	26 152 418	16	SVG	00:03:45,1	13 079 255
17	SVG	00:26:33,1	100 203 194	17	SVG	00:19:03,1	50 107 909

Puzzle builds

prev. Solutions

Rolf LANG - Remsstr. 39 - 71384 Weinstadt | 08:19:07 up 4 days, 19:08, 0 users, load average: 0.01, 0.10, 0.09

how to build and solve puzzles

Definition

How to rotate

Basic

24 rotations

rot 0

rot 1

rot 2

rot 3

rot 4

rot 5

rot 6

rot 7

rot 8

rot 9

rot 10

rot 11

rot 12

rot 13

rot 14

rot 15

rot 16

rot 17

rot 18

rot 19

rot 20

rot 21

rot 22

rot 23