Pebbling a checkerboard. We are given a checkerboard which has 4 rows and n colu

Question

Pebbling a checkerboard. 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 fine). (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 first 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

Explanation / Answer

The value of a placement is the sum of the integers in the squares that are covered by the pebbles of that placement.

Enumerating, there are 8 possible patterns which can occur in any column:

1. All empty - Empty Pattern

2. 4 patterns which have exactly one pebble (just 1 pebble in column of 4)

3. 3 patterns which have 2 pebbles (alternate placement 1010, 0101, 1001 where 1 denotes pebble)

Now, let us check how these patterns pair up in adjacent columns:

1. Every pattern is compatible with empty pattern (obvious as no constraint is violated)

2. Patterns with 1 pebble are compatible with all paterns which do not have pebble in the same row

3. Patterns with 2 pebbles are compatible with the complementary pattern i.e 0101 and 1010 are compatible. 1001 is not compatible with any 2-pattern but is compatible with 0010, 0100.

With this background, let us implement a dynamic programming solution.

We maintain 8 arrays of n elements for each of the 8 patterns.

To reconstruct the actual pebbling, nd themaximum value c from from cj[n], and pebble the n-th column according to some j such that c = cj[n].

Now, subtract value of pebbled square from c and search for best cj[n-1]. This way, the dynamic programming solution grows.

Proof of Running Time Complexity:

There are 8 arrays. Filling each array takes O(n) time.

Backtracking takes O(1) time (as we backtrack one element at a time)

Hence, O(n) running time

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.