doasku

0 #include <algorithm>

1 #include <bitset>

2 #include <functional>

3 #include <iostream>

4

5 #include "grid.hpp"

6

7 template<class Input, class UnaryFunc>

8 UnaryFunc for_each(Input input, UnaryFunc func)

9 {

10 return std::for_each(begin(input), end(input), func);

11 }

12

13 using other_t = std::tuple<uint8_t, uint8_t>;

14

15 other_t other_subgrid_row(uint8_t subgrid)

16 {

17 static const auto mapping = std::to_array<other_t>({{1, 2},

18 {0, 2},

19 {0, 1},

20 {4, 5},

21 {3, 5},

22 {3, 4},

23 {7, 8},

24 {6, 8},

25 {6, 7}});

26 return mapping.at(subgrid);

27 }

28

29 other_t other_subgrid_col(uint8_t subgrid)

30 {

31 static const auto mapping = std::to_array<other_t>({{3, 6},

32 {4, 7},

33 {5, 8},

34 {0, 6},

35 {1, 7},

36 {2, 8},

37 {0, 3},

38 {1, 4},

39 {2, 5}});

40 return mapping.at(subgrid);

41 }

42

43 grid::grid(const std::string& str)

44 {

45 std::size_t idx = 0;

46 for (uint8_t i = 0; i < 9; i++) {

47 for (uint8_t j = 0; j < 9; j++, idx++) {

48 if (str[idx] == '0') continue;

49 set({i, j}, static_cast<uint8_t>(str[idx] - '1'));

50 }

51 }

52 }

53

54 bool grid::solve()

55 {

56 // clang-format off

57 static const auto sub_op =

58 [this](auto opr, const auto func) {

59 for(uint8_t subgrid = 0; subgrid < 9; subgrid++) {

60 for_each(std::invoke(func, m_subgrids.at(subgrid)), [&](auto& chng) {

61 std::invoke(opr, this, operation_t({cord_t(subgrid), cord_t(std::get<0>(chng))}, std::get<1>(chng)));

62 });

63 }

64 return m_changed;

65 };

66

67 static const auto row_op =

68 [this](auto opr, const auto func) {

69 for(uint8_t row = 0; row < 9; row++) {

70 for_each(std::invoke(func, m_rows.at(row)), [&](auto& chng) {

71 std::invoke(opr, this, operation_t({row, std::get<0>(chng)}, std::get<1>(chng)));

72 });

73 }

74 return m_changed;

75 };

76

77 static const auto col_op =

78 [this](auto opr, const auto func) {

79 for(uint8_t col = 0; col < 9; col++) {

80 for_each(std::invoke(func, m_cols.at(col)), [&](auto &chng) {

81 std::invoke(opr, this, operation_t({std::get<0>(chng), col}, std::get<1>(chng)));

82 });

83 }

84 return m_changed;

85 };

86

87 static const auto all_op =

88 [this](auto opr, const auto func) {

89 sub_op(opr, func), row_op(opr, func), col_op(opr, func);

90 return m_changed;

91 };

92 // clang-format on

93

94 m_changed = true;

95 while (m_changed) {

96 m_changed = false;

97

98 if (sub_op(&grid::op_set, &ref::get_naked_singles)) continue;

99 if (all_op(&grid::op_set, &ref::get_hidden_singles)) continue;

100 if (sub_op(&grid::op_clear_row, &ref::get_pointing_row)) continue;

101 if (sub_op(&grid::op_clear_col, &ref::get_pointing_col)) continue;

102 if (all_op(&grid::op_mask, &ref::get_hidden_pairs)) continue;

103 if (all_op(&grid::op_mask, &ref::get_hidden_triplets)) continue;

104 if (all_op(&grid::op_mask, &ref::get_hidden_quads)) continue;

105 if (all_op(&grid::op_clear, &ref::get_naked_pairs)) continue;

106 if (all_op(&grid::op_clear, &ref::get_naked_triplets)) continue;

107 if (all_op(&grid::op_clear, &ref::get_naked_quads)) continue;

108

109 row_op(&grid::op_clear_row_rel, &ref::get_pointing_row);

110 col_op(&grid::op_clear_col_rel, &ref::get_pointing_row);

111 }

112

113 return is_finished();

114 }

115

116 void grid::print() const

117 {

118 // clang-format off

119 static const auto print_i = [](const auto& refs, uint16_t (ref::*func)(uint8_t) const, bool bits) {

120 for (uint8_t i = 0; i < 9; i++) {

121 for (uint8_t j = 0; j < 9; j++) {

122 const cord_t subgrid = {static_cast<uint8_t>(i / 3), static_cast<uint8_t>(j / 3)};

123 const cord_t field = {static_cast<uint8_t>(i % 3), static_cast<uint8_t>(j % 3)};

124

125 const uint16_t value = std::invoke(func, refs.at(subgrid), field);

126 const std::bitset<9>bts(value);

127

128 if (bits) std::cout << bts << " ";

129 else std::cout << value << " ";

130

131 if (j % 3 == 2) std::cout << " ";

132 }

133

134 std::cout << std::endl;

135 if (i % 3 == 2) std::cout << std::endl;

136 }

137 };

138 // clang-format on

139

140 std::cout << "Field: " << std::endl;

141 print_i(m_subgrids, &ref::get, true);

142

143 std::cout << "Refs: " << std::endl;

144 print_i(m_subgrids, &ref::get_ref, true);

145

146 std::cout << "Board: " << std::endl;

147 print_i(m_subgrids, &ref::get_value, false);

148 }

