Analysis of zz-www.sudokuwiki.org-0242-base.sdk
Contents
Sudoku from http://www.sudokuwiki.org/Print_Weekly_Sudoku.asp?unsolvable=242
level: deep
position: .....2..1...3..85....86..7.3...8.7...9...4.....1......5.......76..5...3..24.....9 initial
Autosolve
position: .....2..1...3..85....86..7.3...8.7...9...4.....1......5.......76..5...3..24...5.9 autosolve
Pair Reduction Variants
Deep Constraint Pair Analysis
Time used: 0:00:00.000006
List of important HDP chains detected for E1,F3: 5..:
* DIS # E1: 5 # F4: 1,9 => CTR => F4: 5,6 * DIS # F3: 5 # G3: 2,3 => CTR => G3: 4,9 * DIS # F3: 5 + G3: 4,9 # I3: 4 => CTR => I3: 2,3 * DIS # F3: 5 + G3: 4,9 + I3: 2,3 # A3: 9 => CTR => A3: 1,4 * DIS # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 # I6: 4,8 => CTR => I6: 3,5,6 * DIS # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 + I6: 3,5,6 # B1: 6,7 => CTR => B1: 3,5,8 * PRF # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 + I6: 3,5,6 + B1: 3,5,8 # G1: 4,6 => SOL * STA # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 + I6: 3,5,6 + B1: 3,5,8 + G1: 4,6 * CNT 7 HDP CHAINS / 45 HYP OPENED
See Appendix: Full HDP Chains for full list of HDP chains.
Details
This sudoku is deep. Here is some information that may be helpful on how to proceed.
Positions
| .....2..1...3..85....86..7.3...8.7...9...4.....1......5.......76..5...3..24.....9 | initial |
| .....2..1...3..85....86..7.3...8.7...9...4.....1......5.......76..5...3..24...5.9 | autosolve |
Classification
level: deep
Pairing Analysis
-------------------------------------------------- * CONSTRAINT PAIRS (AUTO SOLVE) B7,C7: 3.. / B7 = 3 => 1 pairs (_) / C7 = 3 => 2 pairs (_) E9,F9: 3.. / E9 = 3 => 0 pairs (_) / F9 = 3 => 1 pairs (_) F6,F9: 3.. / F6 = 3 => 0 pairs (_) / F9 = 3 => 1 pairs (_) D1,D7: 4.. / D1 = 4 => 1 pairs (_) / D7 = 4 => 1 pairs (_) E1,F3: 5.. / E1 = 5 => 1 pairs (_) / F3 = 5 => 1 pairs (_) C7,C8: 9.. / C7 = 9 => 1 pairs (_) / C8 = 9 => 1 pairs (_) * DURATION: 0:00:05.499314 START: 16:31:36.591262 END: 16:31:42.090576 2017-04-29 * CP COUNT: (6) -------------------------------------------------- * DEEP CONSTRAINT PAIRS (PAIR REDUCTION) B7,C7: 3.. / B7 = 3 ==> 1 pairs (_) / C7 = 3 ==> 2 pairs (_) C7,C8: 9.. / C7 = 9 ==> 1 pairs (_) / C8 = 9 ==> 1 pairs (_) E1,F3: 5.. / E1 = 5 ==> 4 pairs (_) / F3 = 5 ==> 0 pairs (*) * DURATION: 0:00:52.182518 START: 16:31:42.090980 END: 16:32:34.273498 2017-04-29 * REASONING E1,F3: 5.. * DIS # E1: 5 # F4: 1,9 => CTR => F4: 5,6 * DIS # F3: 5 # G3: 2,3 => CTR => G3: 4,9 * DIS # F3: 5 + G3: 4,9 # I3: 4 => CTR => I3: 2,3 * DIS # F3: 5 + G3: 4,9 + I3: 2,3 # A3: 9 => CTR => A3: 1,4 * DIS # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 # I6: 4,8 => CTR => I6: 3,5,6 * DIS # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 + I6: 3,5,6 # B1: 6,7 => CTR => B1: 3,5,8 * PRF # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 + I6: 3,5,6 + B1: 3,5,8 # G1: 4,6 => SOL * STA # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 + I6: 3,5,6 + B1: 3,5,8 + G1: 4,6 * CNT 7 HDP CHAINS / 45 HYP OPENED * DCP COUNT: (3) * SOLUTION FOUND
Header Info
http://www.sudokuwiki.org/Print_Weekly_Sudoku.asp?unsolvable=242 From comment on the site: Ron Davis · Retired Professor of Management Science at CalPERS The "Unsolveable #242 is more challenging than the others I've commented on recently for two reasons: (1) there aren't any bivalued cells at the first Rooks (Run Out Of Known Strategies); and (2) the bifurcation tree goes down to 5 or 6 levels instead of 2 or 3. But by working with bi-located digits and being patient, the bifurcation search tree yields the solution once again, as it must in all cases (i.e. there are no unsolveable sudoku puzzles constructed with one unique solution). You can mix bivalued cels and bi-located digits in the same search tree, but for illustration I have built my bifurcation tree with bi-located digits only in this solution. You can choose your bifurcations in any sequence you like, and that may affect the number of levels you have to go down, but here is the sequence I chose first: Set G2,3 to 3 Set I5,6 to 3 Set A,C3 to 3 Set C7,9 to 3 Set A1,2 to 8 Set B,C1 to 9 where G2,3 stands for G2 or G3 and A,C3 stands for A3 or C3, etc. Luckily, it turns out in this case that the first choice in each bifurcation is correct except for set C7 to 3. After discovering that there are no feasible completions with C7 set to 3, you set C9 to 3 and then find that A1=8 and B1=9 lead to the solution without any more branching or backtracking. With hind sight, we see that we could have just not included the Set C7,9 to 3 branch point in the list, and gone directly to the last two, which imply that C9=3. This refinement shortens the list to 5 levels only, in which the first choice is correct in each case, a very fortuitous result. The question remains, however, could one pick other bifurcation sequences to find the solution in less than 5 levels? And what is the minimum number of levels one has to include to find the solution? I certainly do not know the answer to those questions at the present time. However, hueristics for choosing bifurcations with an eye towards keeping the tree as small as possible are probably possible. Like · Reply · Mar 12, 2017 11:09am
Appendix: Full HDP Chains
A1. Deep Constraint Pair Analysis
Full list of HDP chains traversed for B7,C7: 3..:
* INC # C7: 3 # C4: 2,5 => UNS * INC # C7: 3 # C5: 2,5 => UNS * INC # C7: 3 # B8: 1,8 => UNS * INC # C7: 3 # A9: 1,8 => UNS * INC # C7: 3 # F7: 1,8 => UNS * INC # C7: 3 # H7: 1,8 => UNS * INC # C7: 3 => UNS * INC # B7: 3 # C8: 8,9 => UNS * INC # B7: 3 # C8: 7 => UNS * INC # B7: 3 # F7: 8,9 => UNS * INC # B7: 3 # F7: 1,6 => UNS * INC # B7: 3 => UNS * CNT 12 HDP CHAINS / 12 HYP OPENED
Full list of HDP chains traversed for C7,C8: 9..:
* INC # C7: 9 # B8: 7,8 => UNS * INC # C7: 9 # A9: 7,8 => UNS * INC # C7: 9 # F8: 7,8 => UNS * INC # C7: 9 # F8: 1,9 => UNS * INC # C7: 9 # C1: 7,8 => UNS * INC # C7: 9 # C5: 7,8 => UNS * INC # C7: 9 => UNS * INC # C8: 9 # B7: 3,8 => UNS * INC # C8: 9 # B7: 1 => UNS * INC # C8: 9 # C1: 3,8 => UNS * INC # C8: 9 # C1: 5,6,7 => UNS * INC # C8: 9 => UNS * CNT 12 HDP CHAINS / 12 HYP OPENED
Full list of HDP chains traversed for E1,F3: 5..:
* INC # E1: 5 # E2: 1,9 => UNS * INC # E1: 5 # F2: 1,9 => UNS * INC # E1: 5 # A3: 1,9 => UNS * INC # E1: 5 # A3: 2,4 => UNS * DIS # E1: 5 # F4: 1,9 => CTR => F4: 5,6 * INC # E1: 5 + F4: 5,6 # F7: 1,9 => UNS * INC # E1: 5 + F4: 5,6 # F8: 1,9 => UNS * INC # E1: 5 + F4: 5,6 # E2: 1,9 => UNS * INC # E1: 5 + F4: 5,6 # F2: 1,9 => UNS * INC # E1: 5 + F4: 5,6 # A3: 1,9 => UNS * INC # E1: 5 + F4: 5,6 # A3: 2,4 => UNS * INC # E1: 5 + F4: 5,6 # F7: 1,9 => UNS * INC # E1: 5 + F4: 5,6 # F8: 1,9 => UNS * INC # E1: 5 + F4: 5,6 # E2: 1,9 => UNS * INC # E1: 5 + F4: 5,6 # F2: 1,9 => UNS * INC # E1: 5 + F4: 5,6 # A3: 1,9 => UNS * INC # E1: 5 + F4: 5,6 # A3: 2,4 => UNS * INC # E1: 5 + F4: 5,6 # F7: 1,9 => UNS * INC # E1: 5 + F4: 5,6 # F8: 1,9 => UNS * INC # E1: 5 + F4: 5,6 # D7: 1,9 => UNS * INC # E1: 5 + F4: 5,6 # D7: 2,4,6 => UNS * INC # E1: 5 + F4: 5,6 # F6: 5,6 => UNS * INC # E1: 5 + F4: 5,6 # F6: 3,7,9 => UNS * INC # E1: 5 + F4: 5,6 # B4: 5,6 => UNS * INC # E1: 5 + F4: 5,6 # C4: 5,6 => UNS * INC # E1: 5 + F4: 5,6 # I4: 5,6 => UNS * INC # E1: 5 + F4: 5,6 => UNS * DIS # F3: 5 # G3: 2,3 => CTR => G3: 4,9 * INC # F3: 5 + G3: 4,9 # I3: 2,3 => UNS * INC # F3: 5 + G3: 4,9 # I3: 2,3 => UNS * DIS # F3: 5 + G3: 4,9 # I3: 4 => CTR => I3: 2,3 * INC # F3: 5 + G3: 4,9 + I3: 2,3 # A3: 1,4 => UNS * DIS # F3: 5 + G3: 4,9 + I3: 2,3 # A3: 9 => CTR => A3: 1,4 * INC # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 # H7: 4,8 => UNS * INC # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 # H7: 1,2,6 => UNS * DIS # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 # I6: 4,8 => CTR => I6: 3,5,6 * INC # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 + I6: 3,5,6 # H7: 4,8 => UNS * INC # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 + I6: 3,5,6 # H7: 1,2,6 => UNS * DIS # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 + I6: 3,5,6 # B1: 6,7 => CTR => B1: 3,5,8 * INC # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 + I6: 3,5,6 + B1: 3,5,8 # C1: 6,7 => UNS * INC # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 + I6: 3,5,6 + B1: 3,5,8 # C2: 6,7 => UNS * INC # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 + I6: 3,5,6 + B1: 3,5,8 # B6: 6,7 => UNS * INC # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 + I6: 3,5,6 + B1: 3,5,8 # B6: 4,5,8 => UNS * PRF # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 + I6: 3,5,6 + B1: 3,5,8 # G1: 4,6 => SOL * STA # F3: 5 + G3: 4,9 + I3: 2,3 + A3: 1,4 + I6: 3,5,6 + B1: 3,5,8 + G1: 4,6 * CNT 44 HDP CHAINS / 45 HYP OPENED