#include #include #ifndef RJ #define RJ 0 // 0 no debugging, 1 print solutions, 2 print puzzles, 3 print steps, 4 print pencil marks #endif int q, // Number of unsolved Cell positions Grid wise r[81], // Used for sorting and eliminating each unsolved Cell positions Grid wise s[81], // Sudoku Grid 81 Cell positions for clues and solved g[81], // Bitwise Candidates for each unsolved Cell positions Grid wise n[3]; // Number of Naked Singles, Hidden Singles and Guesses Grid wise static int b[512] = { // Bitwise Candidates 0, 1, 2, 12, 3, 13, 23, 123, 4, 14, 24, 124, 34, 134, 234, 1234, 5, 15, 25, 125, 35, 135, 235, 1235, 45, 145, 245, 1245, 345, 1345, 2345, 12345, 6, 16, 26, 126, 36, 136, 236, 1236, 46, 146, 246, 1246, 346, 1346, 2346, 12346, 56, 156, 256, 1256, 356, 1356, 2356, 12356, 456, 1456, 2456, 12456, 3456, 13456, 23456, 123456, 7, 17, 27, 127, 37, 137, 237, 1237, 47, 147, 247, 1247, 347, 1347, 2347, 12347, 57, 157, 257, 1257, 357, 1357, 2357, 12357, 457, 1457, 2457, 12457, 3457, 13457, 23457, 123457, 67, 167, 267, 1267, 367, 1367, 2367, 12367, 467, 1467, 2467, 12467, 3467, 13467, 23467, 123467, 567, 1567, 2567, 12567, 3567, 13567, 23567, 123567, 4567, 14567, 24567, 124567, 34567, 134567, 234567, 1234567, 8, 18, 28, 128, 38, 138, 238, 1238, 48, 148, 248, 1248, 348, 1348, 2348, 12348, 58, 158, 258, 1258, 358, 1358, 2358, 12358, 458, 1458, 2458, 12458, 3458, 13458, 23458, 123458, 68, 168, 268, 1268, 368, 1368, 2368, 12368, 468, 1468, 2468, 12468, 3468, 13468, 23468, 123468, 568, 1568, 2568, 12568, 3568, 13568, 23568, 123568, 4568, 14568, 24568, 124568, 34568, 134568, 234568, 1234568, 78, 178, 278, 1278, 378, 1378, 2378, 12378, 478, 1478, 2478, 12478, 3478, 13478, 23478, 123478, 578, 1578, 2578, 12578, 3578, 13578, 23578, 123578, 4578, 14578, 24578, 124578, 34578, 134578, 234578, 1234578, 378, 1678, 2678, 12678, 3678, 13678, 23678, 123678, 4678, 14678, 24678, 124678, 34678, 134678, 234678, 1234678, 5678, 15678, 25678, 125678, 35678, 135678, 235678, 1235678, 45678, 145678, 245678, 1245678, 345678, 1345678, 2345678, 12345678, 9, 19, 29, 129, 39, 139, 239, 1239, 49, 149, 249, 1249, 349, 1349, 2349, 12349, 59, 159, 259, 1259, 359, 1359, 2359, 12359, 459, 1459, 2459, 12459, 3459, 13459, 23459, 123459, 69, 169, 269, 1269, 369, 1369, 2369, 12369, 469, 1469, 2469, 12469, 3469, 13469, 23469, 123469, 569, 1569, 2569, 12569, 3569, 13569, 23569, 123569, 4569, 14569, 24569, 124569, 34569, 134569, 234569, 1234569, 79, 179, 279, 1279, 379, 1379, 2379, 12379, 479, 1479, 2479, 12479, 3479, 13479, 23479, 123479, 579, 1579, 2579, 12579, 3579, 13579, 23579, 123579, 4579, 14579, 24579, 124579, 34579, 134579, 234579, 1234579, 679, 1679, 2679, 12679, 3679, 13679, 23679, 123679, 4679, 14679, 24679, 124679, 34679, 134679, 234679, 1234679, 5679, 15679, 25679, 125679, 35679, 135679, 235679, 1235679, 45679, 145679, 245679, 1245679, 345679, 1345679, 2345679, 12345679, 89, 189, 289, 1289, 389, 1389, 2389, 12389, 489, 1489, 2489, 12489, 3489, 13489, 23489, 123489, 589, 1589, 2589, 12589, 3589, 13589, 23589, 123589, 4589, 14589, 24589, 124589, 34589, 134589, 234589, 1234589, 689, 1689, 2689, 12689, 3689, 13689, 23689, 123689, 4689, 14689, 24689, 124689, 34689, 134689, 234689, 1234689, 5689, 15689, 25689, 125689, 35689, 135689, 235689, 1235689, 45689, 145689, 245689, 1245689, 345689, 1345689, 2345689, 12345689, 789, 1789, 2789, 12789, 3789, 13789, 23789, 123789, 4789, 14789, 24789, 124789, 34789, 134789, 234789, 1234789, 5789, 15789, 25789, 125789, 35789, 135789, 235789, 1235789, 45789, 145789, 245789, 1245789, 345789, 1345789, 2345789, 12345789, 6789, 16789, 26789, 126789, 36789, 136789, 236789, 1236789, 46789, 146789, 246789, 1246789, 346789, 1346789, 2346789, 12346789, 56789, 156789, 256789, 1256789, 356789, 1356789, 2356789, 12356789, 456789, 1456789, 2456789, 12456789, 3456789, 13456789, 23456789,123456789}, B[513] = { // Count bitwise Candidates 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9,10}, w[81][20] = { // 20 affected Cell positions for 81 Cell positions { 3, 4, 5, 6, 7, 8, 1, 2,10,11,19,20, 9,18,27,36,45,54,63,72}, { 3, 4, 5, 6, 7, 8, 0, 2, 9,11,18,20,10,19,28,37,46,55,64,73}, { 3, 4, 5, 6, 7, 8, 0, 1, 9,10,18,19,11,20,29,38,47,56,65,74}, { 0, 1, 2, 6, 7, 8, 4, 5,13,14,22,23,12,21,30,39,48,57,66,75}, { 0, 1, 2, 6, 7, 8, 3, 5,12,14,21,23,13,22,31,40,49,58,67,76}, { 0, 1, 2, 6, 7, 8, 3, 4,12,13,21,22,14,23,32,41,50,59,68,77}, { 0, 1, 2, 3, 4, 5, 7, 8,16,17,25,26,15,24,33,42,51,60,69,78}, { 0, 1, 2, 3, 4, 5, 6, 8,15,17,24,26,16,25,34,43,52,61,70,79}, { 0, 1, 2, 3, 4, 5, 6, 7,15,16,24,25,17,26,35,44,53,62,71,80}, {12,13,14,15,16,17,10,11, 1, 2,19,20, 0,18,27,36,45,54,63,72}, {12,13,14,15,16,17, 9,11, 0, 2,18,20, 1,19,28,37,46,55,64,73}, {12,13,14,15,16,17, 9,10, 0, 1,18,19, 2,20,29,38,47,56,65,74}, { 9,10,11,15,16,17,13,14, 4, 5,22,23, 3,21,30,39,48,57,66,75}, { 9,10,11,15,16,17,12,14, 3, 5,21,23, 4,22,31,40,49,58,67,76}, { 9,10,11,15,16,17,12,13, 3, 4,21,22, 5,23,32,41,50,59,68,77}, { 9,10,11,12,13,14,16,17, 7, 8,25,26, 6,24,33,42,51,60,69,78}, { 9,10,11,12,13,14,15,17, 6, 8,24,26, 7,25,34,43,52,61,70,79}, { 9,10,11,12,13,14,15,16, 6, 7,24,25, 8,26,35,44,53,62,71,80}, {21,22,23,24,25,26,19,20, 1, 2,10,11, 0, 9,27,36,45,54,63,72}, {21,22,23,24,25,26,18,20, 0, 2, 9,11, 1,10,28,37,46,55,64,73}, {21,22,23,24,25,26,18,19, 0, 1, 9,10, 2,11,29,38,47,56,65,74}, {18,19,20,24,25,26,22,23, 4, 5,13,14, 3,12,30,39,48,57,66,75}, {18,19,20,24,25,26,21,23, 3, 5,12,14, 4,13,31,40,49,58,67,76}, {18,19,20,24,25,26,21,22, 3, 4,12,13, 5,14,32,41,50,59,68,77}, {18,19,20,21,22,23,25,26, 7, 8,16,17, 6,15,33,42,51,60,69,78}, {18,19,20,21,22,23,24,26, 6, 8,15,17, 7,16,34,43,52,61,70,79}, {18,19,20,21,22,23,24,25, 6, 7,15,16, 8,17,35,44,53,62,71,80}, {30,31,32,33,34,35,28,29,37,38,46,47,36,45, 0, 9,18,54,63,72}, {30,31,32,33,34,35,27,29,36,38,45,47,37,46, 1,10,19,55,64,73}, {30,31,32,33,34,35,27,28,36,37,45,46,38,47, 2,11,20,56,65,74}, {27,28,29,33,34,35,31,32,40,41,49,50,39,48, 3,12,21,57,66,75}, {27,28,29,33,34,35,30,32,39,41,48,50,40,49, 4,13,22,58,67,76}, {27,28,29,33,34,35,30,31,39,40,48,49,41,50, 5,14,23,59,68,77}, {27,28,29,30,31,32,34,35,43,44,52,53,42,51, 6,15,24,60,69,78}, {27,28,29,30,31,32,33,35,42,44,51,53,43,52, 7,16,25,61,70,79}, {27,28,29,30,31,32,33,34,42,43,51,52,44,53, 8,17,26,62,71,80}, {39,40,41,42,43,44,37,38,28,29,46,47,27,45, 0, 9,18,54,63,72}, {39,40,41,42,43,44,36,38,27,29,45,47,28,46, 1,10,19,55,64,73}, {39,40,41,42,43,44,36,37,27,28,45,46,29,47, 2,11,20,56,65,74}, {36,37,38,42,43,44,40,41,31,32,49,50,30,48, 3,12,21,57,66,75}, {36,37,38,42,43,44,39,41,30,32,48,50,31,49, 4,13,22,58,67,76}, {36,37,38,42,43,44,39,40,30,31,48,49,32,50, 5,14,23,59,68,77}, {36,37,38,39,40,41,43,44,34,35,52,53,33,51, 6,15,24,60,69,78}, {36,37,38,39,40,41,42,44,33,35,51,53,34,52, 7,16,25,61,70,79}, {36,37,38,39,40,41,42,43,33,34,51,52,35,53, 8,17,26,62,71,80}, {48,49,50,51,52,53,46,47,28,29,37,38,27,36, 0, 9,18,54,63,72}, {48,49,50,51,52,53,45,47,27,29,36,38,28,37, 1,10,19,55,64,73}, {48,49,50,51,52,53,45,46,27,28,36,37,29,38, 2,11,20,56,65,74}, {45,46,47,51,52,53,49,50,31,32,40,41,30,39, 3,12,21,57,66,75}, {45,46,47,51,52,53,48,50,30,32,39,41,31,40, 4,13,22,58,67,76}, {45,46,47,51,52,53,48,49,30,31,39,40,32,41, 5,14,23,59,68,77}, {45,46,47,48,49,50,52,53,34,35,43,44,33,42, 6,15,24,60,69,78}, {45,46,47,48,49,50,51,53,33,35,42,44,34,43, 7,16,25,61,70,79}, {45,46,47,48,49,50,51,52,33,34,42,43,35,44, 8,17,26,62,71,80}, {57,58,59,60,61,62,55,56,64,65,73,74,63,72, 0, 9,18,27,36,45}, {57,58,59,60,61,62,54,56,63,65,72,74,64,73, 1,10,19,28,37,46}, {57,58,59,60,61,62,54,55,63,64,72,73,65,74, 2,11,20,29,38,47}, {54,55,56,60,61,62,58,59,67,68,76,77,66,75, 3,12,21,30,39,48}, {54,55,56,60,61,62,57,59,66,68,75,77,67,76, 4,13,22,31,40,49}, {54,55,56,60,61,62,57,58,66,67,75,76,68,77, 5,14,23,32,41,50}, {54,55,56,57,58,59,61,62,70,71,79,80,69,78, 6,15,24,33,42,51}, {54,55,56,57,58,59,60,62,69,71,78,80,70,79, 7,16,25,34,43,52}, {54,55,56,57,58,59,60,61,69,70,78,79,71,80, 8,17,26,35,44,53}, {66,67,68,69,70,71,64,65,55,56,73,74,54,72, 0, 9,18,27,36,45}, {66,67,68,69,70,71,63,65,54,56,72,74,55,73, 1,10,19,28,37,46}, {66,67,68,69,70,71,63,64,54,55,72,73,56,74, 2,11,20,29,38,47}, {63,64,65,69,70,71,67,68,58,59,76,77,57,75, 3,12,21,30,39,48}, {63,64,65,69,70,71,66,68,57,59,75,77,58,76, 4,13,22,31,40,49}, {63,64,65,69,70,71,66,67,57,58,75,76,59,77, 5,14,23,32,41,50}, {63,64,65,66,67,68,70,71,61,62,79,80,60,78, 6,15,24,33,42,51}, {63,64,65,66,67,68,69,71,60,62,78,80,61,79, 7,16,25,34,43,52}, {63,64,65,66,67,68,69,70,60,61,78,79,62,80, 8,17,26,35,44,53}, {75,76,77,78,79,80,73,74,55,56,64,65,54,63, 0, 9,18,27,36,45}, {75,76,77,78,79,80,72,74,54,56,63,65,55,64, 1,10,19,28,37,46}, {75,76,77,78,79,80,72,73,54,55,63,64,56,65, 2,11,20,29,38,47}, {72,73,74,78,79,80,76,77,58,59,67,68,57,66, 3,12,21,30,39,48}, {72,73,74,78,79,80,75,77,57,59,66,68,58,67, 4,13,22,31,40,49}, {72,73,74,78,79,80,75,76,57,58,66,67,59,68, 5,14,23,32,41,50}, {72,73,74,75,76,77,79,80,61,62,70,71,60,69, 6,15,24,33,42,51}, {72,73,74,75,76,77,78,80,60,62,69,71,61,70, 7,16,25,34,43,52}, {72,73,74,75,76,77,78,79,60,61,69,70,62,71, 8,17,26,35,44,53}}, l[27][9] = { // 9 Cell positions for 27 Units { 0, 1, 2, 3, 4, 5, 6, 7, 8}, { 9,10,11,12,13,14,15,16,17}, {18,19,20,21,22,23,24,25,26}, {27,28,29,30,31,32,33,34,35}, {36,37,38,39,40,41,42,43,44}, {45,46,47,48,49,50,51,52,53}, {54,55,56,57,58,59,60,61,62}, {63,64,65,66,67,68,69,70,71}, {72,73,74,75,76,77,78,79,80}, { 0, 9,18,27,36,45,54,63,72}, { 1,10,19,28,37,46,55,64,73}, { 2,11,20,29,38,47,56,65,74}, { 3,12,21,30,39,48,57,66,75}, { 4,13,22,31,40,49,58,67,76}, { 5,14,23,32,41,50,59,68,77}, { 6,15,24,33,42,51,60,69,78}, { 7,16,25,34,43,52,61,70,79}, { 8,17,26,35,44,53,62,71,80}, { 0, 1, 2, 9,10,11,18,19,20}, { 3, 4, 5,12,13,14,21,22,23}, { 6, 7, 8,15,16,17,24,25,26}, {27,28,29,36,37,38,45,46,47}, {30,31,32,39,40,41,48,49,50}, {33,34,35,42,43,44,51,52,53}, {54,55,56,63,64,65,72,73,74}, {57,58,59,66,67,68,75,76,77}, {60,61,62,69,70,71,78,79,80}}, h[246][9] = { // 36 pairs/84 triplets/126 quads and other Cell positions for each Unit { 0, 1, 2, 3, 4, 5, 6, 7, 8}, { 0, 2, 1, 3, 4, 5, 6, 7, 8}, { 0, 3, 1, 2, 4, 5, 6, 7, 8}, { 0, 4, 1, 2, 3, 5, 6, 7, 8}, { 0, 5, 1, 2, 3, 4, 6, 7, 8}, { 0, 6, 1, 2, 3, 4, 5, 7, 8}, { 0, 7, 1, 2, 3, 4, 5, 6, 8}, { 0, 8, 1, 2, 3, 4, 5, 6, 7}, { 1, 2, 0, 3, 4, 5, 6, 7, 8}, { 1, 3, 0, 2, 4, 5, 6, 7, 8}, { 1, 4, 0, 2, 3, 5, 6, 7, 8}, { 1, 5, 0, 2, 3, 4, 6, 7, 8}, { 1, 6, 0, 2, 3, 4, 5, 7, 8}, { 1, 7, 0, 2, 3, 4, 5, 6, 8}, { 1, 8, 0, 2, 3, 4, 5, 6, 7}, { 2, 3, 0, 1, 4, 5, 6, 7, 8}, { 2, 4, 0, 1, 3, 5, 6, 7, 8}, { 2, 5, 0, 1, 3, 4, 6, 7, 8}, { 2, 6, 0, 1, 3, 4, 5, 7, 8}, { 2, 7, 0, 1, 3, 4, 5, 6, 8}, { 2, 8, 0, 1, 3, 4, 5, 6, 7}, { 3, 4, 0, 1, 2, 5, 6, 7, 8}, { 3, 5, 0, 1, 2, 4, 6, 7, 8}, { 3, 6, 0, 1, 2, 4, 5, 7, 8}, { 3, 7, 0, 1, 2, 4, 5, 6, 8}, { 3, 8, 0, 1, 2, 4, 5, 6, 7}, { 4, 5, 0, 1, 2, 3, 6, 7, 8}, { 4, 6, 0, 1, 2, 3, 5, 7, 8}, { 4, 7, 0, 1, 2, 3, 5, 6, 8}, { 4, 8, 0, 1, 2, 3, 5, 6, 7}, { 5, 6, 0, 1, 2, 3, 4, 7, 8}, { 5, 7, 0, 1, 2, 3, 4, 6, 8}, { 5, 8, 0, 1, 2, 3, 4, 6, 7}, { 6, 7, 0, 1, 2, 3, 4, 5, 8}, { 6, 8, 0, 1, 2, 3, 4, 5, 7}, { 7, 8, 0, 1, 2, 3, 4, 5, 6}, { 0, 1, 2, 3, 4, 5, 6, 7, 8}, { 0, 1, 3, 2, 4, 5, 6, 7, 8}, { 0, 1, 4, 2, 3, 5, 6, 7, 8}, { 0, 1, 5, 2, 3, 4, 6, 7, 8}, { 0, 1, 6, 2, 3, 4, 5, 7, 8}, { 0, 1, 7, 2, 3, 4, 5, 6, 8}, { 0, 1, 8, 2, 3, 4, 5, 6, 7}, { 0, 2, 3, 1, 4, 5, 6, 7, 8}, { 0, 2, 4, 1, 3, 5, 6, 7, 8}, { 0, 2, 5, 1, 3, 4, 6, 7, 8}, { 0, 2, 6, 1, 3, 4, 5, 7, 8}, { 0, 2, 7, 1, 3, 4, 5, 6, 8}, { 0, 2, 8, 1, 3, 4, 5, 6, 7}, { 0, 3, 4, 1, 2, 5, 6, 7, 8}, { 0, 3, 5, 1, 2, 4, 6, 7, 8}, { 0, 3, 6, 1, 2, 4, 5, 7, 8}, { 0, 3, 7, 1, 2, 4, 5, 6, 8}, { 0, 3, 8, 1, 2, 4, 5, 6, 7}, { 0, 4, 5, 1, 2, 3, 6, 7, 8}, { 0, 4, 6, 1, 2, 3, 5, 7, 8}, { 0, 4, 7, 1, 2, 3, 5, 6, 8}, { 0, 4, 8, 1, 2, 3, 5, 6, 7}, { 0, 5, 6, 1, 2, 3, 4, 7, 8}, { 0, 5, 7, 1, 2, 3, 4, 6, 8}, { 0, 5, 8, 1, 2, 3, 4, 6, 7}, { 0, 6, 7, 1, 2, 3, 4, 5, 8}, { 0, 6, 8, 1, 2, 3, 4, 5, 7}, { 0, 7, 8, 1, 2, 3, 4, 5, 6}, { 1, 2, 3, 0, 4, 5, 6, 7, 8}, { 1, 2, 4, 0, 3, 5, 6, 7, 8}, { 1, 2, 5, 0, 3, 4, 6, 7, 8}, { 1, 2, 6, 0, 3, 4, 5, 7, 8}, { 1, 2, 7, 0, 3, 4, 5, 6, 8}, { 1, 2, 8, 0, 3, 4, 5, 6, 7}, { 1, 3, 4, 0, 2, 5, 6, 7, 8}, { 1, 3, 5, 0, 2, 4, 6, 7, 8}, { 1, 3, 6, 0, 2, 4, 5, 7, 8}, { 1, 3, 7, 0, 2, 4, 5, 6, 8}, { 1, 3, 8, 0, 2, 4, 5, 6, 7}, { 1, 4, 5, 0, 2, 3, 6, 7, 8}, { 1, 4, 6, 0, 2, 3, 5, 7, 8}, { 1, 4, 7, 0, 2, 3, 5, 6, 8}, { 1, 4, 8, 0, 2, 3, 5, 6, 7}, { 1, 5, 6, 0, 2, 3, 4, 7, 8}, { 1, 5, 7, 0, 2, 3, 4, 6, 8}, { 1, 5, 8, 0, 2, 3, 4, 6, 7}, { 1, 6, 7, 0, 2, 3, 4, 5, 8}, { 1, 6, 8, 0, 2, 3, 4, 5, 7}, { 1, 7, 8, 0, 2, 3, 4, 5, 6}, { 2, 3, 4, 0, 1, 5, 6, 7, 8}, { 2, 3, 5, 0, 1, 4, 6, 7, 8}, { 2, 3, 6, 0, 1, 4, 5, 7, 8}, { 2, 3, 7, 0, 1, 4, 5, 6, 8}, { 2, 3, 8, 0, 1, 4, 5, 6, 7}, { 2, 4, 5, 0, 1, 3, 6, 7, 8}, { 2, 4, 6, 0, 1, 3, 5, 7, 8}, { 2, 4, 7, 0, 1, 3, 5, 6, 8}, { 2, 4, 8, 0, 1, 3, 5, 6, 7}, { 2, 5, 6, 0, 1, 3, 4, 7, 8}, { 2, 5, 7, 0, 1, 3, 4, 6, 8}, { 2, 5, 8, 0, 1, 3, 4, 6, 7}, { 2, 6, 7, 0, 1, 3, 4, 5, 8}, { 2, 6, 8, 0, 1, 3, 4, 5, 7}, { 2, 7, 8, 0, 1, 3, 4, 5, 6}, { 3, 4, 5, 0, 1, 2, 6, 7, 8}, { 3, 4, 6, 0, 1, 2, 5, 7, 8}, { 3, 4, 7, 0, 1, 2, 5, 6, 8}, { 3, 4, 8, 0, 1, 2, 5, 6, 7}, { 3, 5, 6, 0, 1, 2, 4, 7, 8}, { 3, 5, 7, 0, 1, 2, 4, 6, 8}, { 3, 5, 8, 0, 1, 2, 4, 6, 7}, { 3, 6, 7, 0, 1, 2, 4, 5, 8}, { 3, 6, 8, 0, 1, 2, 4, 5, 7}, { 3, 7, 8, 0, 1, 2, 4, 5, 6}, { 4, 5, 6, 0, 1, 2, 3, 7, 8}, { 4, 5, 7, 0, 1, 2, 3, 6, 8}, { 4, 5, 8, 0, 1, 2, 3, 6, 7}, { 4, 6, 7, 0, 1, 2, 3, 5, 8}, { 4, 6, 8, 0, 1, 2, 3, 5, 7}, { 4, 7, 8, 0, 1, 2, 3, 5, 6}, { 5, 6, 7, 0, 1, 2, 3, 4, 8}, { 5, 6, 8, 0, 1, 2, 3, 4, 7}, { 5, 7, 8, 0, 1, 2, 3, 4, 6}, { 6, 7, 8, 0, 1, 2, 3, 4, 5}, { 0, 1, 2, 3, 4, 5, 6, 7, 8}, { 0, 1, 2, 4, 3, 5, 6, 7, 8}, { 0, 1, 2, 5, 3, 4, 6, 7, 8}, { 0, 1, 2, 6, 3, 4, 5, 7, 8}, { 0, 1, 2, 7, 3, 4, 5, 6, 8}, { 0, 1, 2, 8, 3, 4, 5, 6, 7}, { 0, 1, 3, 4, 2, 5, 6, 7, 8}, { 0, 1, 3, 5, 2, 4, 6, 7, 8}, { 0, 1, 3, 6, 2, 4, 5, 7, 8}, { 0, 1, 3, 7, 2, 4, 5, 6, 8}, { 0, 1, 3, 8, 2, 4, 5, 6, 7}, { 0, 1, 4, 5, 2, 3, 6, 7, 8}, { 0, 1, 4, 6, 2, 3, 5, 7, 8}, { 0, 1, 4, 7, 2, 3, 5, 6, 8}, { 0, 1, 4, 8, 2, 3, 5, 6, 7}, { 0, 1, 5, 6, 2, 3, 4, 7, 8}, { 0, 1, 5, 7, 2, 3, 4, 6, 8}, { 0, 1, 5, 8, 2, 3, 4, 6, 7}, { 0, 1, 6, 7, 2, 3, 4, 5, 8}, { 0, 1, 6, 8, 2, 3, 4, 5, 7}, { 0, 1, 7, 8, 2, 3, 4, 5, 6}, { 0, 2, 3, 4, 1, 5, 6, 7, 8}, { 0, 2, 3, 5, 1, 4, 6, 7, 8}, { 0, 2, 3, 6, 1, 4, 5, 7, 8}, { 0, 2, 3, 7, 1, 4, 5, 6, 8}, { 0, 2, 3, 8, 1, 4, 5, 6, 7}, { 0, 2, 4, 5, 1, 3, 6, 7, 8}, { 0, 2, 4, 6, 1, 3, 5, 7, 8}, { 0, 2, 4, 7, 1, 3, 5, 6, 8}, { 0, 2, 4, 8, 1, 3, 5, 6, 7}, { 0, 2, 5, 6, 1, 3, 4, 7, 8}, { 0, 2, 5, 7, 1, 3, 4, 6, 8}, { 0, 2, 5, 8, 1, 3, 4, 6, 7}, { 0, 2, 6, 7, 1, 3, 4, 5, 8}, { 0, 2, 6, 8, 1, 3, 4, 5, 7}, { 0, 2, 7, 8, 1, 3, 4, 5, 6}, { 0, 3, 4, 5, 1, 2, 6, 7, 8}, { 0, 3, 4, 6, 1, 2, 5, 7, 8}, { 0, 3, 4, 7, 1, 2, 5, 6, 8}, { 0, 3, 4, 8, 1, 2, 5, 6, 7}, { 0, 3, 5, 6, 1, 2, 4, 7, 8}, { 0, 3, 5, 7, 1, 2, 4, 6, 8}, { 0, 3, 5, 8, 1, 2, 4, 6, 7}, { 0, 3, 6, 7, 1, 2, 4, 5, 8}, { 0, 3, 6, 8, 1, 2, 4, 5, 7}, { 0, 3, 7, 8, 1, 2, 4, 5, 6}, { 0, 4, 5, 6, 1, 2, 3, 7, 8}, { 0, 4, 5, 7, 1, 2, 3, 6, 8}, { 0, 4, 5, 8, 1, 2, 3, 6, 7}, { 0, 4, 6, 7, 1, 2, 3, 5, 8}, { 0, 4, 6, 8, 1, 2, 3, 5, 7}, { 0, 4, 7, 8, 1, 2, 3, 5, 6}, { 0, 5, 6, 7, 1, 2, 3, 4, 8}, { 0, 5, 6, 8, 1, 2, 3, 4, 7}, { 0, 5, 7, 8, 1, 2, 3, 4, 6}, { 0, 6, 7, 8, 1, 2, 3, 4, 5}, { 1, 2, 3, 4, 0, 5, 6, 7, 8}, { 1, 2, 3, 5, 0, 4, 6, 7, 8}, { 1, 2, 3, 6, 0, 4, 5, 7, 8}, { 1, 2, 3, 7, 0, 4, 5, 6, 8}, { 1, 2, 3, 8, 0, 4, 5, 6, 7}, { 1, 2, 4, 5, 0, 3, 6, 7, 8}, { 1, 2, 4, 6, 0, 3, 5, 7, 8}, { 1, 2, 4, 7, 0, 3, 5, 6, 8}, { 1, 2, 4, 8, 0, 3, 5, 6, 7}, { 1, 2, 5, 6, 0, 3, 4, 7, 8}, { 1, 2, 5, 7, 0, 3, 4, 6, 8}, { 1, 2, 5, 8, 0, 3, 4, 6, 7}, { 1, 2, 6, 7, 0, 3, 4, 5, 8}, { 1, 2, 6, 8, 0, 3, 4, 5, 7}, { 1, 2, 7, 8, 0, 3, 4, 5, 6}, { 1, 3, 4, 5, 0, 2, 6, 7, 8}, { 1, 3, 4, 6, 0, 2, 5, 7, 8}, { 1, 3, 4, 7, 0, 2, 5, 6, 8}, { 1, 3, 4, 8, 0, 2, 5, 6, 7}, { 1, 3, 5, 6, 0, 2, 4, 7, 8}, { 1, 3, 5, 7, 0, 2, 4, 6, 8}, { 1, 3, 5, 8, 0, 2, 4, 6, 7}, { 1, 3, 6, 7, 0, 2, 4, 5, 8}, { 1, 3, 6, 8, 0, 2, 4, 5, 7}, { 1, 3, 7, 8, 0, 2, 4, 5, 6}, { 1, 4, 5, 6, 0, 2, 3, 7, 8}, { 1, 4, 5, 7, 0, 2, 3, 6, 8}, { 1, 4, 5, 8, 0, 2, 3, 6, 7}, { 1, 4, 6, 7, 0, 2, 3, 5, 8}, { 1, 4, 6, 8, 0, 2, 3, 5, 7}, { 1, 4, 7, 8, 0, 2, 3, 5, 6}, { 1, 5, 6, 7, 0, 2, 3, 4, 8}, { 1, 5, 6, 8, 0, 2, 3, 4, 7}, { 1, 5, 7, 8, 0, 2, 3, 4, 6}, { 1, 6, 7, 8, 0, 2, 3, 4, 5}, { 2, 3, 4, 5, 0, 1, 6, 7, 8}, { 2, 3, 4, 6, 0, 1, 5, 7, 8}, { 2, 3, 4, 7, 0, 1, 5, 6, 8}, { 2, 3, 4, 8, 0, 1, 5, 6, 7}, { 2, 3, 5, 6, 0, 1, 4, 7, 8}, { 2, 3, 5, 7, 0, 1, 4, 6, 8}, { 2, 3, 5, 8, 0, 1, 4, 6, 7}, { 2, 3, 6, 7, 0, 1, 4, 5, 8}, { 2, 3, 6, 8, 0, 1, 4, 5, 7}, { 2, 3, 7, 8, 0, 1, 4, 5, 6}, { 2, 4, 5, 6, 0, 1, 3, 7, 8}, { 2, 4, 5, 7, 0, 1, 3, 6, 8}, { 2, 4, 5, 8, 0, 1, 3, 6, 7}, { 2, 4, 6, 7, 0, 1, 3, 5, 8}, { 2, 4, 6, 8, 0, 1, 3, 5, 7}, { 2, 4, 7, 8, 0, 1, 3, 5, 6}, { 2, 5, 6, 7, 0, 1, 3, 4, 8}, { 2, 5, 6, 8, 0, 1, 3, 4, 7}, { 2, 5, 7, 8, 0, 1, 3, 4, 6}, { 2, 6, 7, 8, 0, 1, 3, 4, 5}, { 3, 4, 5, 6, 0, 1, 2, 7, 8}, { 3, 4, 5, 7, 0, 1, 2, 6, 8}, { 3, 4, 5, 8, 0, 1, 2, 6, 7}, { 3, 4, 6, 7, 0, 1, 2, 5, 8}, { 3, 4, 6, 8, 0, 1, 2, 5, 7}, { 3, 4, 7, 8, 0, 1, 2, 5, 6}, { 3, 5, 6, 7, 0, 1, 2, 4, 8}, { 3, 5, 6, 8, 0, 1, 2, 4, 7}, { 3, 5, 7, 8, 0, 1, 2, 4, 6}, { 3, 6, 7, 8, 0, 1, 2, 4, 5}, { 4, 5, 6, 7, 0, 1, 2, 3, 8}, { 4, 5, 6, 8, 0, 1, 2, 3, 7}, { 4, 5, 7, 8, 0, 1, 2, 3, 6}, { 4, 6, 7, 8, 0, 1, 2, 3, 5}, { 5, 6, 7, 8, 0, 1, 2, 3, 4}}, j[54][15] = { // 3 Intersection and affected 6 Line + 6 Box Cell positions for 54 Box-Line { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,18,19,20}, { 3, 4, 5, 0, 1, 2, 6, 7, 8,12,13,14,21,22,23}, { 6, 7, 8, 0, 1, 2, 3, 4, 5,15,16,17,24,25,26}, { 9,10,11,12,13,14,15,16,17, 0, 1, 2,18,19,20}, {12,13,14, 9,10,11,15,16,17, 3, 4, 5,21,22,23}, {15,16,17, 9,10,11,12,13,14, 6, 7, 8,24,25,26}, {18,19,20,21,22,23,24,25,26, 0, 1, 2, 9,10,11}, {21,22,23,18,19,20,24,25,26, 3, 4, 5,12,13,14}, {24,25,26,18,19,20,21,22,23, 6, 7, 8,15,16,17}, {27,28,29,30,31,32,33,34,35,36,37,38,45,46,47}, {30,31,32,27,28,29,33,34,35,39,40,41,48,49,50}, {33,34,35,27,28,29,30,31,32,42,43,44,51,52,53}, {36,37,38,39,40,41,42,43,44,27,28,29,45,46,47}, {39,40,41,36,37,38,42,43,44,30,31,32,48,49,50}, {42,43,44,36,37,38,39,40,41,33,34,35,51,52,53}, {45,46,47,48,49,50,51,52,53,27,28,29,36,37,38}, {48,49,50,45,46,47,51,52,53,30,31,32,39,40,41}, {51,52,53,45,46,47,48,49,50,33,34,35,42,43,44}, {54,55,56,57,58,59,60,61,62,63,64,65,72,73,74}, {57,58,59,54,55,56,60,61,62,66,67,68,75,76,77}, {60,61,62,54,55,56,57,58,59,69,70,71,78,79,80}, {63,64,65,66,67,68,69,70,71,54,55,56,72,73,74}, {66,67,68,63,64,65,69,70,71,57,58,59,75,76,77}, {69,70,71,63,64,65,66,67,68,60,61,62,78,79,80}, {72,73,74,75,76,77,78,79,80,54,55,56,63,64,65}, {75,76,77,72,73,74,78,79,80,57,58,59,66,67,68}, {78,79,80,72,73,74,75,76,77,60,61,62,69,70,71}, { 0, 9,18,27,36,45,54,63,72, 1, 2,10,11,19,20}, {27,36,45, 0, 9,18,54,63,72,28,29,37,38,46,47}, {54,63,72, 0, 9,18,27,36,45,55,56,64,65,73,74}, { 1,10,19,28,37,46,55,64,73, 0, 2, 9,11,18,20}, {28,37,46, 1,10,19,55,64,73,27,29,36,38,45,47}, {55,64,73, 1,10,19,28,37,46,54,56,63,65,72,74}, { 2,11,20,29,38,47,56,65,74, 0, 1, 9,10,18,19}, {29,38,47, 2,11,20,56,65,74,27,28,36,37,45,46}, {56,65,74, 2,11,20,29,38,47,54,55,63,64,72,73}, { 3,12,21,30,39,48,57,66,75, 4, 5,13,14,22,23}, {30,39,48, 3,12,21,57,66,75,31,32,40,41,49,50}, {57,66,75, 3,12,21,30,39,48,58,59,67,68,76,77}, { 4,13,22,31,40,49,58,67,76, 3, 5,12,14,21,23}, {31,40,49, 4,13,22,58,67,76,30,32,39,41,48,50}, {58,67,76, 4,13,22,31,40,49,57,59,66,68,75,77}, { 5,14,23,32,41,50,59,68,77, 3, 4,12,13,21,22}, {32,41,50, 5,14,23,59,68,77,30,31,39,40,48,49}, {59,68,77, 5,14,23,32,41,50,57,58,66,67,75,76}, { 6,15,24,33,42,51,60,69,78, 7, 8,16,17,25,26}, {33,42,51, 6,15,24,60,69,78,34,35,43,44,52,53}, {60,69,78, 6,15,24,33,42,51,61,62,70,71,79,80}, { 7,16,25,34,43,52,61,70,79, 6, 8,15,17,24,26}, {34,43,52, 7,16,25,61,70,79,33,35,42,44,51,53}, {61,70,79, 7,16,25,34,43,52,60,62,69,71,78,80}, { 8,17,26,35,44,53,62,71,80, 6, 7,15,16,24,25}, {35,44,53, 8,17,26,62,71,80,33,34,42,43,51,52}, {62,71,80, 8,17,26,35,44,53,60,61,69,70,78,79}}, J[20] = { // Bit positions 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536,131072,262144,524288}, W[11][4] = { // References for XY-Wings Type 2 and XYZ-Wings { 0, 1, 2, 3}, { 1, 0, 3, 2}, { 2, 0, 3, 2}, { 3, 1, 2, 0}, { 8, 6, 0, 0}, {14,12, 0, 0}, { 0,14, 0, 0}, { 6,20, 0, 0}, { 6,12, 0, 0}, { 7,13, 0, 0}, { 3,17, 0, 0}}; void prn (void) { int a = 0; printf (" 1 2 3 4 5 6 7 8 9\nA"); for (; a < 81; ++a) { printf ("%9d", b[g[a] | s[a]]); if (a % 9 == 8) { printf ("\n"); if (a < 80) printf("%c", a / 9 + 66); } } } int solve (int p) { int a = p, Y, x, // Unsolved Cell position for first time least Candidates checking y = 0, // 0 Represent Naked Single z = 512; // 512 Represent greatest value for first time least Candidates checking #if RJ > 3 prn (); #endif for (; a < q; ++a) // Search Naked/Hidden Single or Guess Candidate for each unsolved Cell position { if (B[z] > B[g[r[a]]]) // Check least Candidates in unsolved Cell position if (B[z = g[r[x = a]]] == 1) goto NHSCF; // Naked Single Candidate found Y = g[r[a]] & ((g[r[a]] ^ (g[w[r[a]][0]] | g[w[r[a]][1]] | g[w[r[a]][2]] | g[w[r[a]][3]] | g[w[r[a]][4]] | g[w[r[a]][5]] | g[w[r[a]][6]] | g[w[r[a]][7]])) | (g[r[a]] ^ (g[w[r[a]][6]] | g[w[r[a]][7]] | g[w[r[a]][8]] | g[w[r[a]][9]] | g[w[r[a]][10]] | g[w[r[a]][11]] | g[w[r[a]][12]] | g[w[r[a]][13]])) | (g[r[a]] ^ (g[w[r[a]][12]] | g[w[r[a]][13]] | g[w[r[a]][14]] | g[w[r[a]][15]] | g[w[r[a]][16]] | g[w[r[a]][17]] | g[w[r[a]][18]] | g[w[r[a]][19]]))); // Assign Hidden Single Candidates if (!Y) // Check Hidden Single Candidate not found in unsolved Cell position continue; z = Y; // Assign Hidden Single Candidate x = a; // Assign Hidden Single Cell position y = 1; // 1 Represent Hidden Single goto NHSCF; } for (; y < 27; ++y) // Search Naked/Hidden Tuples for each Unit { Y = (g[l[y][0]] ? 1 : 0) + (g[l[y][1]] ? 1 : 0) + (g[l[y][2]] ? 1 : 0) + (g[l[y][3]] ? 1 : 0) + (g[l[y][4]] ? 1 : 0) + (g[l[y][5]] ? 1 : 0) + (g[l[y][6]] ? 1 : 0) + (g[l[y][7]] ? 1 : 0) + (g[l[y][8]] ? 1 : 0); // Count Unit unsolved Cell positions if (Y < 4) continue; // Skip Unit for less than 4 unsolved Cell positions for (a = 0; a < 36; ++a) // Search Naked/Hidden pair Candidates for each Unit 36 pair Cell positions { if (!g[l[y][h[a][0]]] || !g[l[y][h[a][1]]]) { // Skip solved Cell positions if (!g[l[y][h[a][0]]]) a += 7 - h[a][0]; continue; } int K[2] = {g[l[y][h[a][0]]] | g[l[y][h[a][1]]], g[l[y][h[a][2]]] | g[l[y][h[a][3]]] | g[l[y][h[a][4]]] | g[l[y][h[a][5]]] | g[l[y][h[a][6]]] | g[l[y][h[a][7]]] | g[l[y][h[a][8]]]}; // Assign Candidates in Unit pair and other Cell positions if (B[K[0]] == 2) // Check Naked pair Candidates found in Unit pair Cell positions { if (!(K[0] & K[1])) // Check Naked pair Candidates not found in Unit other Cell positions continue; int k[7] = {g[l[y][h[a][2]]], g[l[y][h[a][3]]], g[l[y][h[a][4]]], g[l[y][h[a][5]]], g[l[y][h[a][6]]], g[l[y][h[a][7]]], g[l[y][h[a][8]]]}; // Backup and remove Naked pair Candidates from Unit other Cell positions g[l[y][h[a][2]]] &= ~K[0]; g[l[y][h[a][3]]] &= ~K[0]; g[l[y][h[a][4]]] &= ~K[0]; g[l[y][h[a][5]]] &= ~K[0]; g[l[y][h[a][6]]] &= ~K[0]; g[l[y][h[a][7]]] &= ~K[0]; g[l[y][h[a][8]]] &= ~K[0]; #if RJ > 2 printf ("%d) Found Naked pair Candidates %d at Unit %d Cells %d %d\n", a, b[K[0]], y, l[y][h[a][0]], l[y][h[a][1]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Naked pair Candidates %d at Unit %d Cells %d %d\n", a, b[K[0]], y, l[y][h[a][0]], l[y][h[a][1]]); #endif #if RJ > 3 prn (); #endif g[l[y][h[a][2]]] = k[0]; g[l[y][h[a][3]]] = k[1]; g[l[y][h[a][4]]] = k[2]; g[l[y][h[a][5]]] = k[3]; g[l[y][h[a][6]]] = k[4]; g[l[y][h[a][7]]] = k[5]; g[l[y][h[a][8]]] = k[6]; return 0; // Restore Naked pair Candidates to Unit other Cell positions } if (B[K[0] &= K[0] ^ K[1]] != 2) continue; // Check Hidden pair Candidates not found in Unit pair Cell positions int k[2] = {g[l[y][h[a][0]]], g[l[y][h[a][1]]]}; // Backup and remove other than Hidden pair Candidates from Unit pair Cell positions g[l[y][h[a][0]]] &= K[0]; g[l[y][h[a][1]]] &= K[0]; #if RJ > 2 printf ("%d) Found Hidden pair Candidates %d at Unit %d Cells %d %d\n", a, b[K[0]], y, l[y][h[a][0]], l[y][h[a][1]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Hidden pair Candidates %d at Unit %d Cells %d %d\n", a, b[K[0]], y, l[y][h[a][0]], l[y][h[a][1]]); #endif #if RJ > 3 prn (); #endif g[l[y][h[a][0]]] = k[0]; g[l[y][h[a][1]]] = k[1]; return 0; // Restore other than Hidden pair Candidates to Unit pair Cell positions } if (Y < 6) continue; // Skip triplets and quads for less than 6 unsolved Cell positions for (; a < 120; ++a) // Search Naked/Hidden triplet Candidates for each Unit 84 triplet Cell positions { if (!g[l[y][h[a][0]]] || !g[l[y][h[a][1]]] || !g[l[y][h[a][2]]]) { // Skip solved Cell positions if (!g[l[y][h[a][0]]]) { int K[7] = {27,20,14, 9, 5, 2, 0}; a += K[h[a][0]]; } else if (!g[l[y][h[a][1]]]) a += 7 - h[a][1]; continue; } int K[2] = {g[l[y][h[a][0]]] | g[l[y][h[a][1]]] | g[l[y][h[a][2]]], g[l[y][h[a][3]]] | g[l[y][h[a][4]]] | g[l[y][h[a][5]]] | g[l[y][h[a][6]]] | g[l[y][h[a][7]]] | g[l[y][h[a][8]]]}; // Assign Candidates in Unit triplet and other Cell positions if (B[K[0]] == 3) // Check Naked triplet Candidates found in Unit triplet Cell positions { if (!(K[0] & K[1])) // Check Naked triplet Candidates not found in Unit other Cell positions continue; int k[6] = {g[l[y][h[a][3]]], g[l[y][h[a][4]]], g[l[y][h[a][5]]], g[l[y][h[a][6]]], g[l[y][h[a][7]]], g[l[y][h[a][8]]]}; // Backup and remove Naked triplet Candidates from Unit other Cell positions g[l[y][h[a][3]]] &= ~K[0]; g[l[y][h[a][4]]] &= ~K[0]; g[l[y][h[a][5]]] &= ~K[0]; g[l[y][h[a][6]]] &= ~K[0]; g[l[y][h[a][7]]] &= ~K[0]; g[l[y][h[a][8]]] &= ~K[0]; #if RJ > 2 printf ("%d) Found Naked triplet Candidates %d at Unit %d Cells %d %d %d\n", a, b[K[0]], y, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Naked triplet Candidates %d at Unit %d Cells %d %d %d\n", a, b[K[0]], y, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]]); #endif #if RJ > 3 prn (); #endif g[l[y][h[a][3]]] = k[0]; g[l[y][h[a][4]]] = k[1]; g[l[y][h[a][5]]] = k[2]; g[l[y][h[a][6]]] = k[3]; g[l[y][h[a][7]]] = k[4]; g[l[y][h[a][8]]] = k[5]; return 0; // Restore Naked triplet Candidates to Unit other Cell positions } if (B[K[0] &= K[0] ^ K[1]] != 3) continue; // Check Hidden triplet Candidates not found in Unit triplet Cell positions int k[3] = {g[l[y][h[a][0]]], g[l[y][h[a][1]]], g[l[y][h[a][2]]]}; // Backup and remove other than Hidden triplet Candidates from Unit triplet Cell positions g[l[y][h[a][0]]] &= K[0]; g[l[y][h[a][1]]] &= K[0]; g[l[y][h[a][2]]] &= K[0]; #if RJ > 2 printf ("%d) Found Hidden triplet Candidates %d at Unit %d Cells %d %d %d\n", a, b[K[0]], y, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Hidden triplet Candidates %d at Unit %d Cells %d %d %d\n", a, b[K[0]], y, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]]); #endif #if RJ > 3 prn (); #endif g[l[y][h[a][0]]] = k[0]; g[l[y][h[a][1]]] = k[1]; g[l[y][h[a][2]]] = k[2]; return 0; // Restore other than Hidden triplet Candidates to Unit triplet Cell positions } if (Y < 8) continue; // Skip quads for less than 8 unsolved Cell positions for (; a < 246; ++a) // Search Naked/Hidden quad Candidates for each Unit 126 quad Cell positions { if (!g[l[y][h[a][0]]] || !g[l[y][h[a][1]]] || !g[l[y][h[a][2]]] || !g[l[y][h[a][3]]]) { // Skip solved Cell positions if (!g[l[y][h[a][0]]]) { int K[6] = {55,34,19, 9, 3, 0}; a += K[h[a][0]]; } else if (!g[l[y][h[a][1]]]) { int K[7] = {27,20,14, 9, 5, 2, 0}; a += K[h[a][1]]; } else if (!g[l[y][h[a][2]]]) a += 7 - h[a][2]; continue; } int K[2] = {g[l[y][h[a][0]]] | g[l[y][h[a][1]]] | g[l[y][h[a][2]]] | g[l[y][h[a][3]]], g[l[y][h[a][4]]] | g[l[y][h[a][5]]] | g[l[y][h[a][6]]] | g[l[y][h[a][7]]] | g[l[y][h[a][8]]]}; // Assign Candidates in Unit quad and other Cell positions if (B[K[0]] == 4) // Check Naked quad Candidates found in Unit quad Cell positions { if (!(K[0] & K[1])) // Check Naked quad Candidates not found in Unit other Cell positions continue; int k[5] = {g[l[y][h[a][4]]], g[l[y][h[a][5]]], g[l[y][h[a][6]]], g[l[y][h[a][7]]], g[l[y][h[a][8]]]}; // Backup and remove Naked quad Candidates from Unit other Cell positions g[l[y][h[a][4]]] &= ~K[0]; g[l[y][h[a][5]]] &= ~K[0]; g[l[y][h[a][6]]] &= ~K[0]; g[l[y][h[a][7]]] &= ~K[0]; g[l[y][h[a][8]]] &= ~K[0]; #if RJ > 2 printf ("%d) Found Naked quad Candidates %d at Unit %d Cells %d %d %d %d\n", a, b[K[0]], y, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]], l[y][h[a][3]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Naked quad Candidates %d at Unit %d Cells %d %d %d %d\n", a, b[K[0]], y, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]], l[y][h[a][3]]); #endif #if RJ > 3 prn (); #endif g[l[y][h[a][4]]] = k[0]; g[l[y][h[a][5]]] = k[1]; g[l[y][h[a][6]]] = k[2]; g[l[y][h[a][7]]] = k[3]; g[l[y][h[a][8]]] = k[4]; return 0; // Restore Naked quad Candidates to Unit other Cell positions } if (B[K[0] &= K[0] ^ K[1]] != 4) continue; // Check Hidden quad Candidates not found in Unit quad Cell positions int k[4] = {g[l[y][h[a][0]]], g[l[y][h[a][1]]], g[l[y][h[a][2]]], g[l[y][h[a][3]]]}; // Backup and remove other than Hidden quad Candidates from Unit quad Cell positions g[l[y][h[a][0]]] &= K[0]; g[l[y][h[a][1]]] &= K[0]; g[l[y][h[a][2]]] &= K[0]; g[l[y][h[a][3]]] &= K[0]; #if RJ > 2 printf ("%d) Found Hidden quad Candidates %d at Unit %d Cells %d %d %d %d\n", a, b[K[0]], y, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]], l[y][h[a][3]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Hidden quad Candidates %d at Unit %d Cells %d %d %d %d\n", a, b[K[0]], y, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]], l[y][h[a][3]]); #endif #if RJ > 3 prn (); #endif g[l[y][h[a][0]]] = k[0]; g[l[y][h[a][1]]] = k[1]; g[l[y][h[a][2]]] = k[2]; g[l[y][h[a][3]]] = k[3]; return 0; // Restore other than Hidden quad Candidates to Unit quad Cell positions } } for (y = 0; y < 54; ++y) // Search Intersection Removal for 54 Box-Line 3 Cell positions for (Y = g[j[y][0]] | g[j[y][1]] | g[j[y][2]]; a = Y & -Y; Y -= a) { // Search Box-Line 3 Cell positions for each Intersection Removal Candidate if ((g[j[y][3]] | g[j[y][4]] | g[j[y][5]] | g[j[y][6]] | g[j[y][7]] | g[j[y][8]]) & a) { // Check Intersection Removal Candidate found in Line other Cell positions if ((g[j[y][9]] | g[j[y][10]] | g[j[y][11]] | g[j[y][12]] | g[j[y][13]] | g[j[y][14]]) & a) continue; // Check Intersection Removal Candidate found in Box other Cell positions int k[6] = {g[j[y][3]], g[j[y][4]], g[j[y][5]], g[j[y][6]], g[j[y][7]], g[j[y][8]]}; // Backup and remove Intersection Removal Candidate from Line other Cell positions g[j[y][3]] &= ~a; g[j[y][4]] &= ~a; g[j[y][5]] &= ~a; g[j[y][6]] &= ~a; g[j[y][7]] &= ~a; g[j[y][8]] &= ~a; #if RJ > 2 printf ("%d) Found Pointing and Claiming Intersection Removal Candidate %d at Cells %d %d %d\n", y, b[a], j[y][0], j[y][1], j[y][2]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Pointing and Claiming Intersection Removal Candidate %d at Cells %d %d %d\n", y, b[a], j[y][0], j[y][1], j[y][2]); #endif #if RJ > 3 prn (); #endif g[j[y][3]] = k[0]; // Restore Intersection Removal Candidate to Line other Cell positions g[j[y][4]] = k[1]; g[j[y][5]] = k[2]; g[j[y][6]] = k[3]; g[j[y][7]] = k[4]; g[j[y][8]] = k[5]; return 0; } // Intersection Removal Candidate not found in Line other Cell positions if (!((g[j[y][9]] | g[j[y][10]] | g[j[y][11]] | g[j[y][12]] | g[j[y][13]] | g[j[y][14]]) & a)) continue; // Check Intersection Removal Candidate not found in Box other Cell positions int k[6] = {g[j[y][9]], g[j[y][10]], g[j[y][11]], g[j[y][12]], g[j[y][13]], g[j[y][14]]}; // Backup and remove Intersection Removal Candidate from Box other Cell positions g[j[y][9]] &= ~a; g[j[y][10]] &= ~a; g[j[y][11]] &= ~a; g[j[y][12]] &= ~a; g[j[y][13]] &= ~a; g[j[y][14]] &= ~a; #if RJ > 2 printf ("%d) Found Box-Line Reduction Intersection Removal Candidate %d at Cells %d %d %d\n", y, b[a], j[y][0], j[y][1], j[y][2]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Box-Line Reduction Intersection Removal Candidate %d at Cells %d %d %d\n", y, b[a], j[y][0], j[y][1], j[y][2]); #endif #if RJ > 3 prn (); #endif g[j[y][9]] = k[0]; // Restore Intersection Removal Candidate to Box other Cell positions g[j[y][10]] = k[1]; g[j[y][11]] = k[2]; g[j[y][12]] = k[3]; g[j[y][13]] = k[4]; g[j[y][14]] = k[5]; return 0; } for (Y = 0; Y < 10; Y += 9)// Search Basic Fishes for Row and Column wise for (y = 0; y < 9; ++y) // Search Basic Fishes for each Candidate { int k[9]; // Backup Basic Fish Candidate for Line Cell positions for (a = Y; a < Y + 9; ++a) k[a - Y] = (g[l[a][0]] & J[y] ? 1 : 0) | (g[l[a][1]] & J[y] ? 2 : 0) | (g[l[a][2]] & J[y] ? 4 : 0) | (g[l[a][3]] & J[y] ? 8 : 0) | (g[l[a][4]] & J[y] ? 16 : 0) | (g[l[a][5]] & J[y] ? 32 : 0) | (g[l[a][6]] & J[y] ? 64 : 0) | (g[l[a][7]] & J[y] ? 128 : 0) | (g[l[a][8]] & J[y] ? 256 : 0); for (a = 0; a < 36; ++a) { // Search X-Wing Candidate for Line 36 pair Cell positions int A = k[h[a][0]], K[2], X[2] = {-1,-1}; if (B[A] != 2 || A != k[h[a][1]]) { // Skip for X-Wing Candidate not found in Lines pair Cell positions if (B[A] != 2) a += 7 - h[a][0]; continue; } int L = A, Z = 0; for (; K[Z] = L & -L; L -= K[Z++]) { // Search opposite Line other Cell positions for X-Wing Candidate if (!((k[h[a][2]] | k[h[a][3]] | k[h[a][4]] | k[h[a][5]] | k[h[a][6]] | k[h[a][7]] | k[h[a][8]]) & K[Z])) continue; // Skip for X-Wing Candidate not found in opposite Line other Cell positions X[Z] = b[K[Z]] - Y + 8; g[l[X[Z]][h[a][2]]] &= ~J[y]; g[l[X[Z]][h[a][3]]] &= ~J[y]; g[l[X[Z]][h[a][4]]] &= ~J[y]; g[l[X[Z]][h[a][5]]] &= ~J[y]; g[l[X[Z]][h[a][6]]] &= ~J[y]; g[l[X[Z]][h[a][7]]] &= ~J[y]; g[l[X[Z]][h[a][8]]] &= ~J[y]; } // Remove X-Wing Candidate from opposite Line other Cell positions if (X[0] + X[1] == -2) continue; // Skip for X-Wing Candidate not found in opposite Lines other Cell positions #if RJ > 2 printf ("%d) Found %s wise X-Wing for Candidate %d at r%d%dc%d%d\n", a, Y ? "Column" : "Row", y + 1, Y ? b[K[0]] : h[a][0] + 1, Y ? b[K[1]] : h[a][1] + 1, Y ? h[a][0] + 1 : b[K[0]], Y ? h[a][1] + 1 : b[K[1]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore %s wise X-Wing for Candidate %d at r%d%dc%d%d\n", a, Y ? "Column" : "Row", y + 1, Y ? b[K[0]] : h[a][0] + 1, Y ? b[K[1]] : h[a][1] + 1, Y ? h[a][0] + 1 : b[K[0]], Y ? h[a][1] + 1 : b[K[1]]); #endif #if RJ > 3 prn (); #endif for (Z = 0; Z < 2; ++Z) { // Restore X-Wing Candidate to opposite Lines other Cell positions if (X[Z] == -1) continue; g[l[X[Z]][h[a][2]]] |= k[h[a][2]] & K[Z] ? J[y] : 0; g[l[X[Z]][h[a][3]]] |= k[h[a][3]] & K[Z] ? J[y] : 0; g[l[X[Z]][h[a][4]]] |= k[h[a][4]] & K[Z] ? J[y] : 0; g[l[X[Z]][h[a][5]]] |= k[h[a][5]] & K[Z] ? J[y] : 0; g[l[X[Z]][h[a][6]]] |= k[h[a][6]] & K[Z] ? J[y] : 0; g[l[X[Z]][h[a][7]]] |= k[h[a][7]] & K[Z] ? J[y] : 0; g[l[X[Z]][h[a][8]]] |= k[h[a][8]] & K[Z] ? J[y] : 0; } return 0; } for (; a < 120; ++a) // Search Sword Fish Candidate in Line 84 triplet Cell positions { int A = k[h[a][0]] | k[h[a][1]] | k[h[a][2]], K[3], X[3] = {-1,-1,-1}; if (!k[h[a][0]] || !k[h[a][1]] || !k[h[a][2]] || B[A] != 3) { // Skip for either solved Cell positions or Sord Fish Candidate not found in Lines triplet Cell positions if (!k[h[a][0]] || B[k[h[a][0]]] > 3) { int A[7] = {27,20,14, 9, 5, 2, 0}; a += A[h[a][0]]; } else if (!k[h[a][1]] || B[k[h[a][1]]] > 3) a += 7 - h[a][1]; continue; } int L = A, Z = 0; for (; K[Z] = L & -L; L -= K[Z++]) { // Search opposite Line other Cell positions for Sword Fish Candidate if (!((k[h[a][3]] | k[h[a][4]] | k[h[a][5]] | k[h[a][6]] | k[h[a][7]] | k[h[a][8]]) & K[Z])) continue; // Skip for Sword Fish Candidate not found in opposite Line other Cell positions X[Z] = b[K[Z]] - Y + 8; g[l[X[Z]][h[a][3]]] &= ~J[y]; g[l[X[Z]][h[a][4]]] &= ~J[y]; g[l[X[Z]][h[a][5]]] &= ~J[y]; g[l[X[Z]][h[a][6]]] &= ~J[y]; g[l[X[Z]][h[a][7]]] &= ~J[y]; g[l[X[Z]][h[a][8]]] &= ~J[y]; } // Remove Sword Fish Candidate from opposite Line other Cell positions if (X[0] + X[1] + X[2] == -3) continue; // Skip for Sword Fish Candidate not found in opposite Lines other Cell positions #if RJ > 2 printf ("%d) Found %s wise Sword Fish for Candidate %d at r%d%d%dc%d%d%d\n", a, Y ? "Column" : "Row", y + 1, Y ? b[K[0]] : h[a][0] + 1, Y ? b[K[1]] : h[a][1] + 1, Y ? b[K[2]] : h[a][2] + 1, Y ? h[a][0] + 1 : b[K[0]], Y ? h[a][1] + 1 : b[K[1]], Y ? h[a][2] + 1 : b[K[2]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore %s wise Sword Fish for Candidate %d at r%d%d%dc%d%d%d\n", a, Y ? "Column" : "Row", y + 1, Y ? b[K[0]] : h[a][0] + 1, Y ? b[K[1]] : h[a][1] + 1, Y ? b[K[2]] : h[a][2] + 1, Y ? h[a][0] + 1 : b[K[0]], Y ? h[a][1] + 1 : b[K[1]], Y ? h[a][2] + 1 : b[K[2]]); #endif #if RJ > 3 prn (); #endif for (Z = 0; Z < 3; ++Z) { // Restore Sword Fish Candidate to opposite Lines other Cell positions if (X[Z] == -1) continue; g[l[X[Z]][h[a][3]]] |= k[h[a][3]] & K[Z] ? J[y] : 0; g[l[X[Z]][h[a][4]]] |= k[h[a][4]] & K[Z] ? J[y] : 0; g[l[X[Z]][h[a][5]]] |= k[h[a][5]] & K[Z] ? J[y] : 0; g[l[X[Z]][h[a][6]]] |= k[h[a][6]] & K[Z] ? J[y] : 0; g[l[X[Z]][h[a][7]]] |= k[h[a][7]] & K[Z] ? J[y] : 0; g[l[X[Z]][h[a][8]]] |= k[h[a][8]] & K[Z] ? J[y] : 0; } return 0; } for (; a < 246; ++a) // Search Jelly Fish Candidate in Line 126 quad Cell positions { int A = k[h[a][0]] | k[h[a][1]] | k[h[a][2]] | k[h[a][3]], K[4], X[4] = {-1,-1,-1,-1}; if (!k[h[a][0]] || !k[h[a][1]] || !k[h[a][2]] || !k[h[a][3]] || B[A] != 4) { // Skip for either solved Cell positions or Jelly Fish Candidate not found in Line quad Cell positions if (!k[h[a][0]] || B[k[h[a][0]]] > 4) { int A[6] = {55,34,19, 9, 3, 0}; a += A[h[a][0]]; } else if (!k[h[a][1]] || B[k[h[a][1]]] > 4) { int A[7] = {27,20,14, 9, 5, 2, 0}; a += A[h[a][1]]; } else if (!k[h[a][2]] || B[k[h[a][2]]] > 4) a += 7 - h[a][2]; continue; } int L = A, Z = 0; for (; K[Z] = L & -L; L -= K[Z++]) { // Search opposite Line other Cell positions for Jelly Fish Candidate if (!((k[h[a][4]] | k[h[a][5]] | k[h[a][6]] | k[h[a][7]] | k[h[a][8]]) & K[Z])) continue; // Skip for Jelly Fish Candidate not found in opposite Line other Cell positions X[Z] = b[K[Z]] - Y + 8; g[l[X[Z]][h[a][4]]] &= ~J[y]; g[l[X[Z]][h[a][5]]] &= ~J[y]; g[l[X[Z]][h[a][6]]] &= ~J[y]; g[l[X[Z]][h[a][7]]] &= ~J[y]; g[l[X[Z]][h[a][8]]] &= ~J[y]; } // Remove Jelly Fish Candidate from opposite Line other Cell positions if (X[0] + X[1] + X[2] + X[3] == -4) continue; // Skip for Jelly Fish Candidate not found in opposite Lines other Cell positions #if RJ > 2 printf ("%d) Found %s wise Jelly Fish for Candidate %d at r%d%d%d%dc%d%d%d%d\n", a, Y ? "Column" : "Row", y + 1, Y ? b[K[0]] : h[a][0] + 1, Y ? b[K[1]] : h[a][1] + 1, Y ? b[K[2]] : h[a][2] + 1, Y ? b[K[3]] : h[a][3] + 1, Y ? h[a][0] + 1 : b[K[0]], Y ? h[a][1] + 1 : b[K[1]], Y ? h[a][2] + 1 : b[K[2]], Y ? h[a][3] + 1 : b[K[3]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore %s wise Jelly Fish for Candidate %d at r%d%d%d%dc%d%d%d%d\n", a, Y ? "Column" : "Row", y + 1, Y ? b[K[0]] : h[a][0] + 1, Y ? b[K[1]] : h[a][1] + 1, Y ? b[K[2]] : h[a][2] + 1, Y ? b[K[3]] : h[a][3] + 1, Y ? h[a][0] + 1 : b[K[0]], Y ? h[a][1] + 1 : b[K[1]], Y ? h[a][2] + 1 : b[K[2]], Y ? h[a][3] + 1 : b[K[3]]); #endif #if RJ > 3 prn (); #endif for (Z = 0; Z < 4; ++Z) { // Restore Jelly Fish Candidate to opposite Lines other Cell positions if (X[Z] == -1) continue; g[l[X[Z]][h[a][4]]] |= k[h[a][4]] & K[Z] ? J[y] : 0; g[l[X[Z]][h[a][5]]] |= k[h[a][5]] & K[Z] ? J[y] : 0; g[l[X[Z]][h[a][6]]] |= k[h[a][6]] & K[Z] ? J[y] : 0; g[l[X[Z]][h[a][7]]] |= k[h[a][7]] & K[Z] ? J[y] : 0; g[l[X[Z]][h[a][8]]] |= k[h[a][8]] & K[Z] ? J[y] : 0; } return 0; } } for (y = 0; y < 54; y += 9)// Search XY-Wings Type 1 X-Wings wise { int K[4] = {y}; for (; K[0] < y + 6; ++K[0]) { // Search top left Cell position if (!g[K[0]]) continue; // Skip for top left Cell empty for (K[1] = y + (K[0] < y + 3 ? 3 : 6); K[1] < y + 9; ++K[1]) { // Search top right Cell position if (!g[K[1]]) continue; // Skip for top right Cell empty for (K[2] = K[0] - y + (y < 27 ? 27 : 54); K[2] < 81; K[2] += 9) { // Search bottom left Cell position K[3] = K[1] - y + (y < 27 ? 27 : 54); if (!g[K[2]] || !g[K[3]]) continue; // Skip for bottom either left or right Cell empty for (a = 0; a < 4; ++a) { // Search four combinations of Pivot, Pincers and elimination Cell positions if (B[g[K[W[a][0]]] | g[K[W[a][1]]] | g[K[W[a][2]]]] != 3 || g[K[W[a][0]]] & g[K[W[a][1]]] & g[K[W[a][2]]] || !(g[K[W[a][1]]] & g[K[W[a][2]]] & g[K[W[a][3]]])) continue; // Skip for Cells candidates either not three or common or no elimination int k = g[K[W[a][3]]]; // Backup XY-Wing Type 1 elimination Cell candidates and eliminate Pincers common candidate from elimination Cell position g[K[W[a][3]]] &= ~(g[K[W[a][1]]] & g[K[W[a][2]]]); #if RJ > 2 printf ("%d) Found XY-Wing Type 1 in Cells %d %d %d remove candidate %d from cell %d\n", a, K[W[a][0]], K[W[a][1]], K[W[a][2]], b[g[K[W[a][1]]] & g[K[W[a][2]]]], K[W[a][3]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore XY-Wing Type 1 in Cells %d %d %d add candidate %d to cell %d\n", a, K[W[a][0]], K[W[a][1]], K[W[a][2]], b[g[K[W[a][1]]] & g[K[W[a][2]]]], K[W[a][3]]); #endif #if RJ > 3 prn (); #endif g[K[W[a][3]]] = k; return 0; // Restore XY-Wing Type 1 elimination Cell candidates } } } } } for (y = 0; y < 2; ++y) // Search XY-Wings Type 2 and XYZ-Wings Box-Line wise for (a = 0; a < q; ++a) // Search Pivot unsolved Cell position wise { int A = r[a]; // Assign Pivot Cell position if (B[g[A]] < 2 || B[g[A]] > 3) continue; // Skip for Pivot candidates either less than two or greater than three for (Y = W[4][y]; Y < W[5][y]; ++Y) { // Search first Pincer Cell position Box wise if (B[g[w[A][Y]]] != 2 || B[g[A] | g[w[A][Y]]] != 3) continue; // Skip for candidates either Box Pincer not two or Pivot and Box Pincer not three int K = W[6][y]; for (; K < W[7][y]; ++K) { // Search second Pincer Cell position Line wise if (B[g[w[A][K]]] != 2 || B[g[A] | g[w[A][Y]] | g[w[A][K]]] != 3) continue; // Skip for candidates either Line Pincer not two or Cells not three if (!(g[A] & g[w[A][Y]] & g[w[A][K]])) { // Skip for no common candidate for XY-Wing Type 2 int L = W[K < W[10][y] ? 6 : 10][y], k[5] = {g[w[A][W[8][y]]], g[w[A][W[9][y]]], g[w[w[A][Y]][L]], g[w[w[A][Y]][L + 1]], g[w[w[A][Y]][L + 2]]}; // Backup XY-Wing Type 2 elimination Cells candidates if (!(g[w[A][Y]] & g[w[A][K]] & (k[0] | k[1] | k[2] | k[3] | k[4]))) continue; // Skip for no eliminations g[w[A][W[8][y]]] &= ~(g[w[A][Y]] & g[w[A][K]]); g[w[A][W[9][y]]] &= ~(g[w[A][Y]] & g[w[A][K]]); g[w[w[A][Y]][L]] &= ~(g[w[A][Y]] & g[w[A][K]]); g[w[w[A][Y]][L + 1]] &= ~(g[w[A][Y]] & g[w[A][K]]); g[w[w[A][Y]][L + 2]] &= ~(g[w[A][Y]] & g[w[A][K]]); #if RJ > 2 printf ("%d) Found XY-Wing Type 2 in Cells %d %d %d remove candidate %d from cells %d %d %d %d %d\n", y, A, w[A][Y], w[A][K], b[g[w[A][Y]] & g[w[A][K]]], w[A][W[8][y]], w[A][W[9][y]], w[w[A][Y]][L], w[w[A][Y]][L + 1], w[w[A][Y]][L + 2]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore XY-Wing Type 2 in Cells %d %d %d add candidate %d to cells %d %d %d %d %d\n", y, A, w[A][Y], w[A][K], b[g[w[A][Y]] & g[w[A][K]]], w[A][W[8][y]], w[A][W[9][y]], w[w[A][Y]][L], w[w[A][Y]][L + 1], w[w[A][Y]][L + 2]); #endif #if RJ > 3 prn (); #endif g[w[A][W[8][y]]] = k[0]; g[w[A][W[9][y]]] = k[1]; g[w[w[A][Y]][L]] = k[2]; g[w[w[A][Y]][L + 1]] = k[3]; g[w[w[A][Y]][L + 2]] = k[4]; return 0; // Restore XY-Wing Type 2 elimination Cells candidates } if (B[g[w[A][Y]] & g[w[A][K]]] != 1 || B[g[A] & g[w[A][Y]] & g[w[A][K]]] != 1 || !(g[w[A][Y]] & g[w[A][K]] & (g[w[A][W[8][y]]] | g[w[A][W[9][y]]]))) continue; // Skip for either Pincers no common candidate or Cells no common candidate or no eliminations int k[2] = {g[w[A][W[8][y]]], g[w[A][W[9][y]]]}; // Backup XYZ-Wing elimination Cells candidates and remove Pincers common candidate from elimination Cell positions g[w[A][W[8][y]]] &= ~(g[w[A][Y]] & g[w[A][K]]); g[w[A][W[9][y]]] &= ~(g[w[A][Y]] & g[w[A][K]]); #if RJ > 2 printf ("%d) Found XYZ-Wing in Cells %d %d %d remove candidate %d from cells %d %d\n", Y, A, w[A][Y], w[A][K], b[g[w[A][Y]] & g[w[A][K]]], w[A][W[8][y]], w[A][W[9][y]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore XYZ-Wing in Cells %d %d %d add candidate %d to cells %d %d\n", Y, A, w[A][Y], w[A][K], b[g[w[A][Y]] & g[w[A][K]]], w[A][W[8][y]], w[A][W[9][y]]); #endif #if RJ > 3 prn (); #endif g[w[A][W[8][y]]] = k[0]; g[w[A][W[9][y]]] = k[1]; return 0; // Restore XYZ-Wing elimination Cells candidates } } } y = 2; // 2 Represent Guess NHSCF: if (x > p) // Check current Cell position for sorting and eliminating { a = r[p]; r[p] = r[x]; r[x] = a; } for (Y = g[r[p]], g[r[p]] = 0; s[r[p]] = z & -z; z -= s[r[p]]) { // Backup and clear current Cell Candidates and solve current Cell position for each Candidate int k = 0; for (++n[y], a = 0; a < 20; ++a) if (g[w[r[p]][a]] & s[r[p]]) { if(g[w[r[p]][a]] == s[r[p]]) break; // Found one Candidate assigned k |= J[a]; // Backup 20 affected Cell positions current Candidate g[w[r[p]][a]] &= ~s[r[p]]; } // Remove current Candidate from 20 affected Cell positions #if RJ > 2 printf ("%d) Apply %s Candidate %d from Candidates %d at Cell %d\n", p, y ? (y == 2 ? "Trial and Error" : "Hidden Single") : "Naked Single", b[s[r[p]]], b[Y], r[p]); #endif if (a == 20 && (p + 1 == q || solve (p + 1))) return 1; // Check either all Cell positions solved or recursive solve for next unsolved Cell position #if RJ > 2 printf ("%d) Restore %s Candidate %d from Candidates %d at Cell %d\n", p, y ? (y == 2 ? "Trial and Error" : "Hidden Single") : "Naked Single", b[s[r[p]]], b[Y], r[p]); #endif #if RJ > 3 prn (); #endif while (a) // Restore current Candidate to 20 affected Cell positions if (k & J[--a]) g[w[r[p]][a]] |= s[r[p]]; } g[r[p]] = Y; // Restore Candidates to current Cell position return 0; } int check (int p, int q) { int a = 0; for (; a < 20; ++a) if (s[w[p][a]] == q) // Check duplicate Candidate in 20 affected clue Cell positions return 0; return q; } int invalid (void) { int a, p = 0; for (; p < 81; ++p) if (!s[p]) // Check unsolved Cell position { for (a = 1; a < 257; a <<= 1) g[p] |= check (p, a);// Check constraint and assign Candidate for unsolved Cell position if (!g[p]) // Check no Candidate assigned return p; r[q++] = p; // Assign unsolved Cell position for sorting and eliminating } else if (!check (p, s[p])) return p; // Check constraint for clue Cell position return 0; } int main (void) { int a = -1, m, i = 0, t = 0, u = 0, v = 0, y = 0; float c, d = 0, e = 0, f = 0, k = 0; FILE *o = fopen ("sudoku.txt", "r"); if (o == NULL) printf ("Unable to open sudoku.txt file for read !!\n"); else do { if ((m = fgetc (o)) != 10 && m != EOF && a < 80) s[++a] = m < 49 || m > 57 ? 0 : J[m - 49]; // Assign clue Cell positions else if (m == 10 || m == EOF) { #if RJ > 1 printf ("\n"); #endif q = n[0] = n[1] = n[2] = 0; c = clock (); while (a < 80) // Clear remaining unsolved Cell positions s[++a] = 0; if (a = invalid ()) { for (; a > -1; --a) g[a] = 0; c = (clock () - c) / CLOCKS_PER_SEC; d += c; ++t; ++i; #if RJ printf ("%ld) Error: Invalid Sudoku! # I%ld", t, i); #endif } else if (!q) { c = (clock () - c) / CLOCKS_PER_SEC; k += c; ++t; ++y; #if RJ printf ("%ld) Valid Sudoku # V%ld", t, y); #endif } else if (solve (0)) { c = (clock () - c) / CLOCKS_PER_SEC; e += c; ++t; ++v; #if RJ printf ("%ld) ", t); for (a = 0; a < 81; ++a) printf ("%d", b[s[a]]); printf (" # S%ld", v); #endif } else { for (a = 0; a < 81; ++a) g[a] = 0; c = (clock () - c) / CLOCKS_PER_SEC; f += c; ++t; ++u; #if RJ printf ("%ld) Error: Unsolvable Sudoku! # U%ld", t, u); #endif } #if RJ printf (" # N%ld # H%ld # G%ld # %f\n", n[0], n[1], n[2], c); #endif a = -1; } #if RJ > 1 if (m != 10 && m != 13 && m != EOF) printf ("%c", m); #endif } while (m != EOF); printf ("=======================================\n"); printf ("Total Sudoku puzzle read : %ld\n", t); printf ("Total time for all puzzles : %f\n", d + k + e + f); printf ("Average time per puzzle : %f\n", t ? (d + k + e + f) / t : 0); printf ("Number of valid puzzles : %ld\n", y); printf ("Time for valid puzzles : %f\n", k); printf ("Average time per valid : %f\n", y ? k / y : 0); printf ("Number of invalid puzzles : %ld\n", i); printf ("Time for invalid puzzles : %f\n", d); printf ("Average time per invalid : %f\n", i ? d / i : 0); printf ("Number of solved puzzles : %ld\n", v); printf ("Time for solved puzzles : %f\n", e); printf ("Average time per solved : %f\n", v ? e / v : 0); printf ("Number of unsolved puzzle : %ld\n", u); printf ("Time for unsolved puzzles : %f\n", f); printf ("Average time per unsolved : %f\n", u ? f / u : 0); if (fclose (o) == EOF) printf ("Unable to close sudoku.txt file !!"); }