149

150 void grid::op_set(operation_t opr)

151 {

152 set(std::get<0>(opr), static_cast<uint8_t>(std::get<1>(opr)));

153 m_changed = true;

154 }

155

156 void grid::op_mask(operation_t opr)

157 {

158 mask(std::get<0>(opr), std::get<1>(opr));

159 m_changed = true;

160 }

161

162 void grid::op_clear(operation_t opr)

163 {

164 clear(std::get<0>(opr), static_cast<uint8_t>(std::get<1>(opr)));

165 m_changed = true;

166 }

167

168 void grid::op_clear_row(operation_t opr)

169 {

170 const auto val = static_cast<uint8_t>(std::get<1>(opr));

171 const auto abs = std::get<0>(opr);

172

173 const auto [r1, r2] = other_subgrid_row(abs.subgrid());

174 clear_row(cord_t(r1), abs.field(), val);

175 clear_row(cord_t(r2), abs.field(), val);

176

177 m_changed = true;

178 }

179

180 void grid::op_clear_col(operation_t opr)

181 {

182 const auto val = static_cast<uint8_t>(std::get<1>(opr));

183 const auto abs = std::get<0>(opr);

184

185 const auto [c1, c2] = other_subgrid_col(abs.subgrid());

186 clear_col(cord_t(c1), abs.field(), val);

187 clear_col(cord_t(c2), abs.field(), val);

188

189 m_changed = true;

190 }

191

192 void grid::op_clear_row_rel(operation_t opr)

193 {

194 const auto val = static_cast<uint8_t>(std::get<1>(opr));

195 const auto abs = std::get<0>(opr);

196

197 const auto [r1, r2] = other_subgrid_row(abs.row());

198 clear_row(cord_t((r1 / 3), abs.col()), r1 % 3, val);

199 clear_row(cord_t((r2 / 3), abs.col()), r2 % 3, val);

200

201 m_changed = true;

202 }

203

204 void grid::op_clear_col_rel(operation_t opr)

205 {

206 const auto val = static_cast<uint8_t>(std::get<1>(opr));

207 const auto abs = std::get<0>(opr);

208

209 const auto [c1, c2] = other_subgrid_row(abs.col());

210 clear_col(cord_t(abs.row(), c1 / 3), c1 % 3, val);

211 clear_col(cord_t(abs.row(), c2 / 3), c2 % 3, val);

212

213 m_changed = true;

214 }

215

216 void grid::set(acord_t abs, uint8_t value)

217 {

218 m_rows.at(abs.row()).set(abs.col(), value);

219 m_cols.at(abs.col()).set(abs.row(), value);

220 m_subgrids.at(abs.subgrid()).set(abs.field(), value);

221

222 clear_row(abs.subgrid(), 0, value);

223 clear_row(abs.subgrid(), 1, value);

224 clear_row(abs.subgrid(), 2, value);

225

226 const auto [r1, r2] = other_subgrid_row(abs.subgrid());

227 clear_row(cord_t(r1), abs.field().row(), value);

228 clear_row(cord_t(r2), abs.field().row(), value);

229

230 const auto [c1, c2] = other_subgrid_col(abs.subgrid());

231 clear_col(cord_t(c1), abs.field().col(), value);

232 clear_col(cord_t(c2), abs.field().col(), value);

233 }

234

235 void grid::mask(acord_t abs, uint16_t mask)

236 {

237 while (mask != 0) {

238 const auto idx = static_cast<uint8_t>(std::countr_zero(mask));

239 clear(abs, idx);

240 mask ^= 1ULL << idx;

241 }

242 }

243

244 void grid::clear(acord_t abs, uint8_t value)

245 {

246 m_subgrids.at(abs.subgrid()).clear(abs.field(), value);

247

248 m_rows.at(abs.row()).clear(abs.col(), value);

249 m_cols.at(abs.col()).clear(abs.row(), value);

250 }

251

252 void grid::clear_row(cord_t sbgrd, uint8_t row, uint8_t value)

253 {

254 for (uint8_t i = 0; i < 3; i++) {

255 clear({sbgrd, {row, i}}, value);

256 }

257 }

258

259 void grid::clear_col(cord_t sbgrd, uint8_t col, uint8_t value)

260 {

261 for (uint8_t i = 0; i < 3; i++) {

262 clear({sbgrd, {i, col}}, value);

263 }

264 }

265

266 bool grid::is_finished(uint8_t subgrid)

267 {

268 for (uint8_t i = 0; i < 9; i++) {

269 if (m_subgrids.at(subgrid).get_value(i) == 0) return false;

270 }

271 return true;

272 }

273

274 bool grid::is_finished()

275 {

276 for (uint8_t i = 0; i < 9; i++) {

277 if (!is_finished(i)) return false;

278 }

279 return true;

280 }