Puzzle Solving mostly using SMT (integer) solvers

This blog started as collection of descriptions about how to reframe common puzzles into the input language of an SMT (integer) solvers. One or two other problem-solving articles are included. Scripts to transform puzzles, to the language, suitable for a solver, and for re-formatting the output to an HTML display page are available on request from the author. Those items mostly result from a lockdown project, since then the wider field of logic programming and languages has been explored.

Showing posts with label puzzle solver. Show all posts

ChatGPT - not so clever after all - on logical tasks

I really like the work of Adrian Groza who explores the puzzle solving using first order logic.

In this recently printed paper, Adrian explores the reasoning capabilities of ChatGPT. Starting with a large quantity of logical puzzles reformed in a way that can be presented to ChatGPT. The large language model then tries to present reasoned answers. No spoilers, but it doesn't go well.

Link to paper on ResearchGate here:

(PDF) Measuring reasoning capabilities of ChatGPTresearchgate.net

The paper goes the extra mile beyond just testing ChatGPT problem solving capabilities. The paper looks in detail at the dialogue and extracts the type of nature of the logical fallacies that are included in chat GPT's reasoning. There appears to be lack of common sense, better answers are presented as being worse answers. In some cases extra constraints are unnecessarily added to problems, leading to the inability to find the correctly available answer.

One conclusion of the paper correctly identifies that ChatGPT does have strengths in the language processing area, but falls very short when required to do detailed factual, correct problem-solving work.

The dangerous/great thing about "trusting an Oracle" without substantive background and showing the workings is that it can learn from feedback....

From the paper ... Preprint · October 2023

Run today 3 December 2023

Good to see that ChatGPT can make a fair assessment of its own abilities on logical problems and puzzles.

After concluding that 693 is equal to 729 and a father aged 29 can have children aged 24 and 21 Chat GPT provided the admission that "For the most accurate and reliable results on logical puzzles, it's often better to use dedicated problem-solving tools or consult with experts in the relevant field."

*** Update Jan 2024 -- See also ChatGPT bombs test on diagnosing kids’ medical cases with 83% error rate

**** From the Source itself

Q: Can chatGPT solve all sudoku ?

ChatGPT can help solve many Sudoku puzzles by applying a logical, step-by-step approach, but it does have some limitations:

Logical Strategies and Explanation: ChatGPT can walk you through various solving techniques (like Naked Singles, Hidden Pairs, X-Wing, etc.) and apply them in a logical order to solve the puzzle. For many standard Sudoku puzzles, this method is effective and often enough to reach a solution.
Complexity and Advanced Techniques: For highly complex puzzles, such as those requiring advanced techniques (e.g., Swordfish, Jellyfish, or even more intricate techniques used in extreme Sudoku variants), ChatGPT may need external support, like an SMT solver or specific backtracking algorithms, which require computational logic and precision.
Consistency and Verification: ChatGPT may not perfectly track all the placements or logic steps in real-time without a computational system in place. It’s designed for language and reasoning but lacks the persistent, systematic memory needed to ensure that every logical deduction is correct and free of contradictions.
No Access to Real-Time Calculations: In this chat-only environment, ChatGPT doesn't directly execute code to solve Sudoku with brute-force algorithms (such as backtracking or SMT solvers) or check constraints dynamically. It can outline these methods in code (like Python or Z3), which you can run in a suitable programming environment.

Conclusion

In short, while ChatGPT can explain and help solve many standard Sudoku puzzles through logical reasoning and pattern recognition, it may not be able to solve all Sudoku puzzles independently without computational assistance, especially those requiring extensive backtracking or advanced constraints. However, with external tools, such as an SMT solver or a Sudoku-solving algorithm, it could solve even the most challenging puzzles reliably.

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

Satisfiability modulo theories library, is the a grand title given to what we will refer to as SMT – Lib or even just SMT. This blog and its associated articles are the result of trying to find some software that would both complete every possible known Sudoku and provide a way forward for a problem solving project that was bogged down.

SMT has quite a high barrier to entry, the descriptions of how they work and what they can do are very mathematically orientated, using symbols and characters that are unfamiliar to most computer programming folks. However, with a little perseverance, trial and error, they can be a great stepping stone toward solving a multitude of different problems.

Starting out with solving Sudoku in mind. The initial step was understanding how to describe the rules of Sudoku in a way that can be presented to a general purpose, SMT solver. Unlike other programming approaches, the required effort is around describing the rules and conditions of the problem whilst completely ignoring how to progress those rules to reach an answer. The solver takes on all the effort of reconciling the constraints of the particular puzzle, giving a viable answer or rejecting the puzzle as unsatisfiable.

Gone is the complexity of implementing the many solving rules for Sudoku replaced by a simple text manipulation script that reads the input puzzle, generates a SMT language file, passes it to the solver then reads the solver results. This solution pipeline can be applied to many different puzzle types ( but not crosswords) with just minor adjustments to the scripts.

The stages of the puzzle solving pipeline are are :

Image of Puzzle,
Text representation of puzzle,
Script to convert from text to SMT language,
Solver,
Script to convert results to a display.

A detailed writeup on Sudoku and some of its variants can be found here but the short description is as follows :

Tell solver what type problem this is and that answer values will be required
Declare 81 integers each of which can only have values between 1 and 9.
Declare that each row, column and sub-square must have unique values,
Set the known clue numbers,
Ask for the answers

By describing the problem in this exact way the solver will find an answer. For sudoku puzzles of different shapes and answer values, the number of variables and their range can be simply adjusted in the conversion script.

The solver used is not artificial intelligence. They are entirely deterministic and driven purely by the input statements provided to them. By defining the problem in strict logical terms, that logic can be manipulated in order to find the answers. No guesswork or training is required by the solver. Every answer is logically deducted from the provided input statements.

Following on from the success of solving any type and shape of Sudoku, other puzzles were tackled using a similar techniques. The wrinkle being some of the problems require careful manipulation in order to create the required SMT language. The conversion of results into a displayable page image was mostly taken care of using generated HTML text displayed in a browser.

SMT solvers have traditionally been used in the rarefied areas of theorem proofing and program integrity, checking. There use here whilst less formal provides some insight into how deconstructing a problem into its core aspects, and then concentrating just on those features can provide a useful introduction to 1st order logic and getting the job done quickly.

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.

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.

ChatGPT - not so clever after all - on logical tasks

Conclusion

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

Finding the way out of a six burr trap

Down the rabbit hole

Research time

Coding the puzzle pieces

Coding the layouts

Make the code

Results

Going faster

Now with holes in

Next

References and Acknowledgements

Usage

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

Total Concentration from The Turing Tests - Expert Numbers puzzles, solved using SMT (Integer) solver.