doasku

0 #include <cassert>

1 #include <stdexcept>

2

3 #include "ref.hpp"

4

5 void ref::clear(uint8_t field, uint8_t value)

6 {

7 m_value.at(field) &= static_cast<uint16_t>(~(1U << value));

8 m_ref.at(value) &= static_cast<uint16_t>(~(1U << field));

9 }

10

11 void ref::set(uint8_t field, uint8_t value)

12 {

13 for (uint8_t i = 0; i < 9; i++) {

14 m_ref.at(i) &= static_cast<uint16_t>(~(1U << field));

15 }

16

17 m_ref.at(value) = 0;

18 m_value.at(field) = 0;

19 m_res.at(field) = value + 1;

20 }

21

22 ref::changes_t ref::get_hidden_singles() const

23 {

24 changes_t res;

25

26 for (uint8_t candidate = 0; candidate < 9; candidate++) {

27 if (std::popcount(m_ref.at(candidate)) != 1) continue;

28 res.emplace_back(std::countr_zero(m_ref.at(candidate)), candidate);

29 }

30

31 return res;

32 }

33

34 ref::changes_t ref::get_naked_singles() const

35 {

36 changes_t res;

37

38 for (uint8_t i = 0; i < 9; i++) {

39 const auto values = get(i);

40 if (std::popcount(values) != 1) continue;

41 const auto value = static_cast<size_t>(std::countr_zero(values));

42 if (m_ref.at(value) == 0) continue;

43 res.emplace_back(i, value);

44 }

45

46 return res;

47 }

48

49 ref::changes_t ref::get_hidden(uint8_t number) const

50 {

51 assert(number > 1 && number <= 4);

52

53 changes_t res;

54 get_hidden(res, number, number, 0, 0, 0);

55 return res;

56 }

57

58 bool ref::get_hidden(changes_t& res,

59 uint8_t orig,

60 uint8_t number,

61 uint8_t first,

62 uint16_t val,

63 uint16_t mask) const

64 {

65 if (number != 0) {

66 for (uint8_t i = first; i < 9; i++) {

67 if (std::popcount(m_ref.at(i)) < 2) continue;

68 if ((m_seen_hidden.at(orig - 1) & (1UL << i)) != 0) continue;

69

70 const bool used = get_hidden(res,

71 orig,

72 number - 1,

73 i + 1,

74 val | m_ref.at(i),

75 mask | static_cast<uint16_t>(1U << i));

76 if (!used) continue;

77

78 m_seen_hidden.at(orig - 1) |= 1UL << i;

79 if (number != orig) return true;

80 }

81

82 return false;

83 }

84

85 if (std::popcount(val) != orig) return false;

86

87 static std::array<uint8_t, 9> fields;

88 uint8_t size = 0;

89

90 while (val != 0) {

91 const auto idx = static_cast<uint8_t>(std::countr_zero(val));

92 fields.at(size++) = idx;

93 val ^= 1ULL << idx;

94 }

95

96 for (uint8_t i = 0; i < orig; i++) {

97 const uint16_t change =

98 m_value.at(fields.at(i)) & ~(m_value.at(fields.at(i)) & mask);

99 if (change == 0) continue;

100 res.emplace_back(fields.at(i), change);

101 }

102

103 return true;

104 }

105

106 ref::changes_t ref::get_naked(uint8_t number) const

107 {

108 assert(number > 1 && number <= 4);

109

110 changes_t res;

111 get_naked(res, number, number, 0, 0);

112 return res;

113 }

114

115 bool ref::get_naked(changes_t& res,

116 uint8_t orig,

117 uint8_t number,

118 uint8_t first,

119 uint16_t val) const

120 {

121 static std::array<uint8_t, 4> seen = {0};

122

123 if (number != 0) {

124 for (uint8_t i = first; i < 9; i++) {

125 if (m_res.at(i) != 0) continue;

126 if (number == orig && (m_seen_naked.at(orig - 1) & (1UL << i)) != 0)

127 continue;

128

129 seen.at(orig - number) = i;

130 const bool used =

131 get_naked(res, orig, number - 1, i + 1, val | m_value.at(i));

132 if (!used) continue;

133

134 if (number == orig) m_seen_naked.at(orig - 1) |= 1UL << i;

135 if (number != orig) return true;

136 }

137

138 return false;

139 }

140

141 if (std::popcount(val) != orig) return false;

142

143 while (val != 0) {

144 const auto idx = static_cast<uint8_t>(std::countr_zero(val));

145 for (uint8_t pos = 0, i = 0; pos < 9; pos++) {

146 if ((m_value.at(pos) & idx) == 0) continue;

147 for (i = 0; i < orig; i++) {

148 if (pos == seen.at(i)) break;

149 }

150 if (i == orig) res.emplace_back(pos, idx);

151 }

152 val ^= 1ULL << idx;

153 }

154

155 return true;

156 }

157

158 ref::changes_t ref::get_pointing(uint16_t mask, std::size_t seen) const

159 {

160 changes_t res;

161

162 for (uint8_t i = 0; i < 9; i++) {

163 const auto popcnt = std::popcount(m_ref.at(i));

164 if (popcnt < 2 || popcnt > 3) continue;

165

166 if ((m_seen_point.at(seen) & (1UL << i)) == 0) {

167 uint16_t cmask = mask;

168 for (uint8_t k = 0; k < 3; k++, cmask <<= 3U) {

169 const uint16_t lmask = cmask & m_ref.at(i);

170 const auto cpopcnt = std::popcount(lmask);

171 if (cpopcnt != popcnt) continue;

172

173 m_seen_point.at(seen) |= 1U << i;

174 res.emplace_back(k, i);

175 break;

176 }

177 }

178 }

179

180 return res;

181 }