Animals navigate using cognitive maps. However, how they adaptively exploit these maps in changing environments is not fully understood. In this study, we investigated the problem-solving behaviors of mice in a complicated maze in which multiple routes with different intersections were available (Test 1). Although all mice eventually settled on the shortest route, mice that initially exhibited more trial-and-error exploration solved the maze more rapidly. We then introduced one or two barriers that obstructed learned routes such that mice had to establish novel roundabout detours (Tests 2/3). Solutions varied among mice but were predictable based on individual early trial-and-error patterns observed in Test 1: mice that had initially explored more extensively found better solutions. Finally, when the barriers were removed (Test 4), all mice reverted to the best solution after active exploration. Thus, early active exploration helps mice to develop optimal strategies.