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