OFFSET
0,3
LINKS
Math StackExchange, Dividing a square into equal-sized rectangles.
PROG
(Java)
public class Question130758 {
final static int maxn = 23;
static int n;
static int [] divisors = new int [maxn];
static int ndivisors;
static boolean [] [] grid;
static int count;
public static void main (String [] args) {
for (n = 0; n <= maxn; n++) {
ndivisors = 0;
for (int divisor = 1; divisor <= n; divisor++)
if (n % divisor == 0)
divisors [ndivisors++] = divisor;
grid = new boolean [n] [n];
count = 0;
recurse (0, 0, 0);
System.out.print (count + ", ");
}
System.out.println ();
}
static void recurse (int x, int y, int depth) {
if (depth == n) {
count++;
return;
}
while (grid [x] [y])
if (++x == n) {
x = 0;
y++;
}
outer:
for (int k = 0; k < ndivisors; k++) {
int w = divisors [k];
int h = n / w;
if (x + w > n || y + h > n)
continue;
for (int i = 0; i < w; i++)
for (int j = 0; j < h; j++)
if (grid [x + i] [y + j])
continue outer;
for (int i = 0; i < w; i++)
for (int j = 0; j < h; j++)
grid [x + i] [y + j] = true;
recurse (x, y, depth + 1);
for (int i = 0; i < w; i++)
for (int j = 0; j < h; j++)
grid [x + i] [y + j] = false;
}
}
}
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Felix A. Pahl, Apr 12 2012
EXTENSIONS
a(24)-a(31) from Lars Blomberg, Oct 09 2023
STATUS
approved