Finding the way out of a six burr trap

At the local antique shop, where I do some IT support and answer technology questions, the owner said that they were in a bit of a jam. He had an item that required some technical support. A lot of what they sell in the shop is "Treen" ( small wooden items of functional and decorative purpose) which is a bit outside my usual fields of expertise but I am always happy to help. They had a small six piece puzzle that had come apart and he could not figure out how to reassemble the piece. A photo was available of the assembled piece but after after unsuccessfully fiddling with it for a while I took it back to the workbench for further consideration. 

How to get from this ->

All in pieces

To this ->
Reassembled
From the photo it was not clear how the internals of the puzzle are assembled ( which is of course the hard bit) but from the outside it can be seen that there are two parallel pieces going in each up/down, left/right, and front/back directions. Looking closely as the puzzle is rotated around the vertical axis to different viewpoints it can be seen that the crossing pieces change from one above other to side by side. Also each of the gaps between the parallel pieces line up with the centreline of the pair of pieces they embrace. 

For this antique puzzle there are two identical pieces and four different other shapes. Notably one of the pieces is a solid block with no cuts or notches. This key piece can be the last to be placed ( or first to be removed ) giving a very distinctive target stage. If the five non-key pieces can be assembled leaving a hole for the key the puzzle is solved. Working backwards from this near final stage it can be seen that the two vertical pieces face each other with a gap for the final piece and the other pieces wrap around but also pass below the final hole. However these helpful solving clues are not seen until the puzzle is reassembled.


The last step before solving or the "five piece stage"

Down the rabbit hole

Starting from just a pile of pieces and finish line photo I had a go figuring out how to reassemble the puzzle. I had no luck and none either from sister, brother-in-law, daughter or friend who all had a go. If brains can't get a problem solved sometimes money can help. A quick hunt on Amazon showed an identical looking puzzle for just a few pounds. This "practice" puzzle arrived assembled and would save the antique wooden pieces from too much handling, squeezing and pushing.  Before disassembling the ends of the pieces were marked with numbered stickers and with detailed photos taken. Carefully dissembling, with notes, showed how this puzzle could be reassembled.  Unfortunately when looking at the pieces of this puzzle it was clear that they are all different (except the key piece) and do not match the antique puzzle pieces. 

The process of disassembly and reassembly of this "practice" puzzle did provide some clues especially the final stage described above.

 

6 burr puzzle from Amazon

The pieces of this puzzle are all different from each other and mostly different from the vintage pieces except the solid Key piece and Y piece

Research time

Having two similar puzzles suggested that there may be more of this class of puzzle and that a computational solution finder might be fun to build. With only 6 pieces this puzzle did not seem so complex. 

At this point I came across the traditional interlocking burr page on the most excellent Robs puzzle pages. This page describes a classification system for puzzle pieces, some historical examples and groups of pieces that can be assembled into the same burr shape. Turns out, for this type of puzzle there are 25 possible pieces that would assemble in to about 300 different puzzles. There is a more complex puzzle type that assembles into burrs with hollows on the inside and there are thousands of those. 

Coding the puzzle pieces

The piece classification system on Robs puzzle page allows a piece to be described with a single number related to the blocks that have been removed. Each sub-block has a bit position in the piece description number. There is an identification tool to match pieces with the IDnumber showing a text graphic of the piece.

With this classification system the piece shapes in the two puzzles could be translated into two short text files as follows.

#Burr6 Collins Antiques Aug 2020

#Mark,IDValue,Name

0,1,SolidKeyBlock

1,120,ShortCup

2,3328,LongGapShort

3,3322,Tounge

4,3328,LongGapLong

5,3305,AngleShort

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

#Burr6 Amazon bought Aug 2020

#Mark,IDValue,Name

4,1,Key

1,188,Bottle opener

2,976,Enigma

3,768,Many

5,824,Abc824

6,1024,Y

Here are the pieces of the antique puzzle as seen by the program. Each piece is converted from it's reference number to four lines of six 1s and 0s representing the cutouts and blocks as pixels. With a bit of practice you can visualise the pieces from the Cubies lists. 

