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. 

http://www.billcutlerpuzzles.com

http://puzzlewillbeplayed.com/-/burr-6t.xml

https://cubicdissection.com

Antique shop : Collins Antiques 

Amazon version : Logica Puzzles BURR puzzle

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.

Solving Sujiko using an SMT (integer) solver

This blog entry describes how the Sujiko puzzle is deconstructed into logic lines suitable for a solver such as Z3 or MathSat.

Sujiko is a simple arithmetic puzzle where fours simultaneous sums have to be satisfied. Each of the eight empty squares have to be filled with non-repeating numbers 1 to 9 such that the target numbers in the circles are the sum of the surrounding numbers. A clue number is provided.

Sample Sujiko from The Daily Telegraph

Encoding 

The input puzzle can be represented as a text file su_001.txt in this format : 

#sujiko DT_3072

25,13,22,17

P8,6

The first line being a comment, the second the target numbers and finally the clue number as Position 8 value 6.

Puzzle Logic

In this puzzle each of the answer squares are numbered V0 to V8 with the targets numbered T0 to T3.  In the solution T0 must equal V0 + V1 + V3 + V4  and T1=V1 + V2 + V4 +V5 ( similarly for T2 & T3).  Each of the V.. numbers must be between 1 and 9 inclusive but all different.

In essence this is a four simultaneous equation problem with 8 unknowns. There are 362,880 possible Sujiko puzzles being the number of ways that 1..9 can be arranged ( permutations ).

Variables and Targets

Building the SMT-Lib file

Converting the input target and clue into logic lines for the solver is the next stage. Using the SMT-Lib language to describe the problem is the bridge between problem and solver ready solution. The logic lines start with a preamble describing the type of logic being used then each of the unknowns are declared, limited to a range and linked to the other numbers with relationships. 

In the pre-amble we set the solver into integer mode and declare that answer and values will be need beyond proof that the puzzle can be solved.

(set-logic LIA)

(set-option :produce-models true)
(set-option :produce-assignments true)

Each of the targets are declared and set to the required value ...

(declare-const T0 Int)

(assert (= T0 25 ))

(declare-const T1 Int)

(assert (= T1 13 ))

(declare-const T2 Int)

(assert (= T2 22 ))

(declare-const T3 Int)

(assert (= T3 17 ))

Each of the answer squares are declared and a range limit is set as bigger than 0 less than 10 ....

(declare-const V0 Int)

(assert (and (> V0 0) (< V0 10)))

(declare-const V1 Int)

(assert (and (> V1 0) (< V1 10)))

(declare-const V2 Int)

(assert (and (> V2 0) (< V2 10)))

....

(declare-const V7 Int)

(assert (and (> V7 0) (< V7 10)))

(declare-const V8 Int)

(assert (and (> V8 0) (< V8 10)))

The answers must be uniquely different values .....

(assert (distinct V0 V1 V2 V3 V4 V5 V6 V7 V8  ))

The clue is provided by setting V8 to 6

(assert (= V8 6)); Clue provided

finally the sums are configured and the run commands provided....

(assert (= T1 (+ V1 V2 V4 V5)))

(assert (= T2 (+ V3 V4 V6 V7)))

(assert (= T3 (+ V4 V5 V7 V8)))

(assert (= T0 (+ V0 V1 V3 V4)))

(check-sat)

(get-model)

(exit)

Running the solver and displaying the output

The input text puzzle is generated into logic lines using a script. The script output is passed to the solver that will in turn generate "sat" and the values of the cells or if the problem cannot be solved "unsat" is returned. The output of the solver is read into the same script and an .html file of results and check lines are presented.  

This is a very small scale problem for the solver that takes about 0.04 seconds to solve on a Mac Book Pro 2011.

The command line used is :

./sujiko_smt.pl < su_001.txt | tee su_001.smt | ../solver_m5 |tee su_001M5.res | ./sujiko_smt.pl -f su_001.txt > su_001.html

The input SMT logic lines above are saved into file  su_001.smt.

The intermediate  results from the solver are collected into file su_001M5.res showing as :

 

sat

(model

  (define-fun T0 () Int 25)

  (define-fun T1 () Int 13)

  (define-fun T2 () Int 22)

  (define-fun T3 () Int 17)

  (define-fun V0 () Int 9)

  (define-fun V1 () Int 3)

  (define-fun V2 () Int 1)

  (define-fun V3 () Int 8)

  (define-fun V4 () Int 5)

  (define-fun V5 () Int 4)

  (define-fun V6 () Int 7)

  (define-fun V7 () Int 2)

  (define-fun V8 () Int 6)

)

Finally the encoding display script generates a web display page into file su_001.html

Error checking 

When the result value V6 is changed to 5 (from 7) the Sequence checks indicate a **Fail** 

References

MathSAT the m5 solver used here.

Z3 the Z3 solver made by Microsoft - get it here

Sujiko

Using SMT for sudoku puzzles

Programming Z3 Sudoku section from Section 8.1 page 139 uses python and a library to build logic lines.

Appendix usage for logic preparation script

