Mathematicians have proven that four colors are sufficient to color 2-D maps so that no neighboring regions share the same color. Here we consider the psychological 4-color problem: Identifying which 4 colors should be used to make a map easy to use. We build a model of visual search for this design task and demonstrate how to apply it to the task of identifying the optimal colors for a map. We parameterized the model with a set of 7 colors using a visual search experiment in which human participants found a target region on a small map. We then used the model to predict search times for new maps and identified the color assignments that minimize or maximize average search time. The differences between these maps were predicted to be substantial. The model was then tested with a larger set of 31 colors on a map of English counties under conditions in which participants might memorize some aspects of the map. Empirical tests of the model showed that an optimally best colored version of this map is searched 15% faster than the correspondingly worst colored map. Thus, the color assignment seems to affect search times in a way predicted by the model, and this effect persists even when participants might use other sources of knowledge about target location. (Contains 3 tables and 8 figures.)