Cracking and solving anagrams (hints)

 Mixed up word puzzles or anagrams often show up in quizzes and competitions where time to reach a solution quickly is of the essence. Having a few practiced strategies helps prevent just staring at the letters and hoping that they fall into place. The clues to solve an anagram are obvious but can be combined into strategies for effective anagram solution.

Don't be put off that there are up to 8,031,810,176 (Over 8 trillion) possible combination of just 7 letters.

Three clues for solving an anagram

1. The answer must have the same number of letters as the clue. Longer or shorter words can be eliminated.
2. All actual letters provided must form part of the answer. Rare letters (Q Z X Y K etc.) in the clue must be in the answer.
3. The subject matter of the answer is sometimes provided.

Strategies for solving anagrams

A) Where the subject matter is provided take a few moments to think about answers that may fit in the topic. This will warm up and generate associations around the subject that may lead to an answer. Pre-Exercise: Think of 10 each of the dog breeds, African animals, countries, famous brands, trees, makes of car etc. 

B) Pick out each unique letter and take a few moments to think of words in the subject area that might start with that letter.

Looks at the letters in different ways.

B) Write the letters in a circle to break up the visible sequences in the clue.  

C) Write the letter in two groups of vowels and consonant. 

Pick out common patterns as once identified the number of remanning letters to be placed is reduced.

D) Look for subwords that might present in the subject area. If solving anagrams of places look for road, street, lake, town, city etc. 

E) Look for common word starts eg pre, un, st, dis  

F) Look for common word middles such as  ph, sh, qu

G) Look for common word endings such as ing, ed, tion, ness, ly

H) Become familiar with the frequencies of letter pairs and triples as used in simple decoding techniques

Letter and word frequencies in Tolstoy War and Peace

See also Using code to find anagrams in a book.

Solving Seki using an SMT (integer) solver

This entry describes how the Seki puzzle is deconstructed into logic lines suitable for a solver such as Z3 or MathSat. Other puzzles are available. This article is one of a series reframing logic puzzles into a format suitable for an SMT Integer solver.

Seki is a city in the Gifu province of Japan and the name of a simple logical puzzle. The puzzle has a four by four grid of black or white squares painted according to rotors positioned at the intersection of each four cell group. The task is to set the position of the independent rotors so that each cell is either set black or white.

Encoding

This fixed size puzzle can be encoded using a list of the rotor types showing at the cell intersections. 

Possible Rotors are : 

+ = singleOn, one segment is black

- = singleOff, one segment is white, three segments are black

o = opposite2, like the BMW logo 

a = adjacent2, like a 1/2 eaten pie 

For the puzzle above we have :

oo+ooaoo-

The output of the solution would be the settings of the cells numbered V0 to V15 each with a 1 (black) or 0 (white) assignment.

Cell numbers grid

Puzzle Logic

Whilst the intersection rotors are independently set they have interdependencies with neighbouring rotors. Each rotor must be positioned without conflicts over the cells shared between the rotors. We can see that the rotor types dictates the number of surrounding cells that are set to black. For o and a rotors two cells are set. One and three cells are set for the + and - rotor types. By having 16 cells each set to 1 or 0 we can use the rotors as constraints for the setting of the group of cell values that surround each rotor. The similarity of the o and a rotors require some extra logic to constrain which two of the surrounding cells are set.

Each rotor +, - and "a" rotors have 4 possible positions but the "o" rotor only 2. Depending on the number of o rotors in a given puzzle the maximum number of possible rotor arrangements is  4^9 = 262,144. This particular puzzle has 4^3 + 6^2 = 100 possible arrangements.

Building the SMT-Lib file

With the puzzle rotors encoded, the next stage is to convert the puzzle rotor types into logic lines for a solver. The bridge between problem and solver ready input is the SMT-Lib language. The SMT 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 then linked to the other numbers using a constraint relationships.  63 lines of logic are generated in total for this puzzle.

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

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

Each of the target cells are declared and set to the required value range of 0 or 1. In theory we could use a boolean value for each cell but as the constrains are phrased in terms of the number of cells set in a rotor group using integers limited to value 1 or  0 allows for easier addition.

(declare-const V0 Int) 
(assert (or (= V0 0) (= V0 1) )) 
(declare-const V1 Int) 
(assert (or (= V1 0) (= V1 1) )) 
(declare-const V2 Int) 
(assert (or (= V2 0) (= V2 1) ))
.....  

