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?
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])
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.
