ref.cpp (4528B)
1 #include <cassert> 2 #include <stdexcept> 3 4 #include "ref.hpp" 5 6 void ref::clear(uint8_t field, uint8_t value) 7 { 8 m_value.at(field) &= static_cast<uint16_t>(~(1U << value)); 9 m_ref.at(value) &= static_cast<uint16_t>(~(1U << field)); 10 } 11 12 void ref::set(uint8_t field, uint8_t value) 13 { 14 for (uint8_t i = 0; i < 9; i++) { 15 m_ref.at(i) &= static_cast<uint16_t>(~(1U << field)); 16 } 17 18 m_ref.at(value) = 0; 19 m_value.at(field) = 0; 20 m_res.at(field) = value + 1; 21 } 22 23 ref::changes_t ref::get_hidden_singles() const 24 { 25 changes_t res; 26 27 for (uint8_t candidate = 0; candidate < 9; candidate++) { 28 if (std::popcount(m_ref.at(candidate)) != 1) continue; 29 res.emplace_back(std::countr_zero(m_ref.at(candidate)), candidate); 30 } 31 32 return res; 33 } 34 35 ref::changes_t ref::get_naked_singles() const 36 { 37 changes_t res; 38 39 for (uint8_t i = 0; i < 9; i++) { 40 const auto values = get(i); 41 if (std::popcount(values) != 1) continue; 42 const auto value = static_cast<size_t>(std::countr_zero(values)); 43 if (m_ref.at(value) == 0) continue; 44 res.emplace_back(i, value); 45 } 46 47 return res; 48 } 49 50 ref::changes_t ref::get_hidden(uint8_t number) const 51 { 52 assert(number > 1 && number <= 4); 53 54 changes_t res; 55 get_hidden(res, number, number, 0, 0, 0); 56 return res; 57 } 58 59 bool ref::get_hidden(changes_t& res, 60 uint8_t orig, 61 uint8_t number, 62 uint8_t first, 63 uint16_t val, 64 uint16_t mask) const 65 { 66 if (number != 0) { 67 for (uint8_t i = first; i < 9; i++) { 68 if (std::popcount(m_ref.at(i)) < 2) continue; 69 if ((m_seen_hidden.at(orig - 1) & (1UL << i)) != 0) continue; 70 71 const bool used = get_hidden(res, 72 orig, 73 number - 1, 74 i + 1, 75 val | m_ref.at(i), 76 mask | static_cast<uint16_t>(1U << i)); 77 if (!used) continue; 78 79 m_seen_hidden.at(orig - 1) |= 1UL << i; 80 if (number != orig) return true; 81 } 82 83 return false; 84 } 85 86 if (std::popcount(val) != orig) return false; 87 88 static std::array<uint8_t, 9> fields; 89 uint8_t size = 0; 90 91 while (val != 0) { 92 const auto idx = static_cast<uint8_t>(std::countr_zero(val)); 93 fields.at(size++) = idx; 94 val ^= 1ULL << idx; 95 } 96 97 for (uint8_t i = 0; i < orig; i++) { 98 const uint16_t change = 99 m_value.at(fields.at(i)) & ~(m_value.at(fields.at(i)) & mask); 100 if (change == 0) continue; 101 res.emplace_back(fields.at(i), change); 102 } 103 104 return true; 105 } 106 107 ref::changes_t ref::get_naked(uint8_t number) const 108 { 109 assert(number > 1 && number <= 4); 110 111 changes_t res; 112 get_naked(res, number, number, 0, 0); 113 return res; 114 } 115 116 bool ref::get_naked(changes_t& res, 117 uint8_t orig, 118 uint8_t number, 119 uint8_t first, 120 uint16_t val) const 121 { 122 static std::array<uint8_t, 4> seen = {0}; 123 124 if (number != 0) { 125 for (uint8_t i = first; i < 9; i++) { 126 if (m_res.at(i) != 0) continue; 127 if (number == orig && (m_seen_naked.at(orig - 1) & (1UL << i)) != 0) 128 continue; 129 130 seen.at(orig - number) = i; 131 const bool used = 132 get_naked(res, orig, number - 1, i + 1, val | m_value.at(i)); 133 if (!used) continue; 134 135 if (number == orig) m_seen_naked.at(orig - 1) |= 1UL << i; 136 if (number != orig) return true; 137 } 138 139 return false; 140 } 141 142 if (std::popcount(val) != orig) return false; 143 144 while (val != 0) { 145 const auto idx = static_cast<uint8_t>(std::countr_zero(val)); 146 for (uint8_t pos = 0, i = 0; pos < 9; pos++) { 147 if ((m_value.at(pos) & idx) == 0) continue; 148 for (i = 0; i < orig; i++) { 149 if (pos == seen.at(i)) break; 150 } 151 if (i == orig) res.emplace_back(pos, idx); 152 } 153 val ^= 1ULL << idx; 154 } 155 156 return true; 157 } 158 159 ref::changes_t ref::get_pointing(uint16_t mask, std::size_t seen) const 160 { 161 changes_t res; 162 163 for (uint8_t i = 0; i < 9; i++) { 164 const auto popcnt = std::popcount(m_ref.at(i)); 165 if (popcnt < 2 || popcnt > 3) continue; 166 167 if ((m_seen_point.at(seen) & (1UL << i)) == 0) { 168 uint16_t cmask = mask; 169 for (uint8_t k = 0; k < 3; k++, cmask <<= 3U) { 170 const uint16_t lmask = cmask & m_ref.at(i); 171 const auto cpopcnt = std::popcount(lmask); 172 if (cpopcnt != popcnt) continue; 173 174 m_seen_point.at(seen) |= 1U << i; 175 res.emplace_back(k, i); 176 break; 177 } 178 } 179 } 180 181 return res; 182 }