This project is devoted to the science of tiling a rectangle,
or a box, with one or more polyominoes.

What is a polyomino?

A polyomino is a shape that consists of unit squares pasted together.
This is an extension of the word domino, two squares placed side by side.
But the word poly means meny, hence we may have many squares arranged
to form a particular shape.
Can this piece be used, over and over again, to tile a rectangle?
If so, the order of the polyomino is the smallest number of pieces
that will tile a rectangle.
It is notoriously difficult to determine the order of even modest polyominoes.

Of course the polyomino might already be a rectangle,
as illustrated by the domino.
Thus it's order is 1 (not very interesting).
A triomino, three squares pasted together, can assume only two distinct shapes.
The straight line has order 1 and the L shape has order 2.
Two L's join together to make a 2×3 rectangle.
The five tetrominoes are the line, the L, the Y
(three squares in a row with one above the middle), the square, and the stairs.
These have orders 1, 2, 4, 1, and 0, respectively.
The troublesome tetromino, that looks like a set of stairs,
has order 0 because it cannot tile a rectangle.
As you march along the floor of the rectangle,
you must always slide another piece under the notch of the previous piece,
and the stairs go on forever.
You can tile the first quadrant, but not a rectangle.

If you are familiar with the Hex™ puzzle,
which has been on the market since the 1960's,
you already know the 12 pentominoes well.
They are, in my nomenclature: the line, the L, the Y
(you have to tilt it a little to look like a Y), the C, the stairs, the faucet,
the Utah, the lightning bolt, the zigzag, the T, the cross, and the chair.
The Hex puzzle asks you to tile a 6×10 rectangle with these 12 pieces.
I encountered this puzzle at age 8, and have been fascinated by tiling problems
ever since. I wrote a C program, hexsol.c, to find all solutions,
not just for the 6×10 board, but also the
5×12, 4×15, and 3×20 rectangles.
The latter has only two solutions.
The original puzzle, on a 6 by 10 board, has 2339 solutions.

hexsol -c
2339 solutions

This program, and all others in this project, generate solutions as an ascii
matrix. Thus a solution to the Hex puzzle might look like this.

	EEEIIIDDDJ
	EAELIIFDJJ
	AAALLFFDKJ
	CALLFFGGKJ
	CBBBBBHGKK
	CCCHHHHGGK

This is not very satisfying, so I wrote a program to convert the matrix
into an image, using ImageMagick.
The program is letterart.c, included in this project.
If the above matrix is in a file calld hex610.mat, invoke the program this way.

letterart hex610.mat png48:hex610.png

The prefix png48: on the output file is important!
On some machines, ImageMagick generates a space saving 8 bit black&white image
format, which most image programs do not recognize.
png48: forces 16 bit RGB, which can be read by every program, and by every
browser, if you wish to put images on your web site.
The picture that goes with the above matrix is in pictures/hex610.png.
Take a moment and look at it, and compare with the above matrix.

letterart foo is shorthand for letterart foo png48:foo.png

If you want to extract the individual pieces from the matrix, for machine
analysis, use the m2p perl script. (matrix to pieces)
src/m2p <matrix-file >pieces-file

So which pentominoes, on their own, tile a rectangle?
The line, the L, the Utah, and the Y, with orders 1, 2, 2, and 10, respectively.

When I was in junior high I built the 35 distinct hexominoes out of lego
and tried to fit them into a 14×15 frame.
I even thought about marketing the puzzle,
since the Hex puzzle (based on the 12 pentominoes) attained commercial success.
But try as I might, I could not fit the 35 pieces into the frame.
The puzzle wouldn't sell well if there was no solution!
Finally I had an epiphany and applied the checkerboard argument.
Most pieces cover 3 white squares and 3 black,
but an odd number of hexominoes cover 4 white squares and 2 black,
or 2 white squares and 4 black.
These pieces introduce an excess or deficiency of two white squares.
Clearly white and blacks squares must come out eequal.
This is a contradiction, hence there is no solution.
(Wikipedia hexomino also gives this checkerboard proof.)
Of course I could always toss out one of these offending pieces and try
to tile a 12×17 rectangle with the remaining 34 pieces,
but that is not aesthetically pleasing.
I mean, which one do you toss out?
The 35 hexominoes can however be packed into a right triangle,
as determined by the program hp1.c in the src directory.
This is a stroke of good fortune; 210 is a triangular number,
and the triangle covers 110 white squares and 100 black squares.
An example solution is shown in pictures/hextri.png.
This is original with me.

