What algorithm to use to classify data by spatial relations?
The spatial relationships that you describe would correspond to features, and it's not clear that you need to use a neural network for detecting or discovering these features since you have just described them. Could you instead define a feature extractor that detects the correct patterns and returns you a vector of counts of feature occurrences across the image?
In fact gray level co-occurrance matrices might be adaptable to this problem. Since there are only four colours, each matrix would be very small, and you would define one matrix for each local spatial configuration. For example, one matrix might encode the number of times that colour x is below colour y. From these you could then extract counts of interest to use for further downstream processing.