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 Hajime » Tue Sep 28, 2021 3:32 pm

creint wrote:
Hajime wrote:...Nested Forcing NET...

A contradiction results in an exclusion in the previous layer.
Keep doing those exclusions until you can't find anything. Just like normal solving. And then go back to previous layer.

Current -> try A, solve -> try B, solve, (if contradiction remove B from A)
For each A you must try each pencilmark for B every time you find a B with contradiction.
If A gives a contradiction you can finally remove this from current puzzle.

You can also look at an explanation in SukakuExplainer.


Thanks creint, I will look into this. SukakuExplainer has no Forcing Net method? Lots of Forcing chain methods, yes.
User avatar
Hajime
 
Posts: 1348
Joined: 20 April 2018
Location: Fryslân

Re: The hardest sudokus (new thread)

Postby mith » Tue Sep 28, 2021 3:43 pm

I am actually still running the slower version. (Still need to update.) But yes, I average around 10 seconds for rating 11.0 puzzles (I just timed an 11.2 and it took about 20 seconds) with a typical load elsewhere (all the generating scripts).

I have a Ryzen 5950X (16 core, 32 thread) - figured since I do a lot of resource intensive stuff like this might as well go big. :) Typically the SE script is using a third to a half of that.
mith
 
Posts: 950
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby hendrik_monard » Wed Sep 29, 2021 8:40 am

After examination of my result files, I selected these new 11.6's and one 11.7
This should be my last contribution before the upcoming database update.

98.7.......6.5.4.......6...8..4...7..7......3..2..71...9.3....4..1.6.........25.. SER = 11.7/11.7/4.3
98.7..6..7...9......5..4...3...7.8....9..6.42.....1....9..6.3....2.............15 SER = 11.6/11.6/2.6
98.7..6....5.9...........4.79....3....6..3........7.6236...98....1.8.......6..... SER = 11.6/1.2/1.2
98.7..6..7..6..5......4..8.5..9..7...7...3....6......21.......5.9...71.....1...6. SER = 11.6/1.2/1.2
98.7..6..7..6..5......4..8.5..9..7...6......3.....2...1.......5.9...71....71...6. SER = 11.6/1.2/1.2
hendrik_monard
 
Posts: 83
Joined: 19 April 2021
Location: Leuven (Louvain) Belgium

Re: The hardest sudokus (new thread)

Postby mith » Thu Sep 30, 2021 3:38 am

Two new 11.8s tonight (minimals of the same 29c puzzle), and new highs for both clue counts.

Code: Select all
27c
........1......23......4..5...26.....23.784..86.4.3....7.63....34.8.2...6.2..7.8.  ED=11.8/1.2/1.2

26c
........1......23......4..5...26.....23.784..86...3....7.6.....34.8.2...6.2.47.8.  ED=11.8/1.2/1.2
mith
 
Posts: 950
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby hendrik_monard » Thu Sep 30, 2021 12:08 pm

Congratulations Mith,
Both these puzzles are the first ever to beat my Solver. So they must be original. They are also minimal. It appears that you have a powerful tool for further exploring these high regions. I wouldn't be surprised if they lead you to perhaps finding a new 11.9
hendrik_monard
 
Posts: 83
Joined: 19 April 2021
Location: Leuven (Louvain) Belgium

Re: The hardest sudokus (new thread)

Postby mith » Fri Oct 01, 2021 1:48 am

Stopped my generating scripts tonight; I'm going to let the SE rater run on its own for a few days, and then I'll get an update together.
mith
 
Posts: 950
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby denis_berthier » Fri Oct 01, 2021 5:43 am

hendrik_monard wrote:Both these puzzles are the first ever to beat my Solver.

Have you tried any of these:
Code: Select all
..3....8..5....2.17...........5.8..6.9.12....8....3....6.9....5..4....7.....1.6.2
.2...67..4...8......9.......3.....7.5.8....4..1.3....2....9..5....6.1..3...2..6.7
5.......9.2.1...7...8...3...4.6.........5.......2.7.1...3...8...6...4.2.9.......5
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby hendrik_monard » Fri Oct 01, 2021 7:37 am

