I have a cube puzzle similar to bedlam puzzle. It is 4x4x4 and has 12 pentacubes, 1 tetracube. Is there a simple way to solve them?
I hope tags are correct :)
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
There isn't, and it's been mathematically proven that there isn't.
It's clear that, say, 2-dimensional assembly puzzles, and jigsaw puzzles, are simpler special cases of this three-dimensional version. But even the simple case has been proven to be NP-complete (PDF). NP-completeness is a precise technical term, but a good nontechnical approximation is "requires brute-forcing". In other words, in the general case, this sort of puzzle doesn't have a systematic solution.
Note that there may well be a faster solution method in any given specific case, and possibly even in the average case. Any specific puzzle of this nature might have been designed to have some trick or insight to solve it, and it may well be that there's an algorithm that will work effectively on many such puzzles. Most of the research I checked for optimizing the average case deals with traditional-style jigsaws in which the intended destination of each piece can be approximately guessed from its colour, though. This sort of uniformly coloured puzzle is considerably more difficult than that.
-
1$\begingroup$ Great answer. A common trick with this type of puzzle is to mark the little cubes with 2 alternating colours, and see if it tells you anything about where the pieces go. But that doesn't take help in this case that I could see. There are also some great computer algorithms that would be useful for programming it, but as you say it's fundamentally brute force... $\endgroup$ May 14, 2017 at 3:43
-
$\begingroup$ Firstly i was thinking to implementing brute force algorithm. But my algorithm building skills are not enough for that. Nice answer. $\endgroup$ May 14, 2017 at 8:51
$\begingroup$
$\endgroup$
The pointer to NP-Completeness is relevant but contains several misconceptions.
The definition of NP-completeness is pretty technical, but it's about running time of algorithms. You asked for a "simple" way to solve the problem. Is that the same as a fast way? Often in the field of algorithms, there's a simple, slower way, and a complicated, faster way. An example is finding the median of a set of numbers. The simplest way is to sort the numbers and take the number in the middle. A faster way is the Big Five Algorithm, which is rather complicated (but really cool), and wasn't invented until 1973. Much of the field is about replacing simple but slow with fast but complicated. Backtracking is a simple but tedious method for puzzles like yours. Backtracking was applied to a pentomino problem on the MANIAC computer by Dana Scott in 1958. It certainly qualifies as "systematic". It's simply false to say "this sort of puzzle doesn't have a systematic solution."
The second thing to know is that it's about running time as a function of input size, and in fact, when the input size is large (as it approaches infinity, actually.) I guess Kadon sells some giant polyomino puzzles, but the puzzle you show has 12 pieces, which is what typically interests me. A proof that 1000-piece puzzles can take a trillion years isn't that relevant to what we do as puzzlers.
Another point is that an NP-completeness proof is not a proof that a problem requires a long running time. It's widely believed in the mathematical community that this is the case, but there is still no proof 40+ years after the theory was laid out -- one of the great open questions in mathematics. These problems are all connected in the sense that finding a fast algorithm for one will give a fast algorithm for all. No one has found a fast algorithm for any of them yet, but neither has anyone proved that none exists. (A better phrase than "fast" might be "not super slow".)
Another point has to do with how problems are shown to be NP-complete. It involves taking a known NP-complete problem and showing how to transform it into the problem of interest. Usually the resulting problems are rather contrived. For example, in the paper cited, an NP-complete problem involving sums of integers is transformed into a polyomino puzzle made exclusively of 1-by-something sticks! It's not a puzzle I'd buy, but it does have to be solved by a "general" algorithm for polyomino problems. This was alluded to in the previous answer. Sometimes a restricted version of the problem is not NP-complete. For example, we could break this proof by adding a "no sticks" restriction (but we could fix the proof in this case.)
The next point is that many NP-complete problems don't require "brute force" algorithms. "Brute force" means listing out every possible solution until one is found or all are eliminated. Reasonable strategies evaluate and eliminate partial solutions. Backtracking, Branch-and-Bound, and Dynamic Programming are some of the techniques. If you are packing your puzzle pieces into a box and find that the placement of the first three pieces isolates a corner, you will stop without considering placements of the remaining nine pieces, then move on to another placement of the first three pieces. Backtracking is really pretty simple -- slow and tedious, but a lot faster than brute force.
The last point I will make regards the "average case". To average requires the definition of a probability distribution over all puzzles. Probably, we would want to assign equal weight to every puzzle. But then, what is a puzzle, exactly? What restrictions will you put on the pieces to get an interesting puzzle? If you figure that out, you can write a computer program to churn out interesting designs for the rest of us!
