Назад к лучшим решениям Status: AC, problem ZSUD, contest ZEL07. By werewolf (Werewolf), 2007-02-25 18:23:31.
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. typedef unsigned short ushort;
  6. #define BASE 9
  7.  
  8. static const unsigned char BitsSetTable256[] =
  9. {
  10. 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  11. 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  12. 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  13. 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  14. 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  15. 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  16. 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  17. 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  18. 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  19. 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  20. 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  21. 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  22. 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  23. 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  24. 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  25. 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
  26. };
  27.  
  28. static const char LogTable256[] =
  29. {
  30. 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
  31. 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  32. 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  33. 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  34. 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  35. 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  36. 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  37. 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  38. 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  39. 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  40. 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  41. 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  42. 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  43. 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  44. 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  45. 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
  46. };
  47.  
  48. static const char group_to_cell[3][BASE][BASE] =
  49. {
  50. {
  51. { 0, 1, 2, 3, 4, 5, 6, 7, 8 },
  52. { 9, 10, 11, 12, 13, 14, 15, 16, 17 },
  53. { 18, 19, 20, 21, 22, 23, 24, 25, 26 },
  54. { 27, 28, 29, 30, 31, 32, 33, 34, 35 },
  55. { 36, 37, 38, 39, 40, 41, 42, 43, 44 },
  56. { 45, 46, 47, 48, 49, 50, 51, 52, 53 },
  57. { 54, 55, 56, 57, 58, 59, 60, 61, 62 },
  58. { 63, 64, 65, 66, 67, 68, 69, 70, 71 },
  59. { 72, 73, 74, 75, 76, 77, 78, 79, 80 }
  60. },
  61. {
  62. { 0, 9, 18, 27, 36, 45, 54, 63, 72 },
  63. { 1, 10, 19, 28, 37, 46, 55, 64, 73 },
  64. { 2, 11, 20, 29, 38, 47, 56, 65, 74 },
  65. { 3, 12, 21, 30, 39, 48, 57, 66, 75 },
  66. { 4, 13, 22, 31, 40, 49, 58, 67, 76 },
  67. { 5, 14, 23, 32, 41, 50, 59, 68, 77 },
  68. { 6, 15, 24, 33, 42, 51, 60, 69, 78 },
  69. { 7, 16, 25, 34, 43, 52, 61, 70, 79 },
  70. { 8, 17, 26, 35, 44, 53, 62, 71, 80 }
  71. },
  72. {
  73. { 0, 1, 2, 9, 10, 11, 18, 19, 20 },
  74. { 3, 4, 5, 12, 13, 14, 21, 22, 23 },
  75. { 6, 7, 8, 15, 16, 17, 24, 25, 26 },
  76. { 27, 28, 29, 36, 37, 38, 45, 46, 47 },
  77. { 30, 31, 32, 39, 40, 41, 48, 49, 50 },
  78. { 33, 34, 35, 42, 43, 44, 51, 52, 53 },
  79. { 54, 55, 56, 63, 64, 65, 72, 73, 74 },
  80. { 57, 58, 59, 66, 67, 68, 75, 76, 77 },
  81. { 60, 61, 62, 69, 70, 71, 78, 79, 80 }
  82. },
  83. };
  84.  
  85. static const char cell_to_group[BASE*BASE][3][2] =
  86. {
  87. {{ 0, 0 }, { 0, 0 }, { 0, 0 }},
  88. {{ 0, 1 }, { 1, 0 }, { 0, 1 }},
  89. {{ 0, 2 }, { 2, 0 }, { 0, 2 }},
  90. {{ 0, 3 }, { 3, 0 }, { 1, 0 }},
  91. {{ 0, 4 }, { 4, 0 }, { 1, 1 }},
  92. {{ 0, 5 }, { 5, 0 }, { 1, 2 }},
  93. {{ 0, 6 }, { 6, 0 }, { 2, 0 }},
  94. {{ 0, 7 }, { 7, 0 }, { 2, 1 }},
  95. {{ 0, 8 }, { 8, 0 }, { 2, 2 }},
  96. {{ 1, 0 }, { 0, 1 }, { 0, 3 }},
  97. {{ 1, 1 }, { 1, 1 }, { 0, 4 }},
  98. {{ 1, 2 }, { 2, 1 }, { 0, 5 }},
  99. {{ 1, 3 }, { 3, 1 }, { 1, 3 }},
  100. {{ 1, 4 }, { 4, 1 }, { 1, 4 }},
  101. {{ 1, 5 }, { 5, 1 }, { 1, 5 }},
  102. {{ 1, 6 }, { 6, 1 }, { 2, 3 }},
  103. {{ 1, 7 }, { 7, 1 }, { 2, 4 }},
  104. {{ 1, 8 }, { 8, 1 }, { 2, 5 }},
  105. {{ 2, 0 }, { 0, 2 }, { 0, 6 }},
  106. {{ 2, 1 }, { 1, 2 }, { 0, 7 }},
  107. {{ 2, 2 }, { 2, 2 }, { 0, 8 }},
  108. {{ 2, 3 }, { 3, 2 }, { 1, 6 }},
  109. {{ 2, 4 }, { 4, 2 }, { 1, 7 }},
  110. {{ 2, 5 }, { 5, 2 }, { 1, 8 }},
  111. {{ 2, 6 }, { 6, 2 }, { 2, 6 }},
  112. {{ 2, 7 }, { 7, 2 }, { 2, 7 }},
  113. {{ 2, 8 }, { 8, 2 }, { 2, 8 }},
  114. {{ 3, 0 }, { 0, 3 }, { 3, 0 }},
  115. {{ 3, 1 }, { 1, 3 }, { 3, 1 }},
  116. {{ 3, 2 }, { 2, 3 }, { 3, 2 }},
  117. {{ 3, 3 }, { 3, 3 }, { 4, 0 }},
  118. {{ 3, 4 }, { 4, 3 }, { 4, 1 }},
  119. {{ 3, 5 }, { 5, 3 }, { 4, 2 }},
  120. {{ 3, 6 }, { 6, 3 }, { 5, 0 }},
  121. {{ 3, 7 }, { 7, 3 }, { 5, 1 }},
  122. {{ 3, 8 }, { 8, 3 }, { 5, 2 }},
  123. {{ 4, 0 }, { 0, 4 }, { 3, 3 }},
  124. {{ 4, 1 }, { 1, 4 }, { 3, 4 }},
  125. {{ 4, 2 }, { 2, 4 }, { 3, 5 }},
  126. {{ 4, 3 }, { 3, 4 }, { 4, 3 }},
  127. {{ 4, 4 }, { 4, 4 }, { 4, 4 }},
  128. {{ 4, 5 }, { 5, 4 }, { 4, 5 }},
  129. {{ 4, 6 }, { 6, 4 }, { 5, 3 }},
  130. {{ 4, 7 }, { 7, 4 }, { 5, 4 }},
  131. {{ 4, 8 }, { 8, 4 }, { 5, 5 }},
  132. {{ 5, 0 }, { 0, 5 }, { 3, 6 }},
  133. {{ 5, 1 }, { 1, 5 }, { 3, 7 }},
  134. {{ 5, 2 }, { 2, 5 }, { 3, 8 }},
  135. {{ 5, 3 }, { 3, 5 }, { 4, 6 }},
  136. {{ 5, 4 }, { 4, 5 }, { 4, 7 }},
  137. {{ 5, 5 }, { 5, 5 }, { 4, 8 }},
  138. {{ 5, 6 }, { 6, 5 }, { 5, 6 }},
  139. {{ 5, 7 }, { 7, 5 }, { 5, 7 }},
  140. {{ 5, 8 }, { 8, 5 }, { 5, 8 }},
  141. {{ 6, 0 }, { 0, 6 }, { 6, 0 }},
  142. {{ 6, 1 }, { 1, 6 }, { 6, 1 }},
  143. {{ 6, 2 }, { 2, 6 }, { 6, 2 }},
  144. {{ 6, 3 }, { 3, 6 }, { 7, 0 }},
  145. {{ 6, 4 }, { 4, 6 }, { 7, 1 }},
  146. {{ 6, 5 }, { 5, 6 }, { 7, 2 }},
  147. {{ 6, 6 }, { 6, 6 }, { 8, 0 }},
  148. {{ 6, 7 }, { 7, 6 }, { 8, 1 }},
  149. {{ 6, 8 }, { 8, 6 }, { 8, 2 }},
  150. {{ 7, 0 }, { 0, 7 }, { 6, 3 }},
  151. {{ 7, 1 }, { 1, 7 }, { 6, 4 }},
  152. {{ 7, 2 }, { 2, 7 }, { 6, 5 }},
  153. {{ 7, 3 }, { 3, 7 }, { 7, 3 }},
  154. {{ 7, 4 }, { 4, 7 }, { 7, 4 }},
  155. {{ 7, 5 }, { 5, 7 }, { 7, 5 }},
  156. {{ 7, 6 }, { 6, 7 }, { 8, 3 }},
  157. {{ 7, 7 }, { 7, 7 }, { 8, 4 }},
  158. {{ 7, 8 }, { 8, 7 }, { 8, 5 }},
  159. {{ 8, 0 }, { 0, 8 }, { 6, 6 }},
  160. {{ 8, 1 }, { 1, 8 }, { 6, 7 }},
  161. {{ 8, 2 }, { 2, 8 }, { 6, 8 }},
  162. {{ 8, 3 }, { 3, 8 }, { 7, 6 }},
  163. {{ 8, 4 }, { 4, 8 }, { 7, 7 }},
  164. {{ 8, 5 }, { 5, 8 }, { 7, 8 }},
  165. {{ 8, 6 }, { 6, 8 }, { 8, 6 }},
  166. {{ 8, 7 }, { 7, 8 }, { 8, 7 }},
  167. {{ 8, 8 }, { 8, 8 }, { 8, 8 }}
  168. };
  169. ushort comb91[] =
  170. {
  171. 0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80, 0x100
  172. };
  173. ushort comb92[] =
  174. {
  175. 0x3, 0x5, 0x6, 0x9, 0xA, 0xC, 0x11, 0x12, 0x14, 0x18,
  176. 0x21, 0x22, 0x24, 0x28, 0x30, 0x41, 0x42, 0x44, 0x48, 0x50,
  177. 0x60, 0x81, 0x82, 0x84, 0x88, 0x90, 0xA0, 0xC0, 0x101, 0x102,
  178. 0x104, 0x108, 0x110, 0x120, 0x140, 0x180
  179. };
  180.  
  181. ushort comb93[] =
  182. {
  183. 0x7, 0xB, 0xD, 0xE, 0x13, 0x15, 0x16, 0x19, 0x1A, 0x1C,
  184. 0x23, 0x25, 0x26, 0x29, 0x2A, 0x2C, 0x31, 0x32, 0x34, 0x38,
  185. 0x43, 0x45, 0x46, 0x49, 0x4A, 0x4C, 0x51, 0x52, 0x54, 0x58,
  186. 0x61, 0x62, 0x64, 0x68, 0x70, 0x83, 0x85, 0x86, 0x89, 0x8A,
  187. 0x8C, 0x91, 0x92, 0x94, 0x98, 0xA1, 0xA2, 0xA4, 0xA8, 0xB0,
  188. 0xC1, 0xC2, 0xC4, 0xC8, 0xD0, 0xE0, 0x103, 0x105, 0x106, 0x109,
  189. 0x10A, 0x10C, 0x111, 0x112, 0x114, 0x118, 0x121, 0x122, 0x124, 0x128,
  190. 0x130, 0x141, 0x142, 0x144, 0x148, 0x150, 0x160, 0x181, 0x182, 0x184,
  191. 0x188, 0x190, 0x1A0, 0x1C0
  192. };
  193.  
  194. ushort comb94[] =
  195. {
  196. 0xF, 0x17, 0x1B, 0x1D, 0x1E, 0x27, 0x2B, 0x2D, 0x2E, 0x33,
  197. 0x35, 0x36, 0x39, 0x3A, 0x3C, 0x47, 0x4B, 0x4D, 0x4E, 0x53,
  198. 0x55, 0x56, 0x59, 0x5A, 0x5C, 0x63, 0x65, 0x66, 0x69, 0x6A,
  199. 0x6C, 0x71, 0x72, 0x74, 0x78, 0x87, 0x8B, 0x8D, 0x8E, 0x93,
  200. 0x95, 0x96, 0x99, 0x9A, 0x9C, 0xA3, 0xA5, 0xA6, 0xA9, 0xAA,
  201. 0xAC, 0xB1, 0xB2, 0xB4, 0xB8, 0xC3, 0xC5, 0xC6, 0xC9, 0xCA,
  202. 0xCC, 0xD1, 0xD2, 0xD4, 0xD8, 0xE1, 0xE2, 0xE4, 0xE8, 0xF0,
  203. 0x107, 0x10B, 0x10D, 0x10E, 0x113, 0x115, 0x116, 0x119, 0x11A, 0x11C,
  204. 0x123, 0x125, 0x126, 0x129, 0x12A, 0x12C, 0x131, 0x132, 0x134, 0x138,
  205. 0x143, 0x145, 0x146, 0x149, 0x14A, 0x14C, 0x151, 0x152, 0x154, 0x158,
  206. 0x161, 0x162, 0x164, 0x168, 0x170, 0x183, 0x185, 0x186, 0x189, 0x18A,
  207. 0x18C, 0x191, 0x192, 0x194, 0x198, 0x1A1, 0x1A2, 0x1A4, 0x1A8, 0x1B0,
  208. 0x1C1, 0x1C2, 0x1C4, 0x1C8, 0x1D0, 0x1E0
  209. };
  210.  
  211. struct _combination
  212. {
  213. ushort count;
  214. ushort * array;
  215. };
  216.  
  217. struct _combination comb[] =
  218. {
  219. {0,0},
  220. { sizeof(comb91)/sizeof(ushort), comb91 },
  221. { sizeof(comb92)/sizeof(ushort), comb92 },
  222. { sizeof(comb93)/sizeof(ushort), comb93 },
  223. { sizeof(comb94)/sizeof(ushort), comb94 },
  224. };
  225.  
  226.  
  227. #define group_type_row 0
  228. #define group_type_col 1
  229. #define group_type_reg 2
  230. // 2^^BASE-1
  231. #define MASK_INITIAL_STATE 0x1FF
  232.  
  233. #define get_bit_count_16(u) (BitsSetTable256[((unsigned char*)&(u))[0]] + BitsSetTable256[((unsigned char*)&(u))[1]])
  234.  
  235. #define get_bit_set_16(u) (((unsigned char*)&(u))[1]?LogTable256[((unsigned char*)&(u))[1]] + 0x8:LogTable256[((unsigned char*)&(u))[0]])
  236.  
  237.  
  238. #define get_cellId(groupType, groupId, itemId) (group_to_cell[groupType][groupId][itemId])
  239.  
  240. #define get_groupId(cellId, groupType) (cell_to_group[cellId][groupType][0])
  241. #define get_itemId(cellId, groupType) (cell_to_group[cellId][groupType][1])
  242.  
  243. #define num_to_bits(n) (1 << (n))
  244.  
  245.  
  246. char solvedtable[BASE*BASE+1];
  247. ushort masktable[BASE*BASE];
  248. ushort checkmask[BASE*3];
  249. ushort nfound;
  250.  
  251. typedef struct _state
  252. {
  253. ushort nCandidates;
  254. ushort changedId;
  255. ushort changedTo;
  256. char solvedtable[BASE*BASE+1];
  257. ushort masktable[BASE*BASE];
  258. ushort checkmask[BASE*3];
  259. ushort nfound;
  260. struct _state * next;
  261. }state, *pstate;
  262.  
  263. pstate state_stack = 0;
  264.  
  265. int popState(ushort *nCandidates, ushort * changedId, ushort * changedTo)
  266. {
  267. pstate to_del;
  268. if(!state_stack)
  269. return 0;
  270.  
  271. *nCandidates = state_stack->nCandidates;
  272. *changedId = state_stack->changedId;
  273. *changedTo = state_stack->changedTo;
  274.  
  275. memcpy(solvedtable, state_stack->solvedtable, sizeof(solvedtable));
  276. memcpy(masktable, state_stack->masktable, sizeof(masktable));
  277. memcpy(checkmask, state_stack->checkmask, sizeof(checkmask));
  278. nfound = state_stack->nfound;
  279. to_del = state_stack;
  280. state_stack = state_stack->next;
  281. free(to_del);
  282. return 1;
  283. }
  284. void pushState(ushort nCandidates, ushort changedId, ushort changedTo)
  285. {
  286. pstate new_state = 0;
  287. new_state = malloc(sizeof(state));
  288. new_state->changedId = changedId;
  289. new_state->changedTo = changedTo;
  290. new_state->nCandidates = nCandidates;
  291.  
  292. memcpy(new_state->solvedtable, solvedtable, sizeof(solvedtable));
  293. memcpy(new_state->masktable, masktable, sizeof(masktable));
  294. memcpy(new_state->checkmask, checkmask, sizeof(checkmask));
  295. new_state->nfound = nfound;
  296. new_state->next = state_stack;
  297. state_stack = new_state;
  298. }
  299. int findNextTrial(ushort *nCandidates, ushort * changedId, ushort * changedTo)
  300. {
  301. int i, j;
  302. do
  303. {
  304. for(i = *changedId; i < BASE*BASE; i++)
  305. {
  306. if(get_bit_count_16(masktable[i]) == *nCandidates)
  307. {
  308. while(*changedTo != 0x100)
  309. {
  310. if(*changedTo == 0) *changedTo = 1;
  311. else *changedTo <<= 1;
  312. if(masktable[i] & *changedTo)
  313. {
  314. *changedId = i;
  315. if(get_bit_set_16(*changedTo) == get_bit_set_16(masktable[i]))
  316. return 0;
  317. else
  318. return 1;
  319. }
  320. }
  321. *changedTo = 0;
  322. }
  323. }
  324. *changedId = 0;
  325. (*nCandidates)++;
  326. }while( *nCandidates != 10);
  327.  
  328. return -1;
  329. }
  330. void initBuffers()
  331. {
  332. int i;
  333. nfound = 0;
  334. memset(checkmask, 0, sizeof(checkmask));
  335. for( i = 0; i < BASE*BASE; i++ )
  336. {
  337. masktable[i] = MASK_INITIAL_STATE;
  338. solvedtable[i] = '.';
  339. }
  340. solvedtable[BASE*BASE] = '\0';
  341. }
  342.  
  343.  
  344.  
  345. void inputValues()
  346. {
  347. int i;
  348. gets(solvedtable);
  349. for( i = 0; i < BASE*BASE; i++ )
  350. {
  351. if( solvedtable[i] != '.' )
  352. masktable[i] = num_to_bits(solvedtable[i] - '1');
  353. }
  354. }
  355.  
  356.  
  357. void outputTable()
  358. {
  359. /*
  360. ----- -----
  361. |. . * * *
  362. | . * 1 *
  363. | . * * *
  364. ----- -----
  365. */
  366. int i, j, k;
  367. for(i = 0; i < 9; i++)
  368. {
  369. if(i%3==0)
  370. printf(" ----- ----- ----- ----- ----- ----- ----- ----- -----\n");
  371. else
  372. printf("\n\n");
  373. for(k = 0; k < 3; k++)
  374. {
  375. for(j = 0; j < 9; j++)
  376. {
  377. if(j % 3 == 0)
  378. printf("|");
  379. else
  380. printf(" ");
  381. if(masktable[i*BASE+j] == 0)
  382. {
  383. if(k==1)
  384. printf(" %c ", solvedtable[i*BASE+j]);
  385. else
  386. printf(" ");
  387. }else
  388. printf("%c %c %c", num_to_bits(k*3 + 0)&masktable[i*BASE+j]?'.':' ',
  389. num_to_bits(k*3 + 1)&masktable[i*BASE+j]?'.':' ',
  390. num_to_bits(k*3 + 2)&masktable[i*BASE+j]?'.':' ');
  391. }
  392. printf("|\n");
  393. }
  394. }
  395. printf(" ----- ----- ----- ----- ----- ----- ----- ----- -----\n");
  396. }
  397. #ifdef ONLINE_JUDGE
  398. #define output_table()
  399. #else
  400. #define output_table() outputTable()
  401. #endif
  402.  
  403. #define apply_mask(c) { \
  404. ushort rowId = get_groupId(c, group_type_row); \
  405. ushort colId = get_groupId(c, group_type_col); \
  406. ushort regId = get_groupId(c, group_type_reg); \
  407. ushort n = ~masktable[c] & MASK_INITIAL_STATE; \
  408. if(checkmask[rowId] & masktable[c] || \
  409. checkmask[BASE+colId] & masktable[c] || \
  410. checkmask[BASE*2+regId] & masktable[c] ) \
  411. return -1; \
  412. checkmask[rowId] |= masktable[c]; \
  413. checkmask[BASE+colId] |= masktable[c]; \
  414. checkmask[BASE*2+regId] |= masktable[c]; \
  415. solvedtable[c] = get_bit_set_16(masktable[c])+'1'; \
  416. masktable[c] = 0; \
  417. nfound++; \
  418. if(applyMask(rowId, group_type_row, n) == -1) \
  419. return -1; \
  420. if(applyMask(colId, group_type_col, n) == -1) \
  421. return -1; \
  422. if(applyMask(regId, group_type_reg, n) == -1) \
  423. return -1; \
  424. }
  425. int applyMask(ushort groupId, ushort groupType, ushort mask)
  426. {
  427. ushort i, c;
  428. for(i = 0; i < BASE; i++)
  429. {
  430. c = get_cellId(groupType, groupId, i);
  431. if( masktable[c] )
  432. {
  433. masktable[c] &= mask;
  434. if(!masktable[c])
  435. return -1;
  436. if( get_bit_count_16(masktable[c]) == 1 )
  437. apply_mask(c);
  438. }
  439. }
  440. return 1;
  441. }
  442.  
  443. int FindNaked1()
  444. {
  445. int i;
  446. int found = 0;
  447. for(i = 0; i < BASE*BASE; i++)
  448. {
  449. if(!masktable[i] && solvedtable[i]=='.')
  450. {
  451. found = -1;
  452. break;
  453. }
  454. if(masktable[i] && get_bit_count_16(masktable[i]) == 1)
  455. {
  456. apply_mask(i);
  457. found = 1;
  458. }
  459. }
  460. return found;
  461. }
  462. int FindHidden1()
  463. {
  464. int i, j, k;
  465. int found = 0;
  466. ushort s_mask[3], o_mask[3], cell[3];
  467. for(i = 0; i < BASE; i++)
  468. {
  469. for(k = 0; k < 9; k++)
  470. {
  471. s_mask[0]=s_mask[1]=s_mask[2]=0;
  472. o_mask[0]=o_mask[1]=o_mask[2]=0;
  473. for(j = 0; j < BASE; j++)
  474. {
  475. if(k == j)
  476. {
  477. #define or_smask(t) cell[t] = get_cellId(t, i, j); \
  478. s_mask[t] |= masktable[cell[t]];
  479. or_smask(group_type_row);
  480. or_smask(group_type_col);
  481. or_smask(group_type_reg);
  482. #undef or_smask
  483. }else
  484. {
  485. #define or_omask(t) o_mask[t] |= masktable[get_cellId(t, i, j)];
  486. or_omask(group_type_row);
  487. or_omask(group_type_col);
  488. or_omask(group_type_reg);
  489. #undef or_omask
  490. }
  491. }
  492. #define and_smask(t) s_mask[t] &= ~o_mask[t];
  493. and_smask(group_type_row);
  494. and_smask(group_type_col);
  495. and_smask(group_type_reg);
  496. #undef and_smask
  497. #define find_h(t) if(get_bit_count_16(s_mask[t]) == 1) \
  498. { \
  499. ushort c = cell[t]; \
  500. if(masktable[c]) \
  501. { \
  502. masktable[c] = s_mask[t]; \
  503. found = 1; \
  504. apply_mask(c);\
  505. } \
  506. }
  507. find_h(group_type_row);
  508. find_h(group_type_col);
  509. find_h(group_type_reg);
  510. #undef find_h
  511. }
  512. }
  513. return found;
  514. }
  515. int FindLocked()
  516. {
  517. int found = 0;
  518. int i, j, k, g, c, t1, t2;
  519. ushort s_mask[12], cell[12], and_mask[12], n, m;
  520. for(i = 0; i < 9; i++)
  521. {
  522. for(j = 0; j < 12; j++)
  523. {
  524. k = j%3;
  525. switch(j/3)
  526. {
  527. case 0:
  528. cell[j] = get_cellId(group_type_reg, i, k*3);
  529. s_mask[j] = masktable[cell[j]] | masktable[cell[j]+1] | masktable[cell[j]+2];
  530. break;
  531. case 1:
  532. cell[j] = get_cellId(group_type_reg, i, k);
  533. s_mask[j] = masktable[cell[j]] | masktable[cell[j]+BASE] | masktable[cell[j]+BASE*2];
  534. break;
  535. case 2:
  536. cell[j] = get_cellId(group_type_row, i, k*3);
  537. s_mask[j] = masktable[cell[j]] | masktable[cell[j]+1] | masktable[cell[j]+2];
  538. break;
  539. case 3:
  540. cell[j] = get_cellId(group_type_col, i, k*3);
  541. s_mask[j] = masktable[cell[j]] | masktable[cell[j]+BASE] | masktable[cell[j]+BASE*2];
  542. break;
  543. }
  544. }
  545. and_mask[0] = s_mask[0] & ~(s_mask[1] | s_mask[2]);
  546. and_mask[1] = s_mask[1] & ~(s_mask[0] | s_mask[2]);
  547. and_mask[2] = s_mask[2] & ~(s_mask[0] | s_mask[1]);
  548. and_mask[3] = s_mask[3] & ~(s_mask[4] | s_mask[5]);
  549. and_mask[4] = s_mask[4] & ~(s_mask[3] | s_mask[5]);
  550. and_mask[5] = s_mask[5] & ~(s_mask[3] | s_mask[4]);
  551. and_mask[6] = s_mask[6] & ~(s_mask[7] | s_mask[8]);
  552. and_mask[7] = s_mask[7] & ~(s_mask[6] | s_mask[8]);
  553. and_mask[8] = s_mask[8] & ~(s_mask[6] | s_mask[7]);
  554. and_mask[9] = s_mask[9] & ~(s_mask[10] | s_mask[11]);
  555. and_mask[10] = s_mask[10] & ~(s_mask[9] | s_mask[11]);
  556. and_mask[11] = s_mask[11] & ~(s_mask[9] | s_mask[10]);
  557. for(j = 0; j < 12; j++)
  558. {
  559. if(and_mask[j])
  560. {
  561. n = ~and_mask[j];
  562. switch(j/3)
  563. {
  564. case 0:
  565. t1 = group_type_reg;
  566. t2 = group_type_row;
  567. break;
  568. case 1:
  569. t1 = group_type_reg;
  570. t2 = group_type_col;
  571. break;
  572. case 2:
  573. t1 = group_type_row;
  574. t2 = group_type_reg;
  575. break;
  576. case 3:
  577. t1 = group_type_col;
  578. t2 = group_type_reg;
  579. break;
  580. };
  581. g = get_groupId(cell[j], t2);
  582. for(k = 0; k < 9; k++)
  583. {
  584. c = get_cellId(t2, g, k);
  585. if(get_groupId(c, t1) == i)
  586. continue;
  587. m = masktable[c];
  588. masktable[c] &= n;
  589. if(m != masktable[c])
  590. found =1;
  591. }
  592. }
  593. }
  594. if(found)
  595. break;
  596. }
  597. return found;
  598. }
  599. int FindNaked(char x, const char group_to_cell[9][9])
  600. {
  601. int i, j, k;
  602. int found = 0;
  603. ushort s_mask, o_mask, c, notfoundmask;
  604. for(i = 0; i < BASE; i++)
  605. {
  606. notfoundmask = 0;
  607. for(j = BASE-1; j>=0; j--)
  608. {
  609. notfoundmask <<=1;
  610. if(masktable[group_to_cell[i][j]])
  611. notfoundmask |= 1;
  612. }
  613.  
  614. for(k = 0; k < comb[x].count; k++)
  615. {
  616. c = comb[x].array[k];
  617. if((c & notfoundmask) != c)
  618. continue;
  619.  
  620. s_mask = o_mask=0;
  621. for(j = 0; j < BASE; j++)
  622. {
  623. if(c & 1)
  624. s_mask |= masktable[group_to_cell[i][j]];
  625. else
  626. o_mask |= masktable[group_to_cell[i][j]];
  627. c>>=1;
  628. if( get_bit_count_16(s_mask) > x )
  629. break;
  630. }
  631. if( get_bit_count_16(s_mask) == x )
  632. {
  633. s_mask = ~s_mask;
  634. c = comb[x].array[k];
  635. for(j = 0; j < BASE; j++)
  636. {
  637. if((c&1) == 0)
  638. {
  639. ushort m = masktable[group_to_cell[i][j]];
  640. if((m & s_mask) != m)
  641. {
  642. masktable[group_to_cell[i][j]] = m & s_mask;
  643. found = 1;
  644. }
  645. }
  646. c>>=1;
  647. }
  648. }
  649. if(found)
  650. return 1;
  651. }
  652. }
  653. return found;
  654. }
  655.  
  656.  
  657. int FindHidden(char x, const char group_to_cell[9][9])
  658. {
  659. int i, j, k;
  660. int found = 0;
  661. ushort s_mask, o_mask, c, notfoundmask;
  662. for(i = 0; i < BASE; i++)
  663. {
  664. notfoundmask = 0;
  665. for(j = BASE-1; j>=0; j--)
  666. {
  667. notfoundmask <<=1;
  668. if(masktable[group_to_cell[i][j]])
  669. notfoundmask |= 1;
  670. }
  671.  
  672. for(k = 0; k < comb[x].count; k++)
  673. {
  674. c = comb[x].array[k];
  675. if((c & notfoundmask) != c)
  676. continue;
  677.  
  678. s_mask = o_mask=0;
  679. for(j = 0; j < BASE; j++)
  680. {
  681. if(c & 1)
  682. s_mask |= masktable[group_to_cell[i][j]];
  683. else
  684. o_mask |= masktable[group_to_cell[i][j]];
  685. c>>=1;
  686. }
  687. s_mask &= ~o_mask;
  688. if( get_bit_count_16(s_mask) == x )
  689. {
  690. c = comb[x].array[k];
  691. for(j = 0; j < BASE; j++)
  692. {
  693. if((c&1) == 1)
  694. {
  695. ushort m = masktable[group_to_cell[i][j]];
  696. if((m & s_mask) != m)
  697. {
  698. masktable[group_to_cell[i][j]] = m & s_mask;
  699. found = 1;
  700. }
  701. }
  702. c>>=1;
  703. }
  704. }
  705. if(found)
  706. return 1;
  707. }
  708. }
  709. return found;
  710. }
  711. int FindNakedGen(char x, char *group)
  712. {
  713. int i;
  714. for(i = 0; i < 3; i++)
  715. {
  716. if(++*group > group_type_reg)
  717. *group = group_type_row;
  718.  
  719. if(FindNaked(x, group_to_cell[*group]))
  720. return 1;
  721. }
  722.  
  723. return 0;
  724. }
  725. int FindHiddenGen(char x, char *group)
  726. {
  727. int i;
  728. for(i = 0; i < 3; i++)
  729. {
  730. if(++*group > group_type_reg)
  731. *group = group_type_row;
  732.  
  733. if(FindHidden(x, group_to_cell[*group]))
  734. return 1;
  735. }
  736.  
  737. return 0;
  738. }
  739. void ProcessBox()
  740. {
  741. int found = 0;
  742. char group[6] = {0};
  743. ushort nCandidates, changedId, changedTo;
  744. initBuffers();
  745. inputValues();
  746. do
  747. {
  748. do
  749. {
  750. found = FindNaked1();
  751. if(found == -1)
  752. break;
  753.  
  754. if(nfound == 81)
  755. break;
  756.  
  757. output_table();
  758. do
  759. {
  760. found = FindHidden1();
  761. }while(found == 1 && nfound < 81);
  762.  
  763. if(found == -1)
  764. break;
  765.  
  766. if(nfound == 81)
  767. break;
  768.  
  769. output_table();
  770. /*
  771. found = FindLocked();
  772. if(found)
  773. continue;
  774.  
  775. found = FindNakedGen(2, &group[0]);
  776. if(found)
  777. continue;
  778.  
  779. found = FindHiddenGen(2, &group[1]);
  780. if(found)
  781. continue;
  782. found = FindNakedGen(3, &group[2]);
  783. if(found)
  784. continue;
  785.  
  786. found = FindHiddenGen(3, &group[3]);
  787. if(found)
  788. continue;
  789. found = FindNakedGen(4, &group[4]);
  790. if(found)
  791. continue;
  792.  
  793. found = FindHiddenGen(4, &group[5]);
  794. if(found)
  795. continue;
  796. */
  797. // TODO:
  798. // Find cross (x-wing, swordfish etc)
  799. // Implement trial-and-error
  800. }while(found == 1);
  801.  
  802. if(nfound == 81)
  803. break;
  804. if(found == 0)
  805. {
  806. nCandidates = 2;
  807. changedId = 0;
  808. changedTo = 0;
  809. }else if(found == -1)
  810. {
  811. if(!popState(&nCandidates, &changedId, &changedTo))
  812. {
  813. puts("N");
  814. return;
  815. }
  816. }
  817.  
  818. found = findNextTrial(&nCandidates, &changedId, &changedTo);
  819. if(found == -1)
  820. {
  821. puts("N");
  822. return;
  823. }
  824. if(found == 1)
  825. pushState(nCandidates, changedId, changedTo);
  826.  
  827. masktable[changedId] = changedTo;
  828.  
  829. }while(1);
  830. puts("Y");
  831. puts(solvedtable);
  832. while(popState(&nCandidates, &changedId, &changedTo));
  833. }
  834. int main()
  835. {
  836. int t;
  837. char strT[5];
  838. gets(strT);
  839. t = atoi(strT);
  840. while(t--)
  841. ProcessBox();
  842. return 0;
  843. }
  844.