Pieces :Comments: #Burr6 Collins Antiques Aug 2020#Mark,IDValue,Name


Piece { mark:0, name:SolidKeyBlock, IDValue:1, Weight:12, Length:6

Cubies:  [ 

[0,0][1, 1, 1, 1, 1, 1]

[1,0][1, 1, 1, 1, 1, 1]

[0,1][1, 1, 1, 1, 1, 1]

[1,1][1, 1, 1, 1, 1, 1] ] }


Piece { mark:1, name:ShortCup, IDValue:120, Weight:6, Length:6

Cubies:  [ 

[0,0][1, 1, 1, 1, 1, 1]

[1,0][1, 1, 1, 1, 1, 1]

[0,1][1, 0, 0, 0, 1, 1]

[1,1][1, 0, 0, 0, 1, 1] ] }


Piece { mark:2, name:LongGapShort, IDValue:3328, Weight:2, Length:6

Cubies:  [ 

[0,0][1, 1, 0, 0, 1, 1]

[1,0][1, 1, 1, 1, 1, 1]

[0,1][1, 0, 0, 0, 0, 1]

[1,1][1, 0, 0, 0, 0, 1] ] }


Piece { mark:3, name:Tounge, IDValue:3322, Weight:4, Length:6

Cubies:  [ 

[0,0][1, 1, 0, 0, 1, 1]

[1,0][1, 1, 1, 1, 1, 1]

[0,1][1, 0, 0, 0, 0, 1]

[1,1][1, 0, 1, 1, 0, 1] ] }


Piece { mark:4, name:LongGapLong, IDValue:3328, Weight:2, Length:6

Cubies:  [ 

[0,0][1, 1, 0, 0, 1, 1]

[1,0][1, 1, 1, 1, 1, 1]

[0,1][1, 0, 0, 0, 0, 1]

[1,1][1, 0, 0, 0, 0, 1] ] }


Piece { mark:5, name:AngleShort, IDValue:3305, Weight:6, Length:6

Cubies:  [ 

[0,0][1, 1, 0, 0, 1, 1]

[1,0][1, 1, 1, 1, 1, 1]     

[0,1][1, 1, 0, 0, 0, 1]

[1,1][1, 1, 1, 1, 0, 1] ] }


Total pieces weight 32


Coding the layouts 

We look now at how to generate every possible arrangement of pieces in order to find one that fits together. Assembly starts with the key solid piece because it needs no rotation or flipping. The other five pieces are then selected in one of the 120 possible different orders ... 

[1, 2, 3, 4, 5], 
[2, 1, 3, 4, 5], 
[3, 1, 2, 4, 5], 
[1, 3, 2, 4, 5],  
........

[5, 4, 3, 1, 2], 

[5, 4, 3, 2, 1]


For each order of pieces there are 1024 ways to rotate those 5 placed pieces each into 4 positions 

[0, 0, 0, 0, 0], 

[1, 0, 0, 0, 0], 

[2, 0, 0, 0, 0], 

[3, 0, 0, 0, 0], 

[0, 1, 0, 0, 0], 

[1, 1, 0, 0, 0],

.....

[3, 3, 3, 3, 2], 

[0, 0, 0, 0, 3], 

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

[2, 0, 0, 0, 3]


and 32 ways to flip each of 5 pieces into 2 positions  (1=flipped end over end) 

[0, 0, 0, 0, 0], 

[1, 0, 0, 0, 0], 

[0, 1, 0, 0, 0], 

[1, 1, 0, 0, 0], 

[0, 0, 1, 0, 0], 

......

[0, 1, 1, 1, 1], 

[1, 1, 1, 1, 1]


120 piece orders where each has 1024 rotation possibilities with 32 piece flips There are 3932160 board layouts to try


In total we have 120 * 1024 * 32 just under 4 million piece layouts to try.

Make the code

With a way to visualise the pieces, and lists of how the pieces can be placed in the puzzle, the task of the program was to arrange the pieces and test to see if the puzzle was solved correctly. At the core of the program is a collection of 3 dimensional size 6 * 6 * 6 matrixes that are used to represent the placed pieces and the target final arrangement.  

