The hardest sudokus

Everything about Sudoku that doesn't fit in one of the other sections

Postby Obi-Wahn » Mon Jan 07, 2008 11:01 pm

gsf wrote:what sudoku properties/techniques do you use to propagate the constraints?

I'm not sure what you mean by propagate constraints.
In this approach I'm just thinking of a Sudoku as up to 729 candidates and up to 324 constraints. Every candidate belongs to 4 constraints (a row, a column, a box and a cell) and every constraint contains up to 9 candidates of which only one can be true and at least one must be true. For example all the digits 2 in row 7 build one constraint or all different digits in cell R3C9 build another one.

I start with an empty table of implications and first look at every constraint, one after the other. I look up the 9 (or less) candidates for each constraint and set the A => ~B for every pair of those candidates thus getting a couple of weak inferences if you will by applying the One Rule of sudoku.
I also look if there are only two candidates A and B in the constraint. If so, I set the implication ~A => B.

I then look if I can link any two of the implications I already have. If A => ~B and ~B => C then I set A => C (and its contrapositive ~C => ~A). And if C => ~D, I set ~B => ~D, A => ~D and so on ...

So I don't propagate constraints, I propagate implications. And I don't use sudoku techniques, I just apply the sudoku rule to generate a first set of implications.

The conclusions come if I get a combination like A => B and A => ~B. You would call this a contradiction which proves that A must be false. Or you can view the contrapositive B => ~A and ~B => ~A which leads to the same conclusion.
User avatar
Obi-Wahn
 
Posts: 61
Joined: 05 January 2007
Location: Darmstadt, Germany

Postby gsf » Mon Jan 07, 2008 11:21 pm

Obi-Wahn wrote:
gsf wrote:what sudoku properties/techniques do you use to propagate the constraints?

I'm not sure what you mean by propagate constraints.

that's what I was after
you propagate the basic sudoku property and collapse implications

the q1 method is very similar, except it propagates the naked/hidden singles (and possibly locked candidates) constraints
it reaches closure much faster and only requires 2 simultaneous propositions instead of 4 (probably the main reason for its speed)

the longest one for q1 (4m19s @2Ghz) is
Code: Select all
001004000000060305000900000800000703000000028500070600300080006009200000040001000 # tarek071223170000-052


checking for the simplest constraints first (like your tabling and my q1) has the drawback
that a slightly stronger constraint may render seemingly hard puzzles easy

my guess is that tarek071223170000-052 above, the longest to compute for q1, will be a bear for you too
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Mon Jan 07, 2008 11:33 pm

Here is my first batch of 190 puzzles, it is impossible to know if the filter is missing out on many ? special puzzles below the limits.

BTW a "squirmbag" is a rather derogatory term and "Star" is much more appropriate.

Filter used, -sxt 1000, -sx9 2300, -q1 95300, SE ratings not done.

There are many more puzzles just below / around this,

There are no duplicates puzzles from previously posted puzzles.