Other packings include the 15×15 square with a 3×5 rectangle removed,
and a rhombus 15 units high and 29 units wide with its center square removed.
The rhombus is my creation.
These tilings are discovered by src/hp2.c and src/hp3.c,
with the punctured rhombus shown in pictures/hexrho.png.

You can pack all ominoes, from the single square up to the 35 hexominoes,
56 pieces, into a rectangle that is 13 by 23.
See src/hp4.c and pictures/hexbelow.png.

There are 108 heptominoes, but one has a hole in it, like a snake wrapping
around to kiss its tail, and cannot participate in a solid packing.
If you want a rectangle with a hole in the middle, allowing for all 108 pieces,
that's 108*7 + 1 = 757, which is prime, so no dice there.
All this is in wikipedia heptomino.
However, I found that the 107 simply connected pieces
can make a rather long rectangle 107 by 7.
My program took days and got nowhere, but then I change the order in which
it considered the pieces, saving the nice corner pieces for last, and it found
a solution in 21 seconds. A small change can make a big difference!
See src/hept.c, and pictures/ heptrect.png.

Recall that 4 of the 12 pentominoes tile a rectangle.
Most of the hexominoes are easily solved as well, i.e. they tile a rectangle
with just a few pieces or they don't - except for the Y hexomino,
5 squares in a row and another above the second. Here we have a simple shape
consisting of 6 squares pasted together, yet we must write a computer program
to determine whether it tiles a rectangle. I wrote such a program in 1987,
and was the first to discover that this shape does indeed tile a rectangle,
and its order is 92. (Science News, November 14, 1987.)
Using variations of this program, I have discovered many other tilings.
These patterns illustrate the incredible complexity and beauty of mathematics.

The latest incarnation of my tiling program is in src/trec.c.
It is called trec for tiling a rectangle.
Naturally, it is a work in progress, and I welcome patches,
pull requests, or other forms of collaboration.

The program is typically run with one argument, a config file.
Each of the first eight lines must be present, and syntactically correct.

The first line gives the polyomino in hexadecimal format.
A byte indicates the squares that are present on the first row of the shape,
then the next byte describes the second row, and so on.
Our Y hexomino, the only hexomino with a nontrivial order, is f840,
five squares on the bottom row and one square on the second row.
I find it convenient to use a file of the same name,
thus the first row of the file f840 is f840.
You don't have to do that of course, but it's hard to keep track otherwise.

I also allow a + to set the ninth bit.
Thus ff+fcfc is a long version of Oklahoma,
with a row of 9 squares and two rows of 6 squares.
Use braces for a longer row, as in ffff{e0} for a row of 11,
although shapes with a diameter greaterer than 9 consume almost twice as much
disk space, and are not well tested.

You can specify a set of polyominoes on the first line, using _ as delimiter.
Thus f820_e070 describes a pair of hexominoes
that have order 94[12x47], as a set,
even though neither tiles a rectangle on its own.
At present, all the shapes in a set must have the same number of squares.

The second line sets the initial width.
I search for a rectangle with this width, then increase the width,
until I find a solution.
This line can also be used to resume the program after a controlled shutdown.
If you were analyzing rectangles of width 40,
and the last thing you saw was @27, indicating a depth of 27,
put  40@27  in the second line of the config file.
This resumes the program at width 40, depth 27,
using the files that were present when the program stopped earlier.
Don't panic if you specify the wrong depth; trec will tell you
what the depth should be and then exit.
But if you don't remember the board width it could really get confused.
Resumption should work if the program stopped because of SIGTERM, SIGQUIT,
or q at the interactive menu. Proper resumption is not guaranteed after a power
failure or system crash, or resource exhaustion
(e.g. lack of disk space) that could result in a partial write.
So keep an eye on your disk and your ram, and put a UPS
behind your computer, so you can shut down gracefully upon power failure.
I wrote some code to stop if you run out of disk space, and wait for you to hit
return, assuming you can find a way to free up some space.
This is the only way to continue and recover if you run into that wall.

