A tough pattern ?

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

Postby ronk » Tue May 23, 2006 4:12 pm

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

Postby 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
    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

Postby Ocean » Tue May 23, 2006 10:43 pm

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:               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

Postby Havard » Wed May 24, 2006 6:02 pm

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

Postby 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

Postby tarek » Wed May 24, 2006 6:35 pm

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

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

Postby 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:(
ravel
 
Posts: 998
Joined: 21 February 2006

Postby gsf » Wed May 24, 2006 8:20 pm

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 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

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

Postby Ruud » Wed May 24, 2006 10:02 pm

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.

Thanks for your test results.

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby 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

Previous

Return to General