## The 892 unique ways to partition a 3 x 4 grid

Mar 4, 2011

Designed by Thomas Gaskin. Creative direction by Hugh Dubberly. Algorithms by Patrick Kessler. Patent belongs to William Drenttel + Jessica Helfand.

This poster illustrates a change in design practice. Computation-based design—that is, the use of algorithms to compute options—is becoming more practical and more common. Design tools are becoming more computation-based; designers are working more closely with programmers; and designers are taking up programming.

Above, you see the 892 unique ways to partition a 3 × 4 grid into unit rectangles. For many years, designers have used grids to unify diverse sets of content in books, magazines, screens, and other environments. The 3 × 4 grid is a common example. Yet even in this simple case, generating all the options has—until now—been almost impossible.

Patch Kessler designed algorithms to generate all the possible variations, identify unique ones, and sort them—not only for 3 × 4 grids but also for any n × m grid. He instantiated the algorithms in a MATLAB program, which output PDFs, which Thomas Gaskin imported into Adobe Illustrator to design the poster.

Rules for generating variations
The rule system that generated the variations in the poster was suggested by Bill Drenttel and Jessica Helfand who noted its relationship to the tatami mat system used in Japanese buildings for 1300 years or more. In 2006, Drenttel and Helfand obtained U.S. Patent 7124360 on this grid system—“Method and system for computer screen layout based on recombinant geometric modular structure”.

The tatami system uses 1 × 2 rectangles. Within a 3 × 4 grid, 1 × 2 rectangles can be arranged in 5 ways. They appear at the end of section 6.

Unit rectangles (1 × 1, 1 × 2, 1 × 3, 1 × 4; 2 × 2, 2 × 3, 2 × 4; 3 × 3, 3 × 4) can be arranged in a 3 × 4 grid in 3,164 ways. Many are almost the same—mirrored or rotated versions of the same configuration. The poster includes only unique variations—one version from each mirror or rotation group. Colors indicate the type and number of related non-unique variations. The variations shown in black have 3 related versions; blue, green, and orange have 1 related version; and magenta variations are unique, because mirroring and rotating yields the original, thus no other versions. (See the table to the lower right of the poster for examples.)

Rules for sorting
The poster groups variations according to the number of non-overlapping rectangles. The large figures indicate the beginning of each group. The sequence begins in the upper left and proceeds from left to right and top to bottom. Each group is further divided into sub-groups sharing the same set of elements. The sub-groups are arranged according to the size of their largest element from largest to smallest. Squares precede rectangles of the same area; horizontals precede verticals of the same dimensions. Within sub-groups, variations are arranged according to the position of the largest element, preceding from left to right and top to bottom. Variations themselves are oriented so that the largest rectangle is in the top left. Black dots separate groups by size. Gray dots separate groups by orientation.

Grids have been described in design literature for at least 50 years. French architect Le Corbusier describes grid systems in his 1946 book, Le Modulor. Swiss graphic designer Karl Gerstner describes a number of grid systems or “programmes” in his 1964 book, Designing Programmes. The classic work on grids for graphic designers is Josef Muller-Brockman’s 1981 book, Grid Systems.

Patch Kessler explores the mathematical underpinnings of grid generation in his paper “Arranging Rectangles”.

Thomas Gaskin and Sean Durham have created an interactive tool for viewing variations and generating HTML.

• ##### Ale Muñoz

Mar 4, 2011
3:48 pm

This is lovely, in a “math is beauty” way. I am so hanging it in my walls 🙂

• ##### chris

Mar 6, 2011
2:02 pm

Wow! Really nice.

• ##### Haig Bedrossian

Mar 6, 2011
2:04 pm

Computational design is great. But why do you feel the need to Patent this? Do you want to Patent geometry? That seems absurd.

• ##### Bobby

Mar 6, 2011
3:14 pm

I love how they used baby pastel colours to colour code certain things. Hey, some people just don’t get the computational thing, k? (ie me)

Mar 6, 2011
5:07 pm

