Addressing only the data representation part of the problem:

This is similar to the classic "knight moves" chess problem.

I'd suggest a single-dimension array with 8 elements.
Each element has 8 bits of content, which represents a column of data.

With this structure, the problem reduces to identifying rules to generate legal adjacent bit patters.

It's late in my day - brain too fried to attempt that now - I'm sure wiser, more alert monks will oblige.

Cheers.

Update:Sigh .. - it is even later in the night, but I'm bothered because the representation above is not right.
The values 0..5 can represent your 6 choices - these can fit into 3 bits. Times 8 gives you 24 bits.

So, a single dim array, where each element holds 24 bits can represent your problem.

If you shift items in sequences of 6 bits, you can identify legal vertical patterns. The same rules can apply to adjacent indexes masking out the right bits.

Brain still to fried to conceptualize the actual patterns.