Mondrian Puzzle Sequence

Question

Partition an n X n square into multiple non-congruent integer-sided rectangles. a(n) is the least possible difference between the largest and smallest area.

 ___________
| |S|_______|
| | |   L   |
| |_|_______|
| |     |   |
| |_____|___|
|_|_________| (fig. I)

The largest rectangle (L) has an area of 2 * 4 = 8, and the smallest rectangle (S) has an area of 1 * 3 = 3. Therefore, the difference is 8 - 3 = 5.

Given an integer n>2, output the least possible difference.

All known values of the sequence at the time of posting:

2, 4, 4, 5, 5, 6, 6, 8, 6, 7, 8, 6, 8, 8, 8, 8, 8, 9, 9, 9, 8, 9, 10, 9, 10, 9, 9, 11, 11, 10, 12, 12, 11, 12, 11, 10, 11, 12, 13, 12, 12, 12

So a(3)=2, a(4)=4, ...

OEIS A276523

Related - this related challenge allows non-optimal solutions, has time constraints, and is not code-golf.

For more information, watch this video by Numberphile

Answer 1

CJam, 178

ri_1a*a*L{_:+1&{_[3{_\zW%}*]{_z}%:e<_@={:A0=_1#:X0<{;A1>j}{X>0+0#AzX=0+0#,\,m*1ff+{[_$\~1a*0aX*\+a*A\..-_])s'-&{;}&}%{~j\:X;{Xa&!},Xaf+:$~}%_&}?}{j}?}{;La}?}j{,(},{::*$)\0=-}%:e<

Try it online. It's veeery slow though, I wouldn't recommend going above 6.

To verify that it's really doing the work, you can check this slightly modified program that prints all the possible partitions (each partition is shown as an array of rectangle dimension pairs).

Answer 2

Befunge, 708 bytes

p&>:10p1-:>20p10g:20g\`v`\g02:-1\p00+1g<>g-#v_10g:*30p"~":40p50p060p070p$>^
1#+\#1<\1_^# !`0::-1$  _:00g3p\:00g2p00^^00:>#:


>>:2-#v_$30p50p60p70g1-70p
^<<<<<:#<<<<<<$$$_v#:!g87g78g79$  _v#!\-1:g88$<_ 98p87g97g*00 v:+!\`*84g++7<
^>$1-:77p1g:2g\3g1>78p97p87p10g97g->88p10g87g-0^!\-1:g89_v#-!\_$1-:v>/88g+7^
^|!-3$<   >\87g/88g+77++p:#v_$
^>:5->v   ^+g89%g78:\g77:-1<>98g88g48*577g387g97g98g88v ^>77g87g97v:^g78\+g<
^ v-4:_$77p88p98p:97p\:87p*^^g79g7>#8\#$_40pv5+"A"g77g< ^14g88g89g<>:87g%98^
^v_$88p98p97p87p:77p60g50g-:40g\`#^_$$>>>>>>>
 >#4!_::80p2g\3g*:90p30g`!v>>>#@>#.>#g^#0
^v:g06p03:-g09\2:g03g05g06_^^_7#<0#<g#<3#<1#<<`g04_$00g1->:#-8#10#\g#1`#:_>$
^>90g\-:0`*+:60p50g:90g-:0`*-:50p-80g70g:1+70p1p\!^

Try it online!

This is obviously not going to win any awards for size, but it's actually reasonably fast considering it's a basic bruce force implementation in an esoteric language. On the Befunge reference interpreter it can handle up to n=6 in a couple of seconds. With a compiler it can handle up to n=8 before it starts getting sluggish; n=9 takes a couple of minutes and n=10 is close on 2 hours.

In theory the upper limit is n=11 before we run out of memory (i.e. there's not enough space left in the playfield to fit a larger square). However, at that point, the time taken to calculate the optimal solution is probably longer than anyone would be willing to wait, even when compiled.

The best way to see how the algorithm works is by running it in one of the Befunge "visual debuggers". That way you can watch as it attempts to fit the various rectangle sizes into the available space. If you want to "fast forward" to the point where it has a good match, you can put a breakpoint on the 4 in the sequence $_40p near the middle of the tenth line (9 if zero-based). The value at the top of the stack at that point is the current area difference.

Below is an animation showing the first few frames of this process for n=5:

Each distinct rectangle is represented by a different letter of the alphabet. However, note that the final rectangle is never written out, so that section of the square will just be blank.

I've also written a debug version of the code that outputs the current layout each time it finds a new best match (Try it online!). For the smaller sizes, the first match is often the optimal solution, but once you get past n=6 you'll likely get to see several valid but non-optimal layouts before it settles on the final solution.

The best layout found for n=10 looks like this:

H F F F A A A C C I
H F F F A A A C C I
H J G G A A A C C I
H J G G A A A C C I
H J D D D D D C C I
H J D D D D D C C I
H J K K K K K K K I
H J B B B E E E E I
H J B B B E E E E I
H J B B B L L L L L

12 - 4 = 8