-sxt -sx9 -q1
1636 2690 95019 #...4..7..4....9.3..8.3.....2...9..4...8...6.7......5..3..9...2..6...1.....5..2...# col0701-009
1512 2703 25728 #..3.5...94........68....4.......8.7.7..6.......5.9...3..2..........2.39....5.1..2# col0701-010
1456 2688 70099 #.2.4....9..6....3......25....5..8...3.....86..7..4...2.1...4..7...91......4.7....# col0701-011
1449 2601 82277 #..3..6.8....1......9..7.......53..4...4.....2.....46.8.7.9..4...1.........5..3.6.# col0701-012
1421 2743 73156 #.2...67..4......3...9.....5..58....4.......9..7...21...3.26......8..3......71.3..# col0701-013
1362 2264 35484 #1....6..9..7.8.2.........5....9...4......5..6.7..3.8...34......7...2.4...82..7...# col0701-014
1320 2236 59226 #.2...67.........32..9.....6..85..4...3...2.7.....1......16..9..5..8......6...4..7# col0701-015
1319 2648 45921 #......78...71....6.8....1...4...3.1...15..6..9.......23....4..5..87...6.....9....# col0701-016
1308 2558 91591 #...4..7....71.9...6...7....2.15....8.3.........9.1.4....5.9.1...8......3.....5..2# col0701-017
1266 2042 71731 #.......894....92..........4.6..7.3..5....3.2.....1.....7..6.5...1.......94...5..2# col0701-018
1250 2057 64004 #..34..7...5...9.3.....2...1.96..8............8.5.3..9.....1...25....3.6....7..4..# col0701-019
1229 1911 95101 #........9..71...3..8....4....6.31.......7..6.5..6....2.4.........13...2.9.5.6.8..# col0701-020
1220 2204 70237 #1.......945.....3.....3.51..4..1..6....9.....8....7..2..82.....7....8....1..4.6..# col0701-021
1205 2489 10105 #..3.5....4....9....6.2...1..7.6....83..........5...3.....7...62....4.9...8......7# col0701-022
1164 1790 58871 #.2.......456.8....78......4.....53.....9...1.8...4...5.....19.....3...5..4..7...2# col0701-023
1147 2352 72881 #......7..4...8...6.9.....1.2....8..3...34.5.....26....3..8....4.7.........1.359..# col0701-024
1143 2011 20277 #1....67......8..3...923.......3....8.....16......4..2........4.51.......764...5..# col0701-025
1135 1916 18111 #.23..6.8.4..1.......9........1.4.......9....2.6...2.7..3....8.7..2....5......76.3# col0701-026
1128 1814 92060 #1....6.8.....892.....3....5..5.....4.7.......8...2.1....47...2..3.......9....86..# col0701-027
1119 2430 56116 #.2.4..7....7.8...6.8...3.....5.7..6..4........3.2..9....8.1.6..........1.......58# col0701-028
1109 1909 91466 #....5...9...1..3....9....51.6.7..8..3..........1.2...4.7.6.....8....72....2.1..4.# col0701-029
1109 2920 64042 #..3..67.....18...66...2....2....8..1..93..4.........5...5.6..9.8....1..3.4.......# col0701-030
1096 2029 73960 #1....6..9.5.....3...8...4....4.9.8...3.....5.9..6....1...71...2.........7...62.9.# col0701-031
1094 2061 24252 #1..4.......7.8...6....72....4.....1.5.....9....8..3..2.......9.8..9..5....2.6...8# col0701-032
1092 1845 79304 #..3.5...94.....1...8.....6...79....36.....8...1.....4...25.7......82........93..5# col0701-033
1086 1902 95121 #1.3.......5...9.3...9..........4.8....5..7.9..7..1...2.6.8....55....1.7.....2.4..# col0701-034
1084 2679 62388 #1....6..9..7.8.2.........5....9....7.....5.6..7..3.8...34......7...2.4...82..1...# col0701-035
1081 2446 10229 #.....67.....1....6..9.2..1..3......87.....6....15...4.....4..2...491....8....3...# col0701-036
1080 2062 11187 #.23..67...56....2..............4.9..3....5.7....1....8..78....1....9.4...3...7.5.# col0701-037
1080 1852 95012 #1....6..9.5.1..23........4....67...33..8..........39..6....7..1.4.....5...2.1....# col0701-038
1079 2379 6854 #............1..2.6..9.2..41.3.........6.1...48..5...9...1.9.4..5..8........3...7.# col0701-039
1077 1801 95196 #.......8...6...1.2.8.2..6.4..81...6..7...5...9...3....3...9......48...1......75..# col0701-040
1075 2162 22582 #..3.5.7...571.....6....2....7.9..1...9.....2......4..8........68......4...13..5..# col0701-041
1074 2245 62226 #...4..7....7..9...6...7..152.......8.3.........9.6.5....5.9.1...8...1..3...5...2.# col0701-042
1072 1703 95014 #....56....5.1...3.....3...12..7......1..6..7...4...9...7...3.1.........29..8..4..# col0701-043
1067 1837 66331 #..3..6...4...8..2...91.......19.....8...4...7.6...3..........755...2.8.........42# col0701-044
1066 1937 95302 #.......8...6.8.1.2...2..6.4..81...6..7...5...9...3....3...9......48...1......75..# col0701-045
1063 1635 59916 #1...56....5.....3.....37..12.........1..6..7...4...9...7...3.1.........29..8..4..# col0701-046
1058 1786 64889 #12..5....45....1....9.....6...3....8..1.4.9.......2.7......7..3..2.9.4.....8.....# col0701-047
1055 1737 75196 #1.......9..7.8.2.........5....9....3.7..2.4..6....5.1....6.....7.2.4.....48...6..# col0701-048
1054 1751 95050 #.2...6..9..718...............1.......9...2..38..7...5......46...4....39...25....4# col0701-049
1054 1825 13365 #.23..6....567...2.7..........8...9..3....5.7.....1...4...9..8..6....3.5.....4...1# col0701-050
1053 1937 65755 #..3..67..45.7...2..........2...9.....9.5.......7..3..1.....13.7...9...4...8...6..# col0701-051
1046 1728 10568 #...4...89...........9..15.42...6..1..3...7.....15..8....51....86...2.....7...3...# col0701-052
1046 1717 13808 #.2.4...8......9..6....3.1.......1..3....6.9....58...7..72...5..54.7.......8..3...# col0701-053
1040 1907 10452 #.............891...8..13..42......6...7.....5.9.3..4..6....4.2..4..3.9....5.....7# col0701-054
1040 1696 79221 #.2.4.......6.8....7....3..5....6.8..3....7.1....8....7..4...2.......5.939......7.# col0701-055
1038 1714 69530 #1.......9..7.8..3..6....4.....53..7..4....6..9.......1.3..2.......7...2...28.5...# col0701-056
1037 1751 63013 #1....6..9.5.....3...8...4....4...8...3.....5.9....1..7.....4......762...7...1...2# col0701-057
1035 1720 68465 #.23.5.7...56.....37..........89..4..6...7...2.....1...3...2...7...8..9.......4.1.# col0701-058
1033 1701 9769 #.2.4....9..7.8....6............6..5..1.9..4.....2.4..3.4...3..28......7...5....4.# col0701-059
1033 1577 30734 #1.......94......3...92..5......1..7...56..9........6.23.8.4......29....8.....7...# col0701-060
1032 2019 87722 #........9..71...3..8....4....6.31.......2..6.5..6....7.4........613...7.9...6.8..# col0701-061
1026 1652 95498 #...4....9..7.8....6....2.1.2....1.3....97.....48......3...6.1.5.....53...6.....2.# col0701-062
1024 2098 5473 #...4...........2.6..9.2..41.3.........6.1...48..5...9...1.9.4..5..8........3...7.# col0701-063
1024 1620 64370 #...4...8......92..6...7...1...8...4......29...6..3...731......55.6.1.3...7.......# col0701-064
1023 1891 82103 #1..45...94...89......1........8....5.6.....2...7..23...3.....7...2..46..9.......1# col0701-065
1020 2106 70937 #1....6..9.5.1...3...8...4....4...8...3.....5.9...6...1...6.7..2....9....7...2.1..# col0701-066
1015 1601 44998 #1...56......7.....7..13..6...8...9..6......7..4......2.12..84...9......8...5...3.# col0701-067
1011 2380 66476 #.2...67.....7...32..9.....6..85..4...3...2.7.....1......1...9..5..8......6...4..7# col0701-068
1007 2183 68851 #.2...6.8...71.............4.4...8..35..9.......1.7........9.5...8....9.2.....4.68# col0701-069
1006 1667 15392 #1....6....5..8.2...983.............1..95..8..7......4......4.6.....6...7.3.8..5..# col0701-070
1003 1691 86203 #..34..7...5...9........2.6.2..........13....7.9...5.4.......8.1....7...3..48...7.# col0701-071
1001 2110 93996 #.2..5...9..71.....8...23...2....8..5.74...6..9........5...3...2......1.....6...4.# col0701-073
998 2221 11059 #..345.........9......3..5..2....8..7..8.6.4...7.....1...46..8...1...2.749........# col0701-074
991 1611 19689 #.....6..94.....12....1..5..2..5...3..7...8....6..9....5..2..4...8......7..7....5.# col0701-075
989 2061 90224 #...4...894.7.......9....5...3.8...5...1..76......2.........1....8.3....5..2.6.3..# col0701-076
980 2009 22590 #1....67.........2...9.3..4..3.9.......4.2...18....1..7..85...9.5.............86..# col0701-077
977 2417 63428 #...4....9....8.2..6....7.1....9....47...2.8...3...1.7.37...5...56.........1....5.# col0701-078
974 2281 83636 #...4....9....8.2..6....7.1....9....47...2.8...3...1.7.3.1....5.56........7...5...# col0701-079
974 1692 95336 #...4...8......92..6...3...1.16.....773..6....9.5.........8..9..5...1...3.....2.4.# col0701-080
971 2475 95033 #..3.5.7..4....9....8.......2..3..1....1....7.....1.56..9.82.........4.....5.6.3..# col0701-081
969 2157 59617 #..34......5...9..6....2..1.2.........6...5..7..43......1....8.....59...1.....167.# col0701-082
968 2425 89604 #.....67.......9...8..2....42.1........5..8....8.5....1.3...79....83....5.4....6..# col0701-083
956 1665 14714 #1....67...5.1......89....1......43..........28..6...91.....2..4..6.3....9..8...6.# col0701-084
951 2723 63327 #......7....71.9...68..7......1.9.6..3......42...2.......6.1.9.......5..4.......53# col0701-085
941 2460 20300 #1...5...9..6.......8.2......1.....97.......459...4.31....6.....5...9..7...2.78...# col0701-086
936 2497 95237 #..3....8..5.1....69...................8..739..4.5....2....2...76.47......7..15...# col0701-087
934 1660 95672 #.......8.4.......37....25.4..1.6....5....34...9.8........9..........53.7.6..1..4.# col0701-088
931 1635 2409 #..34......5...9..6....2.1..2..3......6...5..7..4.6.........1.958.......1.1....67.# col0701-089
929 2371 10470 #...4....9..7.8.2..6....7.1....9....4....2.8...3...1.7.37...5...56.........1....5.# col0701-090
927 2792 9742 #...4...8..5...92......3...42.6...1...1.7.....9.5..1....9...26...........7.28...3.# col0701-091
913 1923 95348 #..3...7..4....92...8.7....5.7.6...5.....4....9....3....1.8.....5.......8..8..5.61# col0701-092
910 2379 73016 #1...5.7.......9.3....2............9.5...7.1.....3..42..15.6....6....4.7..84...6..# col0701-093
899 2301 57964 #1...5...9......2...8.7...4.............2.4.7.9...6...53....8.5..91.....3.6..3....# col0701-094
888 2333 95139 #..3.....94.....2...6..7..1..8.7...4.5...64.......18....4...7.6...25....39........# col0701-095
838 1443 95243 #...4....9.5..8.2..6....7.1..3...1.5...59........2..8..37........6......4..1..3.7.# col0701-096
838 2480 50232 #1.......9..67...2..8.......2..5..3....5.67.......4..5............26...4.96....8.1# col0701-097
831 1989 95521 #..3...7..4....92...8.7....5.7.6...5...5.4....9....3....1.8..5..........87......61# col0701-098
826 2673 59434 #1...5...9......12.......5....4..8...5...6..9..3........8..94..66...1.9.......3..7# col0701-099
808 2012 95333 #...4..7....71.9...68..7....2......5...1.9.8...3.........8.1.4..5..6....3.......2.# col0701-100
807 1962 95228 #..3......4...8...6..9...1..2..8....7.....2.......478....15...9.5....8..2...6..3..# col0701-101
803 2849 58995 #1..4......5...9.3.....2....2.4.1....73...5.9...............78..5.6....7..7....9.3# col0701-102
798 2370 256 #...4...8..5...92......3...42.6...1...1.7.....9.5..1....9...26...........7..81..3.# col0701-103
797 2286 78318 #...4.67....7..........7..152..8........9...2...4.1.6..3..........5.4.1..89......3# col0701-104
793 2525 29047 #.2.4....9..7.8....6.....1.......3....3.94...2...5.2.....1....7..9...4..3......64.# col0701-105
792 2354 42668 #..3.....9......1..7....2.4.2....4.7..14.....3.9............56.75..8........24..5.# col0701-106
779 2257 95219 #......7...5.7....3......56.2...9....3...4.....8.6...3..7.8..3....4.2...19.......8# col0701-107
775 2429 3677 #...45.7....71.9...6...7....2..5....8.3.....7...9.1.5....5.9.4...8......3.......2.# col0701-108
756 1577 95376 #..3...7..4....92...8.7....5.7.6...5.....4....9....3....1.8.....5.......87....5.61# col0701-109
745 2340 17625 #1....6.8..5....2..........4...861.7..3...7...7..9...............42...5.89....8.1.# col0701-110
739 2301 95354 #.2.........71....6.9..7.4....5.1...3...5.8........3....4..6.9...8.....2...6..1..8# col0701-111
738 2831 8091 #.23..6...45.....6.6..7........31.9..3....4.2.........85....3.4...68..1......9....# col0701-112
736 2794 51668 #..3....8..5.1....69.........7..15.......2...76.47...........4...4.5....28.....39.# col0701-113
735 2551 13779 #.2..567.....7........2.3....3.5..6....1.9..2.8.......4..4.....85......1..6...52..# col0701-114
732 2499 76286 #...4....9....8....7....2.6.2....3.1...59..4.8...........2..5...5..37.6....1....5.# col0701-115
724 2378 47873 #..34.........8....7....1..62....56.....9...57.......21..8...9..5....7.6..4.3....5# col0701-116
716 2538 9874 #...4..7....71.9...6...7..5.2.......8..1.9.6...3.........6.4.5..81.....23.........# col0701-117
708 1276 95253 #...4....9.5..8.2..6....7.1..3...1.5...59.......62..8..37...............4..1..3.7.# col0701-118
708 2344 95311 #1....6..9..7.8.2.........4.....9...33..56.....81..3...6....5..1..2.......4.....7.# col0701-119
705 2575 12587 #1...5...9.5........96......2..8..3..7....4....1..7...2..1.2...5...3..49.......8..# col0701-120
700 1413 95346 #.....6.8...6.8.1.2...2....4..81...6..7...5...9...3....3...9......48...1......75..# col0701-121
697 1212 95315 #1....6.8..5.7..1....9.2.........48.68.....4.1.......3...25......7..9....6....13..# col0701-122
692 2761 95034 #12....7....7....36.9..7...............1.9.6..7..5.4..8...8....4..2.6.1.........5.# col0701-123
689 2411 2453 #.2.4....9..6......7.....5.......8..3.3..42...9.13............7.5......61.9.2....4# col0701-124
688 1565 95241 #..3...7..4...8...6.9.....1...1....9.6....4..5.7....3......4...25...62......9.8...# col0701-125
680 2425 70141 #......7..4...8...6..9....1.2..5........6.8..2....2.34.3...6...4..........712..9..# col0701-126
677 1226 95294 #.2...67..4...8......91.......19.....8...4...2.6...7.3..7.....56........8.....52..# col0701-127
671 2303 69556 #..34..7...5......6.......1....8...93....478....8..2.....97..3..61...8.5..........# col0701-128
665 1168 95225 #.2...6.8.4..1.......9........1.4......89....2.6...2.7..3....8.7..2....5......76.3# col0701-129
655 1278 95279 #.......8...6...12....2..6.5..15..9..8....3....4..7....3....8.....21....6.7..4....# col0701-130
650 2522 6061 #.....6..94...8.2...6.....5..9...1.....5......8...7.4..3....7......2.83......3..41# col0701-131
647 2572 19950 #......7.9.5.7...3......25...7.6....3..8......9.4.2.........8.1.....4..6..6.5..3..# col0701-132
643 2594 95005 #12....7....7....36.9..7...............1.9.6..7..5.4..8.....8..4..2.6.1.........5.# col0701-133
631 2446 41240 #..34..7......8.1..7....2..62....56.........95........2..4.......683.....9....7.6.# col0701-134
627 951 95212 #.2......9...7...32......56..3.6...7...4......8...15.....1..8...5...4.....6.2....3# col0701-135
624 2499 95019 #..3......4...8...6..9...1..2..8....7..8..2.......47.....15...9.5....8..2...6..3..# col0701-136
622 2335 2724 #..34..7......8.........2..62...17.....93.....87............195...59..3.7......4..# col0701-137
618 2514 60005 #.2...6....5.1.....6...7...4.1...5.7.7...3.4.....2...6.3...9..4.......3.8......9..# col0701-138
617 2537 17783 #...4..7......8.1..7....3..62....7.6..689.......4......3....26......9..25........3# col0701-139
615 2428 17459 #.2...6.8.4.....1....9...6......4......539.....6...7..8.7...28..5......7........23# col0701-140
614 2316 19171 #....5...9..71..2......3..4127.6.....8.1...6....6..3.....87..1.......4.......9...5# col0701-141
614 2492 67732 #1...5...9...7..1........56.2...1.9....8..4.1....3....75...6..9...4.....2.3...8...# col0701-142
600 2325 95042 #....5...9..71...3.......1.4.1..9...5.8...4...7..6...1.3.2......6.........7.3...6.# col0701-143
597 2675 69973 #1....6..9..7.8.2..8......5....9.5..........6..7..1.8...34......7...2.4....2..7...# col0701-144
587 2600 10272 #12....7....7....36....7...4..6.1.3...8.......9..5.....5..9.8..............132.6..# col0701-145
573 2349 71940 #......7..4...8...6.9....1..2..8....4.7...49....1..3...5....8..2...5........26.8..# col0701-146
569 2575 81917 #12....7....7....36....7...4..6.1.3...8.......9..5.....5..9.8........1.....1.3.6..# col0701-147
565 2673 7718 #..3.5...94.....1...8....5..........3..7.2.9..6......27.6.9.8.....5.7..9......4...# col0701-148
561 2766 62881 #1...5...9..67......8.........76.8...5...2...1.........3.....91...1.3..2..45.....3# col0701-149
560 2631 9580 #1...5...9..67......8...2.......6.9516.....3.......4..63...1...5..2....9..7.8.....# col0701-150
551 2492 49249 #12..5......71....668.........5....9.7..2....1.1..4.3...7.8....2....9.4.......3...# col0701-151
550 2262 7015 #..3.5.........91..7..2....42...7......78....286........7.6....86...1.9....4....5.# col0701-152
539 2389 2508 #...4......5...9...7...13.6.2...7...6..9..5....4...23..........28...2.67........18# col0701-153
536 1481 95290 #1....67...571......89....1.....4.3.7........28..5...9.....2...4.....3...9..8...6.# col0701-154
533 2649 13667 #.2.4...8...6...1..7....3.......9..1....1..845.1......23...6.........7....4.8...5.# col0701-155
522 2597 1644 #..3..6....5..8.1..7.......62.....4...4....851....4..9..8..1.9.....3.7........4...# col0701-156
522 2406 856 #.2.4....9..7......6......5...5....6..9.2....8.......7..3..24........8.939.13.....# col0701-157
521 2316 13929 #..3.5...94.....1...8....5..........3..7.2.9..6..1...27.6...8.....5.7..9......4...# col0701-158
497 2667 6611 #..3.5...94.....1...8....5..........3..7.2.9..6..1...27.....8.....5.7..9..6...4...# col0701-159
484 2486 1638 #.2.4...8...6.....37....3..4......6.7..........8.5...4..1.824........5.1.9..1.....# col0701-160
483 2413 10091 #.....67.94..18..6..6........8...7.9....3....5..5.2....3.2............1...1...8.7.# col0701-161
481 2706 7585 #....5..8....7...3..8...1..6.3...86....719......5.........9..2.4.1...4.6.........1# col0701-162
468 2418 11203 #1....67...5......2..9.3.........3.4.3..1........8673....2....9.7....86..........5# col0701-163
454 2567 8404 #.2.4..7......8...2.....3..6.....195..4.9....7......4..3.........642...7.8...1....# col0701-164
430 2756 5630 #....5..8....7...3..8...1..6.3...86....7.9....8.5.........9..2.4.1...4.6.........1# col0701-165
430 2721 6424 #.2.4..7......8...2.....3..6....1.95..4.9....7......4..3.........642...7.8....1...# col0701-166
422 2374 1734 #.2.4...8...6.....37....3.........6.7..........8.5...9..1.824........5.129..1.....# col0701-167
421 2326 5888 #1.....7.....1....6..9..2.5...48..........49.3...52..4.3.8..5.9.67................# col0701-168
418 2394 15211 #1.3..6.8.........6.6.27.....3...7..8...8...........45...4...9..5...9.....7...1..3# col0701-169
414 2363 1907 #.2.4..7......8.........3..6.....195..4.9..2.7......4..3.........642...7.8...1....# col0701-170
412 2412 9568 #..3....8.4...8.1....9....6.2...4..1.......4....7...2.5...9.....8...64..1.7.3.....# col0701-171
405 2751 15711 #....5..8....7...3..8...1..6.3...86...47.9..2...5.........9....4.1...4.6.........1# col0701-172
402 751 95241 #.2......9..6.8.1..7......4....6..8..3.581.........7.....13..6...4.....2.9.......7# col0701-173
394 2561 1133 #...4567....7.8.........7..12.......33..6...9...6..54....8..46...........9......2.# col0701-174
393 2694 17956 #1...5...9......2.....7...4.............2.4.7.9...6.3.53....8.5..91.....3.6..3....# col0701-175
387 2458 18223 #..3.5..8....1.9.........5....4...8.536.....4.....4...2.1......7..8.3..5.9..7.....# col0701-176
384 2375 1862 #.2.4..7......8.........3..6....1.95..4.9..2.7......4..3....1....642...7.8........# col0701-177
382 2314 10102 #....5..8....7..13..8...1..6.3...86....7.9......5....1....9..2.4.1...4.6..........# col0701-178
380 2523 10681 #...4567....7.8.........7..123..7..9............8..56....6..45..........3.9.....2.# col0701-179
370 2613 11041 #....5.7....7189...6..7.....2..........89..1...3.....4...18..5............4...1.32# col0701-180
367 2286 3600 #..3..67...5......2.8.1.....2.......8..7.6.9.........75.....4.......93.....46.73..# col0701-181
359 2361 6743 #1...5.78....1......69.....1..4...3.......4.2.9..8....6.9...........32...6..7....8# col0701-182
347 2330 10805 #....5..8....7...3..8...1..6..7......34...86....5.9.....1...4.6....9..2.4........1# col0701-183
345 2503 14013 #1.3..6.8.........6.6.27.....3...7..8...8...........45...4...9..5...9.....7...2..3# col0701-184
340 2366 2455 #.2....7..4...8......91...6...59..61........93.......5.....21.....13....68...4....# col0701-185
336 2264 7794 #..3......4.......2.8.1...6.....6..9.5..9....7.9..18....758...1...26....3......4..# col0701-186
335 2358 5521 #.2....7....71.9...68..7...........45..6.9.1..8..........8.6.9.......4.3..3.5.....# col0701-187
325 2690 4823 #.2....7....71.9...68..7...........54..6.9.1..8..........8.6.9.......4.3..3.5.....# col0701-188
314 2688 2794 #.2....7..4...8......91...6...59..61........93.......5.....41.....13....68...2....# col0701-189
301 2665 2710 #.2.4.......7..9..6....3......5..7.6..46.2.....3....8....9..567........91.......5.# col0701-190
291 2457 5048 #12....7....7....36.9..7.......5.4.....196.3..............8....4.8.....5...2.3.1..# col0701-191
279 2569 7489 #..34...8.4.......27.....5....8...6..3..8...1...1.9.....3.9...4......5...9....2..6# col0701-192
273 2506 1637 #..3..6....5..8.1..7......6.2.....4...4....815....4..9..8.91.2.....3.7............# col0701-193
272 2372 1618 #..3..6....5..8.1..7......6.2.....4...4....8158...4..9..8..1.2.....3.7............# col0701-194
271 2685 2688 #1.........571....668...........9.....7.6....5....3.4....2....9.7..5....2.6..4.3..# col0701-195
268 2320 1546 #......78...71....6....3.1...4......5..15..6..9.......23..89......27...6.....4....# col0701-196
266 2393 1618 #..3..6....5..8.1..7.8....6.2.....4...4....815....4..9..8..1.2.....3.7............# col0701-197
251 2342 1161 #.2.......4....92...9..7.....4...59..5.......18......6.3...6...7..4..35.....51....# col0701-198


