#include #include #ifndef RJ #define RJ 1 // 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 Cell Values for each unsolved Cell positions Grid wise n[5]; // Number of Naked Singles, Hidden Singles, Guesses and Depth Grid wise static int b[512] = { // Bitwise to digit Cell Values 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 Cell Values 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 peer 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 peer 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}}, W[17][4] = { // References for XY-Wings Type 2, XYZ-Wings and XYZ-Wing Hybrid Type 1 and Type 2 { 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}, { 8, 6, 0, 0}, { 9, 8, 0, 0}, {12,10, 0, 0}, {10, 7, 0, 0}, {11, 9, 0, 0}, {13,11, 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 = 0, Y, x, // Unsolved Cell position for first time least Cell Values checking y = 0, // 0 Represent Naked Single Cell position found z = 512; // 512 Represent greatest Cell Value for first time least Cell Values checking #if RJ > 3 prn (); #endif for (; a < 27; ++a) // Check zero state for each Unit if ((g[l[a][0]] ? 1 : 0) + (g[l[a][1]] ? 1 : 0) + (g[l[a][2]] ? 1 : 0) + (g[l[a][3]] ? 1 : 0) + (g[l[a][4]] ? 1 : 0) + (g[l[a][5]] ? 1 : 0) + (g[l[a][6]] ? 1 : 0) + (g[l[a][7]] ? 1 : 0) + (g[l[a][8]] ? 1 : 0) != B[g[l[a][0]] | g[l[a][1]] | g[l[a][2]] | g[l[a][3]] | g[l[a][4]] | g[l[a][5]] | g[l[a][6]] | g[l[a][7]] | g[l[a][8]]]) return 0; for (a = p; a < q; ++a) // Search Naked Single Cell Value or Guess Cell Values for each unsolved Cell position if (B[z] > B[g[r[a]]]) // Check least Cell Values in current unsolved Cell position if (B[z = g[r[x = a]]] == 1) goto NHSCF; // Naked Single Cell Value found in current unsolved Cell position for (a = p; a < q; ++a) // Search Hidden Single Cell Value for each unsolved Cell position { 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 Cell Values if (!Y) // Check Hidden Single Cell Value not found in unsolved Cell position continue; z = Y; // Assign Hidden Single Cell Value x = a; // Assign Hidden Single Cell position y = 1; // 1 Represent Hidden Single Cell position found goto NHSCF; } for (; y < 27; ++y) // Search Naked/Hidden Tuples Cell Values 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 Cell Values 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 Cell Values in Unit pair Cell positions and Unit other Cell positions if (B[K[0]] == 2) // Check Naked pair Cell Values found in Unit pair Cell positions { if (!(K[0] & K[1])) // Check Naked pair Cell Values 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 Cell Values 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 Cell Values %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 Cell Values %d at Unit %d Cells %d %d\n", a, b[K[0]], y, l[y][h[a][0]], l[y][h[a][1]]); #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]; #if RJ > 3 prn (); #endif return 0; // Restore Naked pair Cell Values to Unit other Cell positions } if (B[K[0] &= K[0] ^ K[1]] != 2) continue; // Check Hidden pair Cell Values 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 Cell Values 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 Cell Values %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 Cell Values %d at Unit %d Cells %d %d\n", a, b[K[0]], y, l[y][h[a][0]], l[y][h[a][1]]); #endif g[l[y][h[a][0]]] = k[0]; g[l[y][h[a][1]]] = k[1]; #if RJ > 3 prn (); #endif return 0; // Restore other than Hidden pair Cell Values 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 Cell Values 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 Cell Values in Unit triplet Cell positions and Unit other Cell positions if (B[K[0]] == 3) // Check Naked triplet Cell Values found in Unit triplet Cell positions { if (!(K[0] & K[1])) // Check Naked triplet Cell Values 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 Cell Values 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 Cell Values %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 Cell Values %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 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]; #if RJ > 3 prn (); #endif return 0; // Restore Naked triplet Cell Values to Unit other Cell positions } if (B[K[0] &= K[0] ^ K[1]] != 3) continue; // Check Hidden triplet Cell Values 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 Cell Values 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 Cell Values %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 Cell Values %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 g[l[y][h[a][0]]] = k[0]; g[l[y][h[a][1]]] = k[1]; g[l[y][h[a][2]]] = k[2]; #if RJ > 3 prn (); #endif return 0; // Restore other than Hidden triplet Cell Values 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 Cell Values 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 Cell Values in Unit quad Cell positions and Unit other Cell positions if (B[K[0]] == 4) // Check Naked quad Cell Values found in Unit quad Cell positions { if (!(K[0] & K[1])) // Check Naked quad Cell Values 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 Cell Values 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 Cell Values %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 Cell Values %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 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]; #if RJ > 3 prn (); #endif return 0; // Restore Naked quad Cell Values to Unit other Cell positions } if (B[K[0] &= K[0] ^ K[1]] != 4) continue; // Check Hidden quad Cell Values 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 Cell Values 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 Cell Values %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 Cell Values %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 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]; #if RJ > 3 prn (); #endif return 0; // Restore other than Hidden quad Cell Values 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 Value 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 Value 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 Value 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 Value 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 Value %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 Value %d at Cells %d %d %d\n", y, b[a], j[y][0], j[y][1], j[y][2]); #endif g[j[y][3]] = k[0]; // Restore Intersection Removal Value 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]; #if RJ > 3 prn (); #endif return 0; } // Intersection Removal Value 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 Value 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 Value 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 Value %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 Value %d at Cells %d %d %d\n", y, b[a], j[y][0], j[y][1], j[y][2]); #endif g[j[y][9]] = k[0]; // Restore Intersection Removal Value 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]; #if RJ > 3 prn (); #endif return 0; } for (Y = 0; Y < 10; Y += 9)// Search Basic Fishes for Row and Column wise for (y = 1; y < 257; y <<= 1) { // Search Basic Fishes for each Cell Value int k[9]; // Backup Basic Fish Value for Line Cell positions for (a = Y; a < Y + 9; ++a) k[a - Y] = (g[l[a][0]] & y ? 1 : 0) | (g[l[a][1]] & y ? 2 : 0) | (g[l[a][2]] & y ? 4 : 0) | (g[l[a][3]] & y ? 8 : 0) | (g[l[a][4]] & y ? 16 : 0) | (g[l[a][5]] & y ? 32 : 0) | (g[l[a][6]] & y ? 64 : 0) | (g[l[a][7]] & y ? 128 : 0) | (g[l[a][8]] & y ? 256 : 0); for (a = 0; a < 36; ++a) { // Search X-Wing Value 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 Value 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 Value 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 Value not found in opposite Line other Cell positions X[Z] = b[K[Z]] - Y + 8; g[l[X[Z]][h[a][2]]] &= ~y; g[l[X[Z]][h[a][3]]] &= ~y; g[l[X[Z]][h[a][4]]] &= ~y; g[l[X[Z]][h[a][5]]] &= ~y; g[l[X[Z]][h[a][6]]] &= ~y; g[l[X[Z]][h[a][7]]] &= ~y; g[l[X[Z]][h[a][8]]] &= ~y; } // Remove X-Wing Value from opposite Line other Cell positions if (X[0] + X[1] == -2) continue; // Skip for X-Wing Value not found in opposite Lines other Cell positions #if RJ > 2 printf ("%d) Found %s wise X-Wing for Value %d at r%d%dc%d%d\n", a, Y ? "Column" : "Row", b[y], 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 Value %d at r%d%dc%d%d\n", a, Y ? "Column" : "Row", b[y], 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 for (Z = 0; Z < 2; ++Z) { // Restore X-Wing Value to opposite Lines other Cell positions if (X[Z] == -1) continue; g[l[X[Z]][h[a][2]]] |= k[h[a][2]] & K[Z] ? y : 0; g[l[X[Z]][h[a][3]]] |= k[h[a][3]] & K[Z] ? y : 0; g[l[X[Z]][h[a][4]]] |= k[h[a][4]] & K[Z] ? y : 0; g[l[X[Z]][h[a][5]]] |= k[h[a][5]] & K[Z] ? y : 0; g[l[X[Z]][h[a][6]]] |= k[h[a][6]] & K[Z] ? y : 0; g[l[X[Z]][h[a][7]]] |= k[h[a][7]] & K[Z] ? y : 0; g[l[X[Z]][h[a][8]]] |= k[h[a][8]] & K[Z] ? y : 0; } #if RJ > 3 prn (); #endif return 0; } for (; a < 120; ++a) // Search Sword Fish Value 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 Value 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 Value 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 Value not found in opposite Line other Cell positions X[Z] = b[K[Z]] - Y + 8; g[l[X[Z]][h[a][3]]] &= ~y; g[l[X[Z]][h[a][4]]] &= ~y; g[l[X[Z]][h[a][5]]] &= ~y; g[l[X[Z]][h[a][6]]] &= ~y; g[l[X[Z]][h[a][7]]] &= ~y; g[l[X[Z]][h[a][8]]] &= ~y; } // Remove Sword Fish Value from opposite Line other Cell positions if (X[0] + X[1] + X[2] == -3) continue; // Skip for Sword Fish Value not found in opposite Lines other Cell positions #if RJ > 2 printf ("%d) Found %s wise Sword Fish for Value %d at r%d%d%dc%d%d%d\n", a, Y ? "Column" : "Row", b[y], 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 Value %d at r%d%d%dc%d%d%d\n", a, Y ? "Column" : "Row", b[y], 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 for (Z = 0; Z < 3; ++Z) { // Restore Sword Fish Value to opposite Lines other Cell positions if (X[Z] == -1) continue; g[l[X[Z]][h[a][3]]] |= k[h[a][3]] & K[Z] ? y : 0; g[l[X[Z]][h[a][4]]] |= k[h[a][4]] & K[Z] ? y : 0; g[l[X[Z]][h[a][5]]] |= k[h[a][5]] & K[Z] ? y : 0; g[l[X[Z]][h[a][6]]] |= k[h[a][6]] & K[Z] ? y : 0; g[l[X[Z]][h[a][7]]] |= k[h[a][7]] & K[Z] ? y : 0; g[l[X[Z]][h[a][8]]] |= k[h[a][8]] & K[Z] ? y : 0; } #if RJ > 3 prn (); #endif return 0; } for (; a < 246; ++a) // Search Jelly Fish Value 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 Value 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 Value 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 Value not found in opposite Line other Cell positions X[Z] = b[K[Z]] - Y + 8; g[l[X[Z]][h[a][4]]] &= ~y; g[l[X[Z]][h[a][5]]] &= ~y; g[l[X[Z]][h[a][6]]] &= ~y; g[l[X[Z]][h[a][7]]] &= ~y; g[l[X[Z]][h[a][8]]] &= ~y; } // Remove Jelly Fish Value from opposite Line other Cell positions if (X[0] + X[1] + X[2] + X[3] == -4) continue; // Skip for Jelly Fish Value not found in opposite Lines other Cell positions #if RJ > 2 printf ("%d) Found %s wise Jelly Fish for Value %d at r%d%d%d%dc%d%d%d%d\n", a, Y ? "Column" : "Row", b[y], 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 Value %d at r%d%d%d%dc%d%d%d%d\n", a, Y ? "Column" : "Row", b[y], 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 for (Z = 0; Z < 4; ++Z) { // Restore Jelly Fish Value to opposite Lines other Cell positions if (X[Z] == -1) continue; g[l[X[Z]][h[a][4]]] |= k[h[a][4]] & K[Z] ? y : 0; g[l[X[Z]][h[a][5]]] |= k[h[a][5]] & K[Z] ? y : 0; g[l[X[Z]][h[a][6]]] |= k[h[a][6]] & K[Z] ? y : 0; g[l[X[Z]][h[a][7]]] |= k[h[a][7]] & K[Z] ? y : 0; g[l[X[Z]][h[a][8]]] |= k[h[a][8]] & K[Z] ? y : 0; } #if RJ > 3 prn (); #endif 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 not unsolved 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 not unsolved for (K[2] = K[0] - y + (y < 27 ? 27 : 54); K[2] < 81; K[2] += 9) { // Search bottom left Cell position K[3] = K[2] - K[0] + K[1]; if (!g[K[2]] || !g[K[3]]) continue; // Skip for bottom either left or right Cell not unsolved 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 Values either not three digits or common digit or no elimination int k = g[K[W[a][3]]]; // Backup XY-Wings Type 1 elimination Cell Values and eliminate Pincer Cells common Value 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-Wings Type 1 in Cells %d %d %d Values %d remove %d from Cell %d\n", y, K[W[a][0]], K[W[a][1]], K[W[a][2]], b[g[K[W[a][1]]] | g[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-Wings Type 1 in Cells %d %d %d Values %d add %d to Cell %d\n", y, K[W[a][0]], K[W[a][1]], K[W[a][2]], b[g[K[W[a][1]]] | g[K[W[a][2]]]], b[g[K[W[a][1]]] & g[K[W[a][2]]]], K[W[a][3]]); #endif g[K[W[a][3]]] = k; #if RJ > 3 prn (); #endif return 0; // Restore XY-Wings Type 1 elimination Cell Values } } } } } for (y = 0; y < 2; ++y) // Search XY-Wings Type 2, XYZ-Wings and XYZ-Wings Hybrid Type 1 and Type 2 for (a = p; a < q; ++a) // Search Pivot unsolved Cell position wise { int K[4] = {r[a]}; // Assign Pivot Cell position if (B[g[K[0]]] > 3) continue; // Skip for Pivot Cell Values more than three digits for (K[1] = W[4][y]; K[1] < W[5][y]; ++K[1]) { // Search first Pincer Cell position Box wise if (B[g[w[K[0]][K[1]]]] != 2 || B[g[K[0]] | g[w[K[0]][K[1]]]] != 3) continue; // Skip for Cell Values either Box Pincer not two digits or Pivot and Box Pincer not three digits for (K[2] = W[6][y]; K[2] < W[7][y]; ++K[2]) { // Search second Pincer Cell position Line wise if (B[g[w[K[0]][K[2]]]] != 2 || B[g[K[0]] | g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]]] != 3) continue; // Skip for Cell Values either Line Pincer not two digits or Cells not three digits K[3] = W[K[2] < W[10][y] ? 6 : 10][y]; // Assign pincer Cells common first elimination Cell position if (!(g[K[0]] & g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]])) { // Search no common Cells Value for XY-Wings Type 2 int k[5] = {g[w[K[0]][W[8][y]]], g[w[K[0]][W[9][y]]], g[w[w[K[0]][K[1]]][K[3]]], g[w[w[K[0]][K[1]]][K[3] + 1]], g[w[w[K[0]][K[1]]][K[3] + 2]]}; // Backup XY-Wings Type 2 elimination Cells Values if (!(g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]] & (k[0] | k[1] | k[2] | k[3] | k[4]))) continue; // Skip for no eliminations // Remove XY-Wings Type 2 Pincer Cells common Value from elimination Cell positions g[w[K[0]][W[8][y]]] &= ~(g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]); g[w[K[0]][W[9][y]]] &= ~(g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]); g[w[w[K[0]][K[1]]][K[3]]] &= ~(g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]); g[w[w[K[0]][K[1]]][K[3] + 1]] &= ~(g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]); g[w[w[K[0]][K[1]]][K[3] + 2]] &= ~(g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]); #if RJ > 2 printf ("%d) Found XY-Wings Type 2 in Cells %d %d %d Values %d remove %d from Cells %d %d %d %d %d\n", a, K[0], w[K[0]][K[1]], w[K[0]][K[2]], b[g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]]], b[g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]], w[K[0]][W[8][y]], w[K[0]][W[9][y]], w[w[K[0]][K[1]]][K[3]], w[w[K[0]][K[1]]][K[3] + 1], w[w[K[0]][K[1]]][K[3] + 2]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore XY-Wings Type 2 in Cells %d %d %d Values %d add %d to Cells %d %d %d %d %d\n", a, K[0], w[K[0]][K[1]], w[K[0]][K[2]], b[g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]]], b[g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]], w[K[0]][W[8][y]], w[K[0]][W[9][y]], w[w[K[0]][K[1]]][K[3]], w[w[K[0]][K[1]]][K[3] + 1], w[w[K[0]][K[1]]][K[3] + 2]); #endif g[w[K[0]][W[8][y]]] = k[0]; g[w[K[0]][W[9][y]]] = k[1]; g[w[w[K[0]][K[1]]][K[3]]] = k[2]; g[w[w[K[0]][K[1]]][K[3] + 1]] = k[3]; g[w[w[K[0]][K[1]]][K[3] + 2]] = k[4]; #if RJ > 3 prn (); #endif return 0; // Restore XY-Wings Type 2 elimination Cells Values } if (B[g[K[0]]] != 3 || B[g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]] != 1) continue; // Skip for either Pivot Cell Values not three digits or Pincer Cells no common Value if (g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]] & (g[w[K[0]][W[8][y]]] | g[w[K[0]][W[9][y]]])) { // Search for XYZ-Wings elimination Cells Value int k[2] = {g[w[K[0]][W[8][y]]], g[w[K[0]][W[9][y]]]}; // Backup XYZ-Wings elimination Cells Values and remove Pincer Cells common Value from elimination Cell positions g[w[K[0]][W[8][y]]] &= ~(g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]); g[w[K[0]][W[9][y]]] &= ~(g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]); #if RJ > 2 printf ("%d) Found XYZ-Wings in Cells %d %d %d Values %d remove %d from Cells %d %d\n", a, K[0], w[K[0]][K[1]], w[K[0]][K[2]], b[g[K[0]]], b[g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]], w[K[0]][W[8][y]], w[K[0]][W[9][y]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore XYZ-Wings in Cells %d %d %d Values %d add %d to Cells %d %d\n", a, K[0], w[K[0]][K[1]], w[K[0]][K[2]], b[g[K[0]]], b[g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]], w[K[0]][W[8][y]], w[K[0]][W[9][y]]); #endif g[w[K[0]][W[8][y]]] = k[0]; g[w[K[0]][W[9][y]]] = k[1]; #if RJ > 3 prn (); #endif return 0; // Restore XYZ-Wings elimination Cells Values } for (Y = 0; Y < 2; ++Y) { // Search XYZ-Wings Hybrid Type 1 and Type 2 int L, X[3], k[3]; if (Y) { // Search XYZ-Wings Hybrid Type 1 X[0] = W[K[2] < W[10][y] ? 10 : 6][y]; X[1] = X[0] + 1; X[2] = X[1] + 1; } else { // Search XYZ-Wings Hybrid Type 2 L = K[1] == W[11][y] || K[1] == W[12][y] || K[1] == W[13][y] ? 14 : 11; X[0] = W[L][y]; X[1] = W[++L][y]; X[2] = W[++L][y]; } L = K[3]; k[0] = g[w[K[0]][X[0]]]; k[1] = g[w[K[0]][X[1]]]; k[2] = g[w[K[0]][X[2]]]; // Backup XYZ-Wings Hybrid Type 1 and Type 2 elimination Cells Values if ((g[w[K[0]][K[Y + 1]]] != g[w[w[K[0]][K[1]]][L]] && g[w[K[0]][K[Y + 1]]] != g[w[w[K[0]][K[1]]][++L]] && g[w[K[0]][K[Y + 1]]] != g[w[w[K[0]][K[1]]][++L]]) || !(g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]] & (k[0] | k[1] | k[2]))) continue; // Skip for either Hybrid Cell not found or no eliminations // Remove Pincer Cells common Value from elimination Cell positions g[w[K[0]][X[0]]] &= ~(g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]); g[w[K[0]][X[1]]] &= ~(g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]); g[w[K[0]][X[2]]] &= ~(g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]); #if RJ > 2 printf ("%d) Found XYZ-Wings Hybrid Type %d in Cells %d %d %d %d Values %d remove %d from Cells %d %d %d\n", a, 2 - Y, K[0], w[K[0]][K[1]], w[K[0]][K[2]], w[w[K[0]][K[1]]][L], b[g[K[0]]], b[g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]], w[K[0]][X[0]], w[K[0]][X[1]], w[K[0]][X[2]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore XYZ-Wings Hybrid Type %d in Cells %d %d %d %d Values %d add %d to Cells %d %d %d\n", a, 2 - Y, K[0], w[K[0]][K[1]], w[K[0]][K[2]], w[w[K[0]][K[1]]][L], b[g[K[0]]], b[g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]], w[K[0]][X[0]], w[K[0]][X[1]], w[K[0]][X[2]]); #endif g[w[K[0]][X[0]]] = k[0]; g[w[K[0]][X[1]]] = k[1]; g[w[K[0]][X[2]]] = k[2]; #if RJ > 3 prn (); #endif return 0; // Restore XYZ-Wings Hybrid Type 1 and Type 2 elimination Cells Values } } } } y = 2; // 2 Represent Guess #if RJ ++n[3]; if (n[3] > n[4]) ++n[4]; #endif 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 Values and assign current Cell position to each current Cell Value int k = 0; #if RJ ++n[y]; #endif for (a = 0; a < 20; ++a) if (g[w[r[p]][a]] & s[r[p]]) { k |= 1 << a; // Backup and remove current Cell Value from 20 peer Cell positions g[w[r[p]][a]] &= ~s[r[p]]; } #if RJ > 2 printf ("%d) Apply %s Cell Value %d from Values %d at Cell %d\n", p, y ? (y > 1 ? "Trial and Error" : "Hidden Single") : "Naked Single", b[s[r[p]]], b[Y], r[p]); #endif if (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 Cell Value %d from Values %d at Cell %d\n", p, y ? (y > 1 ? "Trial and Error" : "Hidden Single") : "Naked Single", b[s[r[p]]], b[Y], r[p]); #endif while (a) // Restore current Cell Value to 20 peer Cell positions if (k & (1 << --a)) g[w[r[p]][a]] |= s[r[p]]; #if RJ > 3 g[r[p]] = Y; // Restore current Cell Values to current Cell position prn (); g[r[p]] = 0; // Remove current Cell Values from current Cell position #endif } #if RJ if (y == 2) --n[3]; #endif g[r[p]] = Y; // Restore current Cell Values 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 Cell Value in 20 peer 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 Cell Value for unsolved Cell position if (!g[p]) // Check no Cell Value 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 : 1 << (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] = n[3] = n[4] = 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 # D%ld # %f\n", n[0], n[1], n[2], n[4], 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 puzzles 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 !!"); }