[Solved] Minimum number of squares required to cover a rectangular grid of size n by m

by


W.l.o.g. we say n>=m and choose m to be of the form 2^x. (If m is arbitrary <= n as well it only means that we apply the same approach to a second rectangle that is n times m-2^x in size, where x=int_floor(ld(m)) and ld is log to the base of 2 of course.)

The following snippet should compute the number of squares needed. 

countSquares(m,n,x) :
  if n == 0 : return 0
  if n == 1 : return m
  if n/2^x >= 1 : 
    return m/2^x + countSquares(m,n-2^x,x-1)
  else
    countSquares(m,n,x-1)

The return in the 3rd if: m/2^x is always a natural number as m is of the form 2^x in the beginning and any 2^(x-(x-i)) remains a natural number.

If we are only interested in a lower bound. I would assume choosing a rectangle of size a times b, where a:=2^x – 1, and b:=2^y -1 should result in roughly ld(a) times ld(b) number of squares.

Extending the code snippet to an arbitrary m seems to involve a second recursion:

partitionAndCount(n,m) :
  if n < m : swap(n,m)

  var x = floor(ld(m))
  var mRes = m - 2^x

  if mRes == 0 : return countSquares(2^x,n,x-1)
  if mRes == 1 : n + return countSquares(2^x,n,x-1)
  return partitionAndCount(n,mRes) + countSquares(2^x,n,x-1)

solved Minimum number of squares required to cover a rectangular grid of size n by m