The letter a means allcheck, so 54a will look for solutions
even if the rectangle is wider than it is tall.
Perhaps you ruled out rectangles up to width 48.
You are dealing with hexominoes, so a width divisible by 6 is better.
Jump ahead to 54, but you still want to check for 54x49.
I don't normally check for that, assuming we are incrementing the width
as we go, but you can override this with the letter a here,
or with -20 on the command line.

The third line is a bound on the order.
Don't look for larger solutions than this.

The fourth line determines the number of nodes,
in millions of nodes, that will be maintained in cache.
You can specify up to 400 million nodes,
but that chews up 2 gig of ram in a linear array.
Basically, multiply the number by 4.5 meg for ram consumed.
If the cache overflows, this program stops, gracefully.
You want to restart it with a higher cache, as per your computer's resources.
It's probably best to start with the highest cache you expect to need,
because the resume process, building the cache from scratch, is not efficient.

The fifth line sets the number of worker threads.
Use 0 to do all calculations in the foreground.
1 worker thread won't bring any benefit, but could be used for testing.
If you have a quad core CPU, 4 threads will use all 4 processors.
But if you want your computer to respond to your interactive commands
in a timely manner, you might want to set 3 worker threads,
and leave a processor for yourself.
You can see if threads are working by checking the load average.
If you asked for 3 threads, and the load average is 3.07, and not much else
is happening on your computer, then the threads are running.

Don't get excited about threads though.
Here is a test on my pi, with four CPUs and a gig of ram.

fcf030
39
130
60
?
1
2
1
-
0: 6m15
2: 5m16
3: 4m39
4: 4m42

Jumping to 2 threads only improved performance by about 20%, 5 minutes
instead of 6. In a perfect world it would run twice as fast, but there is
so much access to the disk and the cache that the threads
often have to wait for each other.
The third thread brings only a modest improvement, and the fourth thread
actually slows things down, even though I have 4 CPUs. 🤔
Also, after 2 threads my pi gets noticeably hotter.
So I can't go past 2 threads, and at that point I may as well stay with 1.
I was thinking about scrapping it altogether, but there is
probably another machine where thread support really makes a difference.
Maybe a core with 64 CPUs, and 8 gig of ram, and a high performance disk - could really go to town.
Give it a try, if you have such a machine, and let me know how it goes.
In any case - it was fun to write.

The sixth line tells the program how many rows to look ahead.
Normally the program tiles up to the breakline and then calls it a node,
but there's no sense wasting cache and disk space on a dead-end node.
So sometimes we want to tile beyond the breakline,
to make sure the node is valid.
Then again, it takes extra time to tile more rows on top of each node.
You'll have to trade space against time.
Lookahead values range from 1 to 4.
Set lookahead high to conserve nodes on disk and in cache.
Set lookahead = 1 for faster performance on small rectangles.
1 is usually best, and in fact it always seems better than 0,
which is why I don't allow 0.

The seventh line is a factor on the order.
Set this to 2 to force an even order.
Sometimes we know the order is divisible by something.
See theorems/order-factor for more information.

The eighth line is a factor on the dimension.
Boundary conditions often force both diminsions to be divisible by something.

The ninth line is optional. It presents a series of bad spans.
A span consists of 3 numbers, the height of the wall, the length of the span,
and the height of the opposite wall. 2,3,3 is a wall of height 2 or greater,
then a floor of width 3, then a wall of height 3 or greater.
2,3,3 is equivalent to 3,3,2. Due to some hard-coded searches,
spans wider than 4 probably won't be discovered.
Multiple spans are separated by pipes.
For example, the hexomino pair e0b0_e070 has bad spans
2,1,2|2,2,2|2,3,2|2,4,2
Spans are assumed to have nothing between the walls and above the floor,
i.e. there aren't any overhangs. Some polyominoes, like f08080_e070, have no
(realistically attainable) bad spans, whence this technique is no help.
You determine the bad spans by hand, and supply them to trec on this line.
Some day trec will compute the bad spans for you, since a mistake here, a span
that can actually be filled, could cause trec to miss a solution.
These spans are particularly helpful for wide rectangles. In some cases
the program runs nearly twice as fast. There may be other tricks,
like this one, that could further optimise the program.