Each arrangement of pieces are loaded into a test 6*6*6 matrix using the placement positions and directions table. As the pieces are loaded checks are made for overlapping pixels which cause the program to move on to the next test arrangement.

// 6 lots of 4 placement position vectors here 


// places   [  x, y, z, xD,yD,zD]  the start pixel address x,y,z and the delta for the next pixel            


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

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

//....... first piece placement above and last below

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

            [ 3, 3, 0,  0, 0, 1 ], [ 3, 4, 0,  0, 0, 1 ],


The program generates a list of piece arrangements (order, rotation, flip), details of the shape of the pieces and how to load those pieces into a test matrix. Finally the program needs to know how to test to see if we have a valid final arrangement.

The following columns represent salami slices through the puzzle at six levels. The P numbers show if there should be a pixel/cubie at that place.  The N numbers show how many pixels would be at that place if a burr was made from six solid key pieces.  Where the N numbers are not 0 or 1 shows us where the overlapping pixels may occur. Where the N numbers equal 1 shows the outer skin of the puzzle that must be intact for a correctly constructed puzzle.  


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

P [0,0,0,0,0,0] [0,0] N 0,0,0,0,0,0   

P [0,0,0,0,0,0] [0,1] N 0,0,0,0,0,0   

P [0,1,1,1,1,0] [0,2] N 0,1,1,1,1,0   

P [0,1,1,1,1,0] [0,3] N 0,1,1,1,1,0   

P [0,0,0,0,0,0] [0,4] N 0,0,0,0,0,0   

P [0,0,0,0,0,0] [0,5] N 0,0,0,0,0,0   

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

P [0,0,1,1,0,0] [1,0] N 0,0,1,1,0,0   

P [0,0,1,1,0,0] [1,1] N 0,0,1,1,0,0   

P [0,1,1,1,1,0] [1,2] N 0,1,2,2,1,0   

P [0,1,1,1,1,0] [1,3] N 0,1,2,2,1,0   

P [0,0,1,1,0,0] [1,4] N 0,0,1,1,0,0   

P [0,0,1,1,0,0] [1,5] N 0,0,1,1,0,0   

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

P [0,0,1,1,0,0] [2,0] N 0,0,1,1,0,0   

P [1,1,1,1,1,1] [2,1] N 1,1,2,2,1,1   

P [1,1,1,1,1,1] [2,2] N 1,2,3,3,2,1   

P [1,1,1,1,1,1] [2,3] N 1,2,3,3,2,1   

P [1,1,1,1,1,1] [2,4] N 1,1,2,2,1,1   

P [0,0,1,1,0,0] [2,5] N 0,0,1,1,0,0   

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

P [0,0,1,1,0,0] [3,0] N 0,0,1,1,0,0   

P [1,1,1,1,1,1] [3,1] N 1,1,2,2,1,1   

P [1,1,1,1,1,1] [3,2] N 1,2,3,3,2,1   

P [1,1,1,1,1,1] [3,3] N 1,2,3,3,2,1   

P [1,1,1,1,1,1] [3,4] N 1,1,2,2,1,1   

P [0,0,1,1,0,0] [3,5] N 0,0,1,1,0,0   

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

P [0,0,1,1,0,0] [4,0] N 0,0,1,1,0,0   

P [0,0,1,1,0,0] [4,1] N 0,0,1,1,0,0   

P [0,1,1,1,1,0] [4,2] N 0,1,2,2,1,0   

P [0,1,1,1,1,0] [4,3] N 0,1,2,2,1,0   

P [0,0,1,1,0,0] [4,4] N 0,0,1,1,0,0   

P [0,0,1,1,0,0] [4,5] N 0,0,1,1,0,0   

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

P [0,0,0,0,0,0] [5,0] N 0,0,0,0,0,0   

P [0,0,0,0,0,0] [5,1] N 0,0,0,0,0,0   

P [0,1,1,1,1,0] [5,2] N 0,1,1,1,1,0   

P [0,1,1,1,1,0] [5,3] N 0,1,1,1,1,0   

P [0,0,0,0,0,0] [5,4] N 0,0,0,0,0,0   

