CS 441/539 Sample Solution Write-up for Homework 2

Practice Problem 1

You are given a 4-row by n-column checkerboard with an integer printed on each square of the checkerboard. You are also given an unlimited number of pebbles where each pebble can be placed on exactly one square of the checkerboard.

A legal placement of pebbles is one in which no two pebbles are placed on horizontally or vertically adjacent squares. (Diagonal adjacencies are OK.) The value of the placement is the sum of the integers corresponding to the squares that are covered by pebbles of that placement. Give the most efficient algorithm you can for computing a placement of maximum value.

Hint: You may use the fact that the number of legal patterns of pebbles that can occur in any one column is eight. You may also talk about two columns being consistent if they do not have pebbles in the same row.

Solution for Practice Problem 1

There are 8 possible patterns for a column: no pebbles, 1 pebble (4 of these for each row), 2 pebbles (rows 1,3; rows 1;4; and rows 2;4). Let's assume that we arbitrarily refer to these as patterns 1,...,8. Let m[i,j] be the value for an optimal layout of the first i columns under the condition that column i ends in pattern j where 0 <= i <= n (where i=0 is the empty board) and 1 <= j <= 8.

The recursive solution is given by:

m[i,j] = 0 if i = 0

and otherwise,

 m[i,j] =      max over         m[i-1,j'] + value for column i using pattern j
         j' consistent with j
The final solution is then obtained by computing: 
    max     m[n,j]
  1<=j<=8
We now argue that this recursive definition yields the correct answer. Given that column i ends with pattern j, then column i-1 must end with one of the patterns that is consistent with pattern j. We consider all such patterns. Furthermore, with the restriction that column i-1 ends in pattern j' (where again, we consider all possibilities for j'), the optimal solution for m[i,j] must include an optimal solution for m[i-1,j'] since the value for m[i,j] just adds the value of the placement for the first i-1 columns with the value for column i. Since part of the subproblem includes the pattern for column i-1 the cost of the solution for the first i-1 columns is independent of the layout used for column i. Thus we have the optimal substructure property, completing the correctness proof. Finally, given that m[n,1], ... m[n,8] are correct, clearly the last column must end in one of the 8 patterns and hence the maximum of the 8 possibilities gives the optimal layout.

We can compute m[i,j] in row major order (i.e., first do all entries for i=0, then all entries when i=1, and so on). A second matrix, p[i,j] can be used to remember the value of j' which yielded the optimal value for m[i,j] which can then be used to construct the optimal solution.

Since here are only 8 patterns, computing each m[i,j] (and p[i,j]) takes O(1) time. And since there are n+1 values for i and 8 values for j, there are 8(n+1) = O(n) subproblems. Finally, it takes O(1) time to compute the maximum of m[n,1], ..., m[n,8]. Hence the overall time complexity is O(n).