#include #include #define RJ 0 // 0 no debugging, 1 print solutions, 2 print puzzles, 3 print steps, 4 print pencil marks int q, // Number of unsolved Cell positions Grid wise r[81], // Used for sorting and excluding each unsolved Cell positions Grid wise s[81], // Sudoku Grid 81 Cell positions for clues and solved g[81], // Bitwise Cell Clues for each unsolved Cell positions Grid wise n[8]; // Number of Naked singles, Hidden singles, Guesses and Depth Grid wise, total without guess, maximum guess and depth static int b[512] = { // Bitwise to digit Cell Clues 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, 678, 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 Clues 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[12][2] = { // References used for Basic, Hybrid and Transport Wings {14,12}, { 0,14}, { 6,20}, { 6,12}, { 7,13}, { 3,17}, { 8, 6}, { 9, 8}, {12,10}, {10, 7}, {11, 9}, {13,11}}; #if RJ > 3 void prn (void) { int a = 0, k[9] = {1, 1, 1, 1, 1, 1, 1, 1, 1}; for (; a < 81; ++a) if (k[a % 9] < B[g[a]]) k[a % 9] = B[g[a]]; printf (" +%.*s+%.*s+%.*s+\n", k[0] + k[1] + k[2] + 4, "-------------------------------", k[3] + k[4] + k[5] + 4, "-------------------------------", k[6] + k[7] + k[8] + 4, "-------------------------------"); for (a = 0; a < 81; ++a) { if (!(a % 3)) printf (" |"); printf (" %-*d", k[a % 9], b[g[a] | s[a]]); if ((a % 9) & 8) { printf (" |\n"); if (a % 27 == 26) printf (" +%.*s+%.*s+%.*s+\n", k[0] + k[1] + k[2] + 4, "-------------------------------", k[3] + k[4] + k[5] + 4, "-------------------------------", k[6] + k[7] + k[8] + 4, "-------------------------------"); } } } #endif int solve (int p) { int a = 0, Y, x, // Unsolved Cell position for least Cell Clues checking y = 0, // 0 Represent Naked single Cell position z = 512; // 512 Represent greatest Cell Clue for first time least Cell Clues checking #if RJ > 3 prn (); #endif for (; a < 27; ++a) // Check zero state for each Unit if (9 - !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]] != 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 Clue or Guess minimum Cell Clues for each unsolved Cell position if (B[z] > B[g[r[a]]]) // Check least Cell Clues in current unsolved Cell position if (B[z = g[r[x = a]]] < 2) goto NHSCF; // Naked single Cell Clue in current unsolved Cell position for (a = p; a < q; ++a) // Search Hidden single Cell Clue for each unsolved Cell position { Y = (((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]]) ^ g[r[a]])) & g[r[a]]; // Assign Hidden single Cell Clue if (!Y) continue; // Skip for no Hidden single Cell Clue in unsolved Cell position x = a; // Assign Hidden single Cell position z = Y; // Assign Hidden single Cell Clue y = 1; // 1 Represent Hidden single Cell position goto NHSCF; } for (; y < 27; ++y) // Search Naked/Hidden Tuples Cell Clues for each Unit { Y = !g[l[y][0]] + !g[l[y][1]] + !g[l[y][2]] + !g[l[y][3]] + !g[l[y][4]] + !g[l[y][5]] + !g[l[y][6]] + !g[l[y][7]] + !g[l[y][8]]; // Count Unit solved Cell positions if (Y > 6) continue; // Skip Unit for more than 6 solved Cell positions for (a = 0; a < 36; ++a) // Search Naked/Hidden pair Cell Clues for each Unit 36 pair Cell positions { if (!g[l[y][h[a][0]]] || !g[l[y][h[a][1]]]) { // Skip for no unsolved 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 Clues in Unit pair Cell positions and Unit other Cell positions if (B[K[0]] == 2) // Check Naked pair Cell Clues in Unit pair Cell positions { if (!(K[0] & K[1])) continue; // Skip for no Naked pair Cell Clues in Unit other Cell positions 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 drop Naked pair Cell Clues 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 Cells %d %d Unit %d drop Clues %d from Cells %d %d %d %d %d %d %d\n", a, l[y][h[a][0]], l[y][h[a][1]], y, b[K[0]], l[y][h[a][2]], l[y][h[a][3]], l[y][h[a][4]], l[y][h[a][5]], l[y][h[a][6]], l[y][h[a][7]], l[y][h[a][8]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Naked pair Cells %d %d Unit %d add Clues %d to Cells %d %d %d %d %d %d %d\n", a, l[y][h[a][0]], l[y][h[a][1]], y, b[K[0]], l[y][h[a][2]], l[y][h[a][3]], l[y][h[a][4]], l[y][h[a][5]], l[y][h[a][6]], l[y][h[a][7]], l[y][h[a][8]]); #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 Clues to Unit other Cell positions } if (B[K[0] &= K[0] ^ K[1]] != 2) continue; // Skip for no Hidden pair Cell Clues in Unit pair Cell positions int k[2] = {g[l[y][h[a][0]]], g[l[y][h[a][1]]]}; // Backup and drop other than Hidden pair Cell Clues 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 Cells %d %d Unit %d Clues %d\n", a, l[y][h[a][0]], l[y][h[a][1]], y, b[K[0]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Hidden pair Cells %d %d Unit %d Clues %d\n", a, l[y][h[a][0]], l[y][h[a][1]], y, b[K[0]]); #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 Clues to Unit pair Cell positions } if (Y > 4) continue; // Skip triplets and quads for more than 4 solved Cell positions for (; a < 120; ++a) // Search Naked/Hidden triplet Cell Clues 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 for no unsolved Cell positions if (!g[l[y][h[a][0]]]) { int A[7] = {27,20,14, 9, 5, 2, 0}; a += A[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 Clues in Unit triplet Cell positions and Unit other Cell positions if (B[K[0]] == 3) // Check Naked triplet Cell Clues in Unit triplet Cell positions { if (!(K[0] & K[1])) continue; // Skip for no Naked triplet Cell Clues in Unit other Cell positions 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 drop Naked triplet Cell Clues 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 Cells %d %d %d Unit %d drop Clues %d from Cells %d %d %d %d %d %d\n", a, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]], y, b[K[0]], l[y][h[a][3]], l[y][h[a][4]], l[y][h[a][5]], l[y][h[a][6]], l[y][h[a][7]], l[y][h[a][8]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Naked triplet Cells %d %d %d Unit %d add Clues %d to Cells %d %d %d %d %d %d\n", a, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]], y, b[K[0]], l[y][h[a][3]], l[y][h[a][4]], l[y][h[a][5]], l[y][h[a][6]], l[y][h[a][7]], l[y][h[a][8]]); #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 Clues to Unit other Cell positions } if (B[K[0] &= K[0] ^ K[1]] != 3) continue; // Skip for no Hidden triplet Cell Clues 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 drop other than Hidden triplet Cell Clues 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 Cells %d %d %d Unit %d Clues %d\n", a, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]], y, b[K[0]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Hidden triplet Cells %d %d %d Unit %d Clues %d\n", a, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]], y, b[K[0]]); #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 Clues to Unit triplet Cell positions } if (Y > 2) continue; // Skip quads for more than 2 solved Cell positions for (; a < 246; ++a) // Search Naked/Hidden quad Cell Clues 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 for no unsolved Cell positions if (!g[l[y][h[a][0]]]) { int A[6] = {55,34,19, 9, 3, 0}; a += A[h[a][0]]; } else if (!g[l[y][h[a][1]]]) { int A[7] = {27,20,14, 9, 5, 2, 0}; a += A[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 Clues in Unit quad Cell positions and Unit other Cell positions if (B[K[0]] == 4) // Check Naked quad Cell Clues in Unit quad Cell positions { if (!(K[0] & K[1])) continue; // Skip for no Naked quad Cell Clues in Unit other Cell positions 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 drop Naked quad Cell Clues 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 Cells %d %d %d %d Unit %d drop Clues %d from Cells %d %d %d %d %d\n", a, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]], l[y][h[a][3]], y, b[K[0]], l[y][h[a][4]], l[y][h[a][5]], l[y][h[a][6]], l[y][h[a][7]], l[y][h[a][8]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Naked quad Cells %d %d %d %d Unit %d add Clues %d to Cells %d %d %d %d\n", a, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]], l[y][h[a][3]], y, b[K[0]], l[y][h[a][4]], l[y][h[a][5]], l[y][h[a][6]], l[y][h[a][7]], l[y][h[a][8]]); #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 Clues to Unit other Cell positions } if (B[K[0] &= K[0] ^ K[1]] != 4) continue; // Skip for no Hidden quad Cell Clues 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 drop other than Hidden quad Cell Clues 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 Cells %d %d %d %d Unit %d Clues %d\n", a, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]], l[y][h[a][3]], y, b[K[0]]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Hidden quad Cells %d %d %d %d Unit %d Clues %d\n", a, l[y][h[a][0]], l[y][h[a][1]], l[y][h[a][2]], l[y][h[a][3]], y, b[K[0]]); #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 Clues to Unit quad Cell positions } } for (a = 0; a < 54; ++a) // Search Intersection Removal for 54 Box-Line 3 Cell positions for (Y = g[j[a][0]] | g[j[a][1]] | g[j[a][2]]; y = Y & -Y; Y -= y) { // Search Box-Line 3 Cell positions for each Intersection Removal Clue if ((g[j[a][3]] | g[j[a][4]] | g[j[a][5]] | g[j[a][6]] | g[j[a][7]] | g[j[a][8]]) & y) { // Check Intersection Removal Clue in Line other Cell positions if ((g[j[a][9]] | g[j[a][10]] | g[j[a][11]] | g[j[a][12]] | g[j[a][13]] | g[j[a][14]]) & y) continue; // Skip for Intersection Removal Clue in Box other Cell positions int k[6] = {g[j[a][3]], g[j[a][4]], g[j[a][5]], g[j[a][6]], g[j[a][7]], g[j[a][8]]}; // Backup and drop Intersection Removal Clue from Line other Cell positions g[j[a][3]] &= ~y; g[j[a][4]] &= ~y; g[j[a][5]] &= ~y; g[j[a][6]] &= ~y; g[j[a][7]] &= ~y; g[j[a][8]] &= ~y; #if RJ > 2 printf ("%d) Found Pointing and Claiming Intersection Removal Cells %d %d %d drop Clue %d from Cells %d %d %d %d %d %d\n", a, j[a][0], j[a][1], j[a][2], b[y], j[a][3], j[a][4], j[a][5], j[a][6], j[a][7], j[a][8]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Pointing and Claiming Intersection Removal Cells %d %d %d add Clue %d to Cells %d %d %d %d %d %d\n", a, j[a][0], j[a][1], j[a][2], b[y], j[a][3], j[a][4], j[a][5], j[a][6], j[a][7], j[a][8]); #endif g[j[a][3]] = k[0]; // Restore Intersection Removal Clue to Line other Cell positions g[j[a][4]] = k[1]; g[j[a][5]] = k[2]; g[j[a][6]] = k[3]; g[j[a][7]] = k[4]; g[j[a][8]] = k[5]; #if RJ > 3 prn (); #endif return 0; } // No Intersection Removal Clue in Line other Cell positions if (~(g[j[a][9]] | g[j[a][10]] | g[j[a][11]] | g[j[a][12]] | g[j[a][13]] | g[j[a][14]]) & y) continue; // Skip for no Intersection Removal Clue in Box other Cell positions int k[6] = {g[j[a][9]], g[j[a][10]], g[j[a][11]], g[j[a][12]], g[j[a][13]], g[j[a][14]]}; // Backup and drop Intersection Removal Clue from Box other Cell positions g[j[a][9]] &= ~y; g[j[a][10]] &= ~y; g[j[a][11]] &= ~y; g[j[a][12]] &= ~y; g[j[a][13]] &= ~y; g[j[a][14]] &= ~y; #if RJ > 2 printf ("%d) Found Box-Line Reduction Intersection Removal Cells %d %d %d drop Clue %d from Cells %d %d %d %d %d %d\n", a, j[a][0], j[a][1], j[a][2], b[y], j[a][9], j[a][10], j[a][11], j[a][12], j[a][13], j[a][14]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore Box-Line Reduction Intersection Removal Cells %d %d %d add Clue %d to Cells %d %d %d %d %d %d\n", a, j[a][0], j[a][1], j[a][2], b[y], j[a][9], j[a][10], j[a][11], j[a][12], j[a][13], j[a][14]); #endif g[j[a][9]] = k[0]; // Restore Intersection Removal Clue to Box other Cell positions g[j[a][10]] = k[1]; g[j[a][11]] = k[2]; g[j[a][12]] = k[3]; g[j[a][13]] = k[4]; g[j[a][14]] = k[5]; #if RJ > 3 prn (); #endif return 0; } for (Y = 0; Y < 10; Y += 9)// Search Basic Fishes Line wise for (y = 1; y < 257; y <<= 1) { // Search Basic Fishes for each digit int k[9]; // Backup Basic Fish Clue for each 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 Clue for Line 36 pair Cell positions int A = k[h[a][0]], K[2], X[2] = {-1,-1}, Z = -1; if (B[A] != 2 || A != k[h[a][1]]) { // Skip for no X-Wing Clue in Lines pair Cell positions if (B[A] != 2) a += 7 - h[a][0]; continue; } for (; K[++Z] = A & -A; A -= K[Z]) { // Search opposite Line other Cell positions for X-Wing Clue 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 no X-Wing Clue 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; } // Drop X-Wing Clue from opposite Line other Cell positions if ((X[0] & X[1]) < 0) continue; // Skip for no X-Wing Clue in opposite Lines other Cell positions #if RJ > 2 printf ("%d) Found %s wise X-Wing r%d%dc%d%d Clue %d\n", a, Y ? "Column" : "Row", 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]], b[y]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore %s wise X-Wing r%d%dc%d%d Clue %d\n", a, Y ? "Column" : "Row", 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]], b[y]); #endif for (Z = 0; Z < 2; ++Z) { // Restore X-Wing Clue to opposite Lines other Cell positions if (X[Z] < 0) continue; // Skip for no X-Wing Clue in opposite Line other Cell positions 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 Clue 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}, Z = -1; if (!k[h[a][0]] || !k[h[a][1]] || !k[h[a][2]] || B[A] != 3) { // Skip for either no unsolved Cell positions; or no Sord Fish Clue 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; } for (; K[++Z] = A & -A; A -= K[Z]) { // Search opposite Line other Cell positions for Sword Fish Clue 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 no Sword Fish Clue 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; } // Drop Sword Fish Clue from opposite Line other Cell positions if ((X[0] & X[1] & X[2]) < 0) continue; // Skip for no Sword Fish Clue in opposite Lines other Cell positions #if RJ > 2 printf ("%d) Found %s wise Sword Fish r%d%d%dc%d%d%d Clue %d\n", a, Y ? "Column" : "Row", 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]], b[y]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore %s wise Sword Fish r%d%d%dc%d%d%d Clue %d\n", a, Y ? "Column" : "Row", 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]], b[y]); #endif for (Z = 0; Z < 3; ++Z) { // Restore Sword Fish Clue to opposite Lines other Cell positions if (X[Z] < 0) continue; // Skip for no Sword Fish Clue in opposite Line other Cell positions 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 Clue 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}, Z = -1; if (!k[h[a][0]] || !k[h[a][1]] || !k[h[a][2]] || !k[h[a][3]] || B[A] != 4) { // Skip for either no unsolved Cell positions; or no Jelly Fish Clue 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; } for (; K[++Z] = A & -A; A -= K[Z]) { // Search opposite Line other Cell positions for Jelly Fish Clue 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 no Jelly Fish Clue 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; } // Drop Jelly Fish Clue from opposite Line other Cell positions if ((X[0] & X[1] & X[2] & X[3]) < 0) continue; // Skip for no Jelly Fish Clue in opposite Lines other Cell positions #if RJ > 2 printf ("%d) Found %s wise Jelly Fish r%d%d%d%dc%d%d%d%d Clue %d\n", a, Y ? "Column" : "Row", 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]], b[y]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore %s wise Jelly Fish r%d%d%d%dc%d%d%d%d Clue %d\n", a, Y ? "Column" : "Row", 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]], b[y]); #endif for (Z = 0; Z < 4; ++Z) { // Restore Jelly Fish Clue to opposite Lines other Cell positions if (X[Z] < 0) continue; // Skip for no Jelly Fish Clue in opposite Line other Cell positions 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 = p; a < q; ++a) // Search XY-Wings Type 1 unsolved Cell position wise { if (B[g[r[a]]] > 2 || // Skip for unsolved Cell Clues more than two digits; or !(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]][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]])) continue; // No unsolved Cell position in either Apex Row or Column int K[5] = {r[a], 0}; // Assign Apex Cell position for (; K[1] < 6; ++K[1]) // Search first Wing Cell position Row wise { if (B[g[w[K[0]][K[1]]]] != 2 || B[g[K[0]] | g[w[K[0]][K[1]]]] != 3) continue; // Skip for either Row Wing Cell Clues not two digits; or Apex and Row Wing Cells Clues not three digits for (K[2] = 14; K[2] < 20; ++K[2]) { // Search second Wing Cell position Column wise if (B[g[w[K[0]][K[2]]]] != 2 || B[g[K[0]] | g[w[K[0]][K[2]]]] != 3 || // Skip for Column Wing Cell Clues not two digits; or Apex and Column Wing Cells Clues not three digits; or B[K[3] = g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]] != 1 || // Wing Cells common Clue not one digit; or (g[K[0]] & K[3])) // Wing Cells common Clue in Apex Cell Clues continue; if (g[K[4] = w[K[0]][K[1]] - K[0] + w[K[0]][K[2]]] & K[3]) { // Check XY-Wings Type 1 exclusion Cell Clues g[K[4]] &= ~K[3]; // Drop Wing Cells common Clue from XY-Wings Type 1 exclusion Cell position #if RJ > 2 printf ("%d) Found XY-Wings Type 1 Cells %d %d %d Clues %d drop Clue %d from Cell %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[K[3]], K[4]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore XY-Wings Type 1 Cells %d %d %d Clues %d add Clue %d to Cell %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[K[3]], K[4]); #endif g[K[4]] |= K[3]; // Restore Wing Cells common Clue to XY-Wings Type 1 exclusion Cell Clues #if RJ > 3 prn (); #endif return 0; } } } } for (a = p; a < q; ++a) // Search XY-Wings Type 2, XYZ-Wings and XYZ-Wings Hybrid Type 1 and Type 2 unsolved Cell position wise { if (B[g[r[a]]] > 3) continue; // Skip for unsolved Cell Clues more than three digits int K[5] = {r[a]}; // Assign Apex Cell position for (y = 0; y < 2; ++y) // Search Wing Cells position Chute wise { if(!(g[w[r[a]][W[6][y]]] | g[w[r[a]][W[6][y] + 1]] | g[w[r[a]][W[6][y] + 2]] | g[w[r[a]][W[6][y] + 3]] | g[w[r[a]][W[6][y] + 4]] | g[w[r[a]][W[6][y] + 5]]) || !(g[w[r[a]][W[1][y]]] | g[w[r[a]][W[1][y] + 1]] | g[w[r[a]][W[1][y] + 2]] | g[w[r[a]][W[1][y] + 3]] | g[w[r[a]][W[1][y] + 4]] | g[w[r[a]][W[1][y] + 5]])) continue; // Skip for no unsolved Cell position in Apex either Box or Line for (K[1] = W[6][y]; K[1] < W[0][y]; ++K[1]) { // Search first Wing Cell position Box wise if (!g[w[K[0]][K[1]]] || B[g[K[0]] | g[w[K[0]][K[1]]]] > 3) continue; // Skip for either Box Wing Cell position not unsolved; or Apex and Box Wing Cells Clues more than three digits for (K[2] = W[1][y]; K[2] < W[2][y]; ++K[2]) { // Search second Wing Cell position Line wise if (!g[w[K[0]][K[2]]] || B[g[K[0]] | g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]]] > 3 || // Skip for either Line Wing Cell position not unsolved; or Apex Cell and Wing Cells Clues more than three digits; or B[K[4] = g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]] != 1) continue; // Wing Cells common Clue not one digit K[3] = W[K[2] < W[5][y] ? 1 : 5][y]; // Assign Wing Cells common first exclusion Cell position int k[5] = {g[w[K[0]][W[3][y]]], g[w[K[0]][W[4][y]]]}; // Backup XY-Wings Type 2 and XYZ-Wings additionalexclusion Cells Clues if (~g[K[0]] & K[4]) { // Check no Wing Cells common Clue in Apex Cell Clues for backup additional XY-Wings Type 2 exclusion Cells Clues k[2] = g[w[w[K[0]][K[1]]][K[3]]]; k[3] = g[w[w[K[0]][K[1]]][K[3] + 1]]; k[4] = g[w[w[K[0]][K[1]]][K[3] + 2]]; } if ((k[0] | k[1] | k[2] | k[3] | k[4]) & K[4]) { // Check Wing Cells common Clue in XY-Wings Type 2 and XYZ-Wings exclusion Cells Clues // Drop Wing Cells common Clue from XYZ-Wings exclusion Cell positions g[w[K[0]][W[3][y]]] &= ~K[4]; g[w[K[0]][W[4][y]]] &= ~K[4]; if (~g[K[0]] & K[4]) { // Drop Wing Cells common Clue from XY-Wings Type 2 additional exclusion Cell positions g[w[w[K[0]][K[1]]][K[3]]] &= ~K[4]; g[w[w[K[0]][K[1]]][K[3] + 1]] &= ~K[4]; g[w[w[K[0]][K[1]]][K[3] + 2]] &= ~K[4]; } #if RJ > 2 printf ("%d) Found XY%s Cells %d %d %d Clues %d drop Clue %d from Cells %d %d", a, g[K[0]] & K[4] ? "Z-Wings" : "-Wings Type 2", 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[K[4]], w[K[0]][W[3][y]], w[K[0]][W[4][y]]); if (~g[K[0]] & K[4]) printf (" %d %d %d", 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]); printf ("\n"); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore XY%s Cells %d %d %d Clues %d add Clue %d to Cells %d %d", a, g[K[0]] & K[4] ? "Z-Wings" : "-Wings Type 2", 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[K[4]], w[K[0]][W[3][y]], w[K[0]][W[4][y]]); if (~g[K[0]] & K[4]) printf (" %d %d %d", 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]); printf ("\n"); #endif g[w[K[0]][W[3][y]]] = k[0]; g[w[K[0]][W[4][y]]] = k[1]; if (~g[K[0]] & K[4]) { // Restore Wing Cells common Clue to XY-Wings Type 2 additional exclusion Cell positions 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 and XYZ-Wings exclusion Cells Clues } if (~g[K[0]] & K[4]) continue; // Skip for no Wing Cells common Clue in Apex Cell Clues for (Y = 0; Y < 2; ++Y) { // Search XYZ-Wings Hybrid Type wise int L, X[3], k[3]; if (Y) { // Search XYZ-Wings Hybrid Type 1 X[0] = W[K[2] < W[5][y] ? 5 : 1][y]; X[1] = X[0] + 1; X[2] = X[1] + 1; } else { // Search XYZ-Wings Hybrid Type 2 L = K[1] == W[6][y] || K[1] == W[7][y] || K[1] == W[8][y] ? 9 : 6; X[0] = W[L][y]; X[1] = W[L + 1][y]; X[2] = W[L + 2][y]; } if ((g[w[K[0]][K[Y + 1]]] != g[w[w[K[0]][K[1]]][L = K[3]]] && 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]][X[0]]] | g[w[K[0]][X[1]]] | g[w[K[0]][X[2]]]) & K[4])) continue; // Skip for either no XYZ-Wings Hybrid Cell position; or no exclusions 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 and drop Wing Cells common Clue from XYZ-Wings Hybrid Type 1 and Type 2 exclusion Cell positions g[w[K[0]][X[0]]] &= ~K[4]; g[w[K[0]][X[1]]] &= ~K[4]; g[w[K[0]][X[2]]] &= ~K[4]; #if RJ > 2 printf ("%d) Found XYZ-Wings Hybrid Type %d Cells %d %d %d %d Clues %d drop Clue %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[K[4]], 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 Cells %d %d %d %d Clues %d add Clue %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[K[4]], 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 exclusion Cells Clues } } } } } for (a = p; a < q; ++a) // Search WXYZ-Wings Type 1 unsolved Cell position wise { if (B[g[r[a]]] > 3 || // Skip for either unsolved Cell Clues more than three digits; or !(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]][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]])) continue; // No unsolved Cell position in Apex either Row or Column Cell Clues int K[6] = {r[a], 0}; // Assign Apex Cell position for (; K[1] < 8; ++K[1]) // Search first Wing Cell position Row wise { if (!g[w[K[0]][K[1]]] || B[g[K[0]] | g[w[K[0]][K[1]]]] > 4) continue; // Skip for either Row Wing Cell position not unsolved; or Apex and Row Wing Cells Clues more than four digits for (K[2] = K[1] > 5 ? 14 : 12; K[2] < 20; ++K[2]) { // Search second Wing Cell position Column wise if (!g[w[K[0]][K[2]]] || B[g[K[0]] | g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]]] > 4) continue; // Skip for either Column Wing Cell position not unsolved; or Apex, Row and Column Wings Cells Clues more than four digits for (y = 0; y < 2; ++y) // Search third Wing Cell position Line wise for (K[3] = !y && K[1] > 5 ? 0 : K[1 + y] + (y && K[2] == 12) + 1; K[3] < W[2][y]; ++K[3]) { // Search Line Wing Cell position if (!g[w[K[0]][K[3]]] || B[g[K[0]] | g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]] | g[w[K[0]][K[3]]]] > 4 || // Skip for either Line Wing Cell position not unsolved; or Apex and Wings Cells Clues more than four digits; or B[g[w[K[0]][K[2 - y]]]] != 2 || // Column (or Row) Wing Cell Clues not two digits; or B[g[w[K[0]][K[1 + y]]] | g[w[K[0]][K[3]]]] != 3 || // Row (or Column) and Line Wing Cells Clues not three digits; or B[K[4] = g[w[K[0]][K[2 - y]]] & (g[w[K[0]][K[1 + y]]] | g[w[K[0]][K[3]]])] != 1 || // Wing Cells common Clue not one digit; or (g[K[0]] & K[4]) || // Wing Cells common Clue in Apex Cell Clues; or (g[w[K[0]][K[1 + y]]] & K[4]) == (g[w[K[0]][K[3]]] & K[4])) continue; // Wing Cells common Clue in Both Row (or Column) and Line Wing Cells Clues if (g[K[5] = w[K[0]][K[g[w[K[0]][K[1]]] & K[4] ? 1 : 3]] - K[0] + w[K[0]][K[g[w[K[0]][K[2]]] & K[4] ? 2 : 3]]] & K[4]) { // Check no Wing Cells common Clue in WXYZ-Wings Type 1 exclusion Cell Clues // Drop Wing Cells common Clue from WXYZ-Wings Type 1 exclusion Cell position g[K[5]] &= ~K[4]; #if RJ > 2 printf ("%d) Found WXYZ-Wings Type 1 Cells %d %d %d %d Clues %d drop Clue %d from Cell %d\n", a, K[0], w[K[0]][K[1]], w[K[0]][K[2]], w[K[0]][K[3]], b[g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]] | g[w[K[0]][K[3]]]], b[K[4]], K[5]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore WXYZ-Wings Type 1 Cells %d %d %d %d Clues %d add Clue %d to Cell %d\n", a, K[0], w[K[0]][K[1]], w[K[0]][K[2]], w[K[0]][K[3]], b[g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]] | g[w[K[0]][K[3]]]], b[K[4]], K[5]); #endif g[K[5]] |= K[4]; #if RJ > 3 prn (); #endif return 0; // Restore Wing Cells common Clue to WXYZ-Wings Type 1 exclusion Cell Clues } } } } } for (a = p; a < q; ++a) // Search WXYZ-Wings Type 2a, Type 2b, Type 3, Type 4a and Type 4b unsolved Cell position wise { if (B[g[r[a]]] > 4) continue; // Skip for unsolved Cell Clues more than four digits int K[5] = {r[a]}; // Assign Apex Cell position for (y = 0; y < 2; ++y) // Search Wing Cells position Chute wise { if(!(g[w[r[a]][W[6][y]]] | g[w[r[a]][W[6][y] + 1]] | g[w[r[a]][W[6][y] + 2]] | g[w[r[a]][W[6][y] + 3]] | g[w[r[a]][W[6][y] + 4]] | g[w[r[a]][W[6][y] + 5]]) || !(g[w[r[a]][W[1][y]]] | g[w[r[a]][W[1][y] + 1]] | g[w[r[a]][W[1][y] + 2]] | g[w[r[a]][W[1][y] + 3]] | g[w[r[a]][W[1][y] + 4]] | g[w[r[a]][W[1][y] + 5]])) continue; // Skip for no unsolved Cell position either Apex Box or Line for (K[1] = W[6][y]; K[1] < W[0][y]; ++K[1]) { // Search first Wing Cell position Box wise if (!g[w[K[0]][K[1]]] || B[g[K[0]] | g[w[K[0]][K[1]]]] > 4) continue; // Skip for either Box Wing Cell position not unsolved; or Apex and Box Wing Cell Clues more than four digits for (K[2] = W[1][y]; K[2] < W[2][y]; ++K[2]) { // Search second Wing Cell position Line wise if (!g[w[K[0]][K[2]]] || B[g[K[0]] | g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]]] > 4) continue; // Skip for either Line Wing Cell position not unsolved; or Apex, Box and Line Wings Cells Clues more than four digits for(K[3] = 3; K[3] < 5; ++K[3]) { // Search second Apex Cell position mini-Line wise if (!g[w[K[0]][W[K[3]][y]]] || // Skip for either second Apex Cell position not unsolved; or B[g[K[0]] | g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]] | g[w[K[0]][W[K[3]][y]]]] != 4 || // Apex Cells Clues and Wing Cells Clues not four digits; or !((g[K[0]] | g[w[K[0]][W[K[3]][y]]]) & g[w[K[0]][K[1]]]) || // No common Clue in Apex Cells and Box Wing Cell Clues; or !((g[K[0]] | g[w[K[0]][W[K[3]][y]]]) & g[w[K[0]][K[2]]]) || // No common Clue in Apex Cells and Line Wing Cell Clues; or B[K[4] = g[w[K[0]][K[1]]] & g[w[K[0]][K[2]]]] != 1) continue; // Wing Cells common Clue not one digit int L = -1, k[4] = {g[w[K[0]][W[7 - K[3]][y]]]}; // Backup WXYZ-Wings Type 4b exclusion Cell position if (~(g[K[0]] | g[w[K[0]][W[K[3]][y]]]) & K[4]) { // Check no Wing Cells common Clue in Apex Cells Clues L = W[K[2] < W[5][y] ? 1 : 5][y]; // Assign Wing Cells common first exclusion Cell position k[1] = g[w[w[K[0]][K[1]]][L]]; k[2] = g[w[w[K[0]][K[1]]][L + 1]]; k[3] = g[w[w[K[0]][K[1]]][L + 2]]; } // Backup WXYZ-Wings Type 4a more exclusion Cell positions if ((k[0] | k[1] | k[2] | k[3]) & K[4]) { // Check WXYZ-Wings Type 4a and Type 4b exclusion Cells Clues // Drop Wing Cells common Clue from WXYZ-Wings Type 4b exclusion Cell position g[w[K[0]][W[7 - K[3]][y]]] &= ~K[4]; if (L > -1) { // Drop Wing Cells common Clue from WXYZ-Wings Type 4a more exclusion Cell positions g[w[w[K[0]][K[1]]][L]] &= ~K[4]; g[w[w[K[0]][K[1]]][L + 1]] &= ~K[4]; g[w[w[K[0]][K[1]]][L + 2]] &= ~K[4]; } #if RJ > 2 printf ("%d) Found WXYZ-Wings Type 4%c Cells %d %d %d %d Clues %d drop Clue %d from Cell", a, L < 0 ? 'b' : 'a', K[0], w[K[0]][W[K[3]][y]], w[K[0]][K[1]], w[K[0]][K[2]], b[g[K[0]] | g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]] | g[w[K[0]][W[K[3]][y]]]], b[K[4]]); if (L < 0) printf (" %d\n", w[K[0]][W[7 - K[3]][y]]); else printf ("s %d %d %d %d\n", w[K[0]][W[7 - K[3]][y]], w[w[K[0]][K[1]]][L], w[w[K[0]][K[1]]][L + 1], w[w[K[0]][K[1]]][L + 2]); #endif if (solve (p)) return 1; #if RJ > 2 printf ("%d) Restore WXYZ-Wings Type 4%c Cells %d %d %d %d Clues %d add Clue %d to Cell", a, L < 0 ? 'b' : 'a', K[0], w[K[0]][W[K[3]][y]], w[K[0]][K[1]], w[K[0]][K[2]], b[g[K[0]] | g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]] | g[w[K[0]][W[K[3]][y]]]], b[K[4]]); if (L < 0) printf (" %d\n", w[K[0]][W[7 - K[3]][y]]); else printf ("x %d %d %d %d\n", w[K[0]][W[7 - K[3]][y]], w[w[K[0]][K[1]]][L], w[w[K[0]][K[1]]][L + 1], w[w[K[0]][K[1]]][L + 2]); #endif g[w[K[0]][W[7 - K[3]][y]]] = k[0]; if (L > -1) { g[w[w[K[0]][K[1]]][L]] = k[1]; g[w[w[K[0]][K[1]]][L + 1]] = k[2]; g[w[w[K[0]][K[1]]][L + 2]] = k[3]; } #if RJ > 3 prn (); #endif return 0; // Restore WXYZ-Wings Type 4a and Type 4b exclusion Cells Clues } } for (Y = 0; Y < 2; ++Y) // Search third Wing Cell position Box and Line wise for (K[3] = K[1 + Y] + 1; K[3] < W[Y + Y][y]; ++K[3]) { // Search third Wing Cell position if (!g[w[K[0]][K[3]]] || // Skip for either third Wing Cell position not unsolved; or B[g[K[0]] | g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]] | g[w[K[0]][K[3]]]] != 4 || // Apex and Wings Cells Clues not four digits; or !(g[K[0]] & g[w[K[0]][K[2 - Y]]]) || // No common Clue in Apex and Box (or Line) Wing Cells Clues; or !(g[K[0]] & (g[w[K[0]][K[1 + Y]]] | g[w[K[0]][K[3]]])) || // No common Clue in Apex and Line (or Box) or third Wings Cells Clues; or B[K[4] = g[w[K[0]][K[2 - Y]]] & (g[w[K[0]][K[1 + Y]]] | g[w[K[0]][K[3]]])] != 1) continue; // Wing Cells common Clue not one digit int X[2] = {-1}, k[5] = {g[w[K[0]][W[3][y]]], g[w[K[0]][W[4][y]]]}; // Backup WXYZ-Wings Type 2b and Type 3 exclusion Cell positions if ((~g[K[0]] & K[4]) && // No Wing Cells common Clue Check Apex Cell Clues; and (w[K[0]][K[3]] == w[w[K[0]][K[1 + Y]]][W[3][y]] || w[K[0]][K[3]] == w[w[K[0]][K[1 + Y]]][W[4][y]] || // Third Wing Cell position within first (or second) Wing Cell position mini-Line; or (g[w[K[0]][K[1 + Y]]] & K[4]) != (g[w[K[0]][K[3]]] & K[4]))) { // Apex and first (or second) Wing Cells Clues not equals to Apex Cell Clues and third Wing Cell Clues X[0] = w[K[0]][K[g[w[K[0]][K[1]]] & g[w[K[0]][K[2 - Y]]] & (g[w[K[0]][K[1 + Y]]] | g[w[K[0]][K[3]]]) ? 1 : 3]]; X[1] = W[K[g[w[K[0]][K[2]]] & g[w[K[0]][K[2 - Y]]] & (g[w[K[0]][K[1 + Y]]] | g[w[K[0]][K[3]]]) ? 2 : 3] < W[5][y] ? 1 : 5][y]; k[2] = g[w[X[0]][X[1]]]; k[3] = g[w[X[0]][X[1] + 1]]; k[4] = g[w[X[0]][X[1] + 2]]; } // Backup WXYZ-Wings Type 2a more exclusion Cell positions if ((k[0] | k[1] | k[2] | k[3] | k[4]) & K[4]) { // Check WXYZ-Wings Type 2a, Type 2b and Type 3 exclusion Cells Clues // Drop Wing Cells common Clue from WXYZ-Wings Type 2b and Type 3 exclusion Cell positions g[w[K[0]][W[3][y]]] &= ~K[4]; g[w[K[0]][W[4][y]]] &= ~K[4]; if (X[0] > -1) { // Drop Wing Cells common Clue from WXYZ-Wings Type 2a more exclusion Cell positions g[w[X[0]][X[1]]] &= ~K[4]; g[w[X[0]][X[1] + 1]] &= ~K[4]; g[w[X[0]][X[1] + 2]] &= ~K[4]; } #if RJ > 2 if (X[0] > -1) printf ("%d) Found WXYZ-Wings Type 2a Cells %d %d %d %d Clues %d drop Clue %d from Cells %d %d %d %d %d\n", a, K[0], w[K[0]][K[1]], w[K[0]][K[2]], w[K[0]][K[3]], b[g[K[0]] | g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]] | g[w[K[0]][K[3]]]], b[K[4]], w[K[0]][W[3][y]], w[K[0]][W[4][y]], w[X[0]][X[1]], w[X[0]][X[1] + 1], w[X[0]][X[1] + 2]); else printf ("%d) Found WXYZ-Wings Type %s Cells %d %d %d %d Clues %d drop Clue %d from Cells %d %d\n", a, g[K[0]] & K[4] ? "3" : "2b", K[0], w[K[0]][K[1]], w[K[0]][K[2]], w[K[0]][K[3]], b[g[K[0]] | g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]] | g[w[K[0]][K[3]]]], b[K[4]], w[K[0]][W[3][y]], w[K[0]][W[4][y]]); #endif if (solve (p)) return 1; #if RJ > 2 if (X[0] > -1) printf ("%d) Restore WXYZ-Wings Type 2a Cells %d %d %d %d Clues %d add Clue %d to Cells %d %d %d %d %d\n", a, K[0], w[K[0]][K[1]], w[K[0]][K[2]], w[K[0]][K[3]], b[g[K[0]] | g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]] | g[w[K[0]][K[3]]]], b[K[4]], w[K[0]][W[3][y]], w[K[0]][W[4][y]], w[X[0]][X[1]], w[X[0]][X[1] + 1], w[X[0]][X[1] + 2]); else printf ("%d) Restore WXYZ-Wings Type %s Cells %d %d %d %d Clues %d add Clue %d to Cells %d %d\n", a, g[K[0]] & K[4] ? "3" : "2b", K[0], w[K[0]][K[1]], w[K[0]][K[2]], w[K[0]][K[3]], b[g[K[0]] | g[w[K[0]][K[1]]] | g[w[K[0]][K[2]]] | g[w[K[0]][K[3]]]], b[K[4]], w[K[0]][W[3][y]], w[K[0]][W[4][y]]); #endif g[w[K[0]][W[3][y]]] = k[0]; g[w[K[0]][W[4][y]]] = k[1]; if (X[0] > -1) { g[w[X[0]][X[1]]] = k[2]; g[w[X[0]][X[1] + 1]] = k[3]; g[w[X[0]][X[1] + 2]] = k[4]; } #if RJ > 3 prn (); #endif return 0; // Restore WXYZ-Wings Type 2a, Type 2b and Type 3 exclusion Cells Clues } } } } } } for (a = 0; a < 81; ++a) // Search Empty Rectangle Intersection Cell position grid wise { int K[7] = {(g[a] | g[w[a][6]] | g[w[a][7]]) & (g[a] | g[w[a][12]] | g[w[a][13]]) & ~(g[w[a][8]] | g[w[a][9]] | g[w[a][10]] | g[w[a][11]]) & (g[w[a][0]] | g[w[a][1]] | g[w[a][2]] | g[w[a][3]] | g[w[a][4]] | g[w[a][5]]) & (g[w[a][14]] | g[w[a][15]] | g[w[a][16]] | g[w[a][17]] | g[w[a][18]] | g[w[a][19]])}; // Assign ERI Cell Clues for (; K[1] = K[0] & -K[0]; K[0] -= K[1]) // Search ERI Strong Link digit wise for (y = 0; y < 6; ++y) { // Search ERI Strong Link Cell position Row wise if (!g[K[2] = w[a][y]] || !(g[K[2]] & K[1])) continue; // Skip for ER-Row Cell either position not unsoved; or no ERI digit in Clues for (Y = 14; Y < 20; ++Y) { // Search ERI Strong Link Cell position Column wise if (!g[K[3] = w[a][Y]] || !g[K[4] = K[2] - a + K[3]] || !(g[K[3]] & g[K[4]] & K[1]) || // Skip for either ER-Column or ER-Row/ER-Column Intersection Strong Link Cell positions not unsolved; or no ERI digit in Cells Clues; or ((K[5] = !(g[w[K[2]][12]] & K[1]) + !(g[w[K[2]][13]] & K[1]) + !(g[w[K[2]][14]] & K[1]) + !(g[w[K[2]][15]] & K[1]) + !(g[w[K[2]][16]] & K[1]) + !(g[w[K[2]][17]] & K[1]) + !(g[w[K[2]][18]] & K[1]) + !(g[w[K[2]][19]] & K[1])) < 7 && (K[6] = !(g[w[K[3]][0]] & K[1]) + !(g[w[K[3]][1]] & K[1]) + !(g[w[K[3]][2]] & K[1]) + !(g[w[K[3]][3]] & K[1]) + !(g[w[K[3]][4]] & K[1]) + !(g[w[K[3]][5]] & K[1]) + !(g[w[K[3]][6]] & K[1]) + !(g[w[K[3]][7]] & K[1])) < 7)) continue; // Sum of no ERI digit in Strong Link Row and Column Cells Clues less than seven #if RJ > 2 if (K[5] > 6) printf ("%d) Found Empty Rectangle Intersection Cell %d Strong Link Column Cells %d %d drop Clue %d from Cell %d\n", a, a, K[2], K[4], b[K[1]], K[3]); if (K[6] > 6) printf ("%d) Found Empty Rectangle Intersection Cell %d Strong Link Row Cells %d %d drop Clue %d from Cell %d\n", a, a, K[3], K[4], b[K[1]], K[2]); #endif if (K[5] > 6) // Drop ERI Strong Link digit from Row Cell position g[K[3]] &= ~K[1]; if (K[6] > 6) // Drop ERI Strong Link digit from Column Cell position g[K[2]] &= ~K[1]; if (solve (p)) return 1; #if RJ > 2 if (K[5] > 6) printf ("%d) Restore Empty Rectangle Intersection Cell %d Strong Link Row Cells %d %d add Clue %d to Cell %d\n", a, a, K[2], K[4], b[K[1]], K[3]); if (K[6] > 6) printf ("%d) Restore Empty Rectangle Intersection Cell %d Strong Link Column Cells %d %d add Clue %d to Cell %d\n", a, a, K[3], K[4], b[K[1]], K[2]); #endif if (K[5] > 6) // Restore ERI Strong Link digit to Row Cell position g[K[3]] |= K[1]; if (K[6] > 6) // Restore ERI Strong Link Column digit to Column Cell position g[K[2]] |= K[1]; #if RJ > 3 prn (); #endif return 0; } } } y = 2; // 2 Represent Guess if (++n[3] > n[4]) ++n[4]; NHSCF: if (x > p) // Check current Cell position for sorting and excluding { 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 Clues and assign current Cell position to each current Cell Clue int k = 0; for (++n[y], a = 0; a < 20; ++a) // Search 20 peer Cell positions if (g[w[r[p]][a]] & s[r[p]]) { k |= 1 << a; // Backup and drop current Cell Clue from 20 peer Cell positions g[w[r[p]][a]] &= ~s[r[p]]; } #if RJ > 2 printf ("%d) Apply %s Cell %d Clue %d from Clues %d\n", p, y ? (y > 1 ? "Trial and Error" : "Hidden single") : "Naked single", r[p], b[s[r[p]]], b[Y]); #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 %d Clue %d to Clues %d\n", p, y ? (y > 1 ? "Trial and Error" : "Hidden single") : "Naked single", r[p], b[s[r[p]]], b[Y]); #endif while (a) // Restore current Cell Clue 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 Clues to current Cell position prn (); g[r[p]] = 0; // Drop current Cell Clues from current Cell position #endif } if (y == 2) --n[3]; g[r[p]] = Y; // Restore current Cell Clues to current Cell position return 0; } int check (int p, int q) { if ((s[w[p][0]] | s[w[p][1]] | s[w[p][2]] | s[w[p][3]] | s[w[p][4]] | s[w[p][5]] | s[w[p][6]] | s[w[p][7]] | s[w[p][8]] | s[w[p][9]] | s[w[p][10]] | s[w[p][11]] | s[w[p][12]] | s[w[p][13]] | s[w[p][14]] | s[w[p][15]] | s[w[p][16]] | s[w[p][17]] | s[w[p][18]] | s[w[p][19]]) & q) return 0; // Check duplicate Cell Clue in 20 peer Clue Cell positions 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 unsolved Cell position constraint and assign Cell Clue digit wise if (!g[p]) // Check no Cell Clue assigned return 1; r[q++] = p; // Assign unsolved Cell position for sorting and excluding } else if (!check (p, s[p])) return 1; // 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"); n[5] = n[6] = n[7] = 0; if (o == NULL) printf ("Error: 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 given 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 (invalid ()) { while (q) g[r[--q]] = 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 (!n[2]) ++n[5]; if (n[2] > n[6]) n[6] = n[2]; if (n[4] > n[7]) n[7] = n[4]; #if RJ printf ("%ld) ", t); for (a = 0; a < 81; ++a) printf ("%d", b[s[a]]); printf (" # S%ld", v); #endif } else { while (q > 0) g[r[--q]] = 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); printf ("Total solved without guess : %d\n", n[5]); printf ("Total solved with guess : %d\n", v - n[5]); printf ("Maximum number of guess : %d\n", n[6]); printf ("Maximum number of depth : %d\n", n[7]); if (fclose (o) == EOF) printf ("Error: Unable to close sudoku.txt file !!"); }