P [0,0,0,0,0,0] [5,5] N 0,0,0,0,0,0   

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


The program generates a test V matrix by placing the pieces according to the test pattern and then just checks to see if the V matrix is identical to the P matrix for a valid answer.  By recording the number of the pieces that sets each corresponding P pixel in a matrix R the final arrangement can be extracted. 

Results 

A few days were spent writing and debugging program in Swift. After a few shake down runs each of the two puzzles took about 7 minutes to complete on a MacBook Pro 2011 Core i7 2.2Ghz and generated 4 solutions for the vintage puzzle and a single solution for the Amazon puzzle 

This represents a solution for the vintage puzzle shown as slices through the puzzle with different interpretations. 

pMarks: [SolidKeyBlock,0 Rotate0  ] [AngleShort,5 Rotate1  Fliped ] [ShortCup,1 Rotate3  ] [LongGapLong,4 Rotate1  ] [Tounge,3 Rotate2  Fliped ] [LongGapShort,2 Rotate1  ]

pixelsVRPN: [

CheckPlaceP: true,CheckEdgeGaps: false  (true,false) is good here

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

[0,0]V [0,0,0,0,0,0]  [0,0]R  .  .  .  .  .  .   [0,0]P [0,0,0,0,0,0]  

[0,1]V [0,0,0,0,0,0]  [0,1]R  .  .  .  .  .  .   [0,1]P [0,0,0,0,0,0]  

[0,2]V [0,1,1,1,1,0]  [0,2]R  .  0  0  4  4  .   [0,2]P [0,1,1,1,1,0]  

[0,3]V [0,1,1,1,1,0]  [0,3]R  .  0  0  4  4  .   [0,3]P [0,1,1,1,1,0]  

[0,4]V [0,0,0,0,0,0]  [0,4]R  .  .  .  .  .  .   [0,4]P [0,0,0,0,0,0]  

[0,5]V [0,0,0,0,0,0]  [0,5]R  .  .  .  .  .  .   [0,5]P [0,0,0,0,0,0]  

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

[1,0]V [0,0,1,1,0,0]  [1,0]R  .  .  5  5  .  .   [1,0]P [0,0,1,1,0,0]  

[1,1]V [0,0,1,1,0,0]  [1,1]R  .  .  5  5  .  .   [1,1]P [0,0,1,1,0,0]  

[1,2]V [0,1,1,1,1,0]  [1,2]R  .  0  0  5  4  .   [1,2]P [0,1,1,1,1,0]  

[1,3]V [0,1,1,1,1,0]  [1,3]R  .  0  0  5  4  .   [1,3]P [0,1,1,1,1,0]  

[1,4]V [0,0,1,1,0,0]  [1,4]R  .  .  5  5  .  .   [1,4]P [0,0,1,1,0,0]  

[1,5]V [0,0,1,1,0,0]  [1,5]R  .  .  5  5  .  .   [1,5]P [0,0,1,1,0,0]  

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

[2,0]V [0,0,1,1,0,0]  [2,0]R  .  .  5  5  .  .   [2,0]P [0,0,1,1,0,0]  

[2,1]V [1,1,1,1,1,1]  [2,1]R  1  1  1  1  1  1   [2,1]P [1,1,1,1,1,1]  

[2,2]V [1,1,1,1,1,1]  [2,2]R  1  0  0  5  1  1   [2,2]P [1,1,1,1,1,1]  

[2,3]V [1,1,1,1,1,1]  [2,3]R  2  0  0  5  4  2   [2,3]P [1,1,1,1,1,1]  

[2,4]V [1,1,1,1,1,1]  [2,4]R  2  2  5  5  2  2   [2,4]P [1,1,1,1,1,1]  

[2,5]V [0,0,1,1,0,0]  [2,5]R  .  .  5  5  .  .   [2,5]P [0,0,1,1,0,0]  

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

[3,0]V [0,0,1,1,0,0]  [3,0]R  .  .  3  3  .  .   [3,0]P [0,0,1,1,0,0]  

[3,1]V [1,1,1,1,1,1]  [3,1]R  1  1  1  1  1  1   [3,1]P [1,1,1,1,1,1]  

[3,2]V [1,1,1,1,1,1]  [3,2]R  1  0  0  3  1  1   [3,2]P [1,1,1,1,1,1]  

[3,3]V [1,1,1,1,1,1]  [3,3]R  2  0  0  3  4  2   [3,3]P [1,1,1,1,1,1]  

[3,4]V [1,1,1,1,1,1]  [3,4]R  2  2  2  2  2  2   [3,4]P [1,1,1,1,1,1]  

[3,5]V [0,0,1,1,0,0]  [3,5]R  .  .  3  3  .  .   [3,5]P [0,0,1,1,0,0]  

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

[4,0]V [0,0,1,1,0,0]  [4,0]R  .  .  3  3  .  .   [4,0]P [0,0,1,1,0,0]  

[4,1]V [0,0,1,1,0,0]  [4,1]R  .  .  3  3  .  .   [4,1]P [0,0,1,1,0,0]  

[4,2]V [0,1,1,1,1,0]  [4,2]R  .  0  0  3  4  .   [4,2]P [0,1,1,1,1,0]  

[4,3]V [0,1,1,1,1,0]  [4,3]R  .  0  0  3  4  .   [4,3]P [0,1,1,1,1,0]  

[4,4]V [0,0,1,1,0,0]  [4,4]R  .  .  3  3  .  .   [4,4]P [0,0,1,1,0,0]  

[4,5]V [0,0,1,1,0,0]  [4,5]R  .  .  3  3  .  .   [4,5]P [0,0,1,1,0,0]  

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

[5,0]V [0,0,0,0,0,0]  [5,0]R  .  .  .  .  .  .   [5,0]P [0,0,0,0,0,0]  

[5,1]V [0,0,0,0,0,0]  [5,1]R  .  .  .  .  .  .   [5,1]P [0,0,0,0,0,0]  

[5,2]V [0,1,1,1,1,0]  [5,2]R  .  0  0  4  4  .   [5,2]P [0,1,1,1,1,0]  

[5,3]V [0,1,1,1,1,0]  [5,3]R  .  0  0  4  4  .   [5,3]P [0,1,1,1,1,0]  

[5,4]V [0,0,0,0,0,0]  [5,4]R  .  .  .  .  .  .   [5,4]P [0,0,0,0,0,0]  

[5,5]V [0,0,0,0,0,0]  [5,5]R  .  .  .  .  .  .   [5,5]P [0,0,0,0,0,0]  

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


The R column provides the answer showing the piece number that is present at that pixel location. Notice how piece 0, being the solid key piece, appears on all the levels of R. The other piece shapes become apparent by following the numbers in the layers of the R matrix.

Where a puzzle has duplicate pieces or a piece that is symmetrical when rotated or flipped, more than one version of the answer is generated.

Going faster

Two ways were devised to make the solution program run faster.

Firstly: when constructing manually the tendency is to put two pieces going in the same direction together then build the other pieces around that foundation. The manual method works well in the hand as the piece alignment takes care of itself but the downside is that any arrangement cannot be failed until after, at least, the third piece is placed. Adjusting the piece placement order in the program so that pieces were placed in a repeated direction order of x then y then z causes overlapping pieces to be detected earlier. However this made no different to the program run time and made the results a bit harder to interpret.

Secondly: Grand central dispatch was used to parallelise the search. Adding the 3 lines required to achieve parallelism caused the code to run in six threads but only halved the run time.

Now with holes in

The program above was built on the assumption that a puzzle would have a solid key piece. Further examination of Robs puzzle pages showed that the among this class of puzzle not all are built the same way.  The revelation that some completed puzzles had holes inside and some did not use a key piece forced a bit of a rethink. These holely puzzles are more complex to build requiring sliding motions to assemble. The basic mechanics of the program still works but the following changes had to be made.

1) The total weight of the pieces is checked to see if there holes in the final assembly - if so then the final completion check has to be more detailed. 

