## 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 aj != bj, bj != cj, 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!