doasku

commit 9abf7bf3f413c07749305dc32de97b8c81395965
parent 38bf75a0ab343789f01b6f30083f0852dec8ae28
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun,  7 Apr 2024 23:03:42 +0200

Add check for hidden triplets

Diffstat:
M
main.cpp
 | 
77
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 77 insertions(+), 0 deletions(-)
diff --git a/main.cpp b/main.cpp
@@ -98,6 +98,51 @@ class Ref {
         return res;
     }
 
+    auto get_hidden_triplets() const {
+        std::vector<std::tuple<uint8_t, uint16_t>> res;
+
+        for (uint8_t i = 0; i < 9; i++) {
+            if (std::popcount(ref[i]) < 2) continue;
+            if (seen_hidden_triplet & (1ul << i)) continue;
+
+            for (uint8_t j = i + 1; j < 9; j++) {
+                if (std::popcount(ref[j]) < 2) continue;
+                if (seen_hidden_triplet & (1ul << j)) continue;
+
+                for (uint8_t k = j + 1; k < 9; k++) {
+                    if (std::popcount(ref[k]) < 2) continue;
+                    if (seen_hidden_triplet & (1ul << k)) continue;
+
+                    uint16_t val = ref[i] | ref[j] | ref[k];
+                    if (std::popcount(val) != 3) continue;
+
+                    seen_hidden_triplet |= 1ul << i;
+                    seen_hidden_triplet |= 1ul << j;
+                    seen_hidden_triplet |= 1ul << k;
+
+                    static uint8_t fields[9];
+                    uint8_t size = 0;
+
+                    uint16_t tval = val;
+                    while (tval) {
+                        const uint8_t idx = std::countr_zero(tval);
+                        fields[size++] = idx;
+                        tval ^= 1ull << idx;
+                    }
+
+                    uint16_t mask = (1 << i) | (1 << j) | (1 << k);
+                    for (uint8_t i = 0; i < 3; i++) {
+                        const uint16_t change = value[fields[i]] & ~(value[fields[i]] & mask);
+                        if (!change) continue;
+                        res.emplace_back(fields[i], change);
+                    }
+                }
+            }
+        }
+
+        return res;
+    }
+
     auto get_naked_singles() const {
         std::vector<std::tuple<uint8_t, uint8_t>> res;
 
@@ -216,6 +261,7 @@ class Ref {
     uint16_t res[9] = {0};
 
     mutable uint16_t seen_hidden_pair = 0;
+    mutable uint16_t seen_hidden_triplet = 0;
 
     mutable uint16_t seen_naked_pair = 0;
     mutable uint16_t seen_naked_triplet = 0;
@@ -276,6 +322,15 @@ class Grid {
                     changes++;
                 }
 
+                const auto ht = subgrids[subgrid].get_hidden_triplets();
+                for (const auto [field, mask] : ht) {
+                    std::cout << "hidden triples: " << (int)subgrid << " " << (int)field << " "
+                              << std::bitset<9>(mask) << " " << std::endl;
+
+                    _mask(subgrid, field, mask);
+                    changes++;
+                }
+
                 const auto ns = subgrids[subgrid].get_naked_singles();
                 for (const auto [field, val] : ns) {
 
@@ -349,6 +404,17 @@ class Grid {
                     changes++;
                 }
 
+                const auto ht = rows[row].get_hidden_triplets();
+                for (const auto [col, mask] : ht) {
+                    const auto [subgrid, field] = row_col_t(row, col).relative();
+
+                    std::cout << "hidden triplets row: " << (int)row << " " << (int)col << " "
+                              << std::bitset<9>(mask) << " " << std::endl;
+
+                    _mask(subgrid, field, mask);
+                    changes++;
+                }
+
                 const auto np = rows[row].get_naked_pairs();
                 for (const auto [val, c1, c2] : np) {
                     std::cout << "naked pairs row: " << (int)row << " " << (int)c1 << " " << (int)c2 << " "
@@ -415,6 +481,17 @@ class Grid {
                     changes++;
                 }
 
+                const auto ht = cols[col].get_hidden_triplets();
+                for (const auto [row, mask] : ht) {
+                    const auto [subgrid, field] = row_col_t(row, col).relative();
+
+                    std::cout << "hidden triplets col: " << (int)row << " " << (int)col << " "
+                              << std::bitset<9>(mask) << " " << std::endl;
+
+                    _mask(subgrid, field, mask);
+                    changes++;
+                }
+
                 const auto np = cols[col].get_naked_pairs();
                 for (const auto [val, r1, r2] : np) {
                     std::cout << "naked pairs col: " << (int)col << " " << (int)r1 << " " << (int)r2 << " "