Hint systems are designed to adjust a video game's difficulty to suit the individual player, but too often they are designed without analyzing player behavior and lack intelligence and adaptability, resulting in hints that are at best ineffective and at worst hurt player experience. We present an alternative approach to hint design focusing on player experience rather than performance. We had 25 participants play a difficult spatial puzzle game and collected player behavior, demographics, and self-reported player experience measures. We found that more exploratory behavior improved player experience, so we designed three types of hints encouraging this behavior: Adaptive, automatic, and on-demand. We found that certain players found hints more helpful regardless of whether the hints changed their behavior, and players seemed to prefer seeing fewer hints than the adaptive and automatic conditions gave them. Our findings contribute a deeper empirical understanding of hint design strategies and their effect on player behavior and experience, with practical recommendations for designers of interactive systems.