<3

• ##### dhaval shah

Mar 7, 2011
11:00 am

Excellent, this is really fantastic. this is really what we need.

Thanks!

• ##### Daniel Rehn

Mar 8, 2011
1:01 am

A concise, clean reminder to design with consideration.

• ##### aaron

Mar 8, 2011
3:02 pm

what about L shapes?

• ##### marc

Mar 9, 2011
4:09 am

So ? Patent mathematics know since longtime … absurde

• ##### Rachel Ann Smit

Mar 9, 2011
7:16 am

Beautiful! Thank you for this amazing graphic! It’s such an elegant way of demonstrating the near-endless possibilities of design.

Thank you!

• ##### Bammer

Mar 13, 2011
3:26 am

I was confused at first because so many partitions are not on the poster. I see that this poster has culled horizontal and vertical symmetries, but the entry is titled “the 892 unique ways to partition a 3×4 grid.” Given this, I think a poster with all 3,164 partitions would have been (counter intuitively) more elegant. Or if the poster had just been titled “892 unique ways to partition a 3×4 grid.”

Looks cool thoughs.

• ##### Robert

Mar 16, 2011
5:02 pm

A patent for this ??? On april 1st perhaps.

Mar 16, 2011
11:23 pm

Amazing example.

Thanks for sharing

• ##### Miklo

Mar 18, 2011
12:31 pm

Aside from the obvious ridiculousness of the patent, I remember reading about the tatami grid system in John Cato’s excellent 2001 book ‘User-Centred Design’.

• ##### Stan Warford

Mar 31, 2011
11:43 am

For a good theoretical treatment about the absurdity of the patent system, see

http://mises.org/resources/3582/Against-Intellectual-Property

• ##### Johnnie Walker

Apr 2, 2011
4:08 am

I really like this! I was about to send it for print, but I notice a couple of things which could be corrected. Most apparently, the large type could be Helvetica. Secondly, the unit rectangle groups shouldn’t have apostrophes (1 x 1’s, 3 × 4’s etc).

Is it too much to ask for the AI source?

• ##### Bob

Apr 4, 2011
10:42 pm

“Yet even in this simple case, generating all the options has—until now—been almost impossible.”

Really? It was not possible for someone to sit down and draw these out? Baloney.

• ##### Andrew

Apr 5, 2011
7:57 pm

In my 10th grade Computer Science class (1993), we wrote a partitioning algorithm very similar to this as an assignment. I do find this article interesting, but to suggest that such a feat has not been possible until this new fancy computer algorithm was invented is just not true.

• ##### joanne mendel

Apr 13, 2011
11:53 am

This is like putting an exploration by Josef Muller-Brockmann on steroids:-)

I recall a visual thinking exercise one summer in Brissago that involved moving typographic elements around by hand as a way to discover, reflect upon and internalize relationships between the elements.

Tools today for doing research analysis & synthesis have little more fidelity…which to your point is a problem when revealing patterns and exploring relationships within volumes of data that one encounters in problem solving.

And yet designing tools for design research is a time consuming and expensive proposition for many firms. Would love any pointers to examples you deem noteworthy.

• ##### Michael

Apr 17, 2011
6:23 pm

Love it, but the title is misleading You haven’t got all the unique variations: the algorithm has limited itself to rectangles and there are no tetris type tetradominos in there 😉

• ##### Timothy

Apr 21, 2011
6:29 am

Just spotted this over at the Design Observer. Not really focusing on the mathematics or the patent issue it’s a very interesting idea. Well done.

• ##### Donald Ansley

Apr 21, 2011
12:33 pm

892 bento boxes 🙂

• ##### Oliver

Apr 23, 2011
1:20 am

Great work. Boring. Think. Outside. The box.

• ##### Jackie

Apr 25, 2011
7:55 pm

This is great! So thankful there are generous mathematicians. I’d be completely lost in numbers.

• ##### Charles

Apr 29, 2011
11:33 pm

