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?Havard wrote:With your point being that...?

26 posts
• Page **2** of **2** • 1, **2**

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

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

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

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

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:**1000**Joined:**16 March 2006

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

26 posts
• Page **2** of **2** • 1, **2**