My solver(s) took some time for solving these three puzzles which is normal for the hardest puzzles. The third one was the toughest, coming close to the maximum time I ever noticed (ca 12 seconds).
I guess that the reason for not solving the last puzzles posted by mith was that they have a large clue number. I checked some earlier puzzles from mith with high clue numbers, and some of them I could not solve either.
I enabled an extension of my solver that I could not test before, and then my solver solved the last two posted by mith in about 35 seconds.
Last edited by hendrik_monard on Sun Oct 03, 2021 2:35 pm, edited 1 time in total.
hendrik_monard
 
Posts: 83
Joined: 19 April 2021
Location: Leuven (Louvain) Belgium

Re: The hardest sudokus (new thread)

Postby denis_berthier » Fri Oct 01, 2021 8:10 am

hendrik_monard wrote:My solver(s) took some time for solving these three puzzles which is normal for the hardest puzzles. The third one was the toughest, coming close to the maximum time I ever noticed (ca 12 seconds).

I chose these 3 because they are the only (known) puzzles with BpB rating = 7.
The last 2 from Mith are in B6B.

hendrik_monard wrote:I guess that the reason for not solving the last puzzles posted by mith was that they have a large clue number. I checked some earlier puzzles from mith with high clue numbers, and some of them I could not solve either.
I enabled an extension of my solver that I could not test before, and then my solver solved nr 3 in about 35 seconds.

There's no meaningful correlation between difficulty and clue number.
There's a larger correlation between difficulty and number of candidates after Singles (and whips[1]), but not very meaningful either.

What kind of techniques is your solver based on?
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby hendrik_monard » Fri Oct 01, 2021 3:52 pm

denis_berthier wrote:There's a larger correlation between difficulty and number of candidates after Singles (and whips[1]), but not very meaningful either.

What kind of techniques is your solver based on?


Let me start by correcting my last message : ........I enabled an extension of my solver that I could not test before, and then my solver solved the last puzzles posted by mith in about 35 seconds.

My solver has 4 stages. When a stage is not able to solve the puzzle, the next stage is called. It can only find a solution if the puzzle is solvable and if there is only one solution.

The first stage is a basic solver (detecting hidden and naked singles, pairs, triples and quads, pointing, claiming)
For puzzles that can't be solved with this basic solver, and as I didn't have the courage or the patience or the expertise for coding the more complicated strategies, I focused on further eliminating candidates until a solution by the basic solver emerges after removal of the 'forbidden' candidates.

In stage 2 all the candidates are examined individually. The current candidate (the one being examined) is transformed into a clue and the modified puzzle is submitted to the basic solver. The only result requested from the solver is the error status. If an error situation appears, the current candidate is considered to be 'forbidden'. This has been detected in the underlying process of the solver which is inherently a logical process. The position and value of the current forbidden candidate is put in a list of forbidden candidates. At regular intervals, the original puzzle together with the list of forbidden candidates is submitted to the basic solver to examine whether enough progress has been obtained for a solution to emerge from the basic solver (in my programme I check this after each addition to the list of forbidden candidates). If solved: end of programme, otherwise the examination of candidates continues.

In stage 3, the process is similar to the one of stage 2. However, in this stage candidates of two cells are combined. If a candidate of cell x combined with each candidate of cell y results every time in an error returned by the basic solver, that candidate of cell x can be eliminated, because one of the candidates of cell y has to be part of the ultimate solution of the puzzle.

Stage 4, which I couldn't test until yesterday when a suitable puzzle (not solvable by stage 3) became available, three cells are involved. A candidate of cell x is combined with all the combinations of the candidates of cells y and z. If the basic solver returns an error for each of these combinations, the current candidate of cell x can be eliminated, because one of the combinations of the candidates of cells y and z must be part of the ultimate solution of the puzzle.

