logical deduction - Dissect a square into 3:2 non-congruent integer-sided rectangles

(Similar to the recent 3:1 rectangle question)

Tile a square completely with rectangles which have aspect ratio 3:2, integral side lengths and all different sizes. In other words selected from 2x3, 4x6, 6x9 etc. Usual tiling rules apply: No gaps, no overlaps.

1. Find the smallest area tiling.


2. Find the tiling with with the fewest rectangles.

I have no way of proving that my answer to (1) is an answer to (2), so you could supply that proof in lieu of a tiling with fewer rectangles. Without such a proof, (2) is open ended - you could conceivably have a square one million units on a side tiled with just a handful of rectangles.

I've tagged this computer-puzzle, but I would not be surprised if it could be found by hand with a healthy dose of logic. So I also tagged it logical-deduction, but I would guess part (1) is easier with computer for most people. Part (2) requires a logical proof in order to not be open ended.

I found this by computer, a brief Google search didn't turn up any existing work in the area but it could still be a known problem.

Answer

My primitive and awfully slow program found this solution for part 1 of the question:

Size: 120; Rectangles: 10

The code:

package puzzle;

import java.util.ArrayDeque;

import java.util.BitSet;
import java.util.Deque;

public class Dissector {
    private static class Rectangle {
        public final int width;
        public final int height;
        public final int x;
        public final int y;


        public Rectangle(int width, int height, int x, int y) {
            super();
            this.width = width;
            this.height = height;
            this.x = x;
            this.y = y;
        }

        public boolean overlap(int width, int height, int x, int y) {
            return this.x < x + width && x < this.x + this.width  &&

                    this.y < y + height && y < this.y + this.height;
        }

        @Override
        public String toString() {
            return width + "x" + height + "+" + x + "+" + y;
        }
    }

    private final int width;

    private final int height;
    private final int factorWidth;
    private final int factorHeight;

    private int areaLeft;
    private final BitSet notPlaced = new BitSet();
    private final Deque placed = new ArrayDeque<>();

    public Dissector(int width, int height, int factorWidth, int factorHeight) {
        this.width = width;

        this.height = height;
        this.factorWidth = factorWidth;
        this.factorHeight = factorHeight;
        this.areaLeft = width * height;
        for (int i = Math.max(width, height) / Math.max(factorWidth, factorHeight); i > 0; -- i) {
            notPlaced.set(i);
        }
    }

    private boolean place(int recId, boolean rotated, int x, int y) {

        int recWidth = (rotated ? factorHeight : factorWidth) * recId;
        int recHeight = (rotated ? factorWidth : factorHeight) * recId;
        if (x + recWidth > width || y + recHeight > height) {
            return false;
        }
        for (Rectangle r : placed) {
            if (r.overlap(recWidth, recHeight, x, y)) {
                return false;
            }
        }

        placed.addFirst(new Rectangle(recWidth, recHeight, x, y));
        return true;
    }

    public void dissect(int startX, int startY) {
        if (areaLeft == 0) {
            System.out.println(placed);
        } else {
            int x = startX;
            int y = startY;

            boolean moved = true;
            while (moved && y < height) {
                moved = false;
                for (Rectangle r : placed) {
                    if (x >= r.x && x < r.x + r.width && y >= r.y && y < r.y + r.height) {
                        x = r.x + r.width;
                        if (x >= width) {
                            x = 0;
                            ++ y;
                        }

                        moved = true;
                        break;
                    }
                }
            }

            if (y < height) {
                int recId = notPlaced.length();
                while ((recId = notPlaced.previousSetBit(recId - 1)) > 0) {
                    notPlaced.clear(recId);

                    areaLeft -= recId * recId * factorWidth * factorHeight;
                    if (areaLeft >= 0) {
                        if (place(recId, false, x, y)) {
                            dissect(x, y);
                            placed.removeFirst();
                        }
                        if ((x > 0 || y > 0) && place(recId, true, x, y)) {
                            dissect(x, y);
                            placed.removeFirst();
                        }

                    }
                    notPlaced.set(recId);
                    areaLeft += recId * recId * factorWidth * factorHeight;
                }
            }
        }
    }

    public static void main(String[] args) {
        for (int size = 6; size < 200; size += 6) {

            System.out.println("size: " + size);
            Dissector splitter = new Dissector(size, size, 3, 2);
            splitter.dissect(0, 0);
        }
    }
}