2) The pieces are checked to see if a key piece is included. - if not then a deeper search is required. With six pieces to be placed a total of over 94 million arrangements have to be checked.

There are 2048 rotations

Starting on a mission from b6_010.txt of 720 piece orders where each has 2048 rotation possibilities with 64 piece flips

There are 94371840 board layouts to try

This takes a while longer (about 100 minutes) even when multitasking but answers are eventually found.

real 99m34.636s   user 694m36.010s  sys 9m9.842s



Pieces :Comments: #burr6 Eight is enough#from http://www.robspuzzlepage.com/interlocking.htm#trad


Piece { mark:0, name:Abc216, IDValue:216, Weight:6, Length:6

Cubies:  [ 

[0,0][1, 1, 1, 1, 1, 1]

[1,0][1, 1, 1, 1, 1, 1]

[0,1][1, 0, 1, 0, 0, 1]

[1,1][1, 0, 0, 0, 1, 1] ] }


Piece { mark:1, name:Abc412, IDValue:412, Weight:6, Length:6

Cubies:  [ 

[0,0][1, 1, 1, 1, 1, 1]

[1,0][1, 1, 0, 1, 1, 1]

[0,1][1, 0, 1, 1, 0, 1]

[1,1][1, 0, 0, 1, 0, 1] ] }


