Pebbling a Checkerboard with Dynamic Programming

Question

I am trying to teach myself Dynamic Programming, and ran into this problem from MIT.

We are given a checkerboard which has 4 rows and n columns, and has an integer written in each square. We are also given a set of 2n pebbles, and we want to place some or all of these on the checkerboard (each pebble can be placed on exactly one square) so as to maximize the sum of the integers in the squares that are covered by pebbles. There is one constraint: for a placement of pebbles to be legal, no two of them can be on horizontally or vertically adjacent squares (diagonal adjacency is ok).

(a) Determine the number of legal patterns that can occur in any column (in isolation, ignoring the pebbles in adjacent columns) and describe these patterns. Call two patterns compatible if they can be placed on adjacent columns to form a legal placement. Let us consider subproblems consisting of the rst k columns 1 k n. Each subproblem can be assigned a type, which is the pattern occurring in the last column.

(b) Using the notions of compatibility and type, give an O(n)-time dynamic programming algorithm for computing an optimal placement.

Ok, so for part a: There are 8 possible solutions.

For part b, I'm unsure, but this is where I'm headed: SPlit into sub-problems. Assume i in n. 1. Define Cj[i] to be the optimal value by pebbling columns 0,...,i, such that column i has pattern type j. 2. Create 8 separate arrays of n elements for each pattern type.

I am not sure where to go from here. I realize there are solutions to this problem online, but the solutions don't seem very clear to me.

Answer 1

You're on the right track. As you examine each new column, you will end up computing all possible best-scores up to that point.

Let's say you built your compatibility list (a 2D array) and called it L_i[y] such that for each pattern i there are one or more compatible patterns L_i[y].

Now, you examine column j. First, you compute that column's isolated scores for each pattern i. Call it S_j[i]. For each pattern i and compatible pattern x = L_i[y], you need to maximize the total score C_j such that C_j[x] = C_j-1[i] + S_j[x]. This is a simple array test and update (if bigger).

In addition, you store the pebbling pattern that led to each score. When you update C_j[x] (ie you increase its score from its present value) then remember the initial and subsequent patterns that caused the update as P_j[x] = i. That says "pattern x gave the best result, given the preceding pattern i".

When you are all done, just find the pattern i with the best score C_n[i]. You can then backtrack using P_j to recover the pebbling pattern from each column that led to this result.