A line with a single hyphen on it marks the end of data
and the beginning of comments about this shape.
Perhaps a proof as to why the order or the dimension are divisible
by certain numbers, or the best solution so far,
or the dimensions we have already explored.

Now let's return to our Y hexomino, the shape that started everything in 1987.
Here is its config file.

f840  # Y hexomino
6  # start from width 6 and grow from there
100  # cap on order
2  # 2 million nodes in cache
0 # no worker threads
1  # standard lookahead
2 # checkerboard argument implies an even order
1  # no constraints on dimension
-
Comments here about the piece.

You can run trek without a config file like this.
trec ^f0e020
Small default values are used: 2 million nodes in cache,
no worker threads, minimal lookahead, etc.
For larger rectangles, you will need a config file to manage things.

You can pause this program by hitting ^C.
Don't be afraid; it won't kill the program.
It will say pause, and wait for you to enter a command.
Other threads will continue to process their nodes, but as soon as those
nodes are finished, those threads will suspend as well.
The entire program stops until you hit return.
From another console, you'll see the load average drop to zero.
If you type q, the program will shut down in a graceful manner,
whereupon it can be restarted again.
r prints the restart parameters.
n prints the nodes pending and in cache.
l gives the lookahead value, and l followed by a digit will change it.
a toggles the lookback feature, to check for solutions of lesser witdh.
d toggles printing of progress dots.
p is performance, printing something every thousand nodes.
b prints or changes the best order.
You can only decrease the best order, you may have already gone through rectangles
of lesser widths without looking for solutions of a larger order.
h is a help message.
Anything else and it just says what, then resumes.

You can run this program in the background, redirecting its output to a file,
and that's fine; you just don't have the interactive features.
It ignores SIGHUP, so you can close your connection and walk away and check in
every now and then; and it responds properly to SIGTERM, shutting down in a
graceful manner, so it can restart later.

The directory dotile must exist for this program to run.
It will create dotile/f840,
and store data files and solutions in this subdirectory.
Each solution is a matrix, as described earlier,
and is stored in dotile/f840/sol*.
run letterart to turn this into a png image.
There may be several solution files, as trec finds ever smaller tilings.

I don't include a dotile directory in this project, because you may want to
clone it, and then create a symbolic link through dotile to another
file system with more disk space available.
Thus dotile is in .gitignore.
With your dotile in place, trec f840 produces the following output.

;f840
?6 @0 @1 :1
?7 @0 @1 @2 @3 @4 @5 @6 @7 @8 @9 @10 @11 :1
?8 :0
?9 :0
?10 @0 @1 @2 @3 @4 @5 @6 @7 @8 :3
?11 @0 @1 @2 @3 @4 :5
?12 @0 @1 :5
?13 @0 @1 @2 @3 @4 @5 :5
?14 @0 @1 @2 @3 @4 @5 @6 @7 @8 @9 @10 @11 :3
?15 @0 @1 :0
?16 @0 @1 @2 @3 @4 @5 @6 @7 @8 @9 @10 @11 @12 @13 @14 @15 @16 @17 :757
?17 @0 @1 @2 @3 @4 @5 @6 @7 @8 @9 @10 @11 :657
?18 @0 @1 @2 @3 @4 @5 @6 @7 @8 @9 @10 @11 @12 @13 @14 :45
?19 @0 @1 @2 @3 @4 @5 @6 @7 @8 @9 @10 :26
?20 @0 @1 @2 @3 @4 @5 @6 :53
?21 @0 @1 @2 @3 @4 @5 @6 @7 @8 @9 @10 @11 :4
?22 @0 @1 @2 @3 @4 @5 @6 @7 @8 @9 @10 @11 :2778
?23 @0 @1 @2 @3 @4 @5 @6 @7 @8 @9 *92[23x24] :32901

