#include #include #ifndef RJ #define RJ 4 // 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 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 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 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 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}}, W[11][4] = { // References for XY-Wings Type 2, XYZ-Wings and XYZ-Wing Hybrid { 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 Values checking y = 0, // 0 Represent Naked Single z = 512; // 512 Represent greatest value for first time least Values checking #if RJ > 3 prn (); #endif for (; a < q; ++a) // Search Naked/Hidden Single or Guess Values for each unsolved Cell position { if (B[z] > B[g[r[a]]]) // Check least Values in unsolved Cell position if (B[z = g[r[x = a]]] == 1) goto NHSCF; // Naked Single Value 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 Values if (!Y) // Check Hidden Single Value not found in unsolved Cell position continue; z = Y; // Assign Hidden Single Value 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 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 Values in Unit pair and other Cell positions if (B[K[0]] == 2) // Check Naked pair Values found in Unit pair Cell positions { if (!(K[0] & K[1])) // Check Naked pair 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 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 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 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 Values to Unit other Cell positions } if (B[K[0] &= K[0] ^ K[1]] != 2) continue; // Check Hidden pair 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 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 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 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 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 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 Values in Unit triplet and other Cell positions if (B[K[0]] == 3) // Check Naked triplet Values found in Unit triplet Cell positions { if (!(K[0] & K[1])) // Check Naked triplet 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 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 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 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 Values to Unit other Cell positions } if (B[K[0] &= K[0] ^ K[1]] != 3) continue; // Check Hidden triplet 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 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 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 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 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 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 Values in Unit quad and other Cell positions if (B[K[0]] == 4) // Check Naked quad Values found in Unit quad Cell positions { if (!(K[0] & K[1])) // Check Naked quad 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 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 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 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 Values to Unit other Cell positions } if (B[K[0] &= K[0] ^ K[1]] != 4) continue; // Check Hidden quad 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 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 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 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 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 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 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[2] - K[0] + K[1]; 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 Values either not three digits or common digit or no elimination int k = g[K[W[a][3]]]; // Backup XY-Wing Type 1 elimination Cell Values and eliminate Pincers 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-Wing 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-Wing 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-Wing Type 1 elimination Cell Values } } } } } for (y = 0; y < 2; ++y) // Search XY-Wings Type 2, XYZ-Wings and XYZ-Wings Hybrid Box-Line wise for (a = p; a < q; ++a) // Search Pivot unsolved Cell position wise { int A = r[a]; // Assign Pivot Cell position if (B[g[A]] > 3) continue; // Skip for more than three Pivot Values 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 Values either Box Pincer not two digits or Pivot and Box Pincer not three digits 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 Values either Line Pincer not two digits or Cells not three digits int L = W[K < W[10][y] ? 6 : 10][y]; // Assign pincers common first elimination Cell position if (!(g[A] & g[w[A][Y]] & g[w[A][K]])) { // Search for no common Value for XY-Wing Type 2 int 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 Values 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 Values %d remove %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]]], 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 Values %d add %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]]], 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 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]; #if RJ > 3 prn (); #endif return 0; // Restore XY-Wing Type 2 elimination Cells Values } if (B[g[w[A][Y]] & g[w[A][K]]] != 1 || B[g[A] & g[w[A][Y]] & g[w[A][K]]] != 1) continue; // Skip for either Pincers no common Value or Cells no common Value if (g[w[A][Y]] & g[w[A][K]] & (g[w[A][W[8][y]]] | g[w[A][W[9][y]]])) { // Search for XYZ-Wings eliminations int k[2] = {g[w[A][W[8][y]]], g[w[A][W[9][y]]]}; // Backup XYZ-Wing elimination Cells Values and remove Pincers common Value 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 Values %d remove %d from Cells %d %d\n", Y, A, w[A][Y], w[A][K], b[g[A]], 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 Values %d add %d to Cells %d %d\n", Y, A, w[A][Y], w[A][K], b[g[A]], b[g[w[A][Y]] & g[w[A][K]]], w[A][W[8][y]], w[A][W[9][y]]); #endif g[w[A][W[8][y]]] = k[0]; g[w[A][W[9][y]]] = k[1]; #if RJ > 3 prn (); #endif return 0; // Restore XYZ-Wing elimination Cells Values } int X = W[K < W[10][y] ? 10 : 6][y], k[3] = {g[w[A][X]], g[w[A][X + 1]], g[w[A][X + 2]]}; // Backup XYZ-Wing Hybrid elimination Cells Values if ((g[w[A][K]] != g[w[w[A][Y]][L]] && g[w[A][K]] != g[w[w[A][Y]][++L]] && g[w[A][K]] != g[w[w[A][Y]][++L]]) || !(g[w[A][Y]] & g[w[A][K]] & (k[0] | k[1] | k[2]))) continue; // Skip for either Hybrid Cell not found or no eliminations g[w[A][X]] &= ~(g[w[A][Y]] & g[w[A][K]]); g[w[A][X + 1]] &= ~(g[w[A][Y]] & g[w[A][K]]); g[w[A][X + 2]] &= ~(g[w[A][Y]] & g[w[A][K]]); // Remove Pincers common Value from elimination Cell positions #if RJ > 2 printf ("%d) Found XYZ-Wing Hybrid in Cells %d %d %d %d Values %d remove %d from Cells %d %d %d\n", Y, A, w[A][Y], w[A][K], w[w[A][Y]][L], b[g[A]], b[g[w[A][Y]] & g[w[A][K]]], w[A][X], w[A][X + 1], w[A][X + 2]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore XYZ-Wing Hybrid in Cells %d %d %d %d Values %d add %d to Cells %d %d %d\n", Y, A, w[A][Y], w[A][K], w[w[A][Y]][L], b[g[A]], b[g[w[A][Y]] & g[w[A][K]]], w[A][X], w[A][X + 1], w[A][X + 2]); #endif g[w[A][X]] = k[0]; g[w[A][X + 1]] = k[1]; g[w[A][X + 2]] = k[2]; #if RJ > 3 prn (); #endif return 0; // Restore XYZ-Wing Hybrid 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 solve current Cell position for each Value 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 Value assigned k |= 1 << a; // Backup 20 affected Cell positions current Value g[w[r[p]][a]] &= ~s[r[p]]; } // Remove current Value from 20 affected Cell positions #if RJ > 2 printf ("%d) Apply %s Value %d from Values %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 > 3 if (a < 20) { g[w[r[p]][a]] = 0; prn (); } #endif #if RJ > 2 printf ("%d) Restore %s Value %d from Values %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 while (a) // Restore current Value to 20 affected Cell positions if (k & (1 << --a)) g[w[r[p]][a]] |= s[r[p]]; #if RJ > 3 prn (); #endif } #if RJ if (y == 2) --n[3]; #endif g[r[p]] = Y; // Restore 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 Value 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 Value for unsolved Cell position if (!g[p]) // Check no 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 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 !!"); }