I'm not sure whether this description is detailed enough, so feel free to ask if something is not clear.
Theoretically, more stages could be added (involving four or more cells), but the probability for a next stage to be required for solving a valid puzzle seems rather slim.
The last (long) test I did was on all puzzles >= SER 12.2 of database ph_1712, and for none of them stage 4 was needed to solve the puzzle.

You mentioned in previous posts qualifications of the type B5B , B6B or B7B. Where can I find more information about that system?
hendrik_monard
 
Posts: 83
Joined: 19 April 2021
Location: Leuven (Louvain) Belgium

Re: The hardest sudokus (new thread)

Postby denis_berthier » Sat Oct 02, 2021 7:11 am

Hi Hendrik
hendrik_monard wrote:My solver has 4 stages. When a stage is not able to solve the puzzle, the next stage is called. It can only find a solution if the puzzle is solvable and if there is only one solution.
The first stage is a basic solver (detecting hidden and naked singles, pairs, triples and quads, pointing, claiming).

OK, let's call S this set of rules.


hendrik_monard wrote:In stage 2 all the candidates are examined individually. The current candidate (the one being examined) is transformed into a clue and the modified puzzle is submitted to the basic solver. The only result requested from the solver is the error status. If an error situation appears, the current candidate is considered to be 'forbidden'. This has been detected in the underlying process of the solver which is inherently a logical process.

If the current candidate (say C) was eliminated instead of just put in the list, that would be what I defined as T&E(S, 1, C)


hendrik_monard wrote:At regular intervals, the original puzzle together with the list of forbidden candidates is submitted to the basic solver to examine whether enough progress has been obtained for a solution to emerge from the basic solver (in my programme I check this after each addition to the list of forbidden candidates). If solved: end of programme, otherwise the examination of candidates continues.

OK, now this is almost what I defined as T&E(1, S) BUT there's a major difference: in T&E(1, S), if the solution is not found after trying all the candidates, but if at least one candidate has been eliminated, one must iterate the whole procedure.
Why?, will you ask. Two reasons:
- because, for any candidate C, the elimination of candidates other than C may give C a new chance to be eliminated during the repetition.
- if you don't do this, the result of the procedure is not well defined. It depends on the order of testing the candidates.


hendrik_monard wrote:In stage 3, the process is similar to the one of stage 2. However, in this stage candidates of two cells are combined. If a candidate of cell x combined with each candidate of cell y results every time in an error returned by the basic solver, that candidate of cell x can be eliminated, because one of the candidates of cell y has to be part of the ultimate solution of the puzzle.

OK, that's akin to T&E(2, S), with the same remarks as above about iterating.


hendrik_monard wrote:Theoretically, more stages could be added (involving four or more cells), but the probability for a next stage to be required for solving a valid puzzle seems rather slim.
The last (long) test I did was on all puzzles >= SER 12.2 of database ph_1712, and for none of them stage 4 was needed to solve the puzzle.

Now guess what. If you do the iterations I mentioned above, you'll never need more stages (and you don't even need intersections or Subsets in S): all the known puzzles are in T&E(2, Singles) - indeed they that are in B7B. I've shown this long ago and keep checking it for all the hardest puzzles proposed in this thread.
Even if some puzzle P appeared to be in B8B, the gap between B8B and not-T&E(2) is so large that it would mean P is "infinitely" harder than any currently known 9x9 puzzle.


hendrik_monard wrote:You mentioned in previous posts qualifications of the type B5B , B6B or B7B. Where can I find more information about that system?

That's a subclassifications of T&E(2, Singles). It is described (together with the definitions of T&E...) in my book "Pattern-Based Constraint Satisfaction" chapter 11, freely available:
- on ResearchGate:https://www.researchgate.net/publication/280100555_Pattern-Based_Constraint_Satisfaction_and_Logic_Puzzles_Second_Edition
- or as part of the documentation of my CSP-Rules solver: https://github.com/denis-berthier/CSP-Rules-V2.1
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby hendrik_monard » Sat Oct 02, 2021 12:32 pm

