grid.cpp (8568B)
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 func) 10 { 11 return std::for_each(begin(input), end(input), func); 12 } 13 14 using other_t = std::tuple<uint8_t, uint8_t>; 15 16 other_t other_subgrid_row(uint8_t subgrid) 17 { 18 static const auto mapping = std::to_array<other_t>({{1, 2}, 19 {0, 2}, 20 {0, 1}, 21 {4, 5}, 22 {3, 5}, 23 {3, 4}, 24 {7, 8}, 25 {6, 8}, 26 {6, 7}}); 27 return mapping.at(subgrid); 28 } 29 30 other_t other_subgrid_col(uint8_t subgrid) 31 { 32 static const auto mapping = std::to_array<other_t>({{3, 6}, 33 {4, 7}, 34 {5, 8}, 35 {0, 6}, 36 {1, 7}, 37 {2, 8}, 38 {0, 3}, 39 {1, 4}, 40 {2, 5}}); 41 return mapping.at(subgrid); 42 } 43 44 grid::grid(const std::string& str) 45 { 46 std::size_t idx = 0; 47 for (uint8_t i = 0; i < 9; i++) { 48 for (uint8_t j = 0; j < 9; j++, idx++) { 49 if (str[idx] == '0') continue; 50 set({i, j}, static_cast<uint8_t>(str[idx] - '1')); 51 } 52 } 53 } 54 55 bool grid::solve() 56 { 57 // clang-format off 58 static const auto sub_op = 59 [this](auto opr, const auto func) { 60 for(uint8_t subgrid = 0; subgrid < 9; subgrid++) { 61 for_each(std::invoke(func, m_subgrids.at(subgrid)), [&](auto& chng) { 62 std::invoke(opr, this, operation_t({cord_t(subgrid), cord_t(std::get<0>(chng))}, std::get<1>(chng))); 63 }); 64 } 65 return m_changed; 66 }; 67 68 static const auto row_op = 69 [this](auto opr, const auto func) { 70 for(uint8_t row = 0; row < 9; row++) { 71 for_each(std::invoke(func, m_rows.at(row)), [&](auto& chng) { 72 std::invoke(opr, this, operation_t({row, std::get<0>(chng)}, std::get<1>(chng))); 73 }); 74 } 75 return m_changed; 76 }; 77 78 static const auto col_op = 79 [this](auto opr, const auto func) { 80 for(uint8_t col = 0; col < 9; col++) { 81 for_each(std::invoke(func, m_cols.at(col)), [&](auto &chng) { 82 std::invoke(opr, this, operation_t({std::get<0>(chng), col}, std::get<1>(chng))); 83 }); 84 } 85 return m_changed; 86 }; 87 88 static const auto all_op = 89 [this](auto opr, const auto func) { 90 sub_op(opr, func), row_op(opr, func), col_op(opr, func); 91 return m_changed; 92 }; 93 // clang-format on 94 95 m_changed = true; 96 while (m_changed) { 97 m_changed = false; 98 99 if (sub_op(&grid::op_set, &ref::get_naked_singles)) continue; 100 if (all_op(&grid::op_set, &ref::get_hidden_singles)) continue; 101 if (sub_op(&grid::op_clear_row, &ref::get_pointing_row)) continue; 102 if (sub_op(&grid::op_clear_col, &ref::get_pointing_col)) continue; 103 if (all_op(&grid::op_mask, &ref::get_hidden_pairs)) continue; 104 if (all_op(&grid::op_mask, &ref::get_hidden_triplets)) continue; 105 if (all_op(&grid::op_mask, &ref::get_hidden_quads)) continue; 106 if (all_op(&grid::op_clear, &ref::get_naked_pairs)) continue; 107 if (all_op(&grid::op_clear, &ref::get_naked_triplets)) continue; 108 if (all_op(&grid::op_clear, &ref::get_naked_quads)) continue; 109 110 row_op(&grid::op_clear_row_rel, &ref::get_pointing_row); 111 col_op(&grid::op_clear_col_rel, &ref::get_pointing_row); 112 } 113 114 return is_finished(); 115 } 116 117 void grid::print() const 118 { 119 // clang-format off 120 static const auto print_i = [](const auto& refs, uint16_t (ref::*func)(uint8_t) const, bool bits) { 121 for (uint8_t i = 0; i < 9; i++) { 122 for (uint8_t j = 0; j < 9; j++) { 123 const cord_t subgrid = {static_cast<uint8_t>(i / 3), static_cast<uint8_t>(j / 3)}; 124 const cord_t field = {static_cast<uint8_t>(i % 3), static_cast<uint8_t>(j % 3)}; 125 126 const uint16_t value = std::invoke(func, refs.at(subgrid), field); 127 const std::bitset<9>bts(value); 128 129 if (bits) std::cout << bts << " "; 130 else std::cout << value << " "; 131 132 if (j % 3 == 2) std::cout << " "; 133 } 134 135 std::cout << std::endl; 136 if (i % 3 == 2) std::cout << std::endl; 137 } 138 }; 139 // clang-format on 140 141 std::cout << "Field: " << std::endl; 142 print_i(m_subgrids, &ref::get, true); 143 144 std::cout << "Refs: " << std::endl; 145 print_i(m_subgrids, &ref::get_ref, true); 146 147 std::cout << "Board: " << std::endl; 148 print_i(m_subgrids, &ref::get_value, false); 149 } 150 151 void grid::op_set(operation_t opr) 152 { 153 set(std::get<0>(opr), static_cast<uint8_t>(std::get<1>(opr))); 154 m_changed = true; 155 } 156 157 void grid::op_mask(operation_t opr) 158 { 159 mask(std::get<0>(opr), std::get<1>(opr)); 160 m_changed = true; 161 } 162 163 void grid::op_clear(operation_t opr) 164 { 165 clear(std::get<0>(opr), static_cast<uint8_t>(std::get<1>(opr))); 166 m_changed = true; 167 } 168 169 void grid::op_clear_row(operation_t opr) 170 { 171 const auto val = static_cast<uint8_t>(std::get<1>(opr)); 172 const auto abs = std::get<0>(opr); 173 174 const auto [r1, r2] = other_subgrid_row(abs.subgrid()); 175 clear_row(cord_t(r1), abs.field(), val); 176 clear_row(cord_t(r2), abs.field(), val); 177 178 m_changed = true; 179 } 180 181 void grid::op_clear_col(operation_t opr) 182 { 183 const auto val = static_cast<uint8_t>(std::get<1>(opr)); 184 const auto abs = std::get<0>(opr); 185 186 const auto [c1, c2] = other_subgrid_col(abs.subgrid()); 187 clear_col(cord_t(c1), abs.field(), val); 188 clear_col(cord_t(c2), abs.field(), val); 189 190 m_changed = true; 191 } 192 193 void grid::op_clear_row_rel(operation_t opr) 194 { 195 const auto val = static_cast<uint8_t>(std::get<1>(opr)); 196 const auto abs = std::get<0>(opr); 197 198 const auto [r1, r2] = other_subgrid_row(abs.row()); 199 clear_row(cord_t((r1 / 3), abs.col()), r1 % 3, val); 200 clear_row(cord_t((r2 / 3), abs.col()), r2 % 3, val); 201 202 m_changed = true; 203 } 204 205 void grid::op_clear_col_rel(operation_t opr) 206 { 207 const auto val = static_cast<uint8_t>(std::get<1>(opr)); 208 const auto abs = std::get<0>(opr); 209 210 const auto [c1, c2] = other_subgrid_row(abs.col()); 211 clear_col(cord_t(abs.row(), c1 / 3), c1 % 3, val); 212 clear_col(cord_t(abs.row(), c2 / 3), c2 % 3, val); 213 214 m_changed = true; 215 } 216 217 void grid::set(acord_t abs, uint8_t value) 218 { 219 m_rows.at(abs.row()).set(abs.col(), value); 220 m_cols.at(abs.col()).set(abs.row(), value); 221 m_subgrids.at(abs.subgrid()).set(abs.field(), value); 222 223 clear_row(abs.subgrid(), 0, value); 224 clear_row(abs.subgrid(), 1, value); 225 clear_row(abs.subgrid(), 2, value); 226 227 const auto [r1, r2] = other_subgrid_row(abs.subgrid()); 228 clear_row(cord_t(r1), abs.field().row(), value); 229 clear_row(cord_t(r2), abs.field().row(), value); 230 231 const auto [c1, c2] = other_subgrid_col(abs.subgrid()); 232 clear_col(cord_t(c1), abs.field().col(), value); 233 clear_col(cord_t(c2), abs.field().col(), value); 234 } 235 236 void grid::mask(acord_t abs, uint16_t mask) 237 { 238 while (mask != 0) { 239 const auto idx = static_cast<uint8_t>(std::countr_zero(mask)); 240 clear(abs, idx); 241 mask ^= 1ULL << idx; 242 } 243 } 244 245 void grid::clear(acord_t abs, uint8_t value) 246 { 247 m_subgrids.at(abs.subgrid()).clear(abs.field(), value); 248 249 m_rows.at(abs.row()).clear(abs.col(), value); 250 m_cols.at(abs.col()).clear(abs.row(), value); 251 } 252 253 void grid::clear_row(cord_t sbgrd, uint8_t row, uint8_t value) 254 { 255 for (uint8_t i = 0; i < 3; i++) { 256 clear({sbgrd, {row, i}}, value); 257 } 258 } 259 260 void grid::clear_col(cord_t sbgrd, uint8_t col, uint8_t value) 261 { 262 for (uint8_t i = 0; i < 3; i++) { 263 clear({sbgrd, {i, col}}, value); 264 } 265 } 266 267 bool grid::is_finished(uint8_t subgrid) 268 { 269 for (uint8_t i = 0; i < 9; i++) { 270 if (m_subgrids.at(subgrid).get_value(i) == 0) return false; 271 } 272 return true; 273 } 274 275 bool grid::is_finished() 276 { 277 for (uint8_t i = 0; i < 9; i++) { 278 if (!is_finished(i)) return false; 279 } 280 return true; 281 }