Knuth's program PERFECT-PARTITION-SQUARE

Donald Knuth has a page on his website where he sometimes posts programs he has written. (He says he writes several programs a week, mostly in CWEB and mostly for his own interest, but occasionally posts some of them online.)

A couple of days ago, on 2024-06-01, Knuth posted a program, with the description “An amusing recreation”, that solves the following problem:

Michael Keller suggested a problem that I couldn’t stop thinking about, although it is extremely special and unlikely to be mathematically useful or elegant: “Place seven 7s, . . . , seven 1s into a 7 × 7 square so that the 14 rows and columns exhibit all 14 of the integer partitions of 7 into more than one part.”

The word “exhibit” above needs some explanation. $$ As an illustration, if a row or column contains (say) 6 5 7 4 5 5 6, then, because it contains three $\mathsf{5}$s, two $\mathsf{6}$s and one each of $\mathsf{7}$ and $\mathsf{4}$, it is said to exhibit the integer partition $7=3+2+1+1$. In other words, if we write (as a string / monomial): $$\mathsf{6}\mathsf{5}\mathsf{7}\mathsf{4}\mathsf{5}\mathsf{5}\mathsf{6}={\mathsf{6}}^2{\mathsf{5}}^3{\mathsf{7}}^1{\mathsf{4}}^1$$ then the exponents give the partition $2+3+1+1$ or canonically $3+2+1+1$ (following the convention of writing the parts of a partition in non-increasing order).

Clearly, the contents of any row or column (having $7$ elements) will exhibit some integer partition of $7$, depending on which elements happen to be equal to which others (for example, if all elements are distinct, it will exhibit the partition $1+1+1+1+1+1+1$). There are $15$ partitions of $7$, and the problem asks to never exhibit the partition $7$ (i.e. never have all elements identical in any row or column), and exhibit all the other $14$ partitions exactly once each.

Note that although, for any $n$, we can always arrange $n$ $\mathsf{1}$s, $n$ $2$s, …, $n$ $n$s in an $n\times n$ square, the number of partitions exhibited by the rows and columns ($2n$) can be equal to the number of partitions into more than one part ($p(n)-1$) only for $n=7$:

and so on: $p(n)$, the number of partitions of n, grows super-polynomially, roughly exponential in $2.6\sqrt{n}$, and so $p(n)-1$ is too small for $n<7$ and too big for $n>7$. This is part of what Knuth means by “extremely special and unlikely to be mathematically useful or elegant”.

(Aside: However, for $n=4$, we can ask for a similar (simpler) constraint: “the 4 rows exhibit all 4 of the integer partitions of 4 into more than one part, and so do the 4 columns”. For this problem, it is easy to manually find solutions like:

The problem with $n=7$ is harder as we cannot work on the rows and columns independently; I’d be surprised if anyone arrived at a solution by hand. End of aside.)

Anyway, for the $n=7$ problem, Knuth writes a program that starts with (after the problem statement quoted above):

I doubt if there’s a solution. But if there is, I guess I want to know. So I’m writing this as fast as I can, using brute force for simplicity wherever possible (and basically throwing efficiency out the door).

Try this as an exercise yourself, and see how far you get, before reading Knuth’s program. You may discover that when Knuth says “brute force for simplicity” and “throwing efficiency out the door”, he still doesn’t quite mean what you or I might mean by it. :-)

For instance, the number of ways of arranging the numbers in the $7\times 7$ square is $(49!)/(7!{)}^7>7.36\times {10}^{36}$, so “brute force” cannot simply mean trying them all. As a teaser, Knuth’s program contains this macro, and it may be fun to puzzle out what it does:

#define gosper(b) { register x=b,y; \
                x=b&-b,y=b+x; \
                b=y+(((y^b)/x)>>2); }

(Spoiler: I was impressed to find that ChatGPT could work this out/reproduce it from its training data, even with the PDF copy-paste that has a control character instead of the right shift. Edit after playing with it a bit more: it’s not very good at follow-up questions and variations, so I guess this is another instance where the model’s wider initial knowledge can fool one into thinking it is more capable than it is.)

His program, compiled at -O3, runs in about 6–8 minutes on my laptop (2023 M2 Pro / 2021 M1 Pro), and finds 30885 solutions, which are already distinct under symmetries like permuting rows, permuting columns, transposing (changing rows to columns and vice-versa), and permuting the digits themselves (swapping all $\mathsf{3}$s and $\mathsf{5}$s, for example).

For example, here is the 24200th solution:

and you can see that the rows and columns cover all $14$ partitions of $7$ into more than one part.

To compile his program I had to change a couple of register declarations to register int, which reminded me of this tweet from Per Vognsen:

People who quote Knuth on premature optimization must not have seen his code. He's that dude who puts 'register' on variables in 2020 and implements a bespoke trie for simple one-off string processing programs.

— Per Vognsen (@pervognsen) April 21, 2020

and:

He's so much a "premature" optimization proponent that he's still putting 'register' on variables in C after compilers stopped paying attention to them 30 years ago. It's basically him just throwing up gang signs.

— Per Vognsen (@pervognsen) April 21, 2020

Note also that section 5 in the program is basically a copy-paste of section 4, with rows changed to columns. Similarly two code blocks inside section 6, and inside section 7 (and I wonder if some code could have been reused between 6 and 7?). There are “magic numbers” like 24 and 4 (besides of course 7) everywhere. And of course he uses goto a couple of times (to break out of an inner loop). None of this matters — the program correctly does what is intended, is the way he is comfortable programming and works for him, and after reading it carefully (and picking up at least a couple of tricks for the future), I’m only left wondering what the “efficient” version would look like.

Sources:

• .w file on Knuth’s website
• typeset (PDF) version (The .w file run through cweave and then through pdftex) (See this repo for other programs from his website.)
• .c file (The .w file run through ctangle after replacing a couple of register with register int, and void main with int main.)