Cut rectangle in minimum number of squares

Question

I'm trying to solve the following problem:

A rectangular paper sheet of M*N is to be cut down into squares such that:

1. The paper is cut along a line that is parallel to one of the sides of the paper.
2. The paper is cut such that the resultant dimensions are always integers.

The process stops when the paper can't be cut any further.

What is the minimum number of paper pieces cut such that all are squares?

Limits: 1 <= N <= 100 and 1 <= M <= 100.

Example: Let N=1 and M=2, then answer is 2 as the minimum number of squares that can be cut is 2 (the paper is cut horizontally along the smaller side in the middle).

My code:

cin >> n >> m;

int N = min(n,m);
int M = max(n,m);
int ans = 0;

while (N != M) {
    ans++;
    int x = M - N;
    int y = N;
    M = max(x, y);
    N = min(x, y);
}

if (N == M && M != 0)
   ans++;

But I am not getting what's wrong with this approach as it's giving me a wrong answer.

Answer 1

I think both the DP and greedy solutions are not optimal. Here is the counterexample for the DP solution:

Consider the rectangle of size 13 X 11. DP solution gives 8 as the answer. But the optimal solution has only 6 squares.

This thread has many counter examples: https://mathoverflow.net/questions/116382/tiling-a-rectangle-with-the-smallest-number-of-squares

Also, have a look at this for correct solution: http://int-e.eu/~bf3/squares/

Answer 2

I'd write this as a dynamic (recursive) program.

Write a function which tries to split the rectangle at some position. Call the function recursively for both parts. Try all possible splits and take the one with the minimum result.

The base case would be when both sides are equal, i.e. the input is already a square, in which case the result is 1.

function min_squares(m, n):

    // base case:
    if m == n: return 1

    // minimum number of squares if you split vertically:
    min_ver := min { min_squares(m, i) + min_squares(m, n-i)  |  i ∈ [1, n/2] }

    // minimum number of squares if you split horizontally:
    min_hor := min { min_squares(i, n) + min_squares(m-i, n)  |  i ∈ [1, m/2] }

    return min { min_hor, min_ver }

To improve performance, you can cache the recursive results:

function min_squares(m, n):

    // base case:
    if m == n: return 1

    // check if we already cached this
    if cache contains (m, n):
        return cache(m, n)

    // minimum number of squares if you split vertically:
    min_ver := min { min_squares(m, i) + min_squares(m, n-i)  |  i ∈ [1, n/2] }

    // minimum number of squares if you split horizontally:
    min_hor := min { min_squares(i, n) + min_squares(m-i, n)  |  i ∈ [1, m/2] }

    // put in cache and return
    result := min { min_hor, min_ver }
    cache(m, n) := result
    return result

In a concrete C++ implementation, you could use int cache[100][100] for the cache data structure since your input size is limited. Put it as a static local variable, so it will automatically be initialized with zeroes. Then interpret 0 as "not cached" (as it can't be the result of any inputs).

Possible C++ implementation: http://ideone.com/HbiFOH