The New Sudoku Players' Forum

[denis_berthier]

Likewise, the record will show that rather than my rejecting everything that you write, I have called some of your work here and at Eureka 'brilliant if not ingenious'. I don't use those terms lightly. The problem is two-fold: First, you work is heavy on the theory and mathematical and relies totally on computer solver output for examples. That's not the problem- make no mistake, as I've said more than once, your methods are original and have value & obviously a number of people are interested in that subject, all the more power to you and to them.

Well, glad to hear it, especially after RW's insulting insinuations.
It's true that my global reference to Eureka, with no distinction between the different people there, may be unfair to some of them, including you.

The problem is that you often, directly or indirectly extrapolate your data to relate to human solving and make statements to the effect without anything to remotely prove that application, other than broad references to another forum. That is what I call you on, pure and simple.

You now have the precise references.
I never said that millions of people were using my rules. I said that they have been in use on the French forum ever since they were introduced there (not directly by me, because I didn't even know its existence, but by papyg) - which is enough to prove the only thing I ever claimed wrt to human solvers: my rules can be used by human solvers and they can be freely combined with other rules.

It is inconsistent to rail against someone who is merely asking you to meet the demands you make of others for examples, proof, precision and perfection ...

Did you meet my demand for a better example for SdC?
That's a case where you should consider a computer program as an aid for selecting better examples, that'd give your tutorials and graphics the full impact they deserve.

[DonM]

From Almost SdC thread:

What I'm criticising is your indirect claim (via a reference to Ruud) that Sue de Coq may be a more frequent pattern than it seems.
For such a claim, you should at least provide an example that can't be solved with elementary chains that anyone, human or computer, would have found before a Sue-de-Coq.

From above:

Did you meet my demand for a better example for SdC?
That's a case where you should consider a computer program as an aid for selecting better examples, that'd give your tutorials and graphics the full impact they deserve.

Let's be more specific. Am I meeting the demands that I'm expecting of you?

In my SdC thread, I raised the premise that SdC may be a more frequent pattern than people realize and I supported that with Ruud's computer study. The point here is that even with my qualified premise, I presented something more than my say-so. Even then, I admitted that 'Obviously, this is one study and doesn't prove the point, but it does raise the question.' and went on to point out the possible flaws that might limit the accuracy of Ruud's study. But considering how few studies people do like this, Ruud's study should at the very least raise interest and indicate the possibility of a great frequency of SdC than people may have thought.

However, the point of the SdC thread was never to prove to people the frequency of SdC patterns in the first place, it was to act as a refresher and foundation for the Almost SdC as a possible important addition to manual solving. I have now provided two in-depth threads with examples supporting that premise and will provide more as they come along. Those threads are challenging (for me) because when you put up examples of manual solving and are trying to be innovative, there are so many areas where errors in both the solution and the logic can occur and there are so many bright people on this forum that can find them.

Which brings me back to the point I have been making here. Computer solver examples are one thing, but when claims are made about human solving, examples of same have to be provided for reasons related to the point eleven made above. You may claim directly or indirectly that a method does not use a net or look-back or that it can solve puzzles of a certain difficulty level, but it isn't until others can manually dissect some examples that some or all of the human-solving related claims can be substantiated.

[Edit: I do appreciate the apology related to the broad statements relating to myself & Eureka.]

[RW]

They knew my rules much before I joined the French forum if only because papyg had explicitly introduced them to Sudoku-factory on 26 July 2007, much before I knew its existence.

From what I can see, they were posting similar solutions prior to that.

ONCE MORE, YOU'RE PROVIDING DELIBERATELY FALSE INFORMATION. TO KEEP FACTUAL, WHERE DO YOU SEE THAT?

You have a strange view of true and false... I said "From what I can see". I had asked you before to explain the difference between the solutions before the introduction of your rules and after, an explanation you failed to give. Not knowing what difference to look for, I could see no difference. So you can stop yelling "deliberately false". I did try to look for a thread were papyg had introduced your rules as you said, but it was a bit hard to find as it was in fact not introduced by that poster... Ah, finally:

All the factual information is available here:
http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=676&postdays=0&postorder=asc&start=0&sid=f39b18e1eb07730e40954bf983ea43f8

Then why didn't you post this link immediately? Would have saved both you and me a lot of time. To me it still seems like they are mostly adapting your terminology, the logic behind the elimination was known there in advance, as is suggested by some posters comparing the xyt-chain to other previously known chains that make the same elimination. But I'm not very fluent at French, so there might be some major revelation going on there...

Anyway, there is still a huge difference between actual solving and notating eliminations. I myself have often posted solutions in nice loop notation, yet I never think of strong or weak links while solving a puzzle. The notation using strong and weak links is only a translation of the logical deductions going on in my head. On the factory forums they seem to have a quite strictly defined notation that everybody uses, yet this does in no way imply that they are using similar techniques while looking for eliminations. In fact, this says nothing about what rules or logical foundations they base their solving on. Because of this, I still think your claims are not very solid. I agree with DonM, we would need to see some examples of how your advanced nxtlvl-whips can be applied manually, only then can we evaluate the true validity of your claims.

RW

[denis_berthier]

They knew my rules much before I joined the French forum if only because papyg had explicitly introduced them to Sudoku-factory on 26 July 2007, much before I knew its existence.

From what I can see, they were posting similar solutions prior to that.

ONCE MORE, YOU'RE PROVIDING DELIBERATELY FALSE INFORMATION. TO KEEP FACTUAL, WHERE DO YOU SEE THAT?

You have a strange view of true and false... I said "From what I can see".

OK, then tell us what you can see before that date and where.

why didn't you post this link immediately?

Ask your shrink.

[eleven]

why didn't you post this link immediately?

Ask your shrink.

I am just losing the last interest in whips.

[PIsaacson]

Regarding the frequency of Sue deCoq:

I have posted an analysis of various sudoku puzzle collections to determine the frequency/percentage occurrence.
Refer to http://forum.enjoysudoku.com/viewtopic.php?p=64402#p64402
In summary, SDCs occur in about 20% of all "harder" puzzles and for those 20% that contain SDCs, an SDC can promote to a solution about 40% of the time.
.

[denis_berthier]

Regarding the frequency of Sue deCoq:

I have posted an analysis of various sudoku puzzle collections to determine the frequency/percentage occurrence.
Refer to http://forum.enjoysudoku.com/viewtopic.php?p=64402#p64402
In summary, SDCs occur in about 20% of all "harder" puzzles and for those 20% that contain SDCs, an SDC can promote to a solution about 40% of the time.
.

OK, but most SdC are subsumed by much simpler NLs. So you should put NLs of the same length before SdC in your analysis.

[eleven]

OK, but most SdC are subsumed by much simpler NLs.

If with simpler NL you mean e.g. a w-wing, i agree. If you mean a 5-cell bilocation chain, i dont.

Any fixed technique hierarchy is problematic and statistics based on that will always give a biased result.

When do i look for SdC's ? Mainly when there are many candidates and only a few bivalue cells. In this case i can verify in a minute, if SdC's with a bivalue cell in the line are there. But it would take me at least 10 times longer to find all 5-cell NL's (i dont even have a non-stupid technique to find them systematically, so i never try it).

In a grid with many bivalue cells later i never would look for SdC's, because both the chances are low to find one and the chances for other techniques to be applicable are much higher.

[PIsaacson]

Denis,

My solver normally employs a self-adjusting heuristic on a set of puzzles to select an optimal solution path by re-arranging the execution order of the various methods that I've programmed. I had to override that for the SDC counting because on my first attempt, the solver never (and I mean not a single time!) opted to use SDC. Instead it selected either nrczt-whips or ALS chains with about a 60/40 split depending on the SER level.

Harder puzzles tended to favor nrczt-whips. Easier puzzles tended to favor ALS chains. I'm still looking at those statistics to see why, but it looks like the ALS chains were either faster or easier to locate as the SER level dropped. I always pre-process puzzle sets and sort them by SER level, so I'm looking at where my solver starts to "stutter" and eventually switches from nrczt-braids to ALS chains.

Anyway, the point was to count SDCs, so I deliberately omitted any methods other than those associated with SSTS and SDC/DDS. I even had to "dumb down" the X-cycles/X-coloring to agree with the coloring technique used in Simple Sudoku. The results are "interesting". I've been studying subset counting theory, and hence SDC and DDS, for the past year along with your nrczt chains/whips/braids. From a computer solver POV, both are advanced techniques. From a human solver POV (at least mine) ALSs and thus SDCs are "easier" to spot than nrczt-chains simply because the online sudoku assistants don't make it easy to track/visualize chains. But they all can highlight bi-value cells, and this makes it relatively easy to find SDCs using DonM's technique.

Meanwhile back to nrczt-braids... The gsf8152 braid analysis is taking forever! I'm averaging an hour per puzzle, so don't expect any results for about a year... I've got to improve the algorithm by an order of magnitude. It's spending too much time following non-productive branches, but I can't figure out how to prune the tree effectively/efficiently. Linking to ANY prior RLC is simple in concept, but a nightmare in practice.

[denis_berthier]

The gsf8152 braid analysis is taking forever! I'm averaging an hour per puzzle, so don't expect any results for about a year... I've got to improve the algorithm by an order of magnitude. It's spending too much time following non-productive branches, but I can't figure out how to prune the tree effectively/efficiently. Linking to ANY prior RLC is simple in concept, but a nightmare in practice.

I guess you're speaking of the non-T&E implementation.
I've introduced the rules for short braids in SudoRules; it took me a few hours (with testing), using a straightforward, but very inefficient, modification of the rules for whips.
I meet the same efficiency problem as you: I don't know how to avoid useless branches and memory overflow. Moreover, I have very little time for Sudoku, and probably almost no time at all next year, so don't know if I'll ever program longer braids.

But, using the equivalence with T&E and the easy T&E implementation, we can nevertheless get interesting results about generating families.

[denis_berthier]

Paul, eleven,

About SdC, it'd be better to have this discussion in the SdC thread (my fault: I didn't answer at the right place).