and on up to V15. The constraints between the cells belonging to each rota are set according to the rotor type. For the + and - rotor types there is a single constraint being the total number of the surrounding cell values. The o and a also have the number of cells set as a constraint but also a further constraint line enforcing the rotor pattern type is generated.  o rotors must have one of two pairs of opposite cells set to 1.  a rotors must have one of four pairs of cells set. The combination of constraining the sum of the neighbouring cells and which pairs of cells are set fully described the a rotor constraint.

 

Comment starting with ; are included to annotate the rotorgroup number, rotor type, and cells belonging to that rotor.  



;RotorGroup 0 o 0,1,4,5 
(assert (= 2 (+ V0 V1 V4 V5))) 
(assert (or (= 2 (+ V0 V5)) (= 2 (+ V1 V4)) )); o 
.....
;RotorGroup 2 + 2,3,6,7
(assert (= 1 (+ V2 V3 V6 V7)))
.....
;RotorGroup 5 a 6,7,10,11 
(assert (= 2 (+ V6 V7 V10 V11))) 
(assert (or (= 2 (+ V6 V7)) (= 2 (+ V7 V11)) (= 2 (+ V11 V10)) (= 2 (+ V6 V10)))); a 
.....
;RotorGroup 8 - 10,11,14,15 
(assert (= 3 (+ V10 V11 V14 V15)))

and finally the post-amble to generate the results

(check-sat)

(get-value ( V0 V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 V12 V13 V14 V15))

(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 (piped) into the same script and an .html file of results and checked lines are presented.  
This is a very small scale problem for the solver that takes about 0.01 seconds to solve on a Mac Book Pro 2011.
The command line used is :

$ ./seki_smt.pl < sk_6018.txt | time ../solver_m5  | ./seki_smt.pl -f sk_6018.txt > sk_6018.html 

   

     0.02 real         0.00 user         0.00 sys

The html file results are seen as follows:

#seki MOS 01Feb2021 sk_6018.txt

1	0	1	0
0	1	0	0
1	0	1	1
0	1	0	1

Check Results

RotorGroup 0 ch=o Value=2 [0,1,4,5] gives Sum = 2 finalRes=0
RotorGroup 1 ch=o Value=2 [1,2,5,6] gives Sum = 2 finalRes=0
RotorGroup 2 ch=+ Value=1 [2,3,6,7] gives Sum = 1 finalRes=0
RotorGroup 3 ch=o Value=2 [4,5,8,9] gives Sum = 2 finalRes=0
RotorGroup 4 ch=o Value=2 [5,6,9,10] gives Sum = 2 finalRes=0
RotorGroup 5 ch=a Value=2 [6,7,10,11] gives Sum = 2 finalRes=0
RotorGroup 6 ch=o Value=2 [8,9,12,13] gives Sum = 2 finalRes=0
RotorGroup 7 ch=o Value=2 [9,10,13,14] gives Sum = 2 finalRes=0
RotorGroup 8 ch=- Value=3 [10,11,14,15] gives Sum = 3 finalRes=0

Puzzle OK Solution successful.

 This problem could be easily scaled up to a much larger size. The usual fail confirmation test is successfully run generating this message if the cell values do not match the rotor type values. 

Puzzle has ** ERROR ** Solution failed by difference = 2.

References

Programming Z3 Sudoku section from Section 8.1 page 139

Building a Sudoku Solver with SAT,  

A SAT-based Sudoku Solver,  

Sudoku as a SAT Problem, 

Optimized CNF Encoding for Sudoku Puzzles 

Appendix usage for logic preparation script

Usage: Seki {options} < puzzle.txt  or

    Seki {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 puzzle File paremeter.

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

Game Rules

Given a 4*4 grid with a coloured rotor on each line intersection, colour the grid based on the segments in the rotors ( which can be rotated )

Encode seki - Look at the 9 rotors and encode for type

    Possible Rotors are :

    +  = singleOn only one segment is dark

    -  = singleOff only one segment is light

    o = opposite2 Like the BMW logo

    a = adjacent2 Like a 1/2 eaten pie

    

    $ cat sk_6018.txt

    oo+ooaoo-

OR Process results from solver in the following format

    sat

    ( (V0 9)

    (V1 7)

    (V2 5)

    (V3 3)

    ....

to generate an html layout as output.

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.