59
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ Do you just want to enumerate all 4096 possibilities? If so, label the interior borders as 1, ..., 12. Write the numbers from 0 to 4095 in binary with leading zeros to give a consistent length. Include border 1 if bit 1 is 1, include border 2 if bit 2 is 1 etc. 0 will give you no internal borders hence one 9x9 region. 4095 will give you all internals borders hence 9 1x1 regions. $\endgroup$ – badjohn May 19 '17 at 13:43
  • 15
    $\begingroup$ The 4096 ways also includes all kinds of non-rectangular panels. (Think of Tetris blocks, if you want an image) Naturally there are more of them, then if you only allow rectangles. However your 96 combinations are probably also off, since you overcount some symmetric and leave out others like a single big panel. $\endgroup$ – mlk May 19 '17 at 13:44
  • 8
    $\begingroup$ Not all 4096 combinations of border segments make sense; how do would a panel with only 1 out of 12 border segments make sense? Also; should each of the groups be a rectangle, or are non-rectangular panels also allowed? As a start, there are 127 different panels using only 1x1 and 2x2 blocks, so your picture is missing a lot of panels. $\endgroup$ – Servaes May 19 '17 at 13:57
  • 3
    $\begingroup$ @Servaes Do you mean 1x1 and 2x1, instead of 2x2 for the latter? $\endgroup$ – pjs36 May 19 '17 at 14:06
  • 1
    $\begingroup$ @pjs Yes I do, thanks for the correction. Unfortunately I can not edit the comment anymore. $\endgroup$ – Servaes May 19 '17 at 14:08
42
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Based on a recursive search of all allowable grids in MATLAB, I concur that there are 322 possible. $\endgroup$ – Tom Carpenter May 19 '17 at 23:38
  • 19
    $\begingroup$ For reference this picture shows all of the 322 grids. $\endgroup$ – Tom Carpenter May 20 '17 at 0:33
  • 1
    $\begingroup$ @Tom, that's awesome, I wonder if Gallifreyan will update the answer to the "Watchmen" question using your image. $\endgroup$ – Octopus May 20 '17 at 1:57
  • 8
    $\begingroup$ @Tom I'd say that image is worth an answer of its own. $\endgroup$ – David K May 20 '17 at 2:12
32
$\begingroup$

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.

All 322 Grids

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');
$\endgroup$
  • 1
    $\begingroup$ Wow! Thanks for the MATLAB code! I think I'd understand it better than any mathematical explanation. $\endgroup$ – Gallifreyan May 20 '17 at 10:56
  • $\begingroup$ Heh - tried running the code for a 4-by-4 grid - takes very long. I'll try and see if I can make it use parfor loops. $\endgroup$ – Gallifreyan May 20 '17 at 11:24
  • 1
    $\begingroup$ @Gallifreyan Yep, quite amazing how fast the pool grows. I tried to optimise the code to eliminate checking quite a lot of invalid grids. I've just finished running it for a 6x3 grid (2 pages). Took about 2 hours, result: 314662 possible grids! $\endgroup$ – Tom Carpenter May 20 '17 at 11:26
  • 1
    $\begingroup$ In my answer I mentioned OEIS sequence A208215 which lists the number of 3xn panel patterns. There is however also A116694 which lists the same for general mxn rectangles. There's some Maple and Mathematica code there as well that calculates it, presumably in a fairly clever way. $\endgroup$ – Jaap Scherphuis May 20 '17 at 12:59
  • 1
    $\begingroup$ @Gallifreyan you're welcome to.. $\endgroup$ – Tom Carpenter May 21 '17 at 10:16
23
$\begingroup$

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ Since the grid is square (n x n) I thought that "divide and conquer" would work well - just multiply by 4. But I see your point. $\endgroup$ – Gallifreyan May 19 '17 at 16:52
  • $\begingroup$ Since you got 300 and David got 322, you might consider reviewing yours and his answer to see which of you have made a mistake :) $\endgroup$ – Shufflepants May 19 '17 at 21:15
  • 2
    $\begingroup$ 1x3 + 1x3 + 1x2 -> 1 (*8) + 1(*4) because the 1x2 can be in the middle row as well $\endgroup$ – Octopus May 19 '17 at 22:12
  • 1
    $\begingroup$ I fixed four mistakes, and now it matches David K's answer. I had overlooked some patterns, such as the one @Octopus found, and the pattern with a 1x1 in the centre surrounded by four dominoes. $\endgroup$ – Jaap Scherphuis May 20 '17 at 1:42
  • 3
    $\begingroup$ This is the closest yet to the general answer. Nice use of matrices too. $\endgroup$ – David K May 20 '17 at 4:15
11
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

While this is a fascinating discussion, the reality is that many of these grids would be unreadable because it's not immediately apparent which panel comes next is a sequence. A vertical panel on the right, with stacks on the left is problematic because the reader doesn't know whether to read to the right or down. Of those shown above, only $175$ of them are functional.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ That seems like a correct observation. How did you make that picture? $\endgroup$ – Gallifreyan Jun 27 '17 at 8:19
  • $\begingroup$ This answer is awesome! However, I disagree with only 175 of them are functional. $\endgroup$ – nilon Jul 24 '17 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.