grid.cpp (7440B)
1 #include <algorithm> 2 #include <bitset> 3 #include <functional> 4 #include <iostream> 5 6 #include "grid.hpp" 7 8 template <class Input, class UnaryFunc> 9 UnaryFunc for_each(Input input, UnaryFunc f) { 10 return std::for_each(begin(input), end(input), f); 11 } 12 13 static std::tuple<uint8_t, uint8_t> other_subgrid_row(uint8_t subgrid) { 14 static std::tuple<uint8_t, uint8_t> mapping[9] = {{1, 2}, {0, 2}, {0, 1}, 15 {4, 5}, {3, 5}, {3, 4}, 16 {7, 8}, {6, 8}, {6, 7}}; 17 return mapping[subgrid]; 18 } 19 20 static std::tuple<uint8_t, uint8_t> other_subgrid_col(uint8_t subgrid) { 21 static std::tuple<uint8_t, uint8_t> mapping[9] = {{3, 6}, {4, 7}, {5, 8}, 22 {0, 6}, {1, 7}, {2, 8}, 23 {0, 3}, {1, 4}, {2, 5}}; 24 return mapping[subgrid]; 25 } 26 27 Grid::Grid(const std::string &s) { 28 int idx = 0; 29 for (uint8_t i = 0; i < 9; i++) { 30 for (uint8_t j = 0; j < 9; j++, idx++) { 31 if (s[idx] == '0') continue; 32 _set({i, j}, s[idx] - '1'); 33 } 34 } 35 } 36 37 bool Grid::solve() { 38 // clang-format off 39 static const auto sub_op = 40 [this](auto op, const auto f) { 41 for(uint8_t subgrid = 0; subgrid < 9; subgrid++) { 42 for_each(std::invoke(f, subgrids[subgrid]), [&](auto& ch) { 43 std::invoke(op, this, operation_t({cord_t(subgrid), cord_t(std::get<0>(ch))}, std::get<1>(ch))); 44 }); 45 } 46 return changed; 47 }; 48 49 static const auto row_op = 50 [this](auto op, const auto f) { 51 for(uint8_t row = 0; row < 9; row++) { 52 for_each(std::invoke(f, rows[row]), [&](auto& ch) { 53 std::invoke(op, this, operation_t({row, std::get<0>(ch)}, std::get<1>(ch))); 54 }); 55 } 56 return changed; 57 }; 58 59 static const auto col_op = 60 [this](auto op, const auto f) { 61 for(uint8_t col = 0; col < 9; col++) { 62 for_each(std::invoke(f, cols[col]), [&](auto &ch) { 63 std::invoke(op, this, operation_t({std::get<0>(ch), col}, std::get<1>(ch))); 64 }); 65 } 66 return changed; 67 }; 68 69 static const auto all_op = 70 [this](auto op, const auto f) { 71 sub_op(op, f), row_op(op, f), col_op(op, f); 72 return changed; 73 }; 74 // clang-format on 75 76 changed = true; 77 while (changed) { 78 changed = false; 79 80 if (sub_op(&Grid::op_set, &Ref::get_naked_singles)) continue; 81 if (all_op(&Grid::op_set, &Ref::get_hidden_singles)) continue; 82 if (sub_op(&Grid::op_clear_row, &Ref::get_pointing_row)) continue; 83 if (sub_op(&Grid::op_clear_col, &Ref::get_pointing_col)) continue; 84 if (all_op(&Grid::op_mask, &Ref::get_hidden_pairs)) continue; 85 if (all_op(&Grid::op_mask, &Ref::get_hidden_triplets)) continue; 86 if (all_op(&Grid::op_mask, &Ref::get_hidden_quads)) continue; 87 if (all_op(&Grid::op_clear, &Ref::get_naked_pairs)) continue; 88 if (all_op(&Grid::op_clear, &Ref::get_naked_triplets)) continue; 89 if (all_op(&Grid::op_clear, &Ref::get_naked_quads)) continue; 90 91 row_op(&Grid::op_clear_row_rel, &Ref::get_pointing_row); 92 col_op(&Grid::op_clear_col_rel, &Ref::get_pointing_row); 93 } 94 95 return _is_finished(); 96 } 97 98 void Grid::print() const { 99 // clang-format off 100 static const auto print_i = [this](const Ref refs[9], uint16_t (Ref::*f)(uint8_t) const, bool bits) { 101 for (uint8_t i = 0; i < 9; i++) { 102 for (uint8_t j = 0; j < 9; j++) { 103 const cord_t subgrid = {uint8_t(i / 3), uint8_t(j / 3)}; 104 const cord_t field = {uint8_t(i % 3), uint8_t(j % 3)}; 105 106 uint16_t value = (refs[subgrid].*(f))((uint8_t)field); 107 if (bits) std::cout << std::bitset<9>(value) << " "; 108 else std::cout << value << " "; 109 110 if (j % 3 == 2) std::cout << " "; 111 } 112 113 std::cout << std::endl; 114 if (i % 3 == 2) std::cout << std::endl; 115 } 116 }; 117 // clang-format on 118 119 std::cout << "Field: " << std::endl; 120 print_i(subgrids, &Ref::get, true); 121 122 std::cout << "Refs: " << std::endl; 123 print_i(subgrids, &Ref::get_ref, true); 124 125 std::cout << "Board: " << std::endl; 126 print_i(subgrids, &Ref::get_value, false); 127 } 128 129 void Grid::op_set(operation_t op) { 130 _set(std::get<0>(op), std::get<1>(op)); 131 changed = true; 132 } 133 134 void Grid::op_mask(operation_t op) { 135 _mask(std::get<0>(op), std::get<1>(op)); 136 changed = true; 137 } 138 139 void Grid::op_clear(operation_t op) { 140 _clear(std::get<0>(op), std::get<1>(op)); 141 changed = true; 142 } 143 144 void Grid::op_clear_row(operation_t op) { 145 const auto [ab, val] = op; 146 147 const auto [r1, r2] = other_subgrid_row(ab.subgrid()); 148 _clear_row(r1, ab.field(), val); 149 _clear_row(r2, ab.field(), val); 150 151 changed = true; 152 } 153 154 void Grid::op_clear_col(operation_t op) { 155 const auto [ab, val] = op; 156 157 const auto [c1, c2] = other_subgrid_col(ab.subgrid()); 158 _clear_col(c1, ab.field(), val); 159 _clear_col(c2, ab.field(), val); 160 161 changed = true; 162 } 163 164 void Grid::op_clear_row_rel(operation_t op) { 165 const auto [ab, val] = op; 166 167 const auto [r1, r2] = other_subgrid_row(ab.row()); 168 _clear_row((r1 / 3) * 3 + ab.col(), r1 % 3, val); 169 _clear_row((r2 / 3) * 3 + ab.col(), r2 % 3, val); 170 171 changed = true; 172 } 173 174 void Grid::op_clear_col_rel(operation_t op) { 175 const auto [ab, val] = op; 176 177 const auto [c1, c2] = other_subgrid_row(ab.col()); 178 _clear_col(ab.row() * 3 + c1 / 3, c1 % 3, val); 179 _clear_col(ab.row() * 3 + c2 / 3, c2 % 3, val); 180 181 changed = true; 182 } 183 184 void Grid::_set(acord_t ab, uint8_t value) { 185 rows[ab.row()].set(ab.col(), value); 186 cols[ab.col()].set(ab.row(), value); 187 subgrids[ab.subgrid()].set(ab.field(), value); 188 189 _clear_row(ab.subgrid(), 0, value); 190 _clear_row(ab.subgrid(), 1, value); 191 _clear_row(ab.subgrid(), 2, value); 192 193 const auto [r1, r2] = other_subgrid_row(ab.subgrid()); 194 _clear_row(r1, ab.field().row(), value); 195 _clear_row(r2, ab.field().row(), value); 196 197 const auto [c1, c2] = other_subgrid_col(ab.subgrid()); 198 _clear_col(c1, ab.field().col(), value); 199 _clear_col(c2, ab.field().col(), value); 200 } 201 202 void Grid::_mask(acord_t ab, uint16_t mask) { 203 while (mask) { 204 const uint8_t idx = std::countr_zero(mask); 205 _clear(ab, idx); 206 mask ^= 1ull << idx; 207 } 208 } 209 210 void Grid::_clear(acord_t ab, uint8_t value) { 211 subgrids[ab.subgrid()].clear(ab.field(), value); 212 213 rows[ab.row()].clear(ab.col(), value); 214 cols[ab.col()].clear(ab.row(), value); 215 } 216 217 void Grid::_clear_row(cord_t sg, uint8_t row, uint8_t value) { 218 for (uint8_t i = 0; i < 3; i++) { 219 _clear({sg, {row, i}}, value); 220 } 221 } 222 223 void Grid::_clear_col(cord_t sg, uint8_t col, uint8_t value) { 224 for (uint8_t i = 0; i < 3; i++) { 225 _clear({sg, {i, col}}, value); 226 } 227 } 228 229 bool Grid::_is_finished(uint8_t subgrid) { 230 for (uint8_t i = 0; i < 9; i++) { 231 if (!subgrids[subgrid].get_value(i)) return false; 232 } 233 return true; 234 } 235 236 bool Grid::_is_finished() { 237 for (uint8_t i = 0; i < 9; i++) { 238 if (!_is_finished(i)) return false; 239 } 240 return true; 241 }