This problem benefits from being able to handle real cubes using multilink or similar equipment.

Some sticky labels to identify which cubes have been painted and their locations may also prove beneficial.

Just trying to justify that in theory this should also be possible is a useful little proof.