API tools faq
paste
Guest User

Untitled

a guest
Jan 18th, 2018
100
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 15.51 KB | None | 0 0
raw download clone embed print report
  1. #pragma once
  2. #include <intrin.h>
  3. #include <queue>
  4. #include <array>
  5. #include <optional>
  6. #include <iostream>
  7. #include <string>
  8. #include <numeric>
  9. #pragma intrinsic(_BitScanForward)
  10.  
  11. namespace sudoku
  12. {
  13. typedef uint32_t U32;
  14. constexpr std::array<int, 9> block_region(const int index)
  15. {
  16. const auto start = 27 * (index / 3) + 3 * (index % 3);
  17. return std::array<int, 9>{ start, start + 1, start + 2,
  18. start + 9, start + 10, start + 11,
  19. start + 18, start + 19, start + 20 };
  20.  
  21. }
  22. constexpr std::array<int, 9> row_region(const int col)
  23. {
  24. return std::array<int, 9>{ col, col + 9, col + 18, col + 27, col + 36, col + 45, col + 54, col + 63, col + 72};
  25. }
  26. constexpr std::array<int, 9> col_region(const int row)
  27. {
  28. return std::array<int, 9>{9 * row, 9 * row + 1, 9 * row + 2, 9 * row + 3, 9 * row + 4, 9 * row + 5, 9 * row + 6, 9 * row + 7, 9 * row + 8};
  29. }
  30. const int NEIGHBOR_TABLE[1620] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 18, 27, 36, 45, 54, 63, 72, 10, 11, 19, 20, 0, 2, 3, 4, 5, 6, 7, 8, 10, 19, 28, 37, 46, 55, 64, 73, 9, 11, 18, 20, 0, 1, 3, 4, 5, 6, 7, 8, 11, 20,
  31. 29, 38, 47, 56, 65, 74, 9, 10, 18, 19, 0, 1, 2, 4, 5, 6, 7, 8, 12, 21, 30, 39, 48, 57, 66, 75, 13, 14, 22, 23, 0, 1, 2, 3, 5, 6, 7, 8, 13, 22, 31, 40, 49, 58, 67, 76, 12, 14, 21, 23, 0, 1, 2, 3, 4, 6, 7, 8,
  32. 14, 23, 32, 41, 50, 59, 68, 77, 12, 13, 21, 22, 0, 1, 2, 3, 4, 5, 7, 8, 15, 24, 33, 42, 51, 60, 69, 78, 16, 17, 25, 26, 0, 1, 2, 3, 4, 5, 6, 8, 16, 25, 34, 43, 52, 61, 70, 79, 15, 17, 24, 26, 0, 1, 2, 3, 4,
  33. 5, 6, 7, 17, 26, 35, 44, 53, 62, 71, 80, 15, 16, 24, 25, 10, 11, 12, 13, 14, 15, 16, 17, 0, 18, 27, 36, 45, 54, 63, 72, 1, 2, 19, 20, 9, 11, 12, 13, 14, 15, 16, 17, 1, 19, 28, 37, 46, 55, 64, 73, 0, 2, 18, 20,
  34. 9, 10, 12, 13, 14, 15, 16, 17, 2, 20, 29, 38, 47, 56, 65, 74, 0, 1, 18, 19, 9, 10, 11, 13, 14, 15, 16, 17, 3, 21, 30, 39, 48, 57, 66, 75, 4, 5, 22, 23, 9, 10, 11, 12, 14, 15, 16, 17, 4, 22, 31, 40, 49, 58, 67,
  35. 76, 3, 5, 21, 23, 9, 10, 11, 12, 13, 15, 16, 17, 5, 23, 32, 41, 50, 59, 68, 77, 3, 4, 21, 22, 9, 10, 11, 12, 13, 14, 16, 17, 6, 24, 33, 42, 51, 60, 69, 78, 7, 8, 25, 26, 9, 10, 11, 12, 13, 14, 15, 17, 7, 25,
  36. 34, 43, 52, 61, 70, 79, 6, 8, 24, 26, 9, 10, 11, 12, 13, 14, 15, 16, 8, 26, 35, 44, 53, 62, 71, 80, 6, 7, 24, 25, 19, 20, 21, 22, 23, 24, 25, 26, 0, 9, 27, 36, 45, 54, 63, 72, 1, 2, 10, 11, 18, 20, 21, 22, 23,
  37. 24, 25, 26, 1, 10, 28, 37, 46, 55, 64, 73, 0, 2, 9, 11, 18, 19, 21, 22, 23, 24, 25, 26, 2, 11, 29, 38, 47, 56, 65, 74, 0, 1, 9, 10, 18, 19, 20, 22, 23, 24, 25, 26, 3, 12, 30, 39, 48, 57, 66, 75, 4, 5, 13, 14,
  38. 18, 19, 20, 21, 23, 24, 25, 26, 4, 13, 31, 40, 49, 58, 67, 76, 3, 5, 12, 14, 18, 19, 20, 21, 22, 24, 25, 26, 5, 14, 32, 41, 50, 59, 68, 77, 3, 4, 12, 13, 18, 19, 20, 21, 22, 23, 25, 26, 6, 15, 33, 42, 51, 60,
  39. 69, 78, 7, 8, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 7, 16, 34, 43, 52, 61, 70, 79, 6, 8, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 8, 17, 35, 44, 53, 62, 71, 80, 6, 7, 15, 16, 28, 29, 30, 31, 32, 33, 34, 35, 0,
  40. 9, 18, 36, 45, 54, 63, 72, 37, 38, 46, 47, 27, 29, 30, 31, 32, 33, 34, 35, 1, 10, 19, 37, 46, 55, 64, 73, 36, 38, 45, 47, 27, 28, 30, 31, 32, 33, 34, 35, 2, 11, 20, 38, 47, 56, 65, 74, 36, 37, 45, 46, 27, 28,
  41. 29, 31, 32, 33, 34, 35, 3, 12, 21, 39, 48, 57, 66, 75, 40, 41, 49, 50, 27, 28, 29, 30, 32, 33, 34, 35, 4, 13, 22, 40, 49, 58, 67, 76, 39, 41, 48, 50, 27, 28, 29, 30, 31, 33, 34, 35, 5, 14, 23, 41, 50, 59, 68,
  42. 77, 39, 40, 48, 49, 27, 28, 29, 30, 31, 32, 34, 35, 6, 15, 24, 42, 51, 60, 69, 78, 43, 44, 52, 53, 27, 28, 29, 30, 31, 32, 33, 35, 7, 16, 25, 43, 52, 61, 70, 79, 42, 44, 51, 53, 27, 28, 29, 30, 31, 32, 33, 34,
  43. 8, 17, 26, 44, 53, 62, 71, 80, 42, 43, 51, 52, 37, 38, 39, 40, 41, 42, 43, 44, 0, 9, 18, 27, 45, 54, 63, 72, 28, 29, 46, 47, 36, 38, 39, 40, 41, 42, 43, 44, 1, 10, 19, 28, 46, 55, 64, 73, 27, 29, 45, 47, 36, 37,
  44. 39, 40, 41, 42, 43, 44, 2, 11, 20, 29, 47, 56, 65, 74, 27, 28, 45, 46, 36, 37, 38, 40, 41, 42, 43, 44, 3, 12, 21, 30, 48, 57, 66, 75, 31, 32, 49, 50, 36, 37, 38, 39, 41, 42, 43, 44, 4, 13, 22, 31, 49, 58, 67,
  45. 76, 30, 32, 48, 50, 36, 37, 38, 39, 40, 42, 43, 44, 5, 14, 23, 32, 50, 59, 68, 77, 30, 31, 48, 49, 36, 37, 38, 39, 40, 41, 43, 44, 6, 15, 24, 33, 51, 60, 69, 78, 34, 35, 52, 53, 36, 37, 38, 39, 40, 41, 42, 44,
  46. 7, 16, 25, 34, 52, 61, 70, 79, 33, 35, 51, 53, 36, 37, 38, 39, 40, 41, 42, 43, 8, 17, 26, 35, 53, 62, 71, 80, 33, 34, 51, 52, 46, 47, 48, 49, 50, 51, 52, 53, 0, 9, 18, 27, 36, 54, 63, 72, 28, 29, 37, 38, 45, 47,
  47. 48, 49, 50, 51, 52, 53, 1, 10, 19, 28, 37, 55, 64, 73, 27, 29, 36, 38, 45, 46, 48, 49, 50, 51, 52, 53, 2, 11, 20, 29, 38, 56, 65, 74, 27, 28, 36, 37, 45, 46, 47, 49, 50, 51, 52, 53, 3, 12, 21, 30, 39, 57, 66, 75,
  48. 31, 32, 40, 41, 45, 46, 47, 48, 50, 51, 52, 53, 4, 13, 22, 31, 40, 58, 67, 76, 30, 32, 39, 41, 45, 46, 47, 48, 49, 51, 52, 53, 5, 14, 23, 32, 41, 59, 68, 77, 30, 31, 39, 40, 45, 46, 47, 48, 49, 50, 52, 53, 6,
  49. 15, 24, 33, 42, 60, 69, 78, 34, 35, 43, 44, 45, 46, 47, 48, 49, 50, 51, 53, 7, 16, 25, 34, 43, 61, 70, 79, 33, 35, 42, 44, 45, 46, 47, 48, 49, 50, 51, 52, 8, 17, 26, 35, 44, 62, 71, 80, 33, 34, 42, 43, 55, 56,
  50. 57, 58, 59, 60, 61, 62, 0, 9, 18, 27, 36, 45, 63, 72, 64, 65, 73, 74, 54, 56, 57, 58, 59, 60, 61, 62, 1, 10, 19, 28, 37, 46, 64, 73, 63, 65, 72, 74, 54, 55, 57, 58, 59, 60, 61, 62, 2, 11, 20, 29, 38, 47, 65, 74,
  51. 63, 64, 72, 73, 54, 55, 56, 58, 59, 60, 61, 62, 3, 12, 21, 30, 39, 48, 66, 75, 67, 68, 76, 77, 54, 55, 56, 57, 59, 60, 61, 62, 4, 13, 22, 31, 40, 49, 67, 76, 66, 68, 75, 77, 54, 55, 56, 57, 58, 60, 61, 62, 5,
  52. 14, 23, 32, 41, 50, 68, 77, 66, 67, 75, 76, 54, 55, 56, 57, 58, 59, 61, 62, 6, 15, 24, 33, 42, 51, 69, 78, 70, 71, 79, 80, 54, 55, 56, 57, 58, 59, 60, 62, 7, 16, 25, 34, 43, 52, 70, 79, 69, 71, 78, 80, 54, 55,
  53. 56, 57, 58, 59, 60, 61, 8, 17, 26, 35, 44, 53, 71, 80, 69, 70, 78, 79, 64, 65, 66, 67, 68, 69, 70, 71, 0, 9, 18, 27, 36, 45, 54, 72, 55, 56, 73, 74, 63, 65, 66, 67, 68, 69, 70, 71, 1, 10, 19, 28, 37, 46, 55, 73,
  54. 54, 56, 72, 74, 63, 64, 66, 67, 68, 69, 70, 71, 2, 11, 20, 29, 38, 47, 56, 74, 54, 55, 72, 73, 63, 64, 65, 67, 68, 69, 70, 71, 3, 12, 21, 30, 39, 48, 57, 75, 58, 59, 76, 77, 63, 64, 65, 66, 68, 69, 70, 71, 4,
  55. 13, 22, 31, 40, 49, 58, 76, 57, 59, 75, 77, 63, 64, 65, 66, 67, 69, 70, 71, 5, 14, 23, 32, 41, 50, 59, 77, 57, 58, 75, 76, 63, 64, 65, 66, 67, 68, 70, 71, 6, 15, 24, 33, 42, 51, 60, 78, 61, 62, 79, 80, 63, 64,
  56. 65, 66, 67, 68, 69, 71, 7, 16, 25, 34, 43, 52, 61, 79, 60, 62, 78, 80, 63, 64, 65, 66, 67, 68, 69, 70, 8, 17, 26, 35, 44, 53, 62, 80, 60, 61, 78, 79, 73, 74, 75, 76, 77, 78, 79, 80, 0, 9, 18, 27, 36, 45, 54, 63,
  57. 55, 56, 64, 65, 72, 74, 75, 76, 77, 78, 79, 80, 1, 10, 19, 28, 37, 46, 55, 64, 54, 56, 63, 65, 72, 73, 75, 76, 77, 78, 79, 80, 2, 11, 20, 29, 38, 47, 56, 65, 54, 55, 63, 64, 72, 73, 74, 76, 77, 78, 79, 80, 3, 12,
  58. 21, 30, 39, 48, 57, 66, 58, 59, 67, 68, 72, 73, 74, 75, 77, 78, 79, 80, 4, 13, 22, 31, 40, 49, 58, 67, 57, 59, 66, 68, 72, 73, 74, 75, 76, 78, 79, 80, 5, 14, 23, 32, 41, 50, 59, 68, 57, 58, 66, 67, 72, 73, 74,
  59. 75, 76, 77, 79, 80, 6, 15, 24, 33, 42, 51, 60, 69, 61, 62, 70, 71, 72, 73, 74, 75, 76, 77, 78, 80, 7, 16, 25, 34, 43, 52, 61, 70, 60, 62, 69, 71, 72, 73, 74, 75, 76, 77, 78, 79, 8, 17, 26, 35, 44, 53, 62, 71,
  60. 60, 61, 69, 70 };
  61. const U32 MASK[9] = {
  62. 0x00000001,
  63. 0x00000002,
  64. 0x00000004,
  65. 0x00000008,
  66. 0x00000010,
  67. 0x00000020,
  68. 0x00000040,
  69. 0x00000080,
  70. 0x00000100 };
  71. const U32 MASK_ALL = 0x000001FF;
  72.  
  73. /* a REGION can be either a BLOCK, ROW, or COL*/
  74. const std::array<int, 9> BLOCK[9] = { block_region(0), block_region(1), block_region(2),
  75. block_region(3), block_region(4), block_region(5),
  76. block_region(6), block_region(7), block_region(8) };
  77. const std::array<int, 9> ROW[9] = { row_region(0), row_region(1), row_region(2),
  78. row_region(3),row_region(4), row_region(5),
  79. row_region(6), row_region(7), row_region(8) };
  80. const std::array<int, 9> COL[9] = { col_region(0), col_region(1), col_region(2),
  81. col_region(3),col_region(4), col_region(5),
  82. col_region(6), col_region(7), col_region(8) };
  83. enum class Status
  84. {
  85. Inconsistent, Inconclusive, Solved
  86. };
  87.  
  88. struct Arc
  89. {
  90. int priority;
  91. int from;
  92. int to;
  93. };
  94.  
  95. inline bool operator<(const Arc & lhs, const Arc & rhs)
  96. {
  97. return lhs.priority > rhs.priority;
  98. }
  99.  
  100. inline void revise(int priority, int from, std::priority_queue<Arc> & arcs)
  101. {
  102. for (auto i = 0; i < 20; i++)
  103. {
  104. auto neighbor = NEIGHBOR_TABLE[20 * from + i];
  105. arcs.push(Arc{ priority, neighbor,from });
  106. }
  107. }
  108.  
  109. template<typename ForwardIt>
  110. bool evaluate(ForwardIt forward_iterator);
  111.  
  112. template<typename ForwardIt>
  113. class SudokuBoard
  114. {
  115. friend bool evaluate<ForwardIt>(ForwardIt first);
  116. std::array<U32, 81> domains;
  117. ForwardIt first;
  118. explicit SudokuBoard(ForwardIt it) : first(it)
  119. {
  120. static_assert(std::is_integral<typename std::iterator_traits<ForwardIt>::value_type>::value, "Integral value type required.");
  121. for (auto i = 0; i < 81; i++)
  122. {
  123. if (*it == 0)
  124. {
  125. domains[i] = MASK_ALL;
  126. }
  127. else
  128. {
  129. domains[i] = MASK[*it - 1];
  130. }
  131. ++it;
  132. }
  133. }
  134.  
  135. Status make_consistent(std::priority_queue<Arc> & arcs)
  136. {
  137. while (!arcs.empty())
  138. {
  139. const auto arc = arcs.top();
  140. arcs.pop();
  141. unsigned long to_zval;
  142. if (__popcnt(domains[arc.to]) == 1)
  143. {
  144. _BitScanForward(&to_zval, domains[arc.to]);
  145. auto prev_domain = domains[arc.from];
  146. domains[arc.from] &= ~domains[arc.to];
  147. if (domains[arc.from] != prev_domain) {
  148. if (!domains[arc.from])
  149. {
  150. return Status::Inconsistent;
  151. }
  152. int hamming_weight = __popcnt(domains[arc.from]);
  153. if (hamming_weight == 1)
  154. {
  155. unsigned long from_zval;
  156. _BitScanForward(&from_zval, domains[arc.from]);
  157. }
  158. revise(hamming_weight, arc.from, arcs);
  159. }
  160. }
  161. }
  162. return Status::Inconclusive;
  163. }
  164.  
  165. std::priority_queue<Arc> make_arcs()
  166. {
  167. std::priority_queue<Arc> arcs;
  168. int priorities[81];
  169. for (auto index = 0; index < 81; index++)
  170. {
  171. priorities[index] = __popcnt(domains[index]);
  172. }
  173. for (auto i = 0; i < 1620; i++)
  174. {
  175. arcs.push(Arc{ priorities[NEIGHBOR_TABLE[i]], i / 20, NEIGHBOR_TABLE[i] });
  176. }
  177. return arcs;
  178. }
  179.  
  180. bool solved()
  181. {
  182. for (auto domain : domains)
  183. {
  184. if (__popcnt(domain) != 1)
  185. {
  186. return false;
  187. }
  188. }
  189. return true;
  190. }
  191.  
  192. int min_weight()
  193. {
  194. auto min_index = -1;
  195. auto min = 10;
  196. for (auto index = 0; index < 81; index++)
  197. {
  198. int hamming_weight = __popcnt(domains[index]);
  199. // 2 is a lower-bound
  200. if (hamming_weight == 2)
  201. {
  202. return index;
  203. }
  204. if (hamming_weight != 1 && hamming_weight < min)
  205. {
  206. min = hamming_weight;
  207. min_index = index;
  208. }
  209. }
  210. return min_index;
  211. }
  212.  
  213. SudokuBoard branch(int index, int val) const
  214. {
  215. auto clone(*this);
  216. clone.domains[index] = MASK[val - 1];
  217. return clone;
  218. }
  219.  
  220. bool evaluate(std::priority_queue<Arc> arcs)
  221. {
  222. // Consume current arcs
  223. auto res = make_consistent(arcs);
  224. switch (res) {
  225. case Status::Solved: return true;
  226. case Status::Inconsistent: return false;
  227. case Status::Inconclusive: break;
  228. }
  229. if (solved())
  230. {
  231. update_iterator();
  232. return true;
  233. }
  234. auto unassigned_index = min_weight();
  235. auto value = 0;
  236. unsigned long pos;
  237. auto current = domains[unassigned_index];
  238. while (_BitScanForward(&pos, current))
  239. {
  240. value += (pos + 1);
  241. current >>= (pos + 1);
  242. auto br = branch(unassigned_index, value);
  243. revise(1, unassigned_index, arcs);
  244. if (br.evaluate(arcs))
  245. {
  246. return true;
  247. }
  248. }
  249. return false;
  250. }
  251.  
  252. bool evaluate()
  253. {
  254. return evaluate(make_arcs());
  255. }
  256.  
  257. void update_iterator()
  258. {
  259. for (auto index = 0; index < 81; index++)
  260. {
  261. if (__popcnt(domains[index]) == 1)
  262. {
  263. unsigned long pos;
  264. _BitScanForward(&pos, domains[index]);
  265. auto val = pos + 1;
  266. *first = val;
  267. ++first;
  268. }
  269. }
  270. }
  271. };
  272.  
  273. inline std::string str(int dst[81])
  274. {
  275. std::string str;
  276. str.reserve(81);
  277. for (auto index = 0; index < 81; index++)
  278. {
  279. str.append(std::to_string(dst[index]));
  280. }
  281. return str;
  282. }
  283. inline std::string pretty_str(int dst[81])
  284. {
  285. std::string str;
  286. str.reserve(90);
  287. for (auto row = 0; row < 9; row++)
  288. {
  289. for (auto col = 0; col < 9; col++)
  290. {
  291. auto index = row * 9 + col;
  292. if (dst[index] == 0)
  293. {
  294. str.append("[ ]");
  295. }
  296. else
  297. {
  298. str.append("[");
  299. str.append(std::to_string(dst[index]));
  300. str.append("]");
  301. }
  302. }
  303. str.append("n");
  304. }
  305. return str;
  306. }
  307.  
  308. template<typename ForwardIt>
  309. inline bool evaluate(ForwardIt first)
  310. {
  311. SudokuBoard<ForwardIt> su(first);
  312. return su.evaluate();
  313. }
  314.  
  315. inline bool evaluate(std::istream & in, std::ostream & out, bool pretty = false)
  316. {
  317. int board[81];
  318. auto i = 0;
  319. for (std::string line; std::getline(in, line) && i < 81;)
  320. {
  321. for (const auto c : line)
  322. {
  323. auto val = c - '0';
  324. board[i++] = (val > 0 && val < 10) ? val : 0;
  325. }
  326. }
  327. std::fill(board + i, board + 81, 0);
  328. auto status = evaluate(board);
  329. if (pretty)
  330. {
  331. out << pretty_str(board);
  332. }
  333. else
  334. {
  335. out << str(board);
  336. }
  337. return status;
  338. }
  339. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!