You can see it stepping through rectangles of widths 6 through 23,
finding a solution at 23 by 24.
trec still searches for a smaller solution,
but it would have to have 90 pieces or fewer.
That's 540 squares,
and the width would have to be 23 or less, since 24 times 24 is 576,
and we just finished width 23, so trec stops. The order is 92. More often
trec continues to search after a solution is found, looking for a smaller one.

the chiral program, src/chiral.c, is used to analyze a solution.
It tells you how many pieces are in each orientation.
It also tells you if a piece has too many squares in it.
This happens sometimes, because trec is not meticulously careful
about making sure adjacent pieces use different letters.
They usually do, but on rare occasions you might need to hand edit the matrix,
changing the letters in one of the two conjoined pieces,
to produce a proper tiling.
Do this before you run letterart to create your image.

So how do you build all this software?
Go into src and type make. That's it.
Each program is a stand alone c file.

Type make install (as root) to install. This installs
trec, chiral, and letterart; the other programs are not commonly used.

letterart can be challenging to build.
ImageMagick headers and libraries are all over the place,
depending on your distribution.
This makefile works on Raspbian.
You may have to tweak the makefile to build letterart and drawit.
Again, patches are welcome to properly build these programs on various systems.

Wait a minute - why isn't the code indented‽

I am totally blind, and indenting doesn't help me at all;
in fact it is rather an inconvenience.
But when I am part of a group, as I have been throughout my professional career,
we can all agree to run code through indent before commit, and that works fine.
So let me know if you want me to start doing that.
So far, I have been the only programmer on this project.

A solution-2d file at top level holds tilings in matrix format
for most of the nontrivial polyominoes and pairs of polyominoes.
This will be updated as new patterns are discovered.
Any matrix can be turned into an image via letterart,
but I have created some of the pictures for you.
Again, the file name is the same as the piece, thus f0e040,
an octomino with order 246[41x48], has its matrix in the solution-2d file,
and its picture in pictures/f0e040.png.

At this point it seems my software can only prove a positive -
this piece tiles a rectangle - but in some cases it can prove a negative.
If a piece tiles a rectangle it tiles the first quadrant, so try to tile
the first quadrant, and if you can't, then neither can you tile a rectangle.
Of course there are plenty of pieces, like c06030, that tile the first quadrant
but not a rectangle. Those pieces require a formal proof.
And some pieces, like the cross, 40e040, are obvious,
because they can't even get started. The quadrant test is for a class of pieces
that look promising, but get stuck after a few rows.
Use the at sign for the quadrant test.

trec @f8a0

Failed at diagonal 17.

We start at the lower left and place pieces along diagonals,
moving out into the first quadrant, until we can't,
or we reach a predefined limit.
This piece can't tile the first quadrant out to x+y = 17.
That's a line drawn from 17,0 to 0,17.
Thus it can't tile a rectangle.
Some shapes that yield to this test are:

f8a0
f8c8
f0f0f080
fff8f8
f8e0e0e0
f8f8f0
fffcfcfc
fef8f8
ff+ff+e0
ff+ff+ff+fcfc
ff+ff+ff+fc
f08080
fefef0f0f0f0
fcfcf0
fcfcf0f0f0  (this one goes all the way out to diagonal 55)

You may be wondering about higher dimensions.
Three dimensional polyominoes are built by pasting unit cubes together.
Some shapes can be used to tile rectangular boxes; others cannot. The same
is true in 4 dimensions etc, beyond the bounds of physical puzzles.
john niss hansen has done considerable work in higher dimensions.
Please explore his polyomino projects on github, ID johnniss

An interesting inconsistency emerges as we move from 2 to 3 dimensions.
In 2 dimensions, a Flatlander would notice that some of the pieces in the
"solution" were reflected through a mirror. He cannot imagine the 3-dimensional
being that picked some of the pieces "up" and flipped them over.
He can only assume there were two sets of pieces, some left-handed
and some right-handed, and somebody used pieces from either set, as he wished,
to tile the rectangle.
Indeed, polyomino tilings aren't very interesting if you don't do this.
In contrast, we 3-dimensional beings can't just reflect pieces through a mirror.
Sometimes we need these reflections, and sometimes we don't.
If reflections are necessary, as part of a physical puzzle, then chiral
instances of the piece must be manufactured, in the proper quantitiesw,
which in turn gives a hint as to the solution.