Of note col0701-022 is the only 20 clue puzzle, with a very high sxt and sx9.

Here is the top -q1 from the above list,

-q1
95672 #.......8.4.......37....25.4..1.6....5....34...9.8........9..........53.7.6..1..4.# col0701-088
95521 #..3...7..4....92...8.7....5.7.6...5...5.4....9....3....1.8..5..........87......61# col0701-098
95498 #...4....9..7.8....6....2.1.2....1.3....97.....48......3...6.1.5.....53...6.....2.# col0701-062
95376 #..3...7..4....92...8.7....5.7.6...5.....4....9....3....1.8.....5.......87....5.61# col0701-109
95354 #.2.........71....6.9..7.4....5.1...3...5.8........3....4..6.9...8.....2...6..1..8# col0701-111
95348 #..3...7..4....92...8.7....5.7.6...5.....4....9....3....1.8.....5.......8..8..5.61# col0701-092
95346 #.....6.8...6.8.1.2...2....4..81...6..7...5...9...3....3...9......48...1......75..# col0701-121
95336 #...4...8......92..6...3...1.16.....773..6....9.5.........8..9..5...1...3.....2.4.# col0701-080
95333 #...4..7....71.9...68..7....2......5...1.9.8...3.........8.1.4..5..6....3.......2.# col0701-100
95315 #1....6.8..5.7..1....9.2.........48.68.....4.1.......3...25......7..9....6....13..# col0701-122
95311 #1....6..9..7.8.2.........4.....9...33..56.....81..3...6....5..1..2.......4.....7.# col0701-119
95302 #.......8...6.8.1.2...2..6.4..81...6..7...5...9...3....3...9......48...1......75..# col0701-045
95294 #.2...67..4...8......91.......19.....8...4...2.6...7.3..7.....56........8.....52..# col0701-127
95290 #1....67...571......89....1.....4.3.7........28..5...9.....2...4.....3...9..8...6.# col0701-154
95279 #.......8...6...12....2..6.5..15..9..8....3....4..7....3....8.....21....6.7..4....# col0701-130
95253 #...4....9.5..8.2..6....7.1..3...1.5...59.......62..8..37...............4..1..3.7.# col0701-118
95243 #...4....9.5..8.2..6....7.1..3...1.5...59........2..8..37........6......4..1..3.7.# col0701-096
95241 #..3...7..4...8...6.9.....1...1....9.6....4..5.7....3......4...25...62......9.8...# col0701-125
95241 #.2......9..6.8.1..7......4....6..8..3.581.........7.....13..6...4.....2.9.......7# col0701-173
95237 #..3....8..5.1....69...................8..739..4.5....2....2...76.47......7..15...# col0701-087
95228 #..3......4...8...6..9...1..2..8....7.....2.......478....15...9.5....8..2...6..3..# col0701-101
95225 #.2...6.8.4..1.......9........1.4......89....2.6...2.7..3....8.7..2....5......76.3# col0701-129
95219 #......7...5.7....3......56.2...9....3...4.....8.6...3..7.8..3....4.2...19.......8# col0701-107
95212 #.2......9...7...32......56..3.6...7...4......8...15.....1..8...5...4.....6.2....3# col0701-135
95196 #.......8...6...1.2.8.2..6.4..81...6..7...5...9...3....3...9......48...1......75..# col0701-040
95139 #..3.....94.....2...6..7..1..8.7...4.5...64.......18....4...7.6...25....39........# col0701-095
95121 #1.3.......5...9.3...9..........4.8....5..7.9..7..1...2.6.8....55....1.7.....2.4..# col0701-034
95101 #........9..71...3..8....4....6.31.......7..6.5..6....2.4.........13...2.9.5.6.8..# col0701-020
95050 #.2...6..9..718...............1.......9...2..38..7...5......46...4....39...25....4# col0701-049
95042 #....5...9..71...3.......1.4.1..9...5.8...4...7..6...1.3.2......6.........7.3...6.# col0701-143
95034 #12....7....7....36.9..7...............1.9.6..7..5.4..8...8....4..2.6.1.........5.# col0701-123
95033 #..3.5.7..4....9....8.......2..3..1....1....7.....1.56..9.82.........4.....5.6.3..# col0701-081
95019 #...4..7..4....9.3..8.3.....2...9..4...8...6.7......5..3..9...2..6...1.....5..2...# col0701-009
95019 #..3......4...8...6..9...1..2..8....7..8..2.......47.....15...9.5....8..2...6..3..# col0701-136
95014 #....56....5.1...3.....3...12..7......1..6..7...4...9...7...3.1.........29..8..4..# col0701-043
95012 #1....6..9.5.1..23........4....67...33..8..........39..6....7..1.4.....5...2.1....# col0701-038
95005 #12....7....7....36.9..7...............1.9.6..7..5.4..8.....8..4..2.6.1.........5.# col0701-133

C
Last edited by coloin on Mon Jan 07, 2008 7:49 pm, edited 1 time in total.
coloin
 
Posts: 1662
Joined: 05 May 2005

Postby Obi-Wahn » Mon Jan 07, 2008 11:46 pm

gsf wrote:my guess is that tarek071223170000-052 above, the longest to compute for q1, will be a bear for you too

Actually not. I already checked tarek's list and #170 was the hardest for my solver.

#052 only requires one Sword check which my solver does in 870ms (Athlon XP 2100+).

I'm not sure if we use the same terminology (English is not my native language) but my solver always only uses 2 propositions. It just looks at an increasing number of constraints to determine if both propositions A and B can be true at the same time:

1 constraint is what AW calls a split, which means that every candidate in the constraint is either eliminated by proposition A or B.
2 constraints for a Sword check, where the remaining candidate(s) in the first constraint eliminate all the remaining candidates in the second constraint.
3 constraints for a Jelly check, where every possible combination of remaining candidates in the first two constraints eliminates all remaining candidates of a third one.
And now 4 constraints for a Star check.
User avatar
Obi-Wahn
 
Posts: 61
Joined: 05 January 2007
Location: Darmstadt, Germany

Postby gsf » Mon Jan 07, 2008 11:58 pm

Obi-Wahn wrote:
gsf wrote:my guess is that tarek071223170000-052 above, the longest to compute for q1, will be a bear for you too

Actually not. I already checked tarek's list and #170 was the hardest for my solver.

#052 only requires one Sword check which my solver does in 870ms (Athlon XP 2100+).

I'm not sure if we use the same terminology (English is not my native language)

english is not the problem, brain is
the (re)description of 1,2,3,4 helped
but it will take some more thought to determine any connections
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Obi-Wahn » Tue Jan 08, 2008 9:23 am

I've completed the check of
Code: Select all
coloin-4/13-1600
6.......2.9.4...5...1...7...5..84.......2.......3.5.4.2.....6...3...9.8...7.....1
It scores 1 Star - 7 Jellies - 17 Swords.
The Star check led to 122 new implications.

I could slap myself. I use a rather naive approach to the problem. After selecting the two propositions A and B I create a list of constraints that are effected by either A or B. I then use 4 nested for-next-loops to generate _all_ combinations of 4 constraints which in the first check led to a total of 18 billion (!) cycles of the inner loop.

Now, I already realized that every remaining candidate of one constraint must be linked to at least one candidate in one of the other constraints, because an unlinked candidate can always be true under the propositions A and B, rendering the constraint useless. But I couldn't think of a way to check if all candidates are linked before I selected all 4 constraints.
Actually it's quite easy and I used this idea for a fast search of Distributed Disjoint Subsets already:
After selecting the first constraint each remaining candidate in this constraint must get linked. So I can look at the lists of linked constraints for each candidate, select the shortest list and only cycle through this list for selecting the second constraint. This will add some new candidates to the unlinked list and remove some already linked ones. I can repeat this for constraints 3 and 4 and then check if the list of unlinked candidates is now empty. If not, I don't have to bother with any check and can go on to the next loop. This should considerably cut down on the number of cycles of the innermost loop.

