Date: Feb 28, 2013 4:51 AM
Author: Martin Brown
Subject: 8x8 bit patterns

I have a little puzzle where I think the answer is that it is not 
possible but having tried all the tricks I can think of cannot prove it.

The problem arises from considering the possible bit patterns in an 8x8
JPEG encoding square and searching for one that includes all possible
states for subsampling up to 2x2 - that is 2x1, 4x1, 2x2

ie 0000, 0001, ...., 1111


00 00 00 ........... 11
00, 01, 10, 11

It would be really nice if it did 1x4 as well.

It is obvious that the 4x1 subsampling requirement means that the final
solution if it exists must be a permutation of the nibbles 0,1,...,15

It is also obvious that taken as pairs and interpreted as 2x2 subsampled
there are 16x15 possible states of which those involving 0,5,10,15 will
have duplicate 2x2 subsampling patterns if used together. Using any pair
taken from this set prevents a solution.


4x1 2X2
0 00|00 0001 1
5 01|01 0001 1


4x1 2x2
0 00|00 0000 0
1 00|01 0001 1

The best I have been able to obtain by a directed brute force attack is
any number of solutions getting 11/15 of the 2x2 states and all of 4x1.
I am still not convinced my algorithm is working correctly.

This is based on computing the 2x2 patterns for all the pairs and then
combining them efficiently to try and maximise coverage in both domains.

The 4x1 pair {0,7} is represented as 2x2 {1,3} and bitmasks are used to
compute worthwhile continuations and cull all branches already worse
than existing solutions.

A complete solution should represent 0..15 in both domains 2x2 and 4x1.
But alas I can't find one :(

I can't help thinking there should be some clever parity based argument
to show that it is impossible to do better. Any suggestions?

Thanks for any enlightenment.

Martin Brown