The thre smallest spacial tetrominoes are formed by placing a cube on top of an L triomino.
These all have order 2.
Two of these are chiral, i.e. reflections of each other.
You might consider them the same piece or you might not.
Interestingly, the flat stair tetromino,
which could not tile a rectangle in the plane, has order 6 in 3 dimensions
(Left as an exercise for the reader).
The flat pentomino that looks like the letter C also has order 6.
The spatial pentomino formed by placing a cube ontop of a 2×2 block has order 4.

Recall the hex puzzle, which attained commercial success.
The 12 distinct pentominoes tile a 6 by 10 board.
Perhaps a 3 dimensional version would also attain commercial success.
The command line is rather awkward, but you can designate the 12 pentominoes,
with quantity specifiers, and its containing box, like this.
3dbox f8=1_f080=1_f040=1_e030=1_e08080=1_e04040=1_40e040=1_80e020=1_80e040=1_c06020=1_e0a0=1_e0c0=1 4 3 5
These 12 pentominoes fill a 5 by 4 by 3 box as follows.

aaaaa
bbbbl
bgffl
fffhl
-----
cccci
dciii
gggil
dhhhl
-----
eejjj
deekj
dgekj
dhkkk

They also fill a 2 by 5 by 6 box, and a 2 by 3 by 10 box.

There are 11 new pentominoes in 3 dimensions. As mentioned before,
we humans can't reflect pieces in 3 space, so bring in the left and right handed
versions, and there are 19 new pieces to hold in your hand.
combine this with the original 12, and there are 31, which is a prime number,
and doesn't lead to a convenient rectangle.
Omit the long pentomino, 5 in a row, and find 30 pieces,
suggesting a box 6 by 5 by 5.
I rather wish I had the pieces in my hands to explore this real world puzzle.
More on this later.

My tiling software, in trec.c,
must be restructured to find the order of a 3 dimensional polyomino,
that is, the smallest box that could be filled with this polyomino.
This has been done, in 3dbox.c.
This program is simpler: no interactive features (^c kills the program),
no multithreading, no config file.
Everything is on the command line.
The piece, on the command line, has the same hex syntax as trec.c.
_ delimits multiple pieces in a set, as it did before.
! describes a piece in 3 dimensions. (This is a new syntax)
e080!40 is an L tetromino with a cube pasted on the middle of the long leg,
in the third dimension.
After the piece, you can specify the dimensions of the box to fill,
or an order to start your search.
The solution is a sequence of matrices, one matrix per layer in the box.
I don't have an easy way to turn this into an image,
but John has programs to present the packing in a 3 dimensional animation.
Some basic results are in theorems/order-3d,
and some matrix solutionss are in solution-3d.

If you want to search by nodes, the way trec.c does,
rather than brute force, use the -m option.
-m20 creates a cache of 20 megabytes, and uses nodes.

3dbox e04040 10 3 10
3dbox -m2 e04040 10 3 10

Both produce the same solution, 60 T pentominoes packing a 10 by 3 by 10 box.
As the size of the box increases, you will want to search by nodes,
or the program will take forever!

I am on the path to finding the orders of all the pentominoes in 3d.
There are only a couple yet to resolve.
See solution-3d for these tilings.

Recall the (still open) conjecture that no polyomino has odd order.
This applies to the plane, but in 3 dimensions the conjecture is false.
The flat heptomino e0e080 has order 28 in the plane, but it has order 9 in 3d.
It fills a box 3 by 3 by 7.
(See solution-3d).
This suggests, to me anyways, that the conjecture might be false in the plane,
we just haven't found a counterexample.

Returning to the 30 penominoes, including the mirror versions when chiral,
and omiting the line, let's try to fill a 5 by 5 by 6 box.
My program can search for a solution, though it hasn't found one yet.
I include the command line here, because it is far from obvious,
and it illustrates how to specify the number of left and right handed versions.
I moved the ugly piece to the front, and some friendly pieces to the end,
in hopes of finding a solution sooner, but nothing yet.
Obviously this is not a marketable puzzle for the public.

