The fascination about "how shapes fit together" seems really basic to me. Look at the long story of the Pentomino puzzle. The variety of problems coming out of simple figures made of five squares is amazing. You can hardly escape the attraction. The longer you think about puzzles the wider is the field of related problems. Finally you find yourself in the middle of an ocean of forms and figures.
That's exactly where I started with this subject. As a boy I spent countless hours with my brother looking for solutions of Pentomino, Hexomino and other puzzles. Later – about 1986 – we tortured our Atari-PC to calculate solutions. At that time the Logelium Project evolved with a computer program solving a large class of puzzles with a generic approach. The Atari was moreover one of the first PC allowing reasonable graphics. A historic print-out from that time survived on my shelf (see below).
Pentomino solution with matrix printer nostalgia
After that the Logelium was sleeping for a very long time. It woke up again when I accidentally stepped on an article about the successful solution of the Eternity puzzle. The Eternity puzzle triggered a lot of activity and lots of articles on the internet related to mathematical puzzles. Today this stream has run dry almost. Looks like that the price money generated most of the motivation — too bad.
For me it made me search for the old Modula2 Program on dusty floppy disks. It was still there and I converted it into a modern C++ program. The speed of present-day computers helps too, so that solutions can be calculated in seconds what needed days or more before.
In the meantime many new puzzle types had been invented. It's surprising that Logelium can calculate most of them, but also limitations became visible. These are serving as a source of inspiration to find extensions. Little by little the Logelium developed to a solution concept for a wide range of puzzles.
This site is in German originally. As English is not my first language, there maybe errors or funny expressions. I you find misleading or confused text, please send me corrections. Furthermore some tables contain numbers with German style digit groups separated by dots ( e.g. 2.000.000 is two million ). Please accept this benevolently.
Thanks to Mark Michell for proof reading the English text.
The Logelium is very private project, by no means a commercial one. There is no aim for scientific results, it's just for fun playing with mathematical experiments and finding insights. A reader with little mathematical interest may still enjoy the graphic effects.
The world of integers and the geometry within grids is not at all fully understood, maybe only a bit neglected. Mathematical methods work perfectly in the real or complex continuum and are of very limited use, if you restrict problems to whole numbers. Integer numbers behave strange and are different than just special cases of real numbers, although this is truly the case. Polynomial equations P(X1, X2, …, Xn) = 0 with whole number coefficients, where we look for whole number solutions, are called Diophantine Equations. Geometric figures in integer grids belong to the same type of category. The famous triangles of Pythagoras are a good example. Already in ancient times Diophantos (~ 250 BC) was deeply thinking about these questions. The difficulty of the matter did not decrease over time. Look at the 10th Hilbert problem, which asks for a generic solution concept of diophantine equations. We know just recently that diophantine equations are undecidable generally.
As we see tiling problems and puzzles can be described als diophantine equations. Immediately we find ourselves in a difficult area. It's worth while to set up experiments and find surprising results. The Logelium works with Boolean equations, usually quite a few. Most of the puzzles have a finite search tree, therefore they are always decidable theoretically, even if the actual calculation fails due to the depth of the search. We find a finiteness which is definitely scary. The practical recources to find solutions are rather limited.
As I am travelling on business a lot, I spend a lot of time on planes or in hotels with the invention of new Logelium features. Otherwise this time would be wasted with boring TV programs.
I will publish some fraction of my material through these internet pages, provided I find some spare time. I will select some themes, which are not discussed extensively in other places already. This means I am not aiming for completeness but to shed light on some unstudied aspects of puzzles.
And if I am reaching a few bright minds on this planet, who are delighted and maybe inspired, the intended purpose of this pages is met. I will complete this site with selected chapters by and by. Any comments are truely welcome.
The Logelium finds solutions of tiling problems of many kinds which are based on periodic grids. The grids may be 2D or 3D, I didn't work with more dimensions, although there is no fundamental problem other than the reasonable presentation. The whole subject has a very experimental nature and the selection of puzzles and forms is purely subjective.
These are some examples with solutions (PDF):
 |
 |
 |
 |
 |
TriTetraTan |
Pentomino |
B-Tetromino |
Delta-Tri-Stick |
Hexiamond |
The principal method is brute-force backtracking with some special effects. As I am a believer in P != NP,
its wasted time to look for a magic formula to avoid the complete scan of the search tree. It helps to consider constraint
conditions like parity. This cuts off some branches of the tree but does not alter the NP complexity of the tree.
The original puzzle will be abstracted from unnecessary geometric properties and converted in a algebraic form. This approach proved to be very successful and allows at the same time the solution of a large class of puzzle problems. The relatively complex definition of the puzzle tiles is outweighed by the advantages.
Through the times some variants of the solving algorithm developed which work more or less efficient. It is well known that the intelligent choice of the data structures is crucial as well as the overall sophisticated programming technic to accomplish high performance. Good criteria to detect branches of the search tree with no solutions are a valuable tool to gain speed. To investigate efficiency we look at problems for which we can find all solutions. Only the complete scan of the search tree is a basis for comparing different search methods.
The general design idea is to exploit the scope of the methods rather than finding special algorithms for dedicated problems. Therefore the investigated variants of the solution methods are generic and not puzzle specific.
When experimenting with problems with many tiles, where "many" begins around 50, we encounter quickly the enormous depth of the search tree. Even with leading edge hardware we easily reach the limits. A computer with 10100 times power is on my wish list. I think I have to wait quite a while.