The New Sudoku Players' Forum

[Hajime]

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

[mith]

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.

[hendrik_monard]

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

[mith]

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

[hendrik_monard]

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

[mith]

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.

[denis_berthier]

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

[hendrik_monard]

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.

[denis_berthier]

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.

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?

[hendrik_monard]

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?

[denis_berthier]

Hi Hendrik

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.

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)

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.

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.

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.

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

[hendrik_monard]

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.

[denis_berthier]

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

[hendrik_monard]

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.

[denis_berthier]

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

Sure, otherwise, it would be guessing.

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.