In 1976, Robert Cass Keller proposed a puzzle in Word Ways that was inspired by Benjamin Franklin’s quote “We must all hang together, or assuredly we shall all hang separately”. The puzzle asks you to fit the first 33 distinct surnames of American Presidents into a rectangle of minimum area using the following rules:

Names can only be placed left-to-right or top-to-bottom
Letters in adjacent cells must belong to a common name
Every name must be connected by some path of intersecting names to every other name (“We must all hang together…”)

Keller mentions a similar contest in a British magazine involving the 50 U.S. states. The winner apparently fit them all into a 23-by-29 rectangle.

In the next issue, Sam Harlan presented the first solution to Keller’s puzzle, a 17-by-31 rectangle with total area 527:

1976 was an election year, which meant the set of presidential surnames was about to increase by one. Harlan mentioned that Jimmy Carter (the eventual winner) could easily be packed into the existing solution using the first “e” in Pierce.

In 1993, shortly after Bill Clinton’s election, Darryl Francis produced a new rectangle that was smaller than Harlan’s solution by two columns (17-by-29, for a total area of 493) and included the entire current set of 37 presidential surnames including Carter, Reagan, Bush, and Clinton:

In next issue of Word Ways, Lee Sallows presented a 19-by-22 grid containing the same set of 37 surnames. The resulting area (418) was a massive reduction from previous attempts, but his grid contained an isolated Ford-Polk-Jackson component. Sallows noted that some “purists” might therefore disqualify his rectangle.

Such a purist showed up in the very next issue, when Leonard Gordon presented a completely connected 19-by-22 grid as well as the following new record-setting 17-by-24 grid with area 408:

Gordon published an update a year later, presenting a tighter 18-by-22 solution with an area of 396:

Gordon’s rectangle above from 1994 is the last communication I can find on the Presidential Rectangle for a while, even though thanks to the election of George W. Bush in 2000, the set of presidential surnames didn’t change again until 2008.

The Presidential Rectangle shows up as an exercise in Don Knuth’s Art of Computer Programming Vol. 4, Fascicle 5, although the exercise asks for a square rather than a rectangle, and the exercise asks for the first 38 surnames up to and including Obama.

The 20-by-20 solution (area: 400) is credited to Gary McDonald from 2017:

McDonald’s solution contains some elements from Gordon’s earlier patterns, including an updated 4-way intersection including Coolidge and Nixon. But I think the dense Roosevelt-Adams-Harding-Obama-Cleveland-Jefferson block is really the centerpiece of the packing.

Knuth mentions that a 19-by-19 solution is surely impossible, and after many attempts over the past few weeks, I am also doubtful that a 19-by-19 packing exists. I was, however, able to pack all of the first 38 surnames up to Obama in a 19-by-21 grid, which beats McDonald’s 20-by-20 solution by exactly 1 when scoring by total area.

Here’s my 19-by-21:

I was also able to construct a similar 21-by-21 packing of all 40 presidential surnames as of 2021, including Trump and Biden:

Word Ways has suspended publication as of a year ago, otherwise I’d continue the tradition by posting these constructions there. In the rest of this post, I’ll explain how I found these new rectangles and share some tools that you can use to construct similar word rectangles.

SAT Encoding

You can frame the Presidential Rectangle problem as a set cover problem and use solvers based on the Dancing Links technique to identify solutions but the connectedness property is difficult to specify in that setting. Knuth describes a way to modify a solver to only discover connected solutions instead of filtering out disconnected solutions as a post-processing step. But SAT solvers are usually much more efficient at finding a solution with multiple constraints like this, and I like playing around with complicated SAT encodings, so I wanted to give that approach a go.

My encoding creates a boolean variable C_(ch,r,c) for every possible character ch and row r, column c pair in the rectangle. These variables represent “the cell at (r, c) in the rectangle contains character ch”. I also add clauses that restrict at most one C_(ch,r,c) to be true for any (r, c) pair.

Now I can go through all surnames that I want to pack in the rectangle and create variables PH_(x,r,c) representing “surname x is placed horizontally starting at (r,c)” and PV_(x,r,c) respresenting “x is placed vertically starting at (r,c)”. I create clauses connecting the PH_(x,r,c) and PV_(x,r,c) to the C_(ch,r,c) in the natural way, spelling out the exact placements of characters in surname x into cells in the rectangle if PH_(x,r,c) or PV_(x,r,c) is true. Finally, I add clauses that ensure that exactly one PH_(x,r,c) or PV_(x,r,c) is true for any surname x.

At this point, any satisfying assignment of the variables must pack all of the surnames into the rectangle and ensure that each cell in the rectangle is assigned at most one distinct character. But recall the rules we started with:

Names can only be placed left-to-right or top-to-bottom
Letters in adjacent cells must belong to a common name
Every name must be connected by some path of intersecting names to every other name

Without additional contraints, we could still violate rule 2 above by placing surnames too close together in the rectangle.

To encode the spacing constraints of rule 2, I introduced three more families of variables:

S_(r,c): “spacer” variables.
H_(r,c): “horizontal cell” marker variables.
V_(r,c): “vertical cell” marker variables.