3dbox c040!0060=1=1_f040=1_e030=1_e04040=1_40e040=1_80e020=1_80e040=1_c06020=1_e080!0080=1=1_e080!80=1=1_e080!40=1=1_e080!20=1=1_e040!40=1_e040!0040=1=1_c060!80=1=1_c060!40=1=1_c080!00c0=1_f080=1_e0a0=1_e08080=1_c0c0!80=1_e0c0=1 5 5 6

For modest puzzles, with no repeated pieces, we can generate and/or count all
the solutions. Use -c to count, and -a to see all of them. However, in some
situations, duplicate patterns will appear, and will be flagged accordingly.
The best way to avoid this is to put symmetric pieces at the end, like this.

3dbox -a 80e040=1_f040=1_e030=1_c06020=1_f8=1_e04040=1_e0a0=1_f080=1_e08080=1 3 3 5

This finds the 3 distinct solutions to packing 9 pentominoes in a 3 by 3 by 5 box.

Recall that the 12 flat pentominoes tile a 6 by 10 rectangle in 2339 ways.
Earlier we used these pieces to fill a box 3 by 4 by 5.
According to my software, there are 3940 distinct packings.

3dbox -c 80e040=1_80e020=1_c06020=1_40e040=1_e030=1_f040=1_f080=1_f8=1_e0c0=1_e08080=1_e04040=1_e0a0=1 4 3 5
3940 solutions

The 2 by 3 by 10 box holds 12 solutions, and the 2 by 5 by 6 box holds 264 solutions.

The well known Soma puzzle has 240 solutions.
My software can generate them, without duplicates, but the order of the
pieces in the set is critical. Chiral has to be at the end.
3dbox can't handle a solution with a chiral piece at the origin.

3dbox -a c08080=1_80c080=1_c060=1_c080=1_c080!80=1_c080!40=1=1 3 3 3

The first piece is the L, with no symmetry, and every solution has L at the
origin, thus no duplicates are generated.
By spinning and reflecting, each solution has L in a preferred orientation,
one with its corner in the lower left corner of the cube, and one with its toe
in the lower left corner of the cube.

3dbox -a 80c080=1_c080!80=1_c08080=1_c060=1_c080=1_c080!40=1=1 3 3 3

This line starts with the Y tetromino.
Every solution has the Y at the origin, and 3dbox puts it in a preferred
orientation, with its length running along the edge y = z = 0.
You can place the Y here too, if you have the puzzle in your hand; and
you know you are on your way to a solution, and you won't miss any solutions.
This piece is symmetric, so each solution is printed twice,
courtesy of its reflection through the Y tetromino.
I flag them with the phrase duplicate 2, and adjust the count,
so at the end of the page, it still says 240 solutions.
Yes, the output has duplicates, but hey, if you don't want them,
then put the L back in front.

3dbox -a c080!80=1_c08080=1_80c080=1_c060=1_c080=1_c080!40=1=1 3 3 3

The corner is first in line, and when it fits into the corner of the cube,
there is a 6 fold symmetry. This is indicated by duplicate 6 in the output.
These solutions are repeated 6 times over, rotations and reflections,
but at the end of the page, it still says 240 solutions.

There is another way to use 3dbox - filling the corner of a box of undetermined size.
This can be used to prove a shape has order 0.
If it can't tile the first octant, it can't tile a box.
You may notice, when tiling with nodes, that you never get off the flor,
or you never get very far off the floor.
This is a good time to try the octant test.
An example is e0e0e0!0040,
a 3 by 3 square with another cube placed atop the center square.
Play with it manually, and it seems to get into trouble.
Do this to verify it.

3dbox e0e0e0!0040 0

diag 0
origin 0 e0e0e0!004000
diag 1
diag 2
diag 3
diag 4
no solution

Other examples are a 2 by 2 square with a cube on either side.
80!c0c0!80   80!c0c0!40    80!c0c0!0040

My software contains a lot of optimizations, but is, at the end of the day, brute force.
Marcus Garvie (mgarvie@uoguelph.ca) and others are developing a new technique that overlays color patterns,
and then partitions the board into pieces.
This allows each piece to be tiled in turn.
Read his paper here.
https://www.mdpi.com/1999-4893/15/5/164