Piece { mark:2, name:Abc751, IDValue:751, Weight:5, Length:6

Cubies:  [ 

[0,0][1, 1, 1, 1, 1, 1]

[1,0][1, 1, 1, 0, 1, 1]

[0,1][1, 1, 0, 0, 0, 1]

[1,1][1, 1, 0, 0, 0, 1] ] }


Piece { mark:3, name:Abc896, IDValue:896, Weight:3, Length:6

Cubies:  [ 

[0,0][1, 1, 1, 1, 1, 1]

[1,0][1, 1, 0, 0, 1, 1]

[0,1][1, 0, 0, 0, 1, 1]

[1,1][1, 0, 0, 0, 0, 1] ] }


Piece { mark:4, name:Right Finger, IDValue:960, Weight:3, Length:6

Cubies:  [ 

[0,0][1, 1, 1, 1, 1, 1]

[1,0][1, 1, 0, 0, 1, 1]

[0,1][1, 0, 0, 1, 0, 1]

[1,1][1, 0, 0, 0, 0, 1] ] }


Piece { mark:5, name:Y, IDValue:1024, Weight:2, Length:6

Cubies:  [ 

[0,0][1, 1, 1, 1, 1, 1]

[1,0][1, 1, 0, 0, 1, 1]

[0,1][1, 0, 0, 0, 0, 1]

[1,1][1, 0, 0, 0, 0, 1] ] }


Total pieces weight 25, piece0IsKey:false

.......

