In sunshine, the Vikings navigated on the open sea using sundials. According to a widespread hypothesis, when the Sun was occluded by fog or clouds the Vikings might have navigated by skylight polarization detected with an enigmatic birefringent crystal (sunstone). There are two atmospheric optical prerequisites for this alleged polarimetric Viking navigation under foggy/cloudy skies: (1) the degree of linear polarization p of skylight should be high enough and (2) at a given Sun position, the pattern of the angle of polarization a of the foggy/cloudy sky should be similar to that of the clear sky. Until now, these prerequisites have not been investigated. Using full-sky imaging polarimetry, we measured the p- and a-patterns of Arctic foggy and cloudy skies when the Sun was invisible. These patterns were compared with the polarization patterns of clear Arctic skies. We show here that although prerequisite (2) is always fulfilled under both foggy and cloudy conditions, if the fog layer is illuminated by direct sunlight, prerequisite (1) is usually satisfied only for cloudy skies. In sunlit fog, the Vikings could have navigated by polarization only, if p of light from the foggy sky was sufficiently high.