Question

Pebbling a checkerboard. We are given a checkerboard which has 4 rows and $\mathit{n}$columns, and has an integer written in each square. We are also given a set of $\mathbf{2}\mathit{n}$ 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).

1. 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 columns $\mathbf{1}\mathbf{\le }\mathbf{k}\mathbf{\le }\mathbf{n}$. Each subproblem can be assigned a type, which is the pattern occurring in the last column.

1. Using the notions of compatibility and type, give an $\mathbf{O}\left(n\right)$-time dynamic programming algorithm for computing an optimal placement.

Short answer

1. There are $8$possible patterns which can be legally occur according to the given constraint.
2. For each pattern, there is set of compatible patterns. Split the problem into subproblems and find the optimal value by pebbling column i with patten j. Create separate arrays for each pattern type.

Step-by-step solution

Consider the given information

The checkboard has 4 rows and $n$columns. $2n$pebbles need to be placed on the check board such that they are legal patterns. The condition for the pattern to be legal is that no two pebbles can be placed on vertically or horizontally adjacent squares.

Determining the legal patterns

The following table shows are possible patterns with the given constraint:

Pattern	Description
_ _ _ _	No Pebble in any Row
X _ _ _	Pebble at 1st Row
_ X _ _	Pebble at 2nd Row
_ _ X _	Pebble at 3rd Row
_ _ _ X	Pebble at 4th Row
X _ _ X	Pebble at 1st and 4th Row
_ X _ X	Pebble at 2nd and 4th Row
X _ X _	Pebble at 1st and 3rd Row

Here, ‘X’ denotes Pebble position and ‘_’ denotes empty place.

Thus, the possible legal patterns are 8.

Determine the dynamic programming to compute optimal placement

Consider the initial checkboard be $M[i,j]$. The method compatibility (i) gives the patterns compatible with i. In the array $A[i,j]$, i denotes pattern and j denotes column. Sum (i, j) method returns the sum of numbers on column i when pattern j is applied.

$\begin{array}{l}A\left[i,0\right]=0\text{forall}i\\ \text{for}x\text{from}1\text{to}n:\\ \text{\hspace{0.33em}\hspace{0.33em}for}y\text{from}0\text{to}7\\ \text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}max}=0\\ m=\text{Sum}\left(x,y\right)\\ \text{for}p\text{incompatibility}\left(y\right)\\ n=\text{Sum}\left(x-1,p\right)\\ \text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}if}\left(m+n>\text{max}\right)\\ \text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}thenmax}=m+n\\ \begin{array}{l}A\left[x,y\right]=\text{max}\\ \text{returnMax}(A\left[i,N\right]\text{forall\hspace{0.33em}i}\end{array}\end{array}$

The time complexity of the algorithm is $O\left(n\right)$.