Usage: sujiko {options} < puzzle.txt  or

    sujiko {options} -f puzzle.txt < SolverOutput

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

    -f puzzle.txt :Puzzle file needed when reading Solver output use STDIN otherwise

        

    Programs reads STDIN looking for either puzzleFile format lines or Solver output lines

        If the input is in puzzleFile format the program will generate solver input lines.

        If the input is in Solver output lines format the program will expect a -f puzzleFile paremeter.

            Using both these input streams program will then generate display .html output.

Game Rules

  Complete a grid using each of the numbers 1..9 in the positions 0..8 on the game board such that the sums amounts provided as A,B,C,D are the total of these surrounding position squares. E.G. A=Pos0+Pos1+Pos3+Pos4 and D=Pos4+Pos5+Pos7+Pos8

        

        Layout of board for clue positions:

        0 1 2

         A B

        3 4 5

         C D

        6 7 8

        

        P8,6 would mean that position 8 has clue number set to 6.

        

Each sujiko puzzle Input as follows

        

    #sujiko DT_3072

    25,13,22,16

    P8,6

        

OR Process results from solver in the following format

            sat

            (model

              (define-fun T0 () Int 25)

              (define-fun T1 () Int 13)

              (define-fun T2 () Int 22)

    ....

to generate an html page as output.

            

Puzzle checks will fail with these messages

**ERROR Numbers of input Values not = 4

Solving Kurosu using and SMT (Integer) solver

Solving Kurosu using an SMT (integer) solver

See Original and updates on https://gannett-hscp.blogspot.com  

** UPDATED  May 2023 fix method to Int

Back in 2018 the Kurosu problem was reviewed and solved using a simple two way pattern matching script as noted in the blog here.  This entry looks again at this bit setting puzzle with a view to using an SMT (integer) solver.

Kurosu is essentially a bit setting problem with each cell on a six by six grid having value 0 or X. Each row and column must have three each of 0 and X with no more than two 0 or X (treated as 1) adjacent. No row or column with "111" or "000" is allowed.

Encoding

The puzzle is encoded using 1 for the Xs and 0 making this a binary bit setting problem. The limitation of no 111 and no 000 on a row or column considerably reduces the complexity of the problem. The puzzle above encodes as :

#Kurosu6 DM 01 June 2018

...0.1

0...0.

1.1.1.

..0...

.1.0.1

0....0

Puzzle logic

As seen in the previous analysis there are only 14 line patterns that follow the three sequential bit limitation making 11,222 the total number of puzzle line patterns. However this review is to reset the puzzle for solving using an SMT (Integer) solver. 

Previously the solution was reached by only testing with combinations of the allowable lines but that approach is an unnecessary skip towards the answer. The intent of using an SMT solver is to provide the minimal logic and constraints of the puzzle and let the solver figure out the details.

Lines that have three 1 (or 0 ) clue values can be directly solved by setting the gaps to 0 and vice versa but again this is left to the solver to figure out. 

The general approach will be to set up a variable for each cell and describe the relationship between the cells to match the rules of the puzzle. Each cell variable will only be allowed 1 or 0 as values.

Whilst it would seem logical to use a bit based rather than integer solver the syntax and logic available in the QF_BV BitVec version of the SMT solver is tortuous and does not work well for counting bits. Using a constrained value integer allows for the use sum of line value constraints.

 

Row and column cell numbers

The cells of the original puzzle are sequentially numbered and each row and column member cells are established as follows. Each cell is in one row and one column.

For example cell 25 is in column C1 and row R24

#->grpList cell values = 

C0 = 0 6 12 18 24 30!

C1 = 1 7 13 19 25 31!

C2 = 2 8 14 20 26 32!

C3 = 3 9 15 21 27 33!

C4 = 4 10 16 22 28 34!

C5 = 5 11 17 23 29 35!

R0 = 0 1 2 3 4 5!

R12 = 12 13 14 15 16 17!

R18 = 18 19 20 21 22 23!

R24 = 24 25 26 27 28 29!

R30 = 30 31 32 33 34 35!

R6 = 6 7 8 9 10 11!

The constrains of the puzzle are handled in terms of the column and row identifiers. Each row or column line has 6 cell entries. 

Building the SMT-Lib file

In the preamble we set the solver into Linear Integer LIA mode then create 36 single integer V0..V35 to represent each cell and limit the value range. 

(set-logic LIA)

(set-option :produce-models true)

(set-option :produce-assignments true)

(declare-const V0 Int)       ; Declare V0 as an Integer

(assert (or (= V0 0) (= V0 1))) ; This constraint limits the value of V0 to be either 0 or 1

(declare-const V1 Int)

(assert (or (= V1 0) (= V1 1)))

(declare-const V10 Int)

(assert (or (= V10 0) (= V10 1)))

(declare-const V11 Int)

(assert (or (= V11 0) (= V11 1)))

The known clue cells are set ....

(assert (= V3 0 ))

(assert (= V5 1 ))

(assert (= V6 0 ))

(assert (= V10 0 ))

(assert (= V12 1 ))

…

(assert (= V35 0 ))

In overview each cell belongs to one row and one column. Each row and column has 6 cell; the overall row and column values are constrained to add up to 3. Each of the row and columns are built into 5 constrains. The first being that the sum of values must be 3 and then for each set of three cells the sum must be 2 or less. The less than 3 constraint on each group of 3 cells across each line ensures that the “no adjacent sets of 3 1 values” game rule is enforced. As there are only 6 cells in a row by enforcing the no 3 adjacent 1 cells, rule the no 3 zeros rule is also delivered.

(assert (= 3 (+ V0  V6  V12  V18  V24  V30 ))); Region C0

(assert (> 3 (+ V0 V6 V12 ))); Sub group of C0

(assert (> 3 (+ V6 V12 V18 ))); Sub group of C0

(assert (> 3 (+ V12 V18 V24 ))); Sub group of C0

(assert (> 3 (+ V18 V24 V30 ))); Sub group of C0

…..

(assert (= 3 (+ V0  V1  V2  V3  V4  V5 ))); Region R0

(assert (> 3 (+ V0 V1 V2 ))); Sub group of R0

(assert (> 3 (+ V1 V2 V3 ))); Sub group of R0

(assert (> 3 (+ V2 V3 V4 ))); Sub group of R0

(assert (> 3 (+ V3 V4 V5 ))); Sub group of R0

A set of constraint lines are generated for each of the regions C0 to C5 and R0 to R6 as shown above. The following lines cause the solver evaluate the model and generate then display the resulting values.

(check-sat)

(get-model)

(exit)

151 lines of logic are needed to represent this instance of the puzzle. 

The solver has to choose the values for the cells such that all the constraints are met.

Running the solver and displaying the output

The input puzzles is generated into logic lines using a script. The script output is passed to the solver that will in turn generate "sat" and the values of the cells, rows and columns or if the problem cannot be solved "unsat" is seen. The output of the solver is processed by the same script and an .html file of results and check lines is presented.  The bold values are the clue numbers.

The mathSAT solver finds the answer in less than 0.08s on a MacBook pro 2011 and in 0.02s on a 2022 Mac mini.

The output of the solver is a list of values for each cell.

                                                                  

sat

(model

  (define-fun V0 () Int 1)

  (define-fun V1 () Int 1)

  (define-fun V10 () Int 0)

  (define-fun V11 () Int 1)

  (define-fun V12 () Int 1)

…..

These lines are processed into an HTML table with checks for correct solution.

Error checking

If a solver line output is adjusted the script would flag incorrect column or row total values only. Here sed is used to intercept the values as they flow from the solver to the display script. V10 is changed to be the illegal value 2.

% i="ku_dm_01062018.txt"

% perl kurosu_smt.pl  < $i | time ../../solver_mathsat5| sed '/V10/s/[01])/2)/'| perl kurosu_smt.pl -f $i > xxxxBusted.html

%  open xxxxBusted.html

Scaling up considerations

This puzzle could possibly appear in larger formats. The same constraint generation logic could be used. 

Appendix usage for logic preparation script

Usage: kurosu_smt {options} < puzzle.txt  or

    kurosu_smt {options} -f puzzle.txt < SolverOutput

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

    -f puzzle.txt :Puzzle file needed when reading Solver output use STDIN otherwise

    

    Programs reads STDIN looking for either puzzleFile format lines or Solver output lines

        If the input is in puzzleFile format the program will generate solver input lines.

        If the input is in Solver output lines format the program will expect a -f puzzleFile paremeter.

            Using both these input streams program will then generate display .html output.

Game Rules

        6 * 6 matrix of 1/0/.

        Each Row/Column must have 3 * 0 and 3 * 1

        Positioning - No more than 2 lots of 0 and 1 allowed as row or Column neighbours.

        puzzle is printed with 0 & X

        

Encode kurosu puzzle Input as follows, . for unknown and clue 1 and 0 included.

     ku_dm_01062018.txt

    #Kurosu6 DM 01 June 2018

    ...0.1

    0...0.

    1.1.1.

    ..0...

    .1.0.1

    0....0

OR Process results from MathSat solver in the following format

    sat

    (model

      (define-fun V0 () Int 0)

      (define-fun V1 () Int 1)

      (define-fun V10 () Int 0)

      (define-fun V11 () Int 0)

    .....

    To generate an html layout as output.

Run as

    ./kurosu_smt.pl < ku_dm_01062018.txt | ../solver_m5 | ./kurosu_smt.pl -f ku_dm_01062018.txt >  ku_dm_01062018.html

    

/*  Valid Line patterns

[0] 11 = 0x0b = 001011

[1] 13 = 0x0d = 010011

[2] 19 = 0x13 = 001101

[3] 21 = 0x15 = 010101

[4] 22 = 0x16 = 100101

[5] 25 = 0x19 = 011001

[6] 26 = 0x1a = 101001

[7] 37 = 0x25 = 010110

[8] 38 = 0x26 = 100110

[9] 41 = 0x29 = 011010

[10] 42 = 0x2a = 101010

[11] 44 = 0x2c = 110010

[12] 50 = 0x32 = 101100

[13] 52 = 0x34 = 110100

*/