## A tough pattern ?

Everything about Sudoku that doesn't fit in one of the other sections
Havard wrote:With your point being that...?
While my point should be obvious, you may deduce another. But since we're discussing points, what is the point of quoting an entire post?
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

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
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
If this right, how does tabling fit into the solution?

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

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.
Thanks! Interesting stats. Still curious about which logical methods that crack the puzzles...
(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).

Ruud wrote:Here are the first 10 in my top50000 a.k.a. "Trials and Tabulations"
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:

Code: Select all
`Unsolved puzzles:               42897Solved 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 puzzlesSolves with 3 xy-chains/wings:   1238 puzzlesSolves with 4 xy-chains/wings:   1003 puzzlesSolves 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

ronk wrote:While my point should be obvious, you may deduce another. But since we're discussing points, what is the point of quoting an entire post?

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: 377
Joined: 25 December 2005

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

I agree that some ALS-requiring puzzles are tougher (I have some 15 node examples) than many implication chains....

tarek

tarek

Posts: 3537
Joined: 05 January 2006

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
ravel

Posts: 998
Joined: 21 February 2006

here are some results from my solver on ocean's and ruud's collections
Code: Select all
`notes on oceans's full symmetry minimal 20 clue 101178m45s 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-cycleswhere the solver was set to use the shortest cycle at each steplongest  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]7longest xy-cycle 23 edges       # 20401825 required guessing62 that required guessing had 1 basic constraint backdooraverage 16 basic constraint backdoors for puzzles requiring guessingall puzzles requiring guessing had singleton basic constraint backdoors`

Code: Select all
`notes on ruud's top5000048 min to check ~17 sec/Ghzall symmetries represented but horizontal and horizontal+vertical75 solved using basic constraints{ naked/hidden n-tuples, order n x-wing }:847   1891  5358  7890  11541 15193 17537 20494 24604 32014 35112881   2149  6402  8813  11890 15296 17780 20652 25661 32264 35436938   2405  6575  8876  12355 15350 17954 22074 27791 32852 36149991   3168  6776  9241  12853 15590 18830 22571 28830 33150 369571045  3275  6940  9378  13297 16245 18903 22755 31024 33525 377521085  4021  7061  10568 14270 17325 19425 23524 31213 347351220  5278  7291  10979 15113 17506 20346 24472 31290 35042   34 solved with x-cycles 9261 solved with y-cycles17353 solved with x-cycles + y-cycles-----26723 solved with basic constraints + { x-cycles y-cycles }219 required some fairly long x-cycles and y-cycleswhere the solver was set to use the shortest cycle at each step5 sec/puzzle/Ghz for these puzzleslongest  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]6longest xy-cycle 29 edges       # 1139323277 required guessing86 that required guessing had 1 basic constraint backdooraverage 17 basic constraint backdoors for puzzles requiring guessingall 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

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

I see that the top50000 needs a few replacements. I am rerating my collection now. As soon as it is finished, the list will be updated.

Ruud.
Ruud

Posts: 664
Joined: 28 October 2005

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

Previous