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