Through codified rule-use, humans can accurately solve many problems. Yet, mechanized strategies can also be costly. After adopting a solution strategy, humans often become blind to alternatives, even when those alternatives are more efficient. Termed cognitive set, this failure to switch from a familiar strategy to a better alternative has been considered universally human. Yet, our understanding of this phenomenon is derived almost exclusively from Western subjects. In this study, we used the nonverbal Learned Strategy-Direct Strategy (LS-DS) touchscreen task in which subjects are presented with an opportunity to use either a learned strategy or a more efficient, but novel, shortcut. We found that the remote, seminomadic Himba of northern Namibia exhibited enhanced shortcut-use on the LS-DS task, challenging the claim that cognitive set affects humans universally. In addition, we found that altering subjects' conceptualization of the shortcut as a viable option significantly enhanced its subsequent use in Western but not Himba participants. We discuss how other aspects of cultural variation, namely, environmental uncertainty and educational background, might contribute to the observed cross-cultural differences in flexible strategy-use.