Finding the optimal tiling strategy using squares of different sizes

Question

I have shapes constructed out of 8x8 squares. I need to tile them using the fewest number of squares of size 8x8, 16x16, 32x32 and 64x64. Four 8x8 squares arranged in a square can be replaced by a single 16x16 square, e.g.:

What algorithm can be used to achieve this?

Answer 1

This calls for a dynamic programming solution. I'll assume we have a square[r][c] array of booleans which is true if (r, c) has a 1x1 square (I've simplified the solution to work with 1x1, 2x2, 4x4 and 8x8 squares to make it easier to follow, but it's easy to adapt). Pad it with a wall of false sentinel values on the top row and left column.

Define a 2d count array, where count[r][c] refers to the number of 1x1 squares in the region above and to the left of (r, c). We can add them up using a dp algorithm:

count[0..n][0..m] = 0
for i in 1..n:
  for j in 1..m:
    count[i][j] = count[i-1][j] + count[i][j-1] -
        count[i-1][j-1] + square[i][j]

The above works by adding up two regions we already know the sum of, subtracting the doubly-counted area and adding in the new cell. Using the count array, we can test if a square region is fully covered in 1x1 squares in constant time using a similar method:

// p1 is the top-left coordinate, p2 the bottom-right
function region_count(p1, p2):
  return count[p1.r][p1.c] - count[p1.r][p2.c-1] -
      count[p2.r-1][p1.c] + 2*count[p2.r-1][p2.c-1]

We then create a second 2d min_squares array, where min_squares[r][c] refers to the minimum number of squares required to cover the original 1x1 squares. These values can be calculates using another dp:

min_squares = count
for i in 1..n:
  for j in 1..m:
    for size in [2, 4, 8]:
      if i >= size and j >= size and
          region_count((i-size, j-size), (i, j)) == size*size:
        min_squares[i][j] = min(min_squares[i][j],
            min_squares[i-size-1][j] +
            min_squares[i][j-size-1] -
            min_squares[i-size-1][j-size-1] +
            1)

In order to reconstruct the tiling needed to get the calculated minimum, we use an auxiliary size_used[r][c] array which we use to keep track of the size of square placed at (r, c). From this we can recursively reconstruct the tiling:

function reconstruct(i, j):
  if i < 0 or j < 0:
    return
  place square of size size_used[i][j] at (i-size_used[i][j]+1, j-size_used[i][j]+1)
  reconstruct(i-size_used[i][j], j)
  reconstruct(i, j-size_used[i][j])

Answer 2

You might want to look at Optimal way for partitioning a cell based shape into a minimal amount of rectangles - if I understood correctly, this is the same problem but for rectangles instead of squares.