doasku

commit 38bf75a0ab343789f01b6f30083f0852dec8ae28
parent 234d12dba299bd4c1b0f48d58f44f7082569d00f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun,  7 Apr 2024 22:45:22 +0200

Add check for hidden pairs

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

1 file changed, 78 insertions(+), 0 deletions(-)
diff --git a/main.cpp b/main.cpp
@@ -63,6 +63,41 @@ class Ref {
         return res;
     }
 
+    auto get_hidden_pairs() 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_pair & (1ul << i)) continue;
+            for (uint8_t j = i + 1; j < 9; j++) {
+                if (ref[i] != ref[j]) continue;
+                if (seen_hidden_pair & (1ul << j)) continue;
+
+                seen_hidden_pair |= 1ul << i;
+                seen_hidden_pair |= 1ul << j;
+
+                static uint8_t fields[9];
+                uint8_t size = 0;
+
+                uint16_t tval = ref[i];
+                while (tval) {
+                    const uint8_t idx = std::countr_zero(tval);
+                    fields[size++] = idx;
+                    tval ^= 1ull << idx;
+                }
+
+                uint16_t mask = (1 << i) | (1 << j);
+                for (uint8_t i = 0; i < 2; 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;
 
@@ -180,6 +215,8 @@ class Ref {
 
     uint16_t res[9] = {0};
 
+    mutable uint16_t seen_hidden_pair = 0;
+
     mutable uint16_t seen_naked_pair = 0;
     mutable uint16_t seen_naked_triplet = 0;
     mutable uint16_t seen_naked_quad = 0;
@@ -230,6 +267,15 @@ class Grid {
                     changes++;
                 }
 
+                const auto hp = subgrids[subgrid].get_hidden_pairs();
+                for (const auto [field, mask] : hp) {
+                    std::cout << "hidden pairs: " << (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) {
 
@@ -292,6 +338,17 @@ class Grid {
                     changes++;
                 }
 
+                const auto hp = rows[row].get_hidden_pairs();
+                for (const auto [col, mask] : hp) {
+                    const auto [subgrid, field] = row_col_t(row, col).relative();
+
+                    std::cout << "hidden pairs 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 << " "
@@ -347,6 +404,17 @@ class Grid {
                     changes++;
                 }
 
+                const auto hp = cols[col].get_hidden_pairs();
+                for (const auto [row, mask] : hp) {
+                    const auto [subgrid, field] = row_col_t(row, col).relative();
+
+                    std::cout << "hidden pairs 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 << " "
@@ -424,6 +492,7 @@ class Grid {
             if (i % 3 == 2) std::cout << std::endl;
         }
 
+        /*
         std::cout << "Row Refs: " << std::endl;
         for (uint8_t i = 0; i < 9; i++) {
             for (uint8_t j = 0; j < 9; j++) {
@@ -441,6 +510,7 @@ class Grid {
             std::cout << std::endl;
             if (i % 3 == 2) std::cout << std::endl;
         }
+        */
 
         std::cout << "Board: " << std::endl;
         for (uint8_t i = 0; i < 9; i++) {
@@ -456,6 +526,14 @@ class Grid {
     }
 
   private:
+    void _mask(row_col_t sg, row_col_t field, uint16_t mask) {
+        while (mask) {
+            const uint8_t idx = std::countr_zero(mask);
+            _clear(sg, field, idx);
+            mask ^= 1ull << idx;
+        }
+    }
+
     void _clear(row_col_t sg, row_col_t field, uint8_t value) {
         subgrids[sg].clear(field, value);