Hi Denis,

You wrote:
OK, now this is almost what I defined as T&E(1, S) BUT there's a major difference: in T&E(1, S), if the solution is not found after trying all the candidates, but if at least one candidate has been eliminated, one must iterate the whole procedure.
Why?, will you ask. Two reasons:
- because, for any candidate C, the elimination of candidates other than C may give C a new chance to be eliminated during the repetition.
- if you don't do this, the result of the procedure is not well defined. It depends on the order of testing the candidates.

In fact, when in my solver an examination round of candidates in one of the stages is finished, a new round is started if at least one (new) forbidden candidate was identified during the previous round. In this new round, already identified forbidden candidates are not examined again. I should indeed have mentioned that explicitly in the description I posted yesterday.

Many thanks for your valuable comments and for the link to your book.
hendrik_monard
 
Posts: 83
Joined: 19 April 2021
Location: Leuven (Louvain) Belgium

Re: The hardest sudokus (new thread)

Postby denis_berthier » Sun Oct 03, 2021 5:37 am

hendrik_monard wrote:You wrote:
OK, now this is almost what I defined as T&E(1, S) BUT there's a major difference: in T&E(1, S), if the solution is not found after trying all the candidates, but if at least one candidate has been eliminated, one must iterate the whole procedure.
Why?, will you ask. Two reasons:
- because, for any candidate C, the elimination of candidates other than C may give C a new chance to be eliminated during the repetition.
- if you don't do this, the result of the procedure is not well defined. It depends on the order of testing the candidates.

In fact, when in my solver an examination round of candidates in one of the stages is finished, a new round is started if at least one (new) forbidden candidate was identified during the previous round. In this new round, already identified forbidden candidates are not examined again. I should indeed have mentioned that explicitly in the description I posted yesterday.

I see, but do you also do it at the next level (stage 3 in your description)? If yes, I don't understand why you ever need a stage 4.
The two puzzles by Mith are in T&E(2, Singles).
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby hendrik_monard » Sun Oct 03, 2021 3:14 pm

Hi Denis,
You wrote:
I see, but do you also do it at the next level (stage 3 in your description)? If yes, I don't understand why you ever need a stage 4.
The two puzzles by Mith are in T&E(2, Singles).


Indeed, I do, and therefore I was surprised that a few days ago two puzzles were posted by mith that I could not solve in stage 3. I had to enable (and test for the first time) stage 4 in order to find the solution.
Perhaps this can be explained because in my current solver, when passing to a higher stage, all findings of the previous stage(s) are disregarded. I assumed that the previous findings would be found again at the next stage. In that case, not transmitting them to that stage should not be an impediment.
However, I'll modify my solver so that these findings are transmitted to the next stage. This will also increase the speed for obtaining the final result. As this may take a while, I will communicate the results later.
Perhaps there is a misunderstanding. I do not force 2 cells to obtain a solution, which would be trial and error. I submit the puzzle with two additional clues to the basic solver only to obtain the error status. If there is no error, nothing happens, even if a solution is found. If the solver returns an error, this information is used as described in my earlier post to the process of possibly declaring a candidate as 'forbidden'.
By the way, I downloaded your book. Very impressive, applied mathematics of a very high level, but hard to read for me. At least I got some idea of the BpB rating system.
hendrik_monard
 
Posts: 83
Joined: 19 April 2021
Location: Leuven (Louvain) Belgium

Re: The hardest sudokus (new thread)

Postby denis_berthier » Sun Oct 03, 2021 5:15 pm

hendrik_monard wrote: If there is no error, nothing happens, even if a solution is found.

Sure, otherwise, it would be guessing.

hendrik_monard wrote: By the way, I downloaded your book. Very impressive, applied mathematics of a very high level, but hard to read for me. At least I got some idea of the BpB rating system.

I suggest you skip the most technical parts in a first read.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to General