Skip to content

Instantly share code, notes, and snippets.

@joriki
Created April 12, 2012 07:21
Show Gist options
  • Save joriki/2365404 to your computer and use it in GitHub Desktop.
Save joriki/2365404 to your computer and use it in GitHub Desktop.
Count the number of tilings of an n by n square with n rectangles of integer sides and area n
// Count the number of tilings of an n by n square with n rectangles of integer sides and area n
// See http://math.stackexchange.com/questions/130758
public class Question130758 {
final static int maxn = 100;
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 = 1;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.println (n + " : " + count);
}
}
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;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment