While my point should be obvious, you may deduce another.Havard wrote:With your point being that...?
But since we're discussing points, what is the point of quoting an entire post?A tough pattern ?
33 posts
• Page 2 of 3 • 1, 2, 3
by Ruud » Tue May 23, 2006 6:00 pm
Mike Barker wrote:Could you provide a link to what you mean by "tabling"? It seems that #2 cracks with nothing more than an ALS-xy rule and a finned X-wing:Hidden Single: r3c9 => r3c9=6,r3c156<>6
If this right, how does tabling fit into the solution?
Hidden Single: r5c9 => r5c9=2,r4c8<>2,r5c46<>2
Locked Column: r45c1 => r7c1<>1
Locked Column: r45c3 => r2c3<>7
Locked Column: r89c3 => r2c3<>4
Locked Column: r89c3 => r2c3<>6
Locked Column: r12c7 => r8c7<>1
Locked Column: r56c7 => r8c7<>8
Locked Column Box: r2345c7|r234c8 => r8c7<>7,r78c8<>7
Hidden Column Pair: r89c3 => r8c3=46,r9c3=46
Naked Row Triple: r9c349 => r9c2<>1,r9c6<>16
ALS xy-rule with B=1 cells: r4c378-4-r6c9-5-r8c79|r79c9 => r56c7<>3
Locked Row: r4c78 => r4c156<>3
Naked Single: r4c1 => r4c56<>1,r5c1<>1
Row X-Wing Fillet-o-Fish: r5c16|r9c26 => r7c1<>3
The Solution is completed with singles
I have not yet implemented ALS in my solver. It's on the top of my wishlist, though...
Tabling is my implementation of "Trebor's Tables" developed by Robert Woodhead (Mad Overlord), Nick70 & Doug Bowman. Here is a link to the thread in the programmers forum: http://www.setbb.com/sudoku/viewtopic.php?t=126 I also added this link to my solving technique index.
Ruud.
- Ruud
- Posts: 664
- Joined: 28 October 2005
by Ocean » Tue May 23, 2006 10:43 pm
Thanks! Interesting stats. Still curious about which logical methods that crack the puzzles...ravel wrote:Ocean, i have scanned now the whole list with this 20 clue pattern. Nearly all are rather tough, numbers 40, 75 and 126 needed 4 steps.
(I also have another 2000 puzzles with the same pattern that do not 'solve', but where the solver has some progress. Also 600 puzzles that solve with basic methods, plus 150 extra that solve with xy-chains).
I run Ruud's top50000 through my logical solver - which contains most but not all basic methods (does not catch swordfish or coloring), in addition to xy-chain. Result is:Ruud wrote:Here are the first 10 in my top50000 a.k.a. "Trials and Tabulations"
- Code: Select all
Unsolved puzzles: 42897
Solved with basic methods only: 73 puzzles (First 3: #847, #881, #938)
Basics + one xy-wing: 8 puzzles (First 3: #10791, #19373, #28277)
Solves with 1 xy-chain: 1573 puzzles (First: #102)
Solves with 2 xy-chains/wings: 1463 puzzles
Solves with 3 xy-chains/wings: 1238 puzzles
Solves with 4 xy-chains/wings: 1003 puzzles
Solves with >4 xy-chains/wings: 1745 puzzles
(Total solved puzzles: 7103)
Tried to find a common factor for the 73 puzzles that solve with basics only. Most of them solve with either hidden pairs or triples, (70 puzzles, one of them needed x-wing also). Two of the three left were solved with an x-wing, while one puzzle (#19425) solved with naked pairs + locked candidates only.
- Ocean
- Posts: 442
- Joined: 29 August 2005
by Havard » Wed May 24, 2006 6:02 pm
ronk wrote:While my point should be obvious, you may deduce another.
I'm sure that I am just a bit slow, but sometimes I can't understand you ronk...
I did not understand what your point about the ALS was? Could you explain to a slow norwegian?Havard
- Havard
- Posts: 378
- Joined: 25 December 2005
by ronk » Wed May 24, 2006 6:22 pm
Havard wrote:I did not understand what your point about the ALS was ...
Only that I think it's too soon to remove puzzles that require ALS ... at least those that require the ALS xy-rule ... from lists of difficult puzzles.
- ronk
- 2012 Supporter
- Posts: 4764
- Joined: 02 November 2005
- Location: Southeastern USA
by ravel » Wed May 24, 2006 6:46 pm
After making some changes in my program, both Oceans and Ruuds puzzles, also RW's and Emily's friend's only need 3 steps, Ruuds 10th only 2 steps (r1c1<>4, r4c9<>3).
But it is too slow now for the hardest puzzles or longer lists of puzzles
But it is too slow now for the hardest puzzles or longer lists of puzzles
- ravel
- Posts: 998
- Joined: 21 February 2006
by gsf » Wed May 24, 2006 8:20 pm
here are some results from my solver on ocean's and ruud's collections
I'll post results on gfroyle's 22M 18's when they finish (~2 days crunching)
- Code: Select all
notes on oceans's full symmetry minimal 20 clue 10117
8m45s to check ~19 sec/Ghz
6017 solved using basic constraints { naked/hidden n-tuples, order n x-wing }
257 solved with x-cycles
1101 solved with y-cycles
917 solved with x-cycles + y-cycles
----
8292 solved with basic constraints + { x-cycles y-cycles }
17 required some fairly long x-cycles and y-cycles
where the solver was set to use the shortest cycle at each step
longest x-cycle 9 edges # 2040
[54]-[51][31][33][73][79][98]-[16][24]-
longest y-cycle 18 edges # 8393
[75]7[95]1[93]7[23]9[27]6[57]2[53]6[41]2[31]6[32]2[52]8
[51]9[42]7[49]9[79]2[72]9[71]7[75]7
longest xy-cycle 23 edges # 2040
1825 required guessing
62 that required guessing had 1 basic constraint backdoor
average 16 basic constraint backdoors for puzzles requiring guessing
all puzzles requiring guessing had singleton basic constraint backdoors
- Code: Select all
notes on ruud's top50000
48 min to check ~17 sec/Ghz
all symmetries represented but horizontal and horizontal+vertical
75 solved using basic constraints
{ naked/hidden n-tuples, order n x-wing }:
847 1891 5358 7890 11541 15193 17537 20494 24604 32014 35112
881 2149 6402 8813 11890 15296 17780 20652 25661 32264 35436
938 2405 6575 8876 12355 15350 17954 22074 27791 32852 36149
991 3168 6776 9241 12853 15590 18830 22571 28830 33150 36957
1045 3275 6940 9378 13297 16245 18903 22755 31024 33525 37752
1085 4021 7061 10568 14270 17325 19425 23524 31213 34735
1220 5278 7291 10979 15113 17506 20346 24472 31290 35042
34 solved with x-cycles
9261 solved with y-cycles
17353 solved with x-cycles + y-cycles
-----
26723 solved with basic constraints + { x-cycles y-cycles }
219 required some fairly long x-cycles and y-cycles
where the solver was set to use the shortest cycle at each step
5 sec/puzzle/Ghz for these puzzles
longest x-cycle 11 edges # 18914
[53]-[93][95]-[25][24]-[51][71][78][68]-[47][43]-
longest y-cycle 23 edges # 5695
[28]1[38]6[34]1[54]4[56]3[36]4[16]8[17]7[15]2[65]7[64]5[46]2
[41]5[61]3[69]8[29]4[79]9[89]3[82]9[72]8[32]7[23]8[28]6
longest xy-cycle 29 edges # 11393
23277 required guessing
86 that required guessing had 1 basic constraint backdoor
average 17 basic constraint backdoors for puzzles requiring guessing
all puzzles requiring guessing had singleton basic constraint backdoors
I'll post results on gfroyle's 22M 18's when they finish (~2 days crunching)
- gsf
- 2014 Supporter
- Posts: 7306
- Joined: 21 September 2005
- Location: NJ USA
by RW » Wed May 24, 2006 9:04 pm
ravel wrote:After making some changes in my program, both Oceans and Ruuds puzzles, also RW's and Emily's friend's only need 3 steps, Ruuds 10th only 2 steps (r1c1<>4, r4c9<>3).
Interesting, was it a change that introduced a new technique, or did you just optimize the search for short solutions? I'd also be interested to know how your program handles scrambled versions of the same puzzle. If it could find the shortest path to a "simple" solution, then the scrambling wouldn't affect the outcome. What's the verdict for these 5 different versions of gfroyle's beauty?
- Code: Select all
9....8.....12...5..6..7..........8....41...6.........9.7..9....8....3.....25...1.
....2..9...8..71.....4....5....6..2...1..87.....9....44..........6..38...9.......
...2......5...3.7.....4....3.....1....4.....2.7...9.8..8...7.9...2.....61.....4..
8....64...5.1.......9.7....6....43..........7.......5...3.9.....7.5.....4....82..
........4..2.6.5.........3..4.9.......6.1.2..7....3.....1.2.8...9.5.....3....4...
Original puzzle:
6.......3.7..8..9...2...5.....3......8..1..7......2.....5...1...9..4..8.3.......2
Sudocue solves these with 9, 10, 15, 21 and 26 tabling steps (21 steps for the original puzzle).
[Edit: and here's one more version of the same puzzle that requires 36 tabling steps:
- Code: Select all
.....5....6.9....2....1.....4.8....6..7....9.5.....1...2.6....43.....5....1....7.
RW
- RW
- 2010 Supporter
- Posts: 1010
- Joined: 16 March 2006
by ravel » Thu May 25, 2006 5:19 pm
RW wrote:Interesting, was it a change that introduced a new technique, or did you just optimize the search for short solutions? I'd also be interested to know how your program handles scrambled versions of the same puzzle.
No, no new technique, i dont have much time to improve the program.
It is a simple and time consuming algorithm. When it gets stuck with the few basic techniques, it goes through the remaining candidates, sets it to the cell and looks, if a contradiction arises with the same techniques (or it gets stuck again). From those, which can be eliminated, i greedily choose the (first) one, that proceeds the puzzle most, i.e. after eliminating it, the largest number of other candidates can be eliminated too.
In the current version i try this starting from each of the candidates, that can be eliminated after getting stuck the first time, but it would take me hours to check one of the hardest puzzles this way and it is completely impossible to try all orders of feasible eliminations.
Scrumbling the puzzle will change the result, because often there are more than one candidates, that lead to the same progress of eliminations. In the older version i also tried it starting with the last cell and got an improvement from 12 to 10 steps for one puzzle.
BTW, it seems that i read the trace wrong yesterday, yours and one of Ocean are still in the 4-step list.
- ravel
- Posts: 998
- Joined: 21 February 2006
Re:
by denis_berthier » Mon Mar 01, 2021 9:35 am
I fell upon this old collection of fishes and I wondered what modern techniques would give.
This puzzle is rated SER 8.5, which is hard but far from hardest by modern standards. As expected, it solves with chains, though a large number of them. Although whips are activated in the solution below, their full power is never needed: the z- and t- candidates appear only in different patterns (z-chains and t-whips)
Ruud wrote:#9 is the toughest. 33 tabling steps for SudoCue.
Ruud.
This puzzle is rated SER 8.5, which is hard but far from hardest by modern standards. As expected, it solves with chains, though a large number of them. Although whips are activated in the solution below, their full power is never needed: the z- and t- candidates appear only in different patterns (z-chains and t-whips)
SudoRules solution: Show
- denis_berthier
- 2010 Supporter
- Posts: 4212
- Joined: 19 June 2007
- Location: Paris
Re: Re:
by m_b_metcalf » Mon Mar 01, 2021 10:07 am
denis_berthier wrote:I fell upon this old collection of fishes and I wondered what modern techniques would give.
Here's a selection of ratings from SE (although it's not quite 'modern'). All 411 start with a swordfish.
- Code: Select all
3.8/3.8/3.8 254
7.1/7.1/3.8 95
7.2/7.2/3.8 37
7.3/7.3/3.8 259
7.8/7.2/3.8 215
8.3/8.3/3.8 229
8.4/8.4/3.8 194
8.5/8.5/3.8 241
8.8/8.5/3.8 7
8.9/8.9/3.8 273
9.0/9.0/3.8 329
9.1/9.1/3.8 64
9.2/8.3/3.8 110
The hardest in ruud's top ten is
- Code: Select all
9.2/1.2/1.2 7
-
m_b_metcalf - 2017 Supporter
- Posts: 13622
- Joined: 15 May 2006
- Location: Berlin
Re: A tough pattern ?
by urhegyi » Mon Mar 01, 2021 11:59 am
I have rated them all:
Hidden Text: Show
- urhegyi
- Posts: 748
- Joined: 13 April 2020
Re: A tough pattern ?
by denis_berthier » Mon Mar 01, 2021 3:18 pm
I've tried only the hardest of each of the two collections:
Ocean's #110, SER 9.2, is in W12
Ruud's #10, SER 8.5, is in W6
Ocean's #110, SER 9.2, is in W12
Ruud's #10, SER 8.5, is in W6
- denis_berthier
- 2010 Supporter
- Posts: 4212
- Joined: 19 June 2007
- Location: Paris
33 posts
• Page 2 of 3 • 1, 2, 3
