In how many different ways can a 9-panel comic grid be used?
While writing my answer to Why does “Watchmen” use the 9-panel grid? I used this picture to indicate the many ways it can be divided into groups (which may be used for the panels of a comic, as was the case in “Watchmen”):
Image source
Afterwards, it has been pointed out to me in a comment that there are some combinations that are not present in this picture:
The $81$ variations on the $9$ panel grid in that diagram don't exhaust the possibilities -- there are certainly many others. For example, this one is one of the many that aren't shown there.
Another comment says that the 9-panel grid can be used in $4096$ different ways:
The are $12$ interior borders, each of which can be included or excluded in a particular layout. That's $2^{12} = 4096$ possibilities.
A two-page spread treats two $3 \times 3$ grids as a single $6 \times 3$ grid with $21$ internal borders, for $2,097,152$ possibilities.
How can I calculate that? I tried the following:
- There a $3$ ways to group the third row.
- That leaves us with $4$ panels in 2nd and 3rd rows. I count $4$ ways to group those.
- The $12$ combinations so far must be multiplied by $4$ (because I can rotate them) and by $2$ (because I can mirror them).
This gives me $96$ variations. The picture above has $81$; the comment said there are $4096$.
Is there a layman-friendly geometrical solution? I'm not really interested in a precise value (a lot is enough for me), I'm more interested in the technique or a rule. Is there a general rule for a n-by-n grid?
To clarify: panels must be rectangular, i.e. they must be formed by merging some of the $9$ panels horizontally or vertically:
Suppose we create a layout by deleting borders between the panels of a $3\times 3$ grid, as has been suggested at various times. But let's put some restrictions on which borders we can delete so that no non-rectangular panels are possible, but all layouts with rectangular panels are possible.
Consider the four border segments that meet at a single vertex in the $3\times 3$ grid. Label these segments $N, E, S, W$ in clockwise order starting from the top. If you delete three of these segments and leave one intact, you end up with a panel with a "crack" in it, not a rectangle. There are $4$ forbidden arrangements of this kind. If you delete two "adjacent" segments such as $N, E,$ you end up with a panel that has a "concave" corner, again not a rectangle. That gives us another $4$ forbidden arrangements.
But any of the other $16 - 4 - 4 = 8$ combinations of border segments around a common vertex can occur in a layout consisting purely of rectangles. Call these the permitted combinations.
It seems "obvious" (though maybe not so obvious how to prove) that as long as all four vertices in the interior of the grid have permitted combinations of edges, the layout will consist only of rectangles.
Actually counting the combinations that can occur together is more complicated. It's not $8^4,$ because there are many ways the choice of combination of edges at a vertex can be restricted by the combinations at the adjacent vertices.
To enumerate the possibilities, consider the edges that might or might not exist around the central square of the $3\times 3$ grid.
Case 1. All four edges exist. So the $NE$ vertex of this square has at least $W$ and $S$ edges; there are $3$ permitted combinations of the the other two edges. Similarly, there area $3$ permitted combinations at each of the other three vertices of the central square. This gives us $3^4=81$ possible layouts.
Case 2. Three edges exist. To begin with, we have $4$ choices of which edge to delete. Then, at each of the two vertices adjacent to the deleted edge, there are exactly $2$ permitted combinations of edges. (For example, if we delete the $E$ edge of the central square but not its other three edges, the $NE$ vertex has edge $W$ but not edge $S$; it must therefore have edge $E$ but edge $N$ is optional.) At each of the other two vertices, there are still $3$ permitted combinations. Altogether, there are $4 \times 2^2 \times 3^2 = 144$ layouts of this kind.
Case 3. Two opposite edges exist, the other two are deleted. There are $2$ ways to choose which pair of edges to delete around the central square; at each of the four vertices there are then $2$ permitted combinations of edges. Altogether there are $2\times 2^4 = 32$ layouts of this kind.
Case 4. Two adjacent edges exist, the other two are deleted. There are $4$ ways to choose which pair of edges to delete around the central square. At the vertex with two edges there are then $3$ permitted combinations of edges; at each of the two vertices adjacent to that, there are $2$ permitted combinations of edges; and at the fourth vertex (the one with two adjacent deleted edges already) all four edges must be deleted. Altogether there are $4\times 3 \times 2^2 = 48$ layouts of this kind.
Case 5. One edge exists. We have $4$ choices of which edge this will be. Then, at each of the two vertices adjacent to the remaining edge, there are exactly $2$ permitted combinations of edges. The other two vertices already have two adjacent edges deleted, so they each must have all four edges deleted. Altogether, there are $4 \times 2^2 = 16$ layouts of this kind.
Case 6. No edges exist around the central square. There is only one layout with this property, the one consisting of a single panel.
Adding it up, we have $$ 81 + 144 + 32 + 48 + 16 + 1 = 322,$$ so there are $322$ possible layouts.
While this is not so much of a mathematical solution as a software one, I'm going to add it anyway, if only for the nice image at the end.
The process used to find all of the grids is as follows.
First of all each of the squares on the 3x3 grid is assigned a index 1 to 9 based on the coordinate ($n=3(y-1)+x$), where $(1,1)$ is top-left and $(3,3)$ is bottom-right. This number represents the highest index of a panel which can cover it.
Essentially this means that panels must grow out from any square rightward and downward. This limitation prevents duplicate entries - every panel which grows right-down is identical to one which grows left-up.
The task is then to simply build up a list of possible grids by adding panels. The panels are using a recursive approach which abandons all grids which could only be covered have more than one panel with the same index thus preventing duplicates grids.
For anyone interesting is seeing the MATLAB code which enumerated all the grids, I've including it at the end of the answer.
It's quite impressive how fast the number of possible grids grow.
For a 3x3 grid we have the 322 possibilities as was identified by the other answers. Jumping up to 4x4 gives 70878 possible grids. Going for a two page spread of 3x6 the number increases to a barmy 314662 possible grids!
Having built all possible grids, it only makes sense to export them into something pretty. Below is all of the grids tiled and converted to a combined image of all 322 possible grids. In the image the colour of a panel represents the index of top left square in that panel.
The grids are sorted in the order that they were found - which is essentially one of starting with a solid square and then working back from the bottom right corner.
The following MATLAB functions are used to produce the grids.
function [found] = makeGrids(found,grid,depth,x,y)
if (depth > (x*y))
%If at max depth then grid is valid.
found = [found grid]; %So add to list
disp(grid)
%found=found+1; %So one more found
else
%Show current depth and found count during search.
if (depth<=(x*(y-1)))
disp([repmat('..> ',1,depth) num2str(depth) ' (found:' num2str(numel(found)) ')']);
end
%Another layer to do
for k=1:depth
%For each number in this layer
grid(depth)=k; %Update grid with new number. Depth is linear index
%Now we check to see if the current state of the grid is
%acceptable (if it isn't then no lower down ones possibly can)
if (checkPanels(grid,depth,x,y)) %If it is acceptable (i.e. there are no remaining values with no frame)
found=makeGrids(found,grid,depth+1,x,y); %Work through the next layer
end
end
end
end
function success = checkPanels(grid,depth,x,y)
success = false;
for ys=1:y
for xs=1:x
%Start at (1,1) and work through to (n,n)
expected = xs+(ys-1)*x; %Linear index of this cell
if(expected > depth)
%If the expected val is more than current depth
return; %Then we are done searching
end
panelFound=false;
for xe=x:-1:xs
for ye=y:-1:ys
%For each end value starting from largest to smallest
panel=grid(xs:xe,ys:ye); %Extract the current panel
panel(panel==expected)=0; %Cover all instances of expected value in panel
panelFound = all(all(~panel));%Check if every number in this panel is covered
if (panelFound) %If we have found a complete panel
grid(xs:xe,ys:ye) = -1; %then mark panel a covered in the grid.
break; %We can only have one panel for any given number, so break.
end
end
if (panelFound)
break; %We can only have one panel for any given number, so continue break.
end
end
%Check if entire grid is covered
if (all(all(grid==-1)))
success = true; %Grid is all covered and valid
return;
end
end
end
end
The following script is then used to call the function and create the tiled image (although I added the borders with edge detection in Photoshop)
%Grid Size
x=3; %3x3
y=3;
%Enumerate all grids
grids=makeGrids({},zeros(x,y),1,x,y);
gridCount = numel(grids);
disp(['Grids Found: ' num2str(gridCount)]);
%Colour mapping for image - hot(x*y), hsv(x*y) and jet(x*y) all look good
map=[jet(x*y);0,0,0]; %;0,0,0 is for black borderd
%Create images for all grids
nameFormat = ['%0' num2str(ceil(log10(gridCount))) 'd'];
for i=1:gridCount
img=grids{i};
img(x+1,:)=(x*y)+1;
img(:,y+1)=(x*y)+1;
[img, newmap]=imresize(img,map,32,'nearest');
imwrite(ind2rgb(img,newmap),['Grid' num2str(i,nameFormat) '.png']);
end
%Create tiled montage of images
dirOutput = dir('Grid*.png');
fileNames = {dirOutput.name}';
vertical = max(factor(gridCount));
horizontal = gridCount/vertical;
montage(fileNames, 'Size', [vertical horizontal]);
%And save montage as PNG.
allGrids=getframe(gca);
imwrite(allGrids.cdata,'AllGrids.png');
Unfortunately these kinds of geometrical questions rarely have a neat satisfying answer, like a formula for any sized grid. This is because a "divide and conquer" strategy does not work - as soon as you cut the grid into two smaller grids to be analysed separately, you miss out on all the patterns that have panels crossing your cutting line, and those are not easy to classify or count.
I've tried to count all the patterns by hand, so it is likely I've made mistakes. The table below lists the patterns I found. The left column lists the large panels (the 1x1 are not listed). The right column lists the number of possible arrangements of those panels. The multiplication in brackets is for all the rotations/reflections of that patterns (so an asymmetrical one is multiplied by 8).
[After comparing to David K's answer, I fixed 4 mistakes and my final count it now matches his.]
3x3 -> 1 (*1) 2x3 + 1x3 -> 1 (*4) 2x3 + 1x2 -> 1 (*8) 2x3 -> 1 (*4) 2x2 + 1x3 -> 1 (*8) 2x2 + 1x3 + 2x1 -> 1 (*8) 2x2 + 1x2 + 2x1 -> 1 (*4) + 1 (*8) 2x2 + 1x2 -> 2 (*8) 2x2 -> 1 (*4) 1x3 + 1x3 + 1x3 -> 1 (*2) 1x3 + 1x3 + 1x2 -> 1 (*8) + 1 (*4) 1x3 + 1x3 -> 1 (*4) + 1 (*2) 1x3 + 2x1 + 2x1 + 2x1 -> 1 (*4) 1x3 + 1x2 + 1x2 + 2x1 -> 1 (*8) 1x3 + 1x2 + 1x2 -> 2 (*8) + 2 (*4) 1x3 + 1x2 + 2x1 -> 2 (*8) 1x3 + 2x1 + 2x1 -> 1 (*8) + 1 (*4) 1x3 + 1x2 -> 3 (*8) 1x3 + 2x1 -> 1 (*8) + 1 (*4) 1x3 -> 1 (*4) + 1 (*2) 1x2 + 1x2 + 1x2 + 2x1 -> 2 (*8) 1x2 + 1x2 + 2x1 + 2x1 -> 1 (*2) 1x2 + 1x2 + 1x2 -> 2 (*4) + 1 (*8) 1x2 + 1x2 + 2x1 -> 5 (*8) 1x2 + 1x2 -> 2 (*4) + 2 (*8) 1x2 + 2x1 -> 1 (*4) + 2 (*8) 1x2 -> 1 (*8) + 1 (*4) 1x1 -> 1 (*1)
If my list is correct, and I counted it up correctly, that gives 322 different patterns. If you consider rotated or reflected patterns identical (i.e. leave out all the multiplications in brackets), then there are 54.
Some examples of the patterns missing from the picture in the question are:
- a single 1x3 or 3x1 panel in the middle
- Two non-adjacent 1x3 or 3x1 panels
Addendum
After thinking a bit more about David K's method, I figured out a way to calculate the number of panel patterns in a 3xn grid.
Consider two vertically adjacent vertices. There are two horizontal border segments on the left, two horizontal border segments on the right, and three vertical border segments down the middle. For the two segments on the left there are four possibilities of whether they are present or erased, and similarly on the right. For each of those 4*4=16 combinations we can count how many possibilities there are for the vertical segments.
This is shown in the following picture, where each dark grey vertical segment has two possibilities:
This gives a transition matrix, that tells us how many ways there are to connect up the inputs on the left to the outputs on the right.
$$\begin{pmatrix} 8 & 2 & 2 & 1 \\ 2 & 4 & 1 & 1 \\ 2 & 1 & 4 & 1 \\ 1 & 1 & 1 & 2 \end{pmatrix}$$
Adding up all the entries in the matrix gives 34, which is the number of ways a 3x2 grid can be divided into rectangles.
For a 3x3 grid we apply two transitions, by squaring the matrix.
$$\begin{pmatrix} 8 & 2 & 2 & 1 \\ 2 & 4 & 1 & 1 \\ 2 & 1 & 4 & 1 \\ 1 & 1 & 1 & 2 \end{pmatrix}^2 = \begin{pmatrix} 73 & 27 & 27 & 14 \\ 27 & 22 & 13 & 9 \\ 27 & 13 & 22 & 9 \\ 14 & 9 & 9 & 7 \end{pmatrix}$$
Adding up all the entries, we get the answer for a 3x3 grid:
$$\begin{pmatrix} 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 73 & 27 & 27 & 14 \\ 27 & 22 & 13 & 9 \\ 27 & 13 & 22 & 9 \\ 14 & 9 & 9 & 7 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} = 322$$
Evaluating the same for the n-th power of the matrix gives the number of ways to subdivide a 3x(n+1) grid:
$$\begin{pmatrix} 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 8 & 2 & 2 & 1 \\ 2 & 4 & 1 & 1 \\ 2 & 1 & 4 & 1 \\ 1 & 1 & 1 & 2 \end{pmatrix}^n \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} = 4, 34, 322, 3164, 31484, 314662, 3149674, 31544384, ...$$
This sequence is found in the OEIS as A208215.
If you were to apply this method to 4xn grids, you'd need a 16x16 matrix, Each further row doubles the matrix size, so it soon gets unwieldy.
For square grids, the "Number of ways of dividing an $n\times n$ square into rectangles of integer side lengths" is OEIS sequence A182275. There are no formulas, but for $n\le12$ the following numbers have been calculated by Joshua Smith and Helena Verrill:
1 1
2 8
3 322
4 70878
5 84231996
6 535236230270
7 18100579400986674
8 3250879178100782348462
9 3097923464622249063718465240
10 15657867573050419014814618149422562
11 419678195343896524683571751908598967042082
12 59647666241586874002530830848160043213559146735474
See also A034999 for $2\times n$ grids and A116694 for $m\times n$ grids.