When a PH_(x,r,c) or PV_(x,r,c) is set, we set spacer variables in the two cells before and after the placement of the surname. There may be no cell that comes before or after a surname if it’s placed on the border of the rectangle, and that’s fine, we just omit spacers when that happens. We also set H_(r,c) on all cells covered by the characters in a surname when PH_(x,r,c) is set and V_(r,c) on all cells covered by the characters in a surname when PV_(x,r,c) is set.

With that setup, we add some more clauses to guarantee that:

A spacer and a horizontal cell never co-occur
A spacer and a vertical cell never co-occur
Two horizontal cells can’t be vertically adjacent unless both are also vertical cells
Two vertical cells can’t be horizontally adjacent unless both are also horizontal cells.

At this point, there are already a lot of variables involved, so here’s an example that might help make sense of the encoding so far: If POLK is placed horizontally in the cells (1,1), (1,2), (1,3), (1,4), then PH_(POLK,1,1) is set and no other PH_(POLK,r,c) or PV_(POLK,r,c) can be set. This also means that C_(P,1,1), C_(O,1,2), C_(L,1,3), and C_(K,1,4) get set and no other C_(ch,1,1), C_(ch,1,2), C_(ch,1,3), or C_(ch,1,4) can be set. Also, S_(1,0) and S_(1,5) get set, which keeps any other surnames from using those cells. And H_(1,1), H_(1,2), H_(1,3), and H_(1,4) get set, which keeps horizontal surnames from occurring adjacent to POLK in row 0 or row 2 unless the cells are also vertical cells (to see why we make this exception, look at, for example, the Reagan-Carter-Nixon-Coolidge intersection in Gary McDonald’s solution above).

So we’ve encoded rules 1 and 2, and we’re left with rule 3: “Every name must be connected by some path of intersecting names to every other name”. This is a little tedious but we can do it. Define variables R_(x,y,i) for every pair of surnames x and y and each i from 0 to N-2, where N is the total number of surnames. R_(x,y,i) is true exactly when x is reachable from y through a path consisting of exactly i intermediate surnames. You can define it inductively as follows:

R_(x,y,0) is true if any of the placements of x and y that intersect are selected, or false if there are no such placements.
R_(x,y,i) for i > 0 is true if there’s some z such that R_(x,z,0) and R_(z,y,i-1) are both true.

Finally, we generate a set of variables R_(x,y) for each pair of surnames x, y and define each as the disjunction of R_(x,y,i) for i from 0 to N-2, so that R_(x,y) is true exactly when there’s a path of any length from x to y. Then we add unit clauses for each R_(x,y) to the encoding to ensure everything is connected to everything else.

Now we can just run a SAT solver on the formula. If it returns a satisfying assignment, we can extract the assignments of the PH_(x,r,c) and PV_(x,r,c) for each surname x to reconstruct the solution.

Assisted solutions

Unfortunately, the Presidential Rectangle is a bit too difficult even for modern SAT solvers. You can, for example, find a packing of a dozen or so surnames in, say, a 12-by-12 square or prove that no such packing exists for an 11-by-11 square in a few minutes. But packing even the first 38 presidential surnames into a 20-by-20 rectangle or proving a 19-by-19 packing seems beyond the reach of today’s technology: I ran multiple state-of-the-art solvers for a week each on problems like these with no results.

Since I care more about finding packings than proving they don’t exist, I started to look for ways to make the problem easier by targeting packings with additional constraints instead of solving the general problem.

Along these lines, I played around with:

Forces: Some of the advances in the Presidential Rectangle came from re-using partial packings that were successful in earlier attempts (Lee Sallows re-used Darryl Francis’s Van Buren-Harding-Grant-Buchanan loop and Leonard Gordon’s solutions share many common constructs, for example). It makes sense that you might want to force absolute positions for some of the surnames and let the solver figure out the rest.
Relative Forces: Similar to forces, these allow you to specify relative positions instead of absolute posititions in the form of constraints that say things like “I’d like Harding and Harrison to intersect in their first ‘H’”.
Partial Packings: Allow the solver to pack a subset of a particular size into a sub-rectangle. Partial packings are easy for the solver to figure out, and they could be used incrementally with forces to figure out a full packing.
Minimizing Blank Cells: A constraint that guarantees at most N blank cells in a packing helps create denser partial packings. Without adding something like this, if you ask a solver for a partial packing of any 10 surnames into a 10-by-10 grid you’re likely to just get the 10 shortest names.

I had some promising partial successes with each of these techniques. But the only thing that really worked for me (and what gave me the 19-by-21 and 21-by-21 rectangles above) was to hand-pack some of the trickier surnames and use those as absolute forces, letting the solver figure out the rest. Both of my solutions above share the same lower half which I hand-crafted and then fed into the solver with forces. That lower half helped the solver find both solutions in just a few hours each.

Tools

I’ve put the tools I used to generate the rectangles above up at github.com/aaw/presidential-rectangle. They support all of the advanced features for assisted solutions described in the previous section. Have fun creating your own rectangles!