The hardest sudokus (new thread)

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

Re: The hardest sudokus (new thread)

Postby marek stefanik » Thu Aug 31, 2023 4:47 am

Denis, I should have been more concrete in what I was replying to.
In your post here, you mention the length of chains necessary to solve some of the puzzles in the database after direct eliminations from TH. As (I think) we all agree, for a solver familiar with TH, the chains are the harder part. You are arguing that the puzzle is not easy, while the others argue that it is not among the hardest. Aren't there puzzles that require T&E(2) or puzzles in T&E(1) requiring nets over 40 strong links long where no one has found a bypass with exotic patterns?

Just a couple posts above, Eleven specifically mentioned 10.0 (assuming SER or a similar rating) as a boundary. If I remember, T&E(1) puzzles should top out at 9.5, i.e. a puzzle which after applying TH requires chains/nets of length 8 is nowhere near a puzzle which remains above 10.0 after TH (you also seem to not understand what 'remains' means in this context, it means that the grid state after applying specified eliminations, here direct TH eliminations, is rated instead of the original puzzle and the rating acquired as such is considered; either that or you just don't accept that such a rating can be of interest, in which case I am telling you: It is of interest to us).

Marek
marek stefanik
 
Posts: 359
Joined: 05 May 2021

Re: The hardest sudokus (new thread)

Postby champagne » Thu Aug 31, 2023 5:53 am

mith wrote:Out of curiosity, I did a quick check of all the 11.9s against YZF.

I believe all the known TH-based 11.9s have TH-1 available, and reduce to SER 7.2, 7.8, or 8.3. There is no particular reason (that I am aware of) to expect all TH 11.9s would have this property, though it does seem the current 11.8+ in the te3 database have fewer guardians on average than the 11.7s.

The ph2010 11.9s:

eleven;Patience - MSLS 16 -> SER 9.0
OW;2015_08 - MSLS 16 -> SER 9.2
eleven;Second flush - Weak Exocet -> SER 10.6
dob;12_12_03 - JExocet -> SER 10.8

eleven-Imam_bayildi - JExocet -> SER 11.8
eleven-Kolk - JExocet -> SER 11.8
tarek-Golden_Nugget - JExocet -> SER 11.8
GP-kz0 - JExocet -> SER 11.8
GP-champagne dry - JExocet -> SER 11.8

Clearly some of these are still very hard by this standard (though again this is only taking into account techniques supported by YZF, and I'm not even sure I have the latest version; it's not using the almost SK-Loop in Kolk that Marek mentions, for example).


Hi mith,

I had in mind that several puzzles having the JE were still very hard after.
A small remark, more eliminations were found in some of them applying the "abi loop". An example of additional solving rules not in SER.

But I will agree that the "abi loop" has been more efficient with JE of three digits, solving then in most cases the entire JE pattern.
champagne
2017 Supporter
 
Posts: 7455
Joined: 02 August 2007
Location: France Brittany

Re: The hardest sudokus (new thread)

Postby denis_berthier » Thu Aug 31, 2023 6:16 am

marek stefanik wrote:In your post here, you mention the length of chains necessary to solve some of the puzzles in the database after direct eliminations from TH. As (I think) we all agree, for a solver familiar with TH, the chains are the harder part. You are arguing that the puzzle is not easy, while the others argue that it is not among the hardest. Aren't there puzzles that require T&E(2) or puzzles in T&E(1) requiring nets over 40 strong links long where no one has found a bypass with exotic patterns?

For the T&E(3) database, the referenced results show precisely what can be expected for each number of guardians and each chain length. They also show that there remains puzzles not solved by the largest numbers considered in the tables.
Unlike champagne, I'm not a seasoned practitioner of crystal balls; at this point, there's nothing I can say beyond the above. The results don't justify any serious conjecture about puzzles remaining in T&E(2) or not after longer chains are applied. But they clearly show it would be totally arbitrary to exclude some puzzles from the database, because there's no justification for any specific boundary.


marek stefanik wrote:Just a couple posts above, Eleven specifically mentioned 10.0 (assuming SER or a similar rating) as a boundary.
If I remember, T&E(1) puzzles should top out at 9.5,

9.5 is quite exceptional. The fuzzy boundary is closer to 9.3.


marek stefanik wrote:i.e. a puzzle which after applying TH requires chains/nets of length 8 is nowhere near a puzzle which remains above 10.0 after TH (you also seem to not understand what 'remains' means in this context, it means that the grid state after applying specified eliminations, here direct TH eliminations, is rated instead of the original puzzle and the rating acquired as such is considered; either that or you just don't accept that such a rating can be of interest, in which case I am telling you: It is of interest to us).

You're confusing everything. We're talking about what should be in the databases.
What remains of a puzzle after applying some rules is another topic. I didn't say it's not interesting. I said it doesn't pertain to the discussion about the contents of the databases. It is totally inconsistent of champagne to say that some puzzles shouldn't be in the SER-hardest database while he has been keeping them in it for years.

The idea of what remains after direct tridagon eliminations applies only to the single guardian case. For more guardians, ordinary chains and tridagon-based ORk-chains have to be intertwined in the resolution path in order to reach their full resolution power.
As the single guardian case is only the assertion of one more clue, it shouldn't be too difficult to add this clue and apply SER to it, if you want an answer to your question for specific puzzles in this particular case.
.
denis_berthier
2010 Supporter
 
Posts: 4213
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby champagne » Thu Aug 31, 2023 6:31 am

denis_berthier wrote:It is totally inconsistent of champagne to say that some puzzles shouldn't be in the SER-hardest database while he has been keeping them in it for years.


As usual, bad words are back...

I never wrote that some puzzles should'nt be in the SER data base, but that some puzzles in the data base can not be "the hardest sudokus".
The data base is a collection of puzzles having a high SER. It has been used to find new exotic patterns and to analyze the different families of such patterns. And as I wrote recently, the redundancy control is enough to be forced to keep them in the data base.
champagne
2017 Supporter
 
Posts: 7455
Joined: 02 August 2007
Location: France Brittany

Re: The hardest sudokus (new thread)

Postby denis_berthier » Thu Aug 31, 2023 6:44 am

champagne wrote:
denis_berthier wrote:It is totally inconsistent of champagne to say that some puzzles shouldn't be in the SER-hardest database while he has been keeping them in it for years.

I never wrote that some puzzles should'nt be in the SER data base, but that some puzzles in the data base can not be "the hardest sudokus".
The data base is a collection of puzzles having a high SER. It has been used to find new exotic patterns and to analyze the different families of such patterns.

Great. So, the debate is closed. The ph database is indeed the SER-hardest database. That's all I need to know in order to be able to do something with it.
.
denis_berthier
2010 Supporter
 
Posts: 4213
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby totuan » Thu Aug 31, 2023 12:47 pm

mith wrote:There are certainly puzzles in the te3 database which retain their SER after applications of TOFCs. This one is "only" an 11.0, just one I happened to have saved to look at more closely (specifically, it has guardians in all four boxes, exactly the cells of the 4-cycle in the TH pattern):
Code: Select all
........1..2..134...3.452.6...16.......2.3..523.........1....64.7.5.....89.4.....  ED=11.0/1.2/1.2; minimal of min-expand ID 89616

As reference:
On brief - my attack for this one:
Hidden Text: Show
Code: Select all
 *-----------------------------------------------------------------------------*
 | 4679    468    *789+46  | 36789   23789  *789+2   |*789+5   5789    1       |
 | 5679    568     2       | 6789   *789     1       | 3       4      *789     |
 | 179     18      3       |*789     4       5       | 2      *789     6       |
 |-------------------------+-------------------------+-------------------------|
 | 4579    458    *789+45  | 1       6       789-4   |*789+4   23      23      |
 | 14679   1468   *789+46  | 2      *789     3       | 46789  *789     5       |
 | 2       3       46789#  |*789#    5      *789+4   | 146789  1789   *789#    |
 |-------------------------+-------------------------+-------------------------|
 | 35      2       1       | 3789    3789    789     | 5789    6       4       |
 | 346     7      %46      | 5       12389   2689    | 189     12389   2389    |
 | 8       9      %56      | 4       1237    267     | 157     12357   237     |
 *-----------------------------------------------------------------------------*

01: Impossible pattern(789) * marked cells:
All guardians (except 4r4c7 & 4r6c6) lead to 46r89c3 => r6c3<>46 => triple(789)r6c349 => 4r6c6 => r4c6<>4, r6c6=4

Code: Select all
 *---------------------------------------------------------------------*
 | 4679   468   *789+46 | 36789  23789 *789+2  |*789+5   5789   1      |
 | 5679   58     2      | 6789  *789    1      | 3       4     *789    |
 | 179    18     3      |*789    4      5      | 2      *789    6      |
 |----------------------+----------------------+-----------------------|
 | 4579   458   *789+45 | 1      6     *789    | 4789    23     23     |
 | 14679  1468   789-46 | 2     *789    3      |*789+46 *789    5      |
 | 2      3    A*789+6  |*789    5      4      | 16789   1789  *789    |
 |----------------------+----------------------+-----------------------|
 | 35     2      1      | 3789   3789   789    | 5789    6      4      |
 | 346    7     %46     | 5      12389  2689   | 189     12389  2389   |
 | 8      9     %56     | 4      1237   267    | 157     12357  237    |
 *---------------------------------------------------------------------*

02: Impossible pattern(789) * marked cells:
- All guardians (except 4r5c7) lead to 46r89c3 => r5c3<>46
- In case: 4r5c7 => r4c7<>5 => tridagon => 25r1c67 lead to 46r89c3 => r5c3<>46


Code: Select all
 *--------------------------------------------------------------------*
 | 4679   468    789-46 | 36789  23789 *789+2  |*789+5  5789   1      |
 | 5679   568    2      | 6789  *789    1      | 3      4     *789    |
 | 179    18     3      |*789    4      5      | 2     *789    6      |
 |----------------------+----------------------+----------------------|
 | 4579   458    5789-4 | 1      6     *789    |*789+4  23     23     |
 | 146    146    789    | 2     *789    3      |%46    *789    5      |
 | 2      3     #6789   |*789A   5      4      | 16789  1789  *789    |
 |----------------------+----------------------+----------------------|
 | 35     2      1      | 3789   3789   789    | 5789   6      4      |
 | 346    7     #46     | 5      12389  2689   | 189    12389  2389   |
 | 8      9     #56     | 4      1237   267    | 157    12357  237    |
 *--------------------------------------------------------------------*

03: Tridagon(789) * marked cells => All guardians lead to 46r689c3 => r14c3<>46, r8c3=4 and ER-9.6

Code: Select all
 *---------------------------------------------------------------------*
 | 4679   468   *789    | 36789  23789 *789+2  |*789+5   5789   1      |
 | 5679   568    2      | 6789  *789    1      | 3       4     *789    |
 | 179    18     3      |*789    4      5      | 2      *789    6      |
 |----------------------+----------------------+-----------------------|
 | 4579   458   *789+5  | 1      6     *789    | 4789    23     23     |
 | 146    146   *789    | 2     *789    3      | 46     *789    5      |
 | 2      3      6789   |*789A   5      4      |*1789+6 *1789  *789    |
 |----------------------+----------------------+-----------------------|
 | 35     2      1      | 3789   3789   789    | 5789    6      4      |
 | 36     7      4      | 5      12389  2689   | 189     12389  2389   |
 | 8      9      6-5    | 4      1237   267    | 157     12357  237    |
 *---------------------------------------------------------------------*

04: Impossible pattern(789) * marked cells - like twin:
All guardians lead to 6r9c3, some singles and ER-9.2

Code: Select all
*---------------------------------------------------------------------*
 | 4679   468   *789A   | 36789  3789-2 *789+2  | 5789   5789   1      |
 | 679    5      2      | 6789  *789     1      | 3      4     *789    |
 | 179    18     3      |*789    4       5      | 2     *789    6      |
 |----------------------+-----------------------+----------------------|
 | 479    48     5      | 1      6      *789    |*789    23     23     |
 | 16     16    *789    | 2     *789     3      | 4     *789    5      |
 | 2      3     *789    |*789    5       4      | 6      1     *789    |
 |----------------------+-----------------------+----------------------|
 | 5      2      1      |*789+3  3789   *789    |*789    6      4      |
 | 3      7      4      | 5      1289    6      | 189    289    289    |
 | 8      9      6      | 4      127     27     | 157    2357   237    |
 *---------------------------------------------------------------------*

05: Impossible pattern(789) * marked cells (3 band)
All guardians lead to 2r1c6 => r1c6=2, some singles and ER-6.6

Thanks for the puzzle!
totuan
totuan
 
Posts: 240
Joined: 25 May 2010
Location: vietnam

Re: The hardest sudokus (new thread)

Postby eleven » Thu Aug 31, 2023 4:34 pm

Nice !

denis_berthier wrote:Great. So, the debate is closed. The ph database is indeed the SER-hardest database.

Not anymore. You would have to combine it with the TH database, which includes a lot of simple to solve puzzles. That's the problem.
eleven
 
Posts: 3151
Joined: 10 February 2008

Re: The hardest sudokus (new thread)

Postby denis_berthier » Thu Aug 31, 2023 4:58 pm

eleven wrote:Nice !

denis_berthier wrote:Great. So, the debate is closed. The ph database is indeed the SER-hardest database.

Not anymore. You would have to combine it with the TH database, which includes a lot of simple to solve puzzles. That's the problem.

Right. For non-redundancy reasons, it should become the T&E(2) SER-hardest database.
denis_berthier
2010 Supporter
 
Posts: 4213
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby champagne » Thu Aug 31, 2023 5:46 pm

eleven wrote:Nice !

denis_berthier wrote:Great. So, the debate is closed. The ph database is indeed the SER-hardest database.

Not anymore. You would have to combine it with the TH database, which includes a lot of simple to solve puzzles. That's the problem.

Hi eleven,

Basically, this is true. The only problem I see is that in the original data base, the puzzle had to be minimal.
With the increasing number of clues, this is not a good criteria.

The other problem is that the TH family is huge and seems "relatively easy to solve" (the last example of the "manual expert" totuan surprised me; congratulations to ttt/totuan)
This would push to have them in a separate data base (and the back doors property is not in this thread something to consider, it's not a solving property)

BTW, manual experts have been source of many of the discoveries in the sudoku field thanks to them.
champagne
2017 Supporter
 
Posts: 7455
Joined: 02 August 2007
Location: France Brittany

Re: The hardest sudokus (new thread)

Postby denis_berthier » Fri Sep 01, 2023 6:01 am

mith wrote:My current script will find any potential trivalue oddagon, degenerate or not, useful or not (some of them have 30+ guardian candidates);
[...]
I've never run it on the T&E(2) puzzles, but it would certainly be feasible to do so at the highest SER and filter out puzzles with low guardian counts, degenerate or not, that sort of thing.

Late reaction to this, but I think your first claim should be tempered.
The number of guardians is not a problem (although large numbers rarely lead to anything useful).
But degeneracy is a problem.
What you are saying works only because you apply your script only to T&E(3) puzzles, which all have non-degenerate tridagons.
For puzzles in T&E(2), there may exist degenerate tridagons. However, as long as you don't put a limit on degeneracy, any combination of 12 cells with the right disposition is a degenerate tridagon, even in the extreme case where none of these cells has any of the 3 digits. So, yes, you can certainly find thousands of degenerate "things" but most of them will be totally useless.
denis_berthier
2010 Supporter
 
Posts: 4213
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby Paquita » Fri Sep 01, 2023 3:51 pm

I am not so experienced in advanced solving techniques. There is a site, Phils Folly http://www.philsfolly.net.au/Sudoku/index.htm with the possibility to apply basic and advanced techniques. I imagine a rater could be build around it, that actually a rating program does that, solve a puzzle and give points for the complexity of the technique.
SER/PGE/PGX has a very appealing characteristic, it rates within a scale (from 0 to 12). This makes classification straightforward.

In the past have built a solver with only some simple techniques : naked and hidden pairs and triplets, x,y, z-wings, fish, chains. It helps me to understand the techniques.
Now I want to write a T&E rater, see if I can. I can't get SudokuClassicMinLex to work so I dived into the source code. I also had a look at Denis' CSP-Rules but I find it hard to destillate the algorithm from the Clip code.
I have some questions now. SudokuClassicMinLex rates the dephts only using singles detection(naked and hidden) and contradiction. I think Denis uses more solving techniques, but am not sure. Would the result be the same?
And I assumed that for example T&E(2) means that a good guess is needed, 2 times over. So after the detection of all the singles (first round) the puzzle is not solved, and an educated guess is done. After this first guess, hopefully more singles are detected if it is right, and a contradiction if the guess is wrong. If the guess is right, it is not enough to solve the puzzle. A second round of guessing and singles detection is needed. Is this correct?
If it is, I have a question. In case my first guess was wrong, I can eliminate that candidate. So even though it is not a good guess, I gained some info. That might even solve the puzzle (not if it needs 2 guesses, of course) Maybe I can detect more singles. And if there were only two candidates I now have the correct guess. My question is, where does a wrong guess belong in the T&E rating? And if the guess is wrong, I assume it does not count. For a T&E(2) rating I have to do 2 correct guesses - at least that is what I think I understand.

Can anyone tell me if I am on the right track?
Paquita
 
Posts: 132
Joined: 11 November 2018

Re: The hardest sudokus (new thread)

Postby denis_berthier » Fri Sep 01, 2023 4:13 pm

Paquita wrote:I also had a look at Denis' CSP-Rules but I find it hard to destillate the algorithm from the Clip code

Reverse engineering is rarely the best way to learn something - especially if you don't know the programming language.
Moreover, CLIPS is a very bad choice for programming T&E (I have done it only because all the rest was written in CLIPS. But it's much too slow.)
For formal definitions of T&E, see my book [CRT] or [PBCS] where they were introduced for the 1st time.

Paquita wrote:I have some questions now. SudokuClassicMinLex rates the dephts only using singles detection(naked and hidden) and contradiction. I think Denis uses more solving techniques, but am not sure. Would the result be the same?

I've defined T&E(T, n) for any resolution theory T with the confluence property and for any n≥0.
In practice, T will be Singles, Subsets or some Bp.
T&E(n) is only an abbreviation for T&E(Singles, n). T&E is generally an abbreviation for T&E(1) = T&E(Singles, 1).
And of course, no, if you change T, you don't get the same results.

Paquita wrote:And I assumed that for example T&E(2) means that a good guess is needed, 2 times over.
So after the detection of all the singles (first round) the puzzle is not solved, and an educated guess is done. After this first guess, hopefully more singles are detected if it is right, and a contradiction if the guess is wrong. If the guess is right, it is not enough to solve the puzzle. A second round of guessing and singles detection is needed. Is this correct?

No; T&E has no guessing. It allows to eliminate a candidate if assuming it leads to a contradiction using only Singles. If it leads to a solution, you ignore it (otherwise, it'd be guessing, not T&E).
denis_berthier
2010 Supporter
 
Posts: 4213
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby Paquita » Fri Sep 01, 2023 5:00 pm

Thank you Denis for explaining. You make it much more clear for me.
Yes I can see how a candidate can be eliminated.

It brings new questions as well....
So the T&E(3) depth collection is a T&E(Singles, 3) collection? Does the 3 in T&E(3) mean that 3 candidates were eliminated? Or that 3 assumptions were made? Is there a special technique to select candidates to be assumed and eventually eliminated, or is it random? If an assumption does not lead to contradiction and neither to a solved puzzle, what does one do with it, discard it or keep the assumption? Discard it, I suppose. (I don't remember seeing such things in SudokuClassicMinlex code, but yes, reverse engineering has its limitations, I may have missed it)
Paquita
 
Posts: 132
Joined: 11 November 2018

Re: The hardest sudokus (new thread)

Postby Paquita » Fri Sep 01, 2023 5:06 pm

The SudokuClassicMinLex site https://github.com/dclamage/SudokuClassicMinLex talks about a recursive brute force solver to establish depht. That put me on another track and I am glad I asked because what you explain is different.
Paquita
 
Posts: 132
Joined: 11 November 2018

Re: The hardest sudokus (new thread)

Postby denis_berthier » Fri Sep 01, 2023 5:56 pm

Paquita wrote:So the T&E(3) depth collection is a T&E(Singles, 3) collection?

Yes.
Paquita wrote:Does the 3 in T&E(3) mean that 3 candidates were eliminated? Or that 3 assumptions were made?

At some point,3 assumptions have to be made.

Paquita wrote:Is there a special technique to select candidates to be assumed and eventually eliminated, or is it random?

All the triplets of candidates must be tried.

Paquita wrote:If an assumption does not lead to contradiction and neither to a solved puzzle, what does one do with it, discard it

discard
Last edited by denis_berthier on Fri Sep 01, 2023 6:00 pm, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 4213
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to General