this is awesome! thanks!

• ##### Trish

Oct 4, 2011
9:41 pm

Makes me think of Chuck Close, Frank Lloyd Wright & those who compose music using math.

Oct 6, 2011
8:41 pm

thanks!

• ##### Trisha

Jan 8, 2012
2:49 am

Isn’t that a 4×3 grid? (width:height, 4:3, 16:9, 1024×768, 320×480, etc)

• ##### Ryan

Jan 25, 2012
9:13 am

It’s interesting. Being a programmer and designer i find thinking so structurally really stifles my designs. Even, if i am to illustrate a comic i have to draw my frames without borders then piece together.

• ##### Mick

May 25, 2012
2:36 am

Nice work, thanks!

• ##### John Haugeland

May 25, 2012
7:11 am

Why would this sort of trivial thing be almost impossible without computers? Ancient mathematicians and geometers did radically more complicated things than this on a fairly regular basis.

Any rectilinear gridded partitioning is a simple binary number. Make any normative numbering of the wall pieces – left to right, top to bottom seems natural to me, since it’s the reading order of my native natural language – then write a zero if it’s open, and a one if it’s closed.

Now count from 0 to ((2^wallcount) -1). Pow: that’s every single grid.

I don’t know if ASCII art will work here, but

+-+-+-+ | | | | +-+-+-+ | | | | +-+-+-+

becomes

+-+-+-+ | 1 2 | +3+4+5+ | 6 7 | +-+-+-+

Which is suddenly the seven flag range [0 .. (2^7)-1], meaning there are 128 possible grids. (Possible, not legal.)

So, let’s see. 0 is the empty grid. 127, the top grid, is every cell partitioned. Why? Well, 0 in binary is 000 0000b, which is all those flags being off, or the walls being missing. 127 in binary is 111 1111b, or all those walls being turned on.

Actually writing out those 128 grids is a 15 minute process. It’s trivial. You just type 0 into a calculator that does binary, hit equals; draw that grid. Hit plus one, hit equals; draw that grid. Hit equals; draw that grid. Hit equals; draw that grid. Et cetera. (You can count in binary on an abacus, or in your head; I’m just underscoring how simple this is.) Each grid takes 5-10 seconds.

Next you get like a bingo marker or something? Something that’s meant to leave big color blots. And you blot all the bad grids.

For example, grid 86, in binary, is 101 0110b. I’m not really sure, because they didn’t write their rules out, but that creates a C shape, and I think that’s probably against their rules. That’s, as you can see, walls 2, 4, and 6 turned off. When you render that, it looks like

+-+-+-+ | | | +-+ +-+ | | | +-+-+-+

But, can’t find these without a computer?

Please. Try it. It’s school-child level easy.

This sort of thing was well known to mathematicians in ancient Greece, Persia, et cetera. This is how Al Kwarizmi solved the Towers of Canan, which is roughly equivalent to what we now call The Bridges of Konigsberg. Granted they’re bridges instead of walls, and the cells aren’t square, but not only is it the exact same problem, but Canan/Konigsberg show a far more sophisticated and robust result about node entry and exit on the odd/even count for bridge nodes within a network.

And here you are saying “You couldn’t even make this list without computers.”

The hell you couldn’t. You could do it in three hours with a piece of graph paper. It’s easy.

Stop telling people things aren’t possible without computers. Sometimes hard problems need those skills even when you do have computers. People are liable to believe you. 🙁

It is really important that you go read about George B. Dantzig. That sort of thing happens a lot, and you’re fighting it the wrong way, here.

• ##### Mustafa

Aug 3, 2012
1:37 am

woow thanks guy

• ##### Ben

Apr 26, 2015
4:35 am

this is a very trivial mathematical task. Turning it into a nicely layouted poster doesn’t rise its scientific impact. Boring

• ##### Pablo T

Jun 23, 2015
2:15 am

Would love to get that poster size slidedocs praises. Cheers

Mar 24, 2016
12:46 pm

very kool.