[denis_berthier]

My solver normally employs a self-adjusting heuristic on a set of puzzles to select an optimal solution path by re-arranging the execution order of the various methods that I've programmed.
...
Harder puzzles tended to favor nrczt-whips. Easier puzzles tended to favor ALS chains. I'm still looking at those statistics to see why, but it looks like the ALS chains were either faster or easier to locate as the SER level dropped. I always pre-process puzzle sets and sort them by SER level, so I'm looking at where my solver starts to "stutter" and eventually switches from nrczt-braids to ALS chains.

You mean nrczt-whips?

In spite of the very different sets of rules on which they are based, the global correlation coefficient between the SER and the NRCZT ratings is high: 0.89 (see here http://forum.enjoysudoku.com/viewtopic.php?t=5995&postdays=0&postorder=asc&start=0). It can be partly, and only partly, understood by the fact that the length of chains is the main parameter for both.

One thing that may be relevant here: how does the SER rating (and how does your algorithm) take into account the maximum size of the ALS? As the number of ALS may increase exponentially with their size and the number of chains built on them may also increase exponentially with their length (as chains), this (potential) double exponential factor for the number of ALS-chains may be an explanation. But I agree that more investigation is needed.

[PIsaacson]

Dear Denis,

You mean nrczt-whips?

You're absolutely correct. It was nrczt-whips, not braids. I've spent so much time lately on nrczt-braids that it's burned into my brain.

Regarding exponential run times for increasing ALS size:

If I don't override it, my solver's heuristic dispatcher gradually increases the ALS set size maximum starting from 2 and adding 1 (or subtracting 1) depending on the efficacy over the last N puzzles. ALS chaining for set sizes up to 6 candidates is in the 400-500 msec range. After that, it goes bad fast. 7 candidate ALSs take about 5 seconds. 8 candidates are usually in the minutes and 9 candidates are typically measured in hours.

Regarding the SDC tests that allowed nrczt-whips and ALS-chains but failed to locate a single SDC:

I did not attempt to locate SDC cores with more than 6 candidates, so the ALS maximum set size was constrained to 6. I'm looking at my defaults for the maximum nrczt-whip (currently 10) and the default maximum ALS (currently 6) to see if these are reasonable. The heuristic dispatcher "obeys" these limits, but perhaps I should let it be unbounded and rely on it's ability to interrupt a too-long-running method to throttle back the maximums. When I find time, I'll try that and see if the higher level SER puzzles still favor nrczt-whips and the lower SER puzzles still favor ALS-chains.

I definitely need better tracing of the heuristic's decision making process. My current logs contain nothing other than it decided nrczt-whips were faster/better than ALS-chains, then changed its mind as the SER level dropped below 8 and ALS-chains became favored.

Regarding gsf8152 nrczt-braids vs nrczt-T&E:

Whew... 8152 puzzles at 1 hour each was not looking feasible. Windows XP can't stay up for more than a week without some lock-up and forced re-boot. I'll setup the T&E runs.

Regarding almost no time next year:

That hurts... Can I still ask you an occasional question on braids?

Cheers,
Paul

[denis_berthier]

Regarding gsf8152 nrczt-braids vs nrczt-T&E:
Whew... 8152 puzzles at 1 hour each was not looking feasible. Windows XP can't stay up for more than a week without some lock-up and forced re-boot. I'll setup the T&E runs.

I didn't know about XP. A little free ad for Apple: my Mac is turned off only for system updates or when I leave for a long time.
Contrary to SudoRules, in which I have used a few optimisation techniques in the rules (only a few, because I didn't want to limit the possibilities of changing the resolution strategies), my T&E procedure is not optimised at all. Some of the T&E computations for the tables in the above posts took more than a week.

Regarding almost no time next year: That hurts... Can I still ask you an occasional question on braids?

I have no new idea about Sudoku and it's therefore time for me to start a new research project. But I'll keep some eye on Sudoku. We can still talk of braids and the rest.

[999_Springs]

I would like to ask a question relating to #2 of the top1465 (this was on page 4 of this thread before all those incomprehensible verbose discussions).

After my first chain move and the pair, single and locked candidate:

Code: Select all

 *--------------------------------------------------------------------------*
 | 7      126    8        | 459    4569   4569     | 3      1456   1259     |
 | 469    36     469      | 2      34569  1        | 4679   45678  5789     |
 | 5      1236   12469    | 78     3469   78       | 12469  146    129      |
 |------------------------+------------------------+------------------------|
 | 189    4      1579     | 3579   59     3579     | 178    2      6        |
 | 3      126    1269     | 479    8      2469     | 147    1457   157      |
 | 268    57     2567     | 1      2456   24567    | 478    9      3        |
 |------------------------+------------------------+------------------------|
 | 12     9      12357    | 6      125    2358     | 127    1378   4        |
 | 1246   8      12346    | 349    7      2349     | 5      136    129      |
 | 1246   57     1234567  | 34589  12459  234589   | 12679  13678  12789    |
 *--------------------------------------------------------------------------*

The simplest puzzle-cracking move here appears to be ttt's second move - a short loop. However, I think that you can express this loop as some sort of almost-locked set doubly-linked with an almost-hidden set:
ALS: 1257r7c157
AHS: 578r2c5789
restricted common: 5 and 7
eliminations: r1469c5<>5, r4569c7<>7, r7c368<>12, r2c8<>46, r2c9<>9

I am not very familiar with almost-hidden sets, so could someone please tell me whether this is how they work, and how useful they are?