pixelsVRPN: [

CheckPlaceP: true, CheckEdgeGaps: false  (true,false) is good here

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

[0,0]V [0, 0, 0, 0, 0, 0]  [0,0]R  .  .  .  .  .  .   [0,0]P [0, 0, 0, 0, 0, 0]

[0,1]V [0, 0, 0, 0, 0, 0]  [0,1]R  .  .  .  .  .  .   [0,1]P [0, 0, 0, 0, 0, 0]

[0,2]V [0, 1, 1, 1, 1, 0]  [0,2]R  .  2  2  3  3  .   [0,2]P [0, 1, 1, 1, 1, 0]

[0,3]V [0, 1, 1, 1, 1, 0]  [0,3]R  .  2  2  3  3  .   [0,3]P [0, 1, 1, 1, 1, 0]

[0,4]V [0, 0, 0, 0, 0, 0]  [0,4]R  .  .  .  .  .  .   [0,4]P [0, 0, 0, 0, 0, 0]

[0,5]V [0, 0, 0, 0, 0, 0]  [0,5]R  .  .  .  .  .  .   [0,5]P [0, 0, 0, 0, 0, 0]

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

[1,0]V [0, 0, 1, 1, 0, 0]  [1,0]R  .  .  1  1  .  .   [1,0]P [0, 0, 1, 1, 0, 0]

[1,1]V [0, 0, 1, 1, 0, 0]  [1,1]R  .  .  1  1  .  .   [1,1]P [0, 0, 1, 1, 0, 0]

[1,2]V [0, 1, 1, 1, 1, 0]  [1,2]R  .  2  1  1  3  .   [1,2]P [0, 1, 1, 1, 1, 0]

[1,3]V [0, 1, 1, 1, 1, 0]  [1,3]R  .  2  1  3  3  .   [1,3]P [0, 1, 1, 1, 1, 0]

[1,4]V [0, 0, 1, 1, 0, 0]  [1,4]R  .  .  1  1  .  .   [1,4]P [0, 0, 1, 1, 0, 0]

[1,5]V [0, 0, 1, 1, 0, 0]  [1,5]R  .  .  1  1  .  .   [1,5]P [0, 0, 1, 1, 0, 0]

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

[2,0]V [0, 0, 1, 1, 0, 0]  [2,0]R  .  .  1  1  .  .   [2,0]P [0, 0, 1, 1, 0, 0]

[2,1]V [1, 1, 1, 1, 1, 1]  [2,1]R  0  0  0  0  0  0   [2,1]P [1, 1, 1, 1, 1, 1]

[2,2]V [1, 1, 1, 1, 1, 1]  [2,2]R  0  2  1  1  0  0   [2,2]P [1, 1, 1, 1, 1, 1]

[2,3]V [1, 1, 1, 1, 1, 1]  [2,3]R  5  .  1  .  3  5   [2,3]P [1, 0, 1, 0, 1, 1]

[2,4]V [1, 1, 1, 1, 1, 1]  [2,4]R  5  5  5  5  5  5   [2,4]P [1, 1, 1, 1, 1, 1]

[2,5]V [0, 0, 1, 1, 0, 0]  [2,5]R  .  .  1  1  .  .   [2,5]P [0, 0, 1, 1, 0, 0]

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

[3,0]V [0, 0, 1, 1, 0, 0]  [3,0]R  .  .  4  4  .  .   [3,0]P [0, 0, 1, 1, 0, 0]

[3,1]V [1, 1, 1, 1, 1, 1]  [3,1]R  0  0  0  0  0  0   [3,1]P [1, 1, 1, 1, 1, 1]

[3,2]V [1, 1, 1, 1, 1, 1]  [3,2]R  0  2  0  .  .  0   [3,2]P [1, 1, 1, 0, 0, 1]

[3,3]V [1, 1, 1, 1, 1, 1]  [3,3]R  5  2  .  4  3  5   [3,3]P [1, 1, 0, 1, 1, 1]

[3,4]V [1, 1, 1, 1, 1, 1]  [3,4]R  5  5  .  .  5  5   [3,4]P [1, 1, 0, 0, 1, 1]

[3,5]V [0, 0, 1, 1, 0, 0]  [3,5]R  .  .  4  4  .  .   [3,5]P [0, 0, 1, 1, 0, 0]

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

[4,0]V [0, 0, 1, 1, 0, 0]  [4,0]R  .  .  4  4  .  .   [4,0]P [0, 0, 1, 1, 0, 0]

[4,1]V [0, 0, 1, 1, 0, 0]  [4,1]R  .  .  4  4  .  .   [4,1]P [0, 0, 1, 1, 0, 0]

[4,2]V [0, 1, 1, 1, 1, 0]  [4,2]R  .  2  2  4  3  .   [4,2]P [0, 1, 1, 1, 1, 0]

[4,3]V [0, 1, 1, 1, 1, 0]  [4,3]R  .  2  2  4  3  .   [4,3]P [0, 1, 1, 1, 1, 0]

[4,4]V [0, 0, 1, 1, 0, 0]  [4,4]R  .  .  4  4  .  .   [4,4]P [0, 0, 1, 1, 0, 0]

[4,5]V [0, 0, 1, 1, 0, 0]  [4,5]R  .  .  4  4  .  .   [4,5]P [0, 0, 1, 1, 0, 0]

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

[5,0]V [0, 0, 0, 0, 0, 0]  [5,0]R  .  .  .  .  .  .   [5,0]P [0, 0, 0, 0, 0, 0]

[5,1]V [0, 0, 0, 0, 0, 0]  [5,1]R  .  .  .  .  .  .   [5,1]P [0, 0, 0, 0, 0, 0]

[5,2]V [0, 1, 1, 1, 1, 0]  [5,2]R  .  2  2  3  3  .   [5,2]P [0, 1, 1, 1, 1, 0]

[5,3]V [0, 1, 1, 1, 1, 0]  [5,3]R  .  2  2  3  3  .   [5,3]P [0, 1, 1, 1, 1, 0]

[5,4]V [0, 0, 0, 0, 0, 0]  [5,4]R  .  .  .  .  .  .   [5,4]P [0, 0, 0, 0, 0, 0]

[5,5]V [0, 0, 0, 0, 0, 0]  [5,5]R  .  .  .  .  .  .   [5,5]P [0, 0, 0, 0, 0, 0]

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


Note the interior holes in the R and P matrixes but the skin of 1 is complete in the P matrix indicating that there would be no externally visible holes. Whilst the program can find all final piece arrangements it does not say how to slide and assemble the pieces. That is left as an exercise for the owner.

Next

Now that this class of problem is well understood will try and create a solution method with an SMT solver and see how that performs.

References and Acknowledgements

Burr 6 puzzle pages: 
http://www.robspuzzlepage.com/interlocking.htm - An excellent puzzle reference pages for this and other puzzles. 

Antique shop : Collins Antiques 

Improve your 3D thinking here:
KiKi the nanobot 3D game - not directly related but a lot of fun and insight into thinking in 3D Worlds

Usage


Usage: burr6f.pl {options} -f puzzle.txt

    See http://www.robspuzzlepage.com/interlocking.htm#trad for backstory and more information


    -v N :Be verbose to level N ( use v=10 for more detailed output )

    -f puzzle.txt  {required}

    -h Print this help


    Use -o for operation else do a deep search based on -f contents

    

    -o  t0 - fill a board with solid burrs showing overlap sections

        t1 - use with -f b6_001.txt for answer

        t2 - use with -f b6_002.txt for answer


Hunt for solutions using fit & check and long search for burr6 piece puzzles using the input format

 

Input puzzle file format

#Burr6 Collins Antiques Aug 2020

#Mark,IDValue,Name

0,1,SolidKeyBlock

1,120,ShortCup

2,3328,LongGapShort

3,3322,Tounge

4,3328,LongGapLong

5,3305,AngleShort

 

        Cubbie identification for IDValue

        

            +----+----+----+----+----+----+

          /    / 16 / 32 / 64 / 128/    / |

         +    +----+----+----+----+    +  |

        /    /  1 /  2 /  4 /  8 /    /   +

        +----+----+----+----+----+----+   |

        |    |    |    |    |    |    |   |

        |    |    |    |    |    |    |   +

        +    +----+----+----+----+    +  /

        |         |    |    |         | +

        |      a  | 256| 512|  b      |/

        +----+----+----+----+----+----+


        IDValue are 1 plus the value, shown above, of each cubie removed.

        The cubies behind cubies 256 and 512 can be removed, too, and have respective

        values 1024 and 2048. Such pieces appear infrequently.

        ** if puzzle has a key must be piece 0 in file and IDValue==1


        When trying to identify an arbitrary piece, rotate it about its long axis

        (and maybe flip it end-for-end) until you find an orientation where

        the cubies marked 'a' and 'b' and the cubies behind them are present.

        Sometimes a piece could be assigned more than one number - use the smaller

        number. This entails orienting it so that cubies 1024 and 2048 are present if possible.


        The weight of a whole burr relates to the number of internal holes it has, and can range

        from 32 (no internal holes), down to 12 (the maximum of 20 holes).


        The weight of a piece refers to the number of cubies not removed from it, and can range

        from 12 (the key) down to 2 (the Y). If the sum of the weights of six pieces

        exceeds 32, it is impossible to construct a valid burr from that set.



at No comments:
Labels: , ,
Subscribe to: Posts (Atom)

SMT Solvers, introduction and links (Start here with the readme)

Picat - First steps

 Getting started with a new software system can always be a little daunting. Just a little bit of help to get over the curb can make that jo...