## Problem

Given a 3Xn board, find the number of ways to color it using at most 4 colors such that no two adjacent boxes have the same color. Diagonal neighbors are not treated as adjacent boxes. Output the ways%1000000007 as the answer grows quickly.

## Example:

Input: n = 1 Output: 36

## Solution:

Let’s first think how many of ways there’s exists valid colors when `n = 1`

. For convenience, let’s encode our colors as numbers from 0 to 3. We can use 3 unique colors to form a board. It’s `3!`

factorial times the number of ways we can choose 3 colors out of 4 i.e. `C(4, 3)`

. Then it’s possible to make a board with only using 2 colors. The number of ways is 2: `{1, 0, 1} or {0, 1, 0}`

. There’s exists `C(4, 2)`

of possible combinations of this pairs. Overall, we have: `3! x C(4, 3) + 2 x C(4, 2) = 36`

.

Once we get a grasp of the trivial case, it’s a time to solve it for a general case. For this, we will use a technique called [dynamic programming][db].

Let’s say we are able to solve the problem for the i column, which ends with some triple `<a_i, b_i, c_i>`

. When we need to to solve for the next column j = i + 1, we need to consider such triples, `Triplet<a_j, b_j, c_j>`

such that a`j != b`

j, b`j != c`

j, and previous column elements does not match: `a_i != a_j and b_i != b_j, and c_i != c_j`

. Answer for the `Triple(j) = sum(ValidTriplets(i) + 1)`

.

Below is an implementation of the given approach. Please note as we need only values from the previous iterations, we can only store only it and save a lot of space.

For convenience, I used HashMap to store results and not to bother with static 3D arrays. As usual, all suggestions and recommendations welcome!