However, at least I have some data now to check if the new algorithm finds all possible new implications for a given Star check.:)
Last edited by Obi-Wahn on Tue Jan 08, 2008 8:33 pm, edited 2 times in total.
User avatar
Obi-Wahn
 
Posts: 61
Joined: 05 January 2007
Location: Darmstadt, Germany

Postby tarek » Tue Jan 08, 2008 10:04 am

ravel in a PM to tarek wrote:Hi Tarek,

i found the time now to run my program against your list of 363 puzzles. There were 4 new ones in it, that got 19 points. I updated my last top list here. I have not checked Coloin's and other puzzles posted in the last months and probably will not do it (from my experience those almost symmetrical puzzles get relatively few points, most of them are "cracked" with a big subnet step).

From my POV some of the puzzles are clearly overrated, e.g. for these puzzles my program found solutions with 2-6 forcing nets.
Code: Select all
296##12722#955#461   2
232##18210#1813#636  3
107##95550#1362#884  4
168##95510#1982#733  5
056##95628#1756#1034 6

I also had hoped for more correlation to the sword/jelly-rating:(

So the problem to get good ratings does not seem to have become easier in this time.

Good work in finding toughies has been done anyway.

Cheers,
ravel


Thanks ravel & yes, there were over-rated puzzles. Just ran SE1.2.1 (my mistake) on someselected puzzles to check the ratings:
Code: Select all
Puzzle                                                                            ID                    SE121
-------------------------------------------------------------------------------------------------------------
300000002080070010006900000050704000000000008000510070009000300010040080200000006 tarek-1801            11.3
400000006090070010002000500010307000000010000000908070000000400080030090605000002 tarek071223170000-021 10.4
200000006090010080007000300040508000000040001000900050003200000010050090600000007 tarek071223170000-026 11.3
001004000000060305000900000800000703000000028500070600300080006009200000040001000 tarek071223170000-052  9.9
000000001070009020408000600000250030000007000050930000100000800030005070006000004 tarek071223170000-017 10.0
003400700000009000600020000290064000000000000008300400005000001800030500000500074 col-201107-M3-1        9.8
000000001080040050206000700050304000000090000000805040007000200090030080100000006 tarek071223170000-032 10.0
007000005090040030001000200080403000000090000000806040002000700060030090500000001 tarek071223170000-027 10.6
007001000600090200030500000900000608000000030000080092200040009001300000050007000 tarek071223170000-072 11.5
200000100050090070004006000030007000908050000000300090001000200080070050600000004 tarek071223170000-029 11.1
003006080000100000090070000000530040000004608004000002010000000700900400005003060 col-201107-M2-12      10.2
003050000400009020080100000010030000005800000900004070000000037600000402000002906 col-201107-M3-5       11.2
900004000030060070005000800020106000000070003000200010008000900070010060400000005 tarek071223170000-013 11.2
900000003010060020008000500070006000000020704000001060000905000020040010300000008 tarek071223170000-048 10.7
100000002090400050006000700050903000000070000000850040700000600030009080002000001 Easter-Monster        11.6
100000000040050030002000601050008000700040000000503070006000900080070040900000002 tarek071223170000-044 10.6
000600001090030080200000700030008000504090000000300050007000600080040090100000002 tarek071223170000-007 10.6

ratings have changed & some score less than 10.0..... so, where to go from here:(

tarek
User avatar
tarek
 
Posts: 2631
Joined: 05 January 2006

Postby JPF » Tue Jan 08, 2008 11:20 am

Thanks tarek
Easter Monster set up a new record of Sudoku Explainer 1.2.1 with ER=11.6 ?

JPF
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Postby Obi-Wahn » Tue Jan 08, 2008 12:10 pm

SE 11.6 for the Easter Monster? I thought the Golden Nugget set a new record with 11.5 ...

Well, here's the list of the tough nuts for my solver of your 363:
Code: Select all
Puzzle                                                                            Nr.         Rating
--------------------------------------------------------------------------------------------------------------
....71......9....1.6.4.2...5.....7...1...4..6..3....8..9.2....4..7...3..8......5. #170   4 Jellies - 23 Swords
.......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7..... #001   1 Jelly - 20 Swords
8.......4....9..3...14..7...6.3.5.....2..........69.5...7...1...2..3..9.4.......8 #031   1 Jelly - 11 Swords
...6..7......2...4..9..3.8.3....8.1....7..6......4...29.8....5.51...9....4....... #211   1 Jelly - 11 Swords
...3..6......9...8..5..1.7.1....7.4....6..3......8...95.7....2.42...5....8....... #216   1 Jelly - 11 Swords
3.....9...7...1.5...2.....4....76.1....3.5....6.81....4.....2...5.6...8...9.....3 #103   1 Jelly - 10 Swords
..7..1...6...9.2...3.5.....9.....6.8.......3.....8..922...4...9..13......5...7... #072   1 Jelly -  9 Swords
9.......5.7.4...6...3...2...1.78........2.......1.6.7.2.....9...8...7.4...5.....3 #143   1 Jelly -  5 Swords
3.......5.7...8.6...2...9...1...6......82.......1.7.4...9...2...8.6...1.5.......3 #150   1 Jelly -  5 Swords
3....97...6..4......18.....5......93.....327.........8..4.1....2....7.5..8.6..... #181   1 Jelly -  5 Swords
5....63...2..8......97.....1......35.....546.........7..8.9....4....3.1..7.2..... #196   1 Jelly -  5 Swords
6.......2.9.8...7...1...4...3.9.7.......4.......35..9.4.....6...5...9.8...2.....1 #159   1 Jelly -  4 Swords
5.......7.8...9.3...4...2...1..36.......4.......1.8.6...2...4...9.3...1.7.......5 #189   1 Jelly -  4 Swords


Why is my post looking different than the preview? That's pathetic.
Last edited by Obi-Wahn on Tue Jan 08, 2008 8:46 am, edited 5 times in total.
User avatar
Obi-Wahn
 
Posts: 61
Joined: 05 January 2007
Location: Darmstadt, Germany

Postby tarek » Tue Jan 08, 2008 12:12 pm

JPF wrote:Thanks tarek
Easter Monster set up a new record of Sudoku Explainer 1.2.1 with ER=11.6 ?

Not sure if anyone rated puzzles with SE121 before. I'm not sure why the ratings have changed. It means that all puzzles rated with SE12 should be Re-rated with SE121 before making any comparisons. As we have so many SE ratings here and there, The best is probably to say that Easter-Monster has an SE121=11.6 or E121R=11.6, so that no one gets confused. The golden Nugget was #23 on the queue for Re-rating. I had to stop at #17. From the looks of it, I think this version is a bit faster because the list above was finished in 8 hours.

Obi-Wahn wrote:SE 11.6 for the Easter Monster? I thought the Golden Nugget set a new record with 11.5
The SE has been updated to a version 1.2.1 about a week ago. The ratings have changed with that update

The ratings with both versions are:
Code: Select all
Easter Monster  SE12=11.4  SE121=11.6
Golden Nugget   SE12=11.5  SE121=NOT DONE YET


Obi-Wahn wrote:here's the list of the tough nuts for my solver of your 363:
Thanks, I'll put the in my table to see if some info pops out. At the moment, it seems that every rating system has its own mind:(

tarek
User avatar
tarek
 
Posts: 2631
Joined: 05 January 2006

Postby RW » Tue Jan 08, 2008 1:35 pm

tarek wrote:Not sure if anyone rated puzzles with SE121 before. I'm not sure why the ratings have changed. It means that all puzzles rated with SE12 should be Re-rated with SE121 before making any comparisons.


Nicolas Juillerat wrote:Changed ratings for nested chains. Nesting level has now more impact on rating.
(Basically, this only adds 0.2 to the rating of the rare Sudokus with at least a "xxx Forcing Chain (+Multiple Forcing Chain)" and 0.4 to those with "xxx Forcing
Chain (+Dynamic Forcing Chain)".)

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby tarek » Tue Jan 08, 2008 2:14 pm

RW wrote:
tarek wrote:Not sure if anyone rated puzzles with SE121 before. I'm not sure why the ratings have changed. It means that all puzzles rated with SE12 should be Re-rated with SE121 before making any comparisons.


Nicolas Juillerat wrote:Changed ratings for nested chains. Nesting level has now more impact on rating.
(Basically, this only adds 0.2 to the rating of the rare Sudokus with at least a "xxx Forcing Chain (+Multiple Forcing Chain)" and 0.4 to those with "xxx Forcing
Chain (+Dynamic Forcing Chain)".)

RW

Aha, that's why:D .

The problem is how to know which puzzles have xxx Forcing Chain (+Multiple Forcing Chain) & which have xxx Forcing
Chain (+Dynamic Forcing Chain) without actually runnung them again in the program. Only a few puzzles on the forum have a full SE analysis of them, the rest have only the number:(

tarek
User avatar
tarek
 
Posts: 2631
Joined: 05 January 2006

Postby RW » Tue Jan 08, 2008 3:30 pm

tarek wrote:The problem is how to know which puzzles have xxx Forcing Chain (+Multiple Forcing Chain) & which have xxx Forcing
Chain (+Dynamic Forcing Chain) without actually runnung them again in the program. Only a few puzzles on the forum have a full SE analysis of them, the rest have only the number:(

I think the xxx Forcing chain (+Dynamic Forcing chains) can only be found at very high ratings. According to Eioru's list here, they started at 11.4 in SE 1.2 (I'm not sure where Eioru got those numbers from and I am sure that the numbers are not accurate). I am quite sure that all puzzles above ER 11.0 will require at least one xxx forcing chain (+multiple forcing chain), so all ERs above 10.9 should be raised with at least 0.2. Makes the whole rating business even more confusing if you ask me...

Isn't there anyone who has run batches of the hardest puzzles through ER and actually saved the result file? They usually contain all required data.

At the end of the post mentioned above you find this:
Code: Select all
#082   11.4    3.......4.8.2...7...6...5...1.9.8.......6.........7.2...5...6...9...1.8.4.......3   
57 x Hidden Single
2 x Direct Hidden Pair
1 x Naked Single
5 x Pointing
2 x Naked Pair
1 x X-Wing
3 x Hidden Pair
2 x Naked Triplet
1 x Swordfish
1 x XY-Wing
1 x BUG type 1
1 x Forcing X-Chain
1 x Bidirectional Cycle
8 x Forcing Chain
2 x Nishio Forcing Chains
14 x Region Forcing Chains
5 x Cell Forcing Chains
1 x Dynamic Cell Forcing Chains
7 x Dynamic Contradiction Forcing Chains
3 x Dynamic Region Forcing Chains
3 x Dynamic Contradiction Forcing Chains (+)
11 x Dynamic Contradiction Forcing Chains (+ Forcing Chains)
2 x Dynamic Region Forcing Chains (+ Forcing Chains)
5 x Dynamic Contradiction Forcing Chains (+ Multiple Forcing Chains)
2 x Dynamic Region Forcing Chains (+ Dynamic Forcing Chains)
4 x Dynamic Contradiction Forcing Chains (+ Dynamic Forcing Chains)

This one should now score 11.8.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby tarek » Tue Jan 08, 2008 3:53 pm

RW wrote:I am quite sure that all puzzles above ER 11.0 will require at least one xxx forcing chain (+multiple forcing chain), so all ERs above 10.9 should be raised with at least 0.2. Makes the whole rating business even more confusing if you ask me...

Why the increase though:?:

:idea:probably to Remove a .2 rating score overlap between puzzles that have "forcing chain (+multiple forcing chain)" & the ones that don't, so maybe there are 11.0 & 11.1 SE12 puzzles without xxx forcing chain (+multiple forcing chain). A similar overlap probably exists with "forcing chain (+dynamic forcing chain)" which would explain the .4 increase there.

I agree totally regarding the mess that this would create in this particular thread if we don't refer to the correct version of SE.

tarek
Last edited by tarek on Tue Jan 08, 2008 11:56 am, edited 1 time in total.
User avatar
tarek
 
Posts: 2631
Joined: 05 January 2006

Postby gsf » Tue Jan 08, 2008 3:54 pm

RW wrote:Isn't there anyone who has run batches of the hardest puzzles through ER and actually saved the result file? They usually contain all required data.

the hardest can bring a 2Ghz p4 to its knees for ~12hours
the SE rating for 2087 entries that were SE rated took 2w0d (1248277s) to compute @2GHz
the q1 rating for all 8152 took 3h1m (10871s)
doing a compute intensive app in java is unfortunate
a small consortium could recode the opensource SE in C quicker than re-rating 10K hard puzzles
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

PreviousNext

Return to General