The New Sudoku Players' Forum

[DEFISE]

here is a short solution with whips[<=5]:

Hidden Text: Show

Single: 5r3c8
Single: 7r7c7
Single: 4r2c7
Single: 3r3c7
Single: 1r7c8
Single: 2r8c8
Single: 8r8c7
Single: 5r6c7
Single: 2r4c7
Single: 4r8c2
Single: 9r8c3
Single: 6r7c3
Single: 1r2c3
Single: 5r7c2
Single: 9r7c4
Single: 3r7c6
Single: 1r8c5
Single: 8r9c1
Single: 6r9c9
Alignment: 6-c1-b4 => -6r5c2
XWing: 7c28-r25 => -7r5c1 -7r5c6 -7r5c9
whip[4]: r3n6{c4 c2}- r2c2{n6 n7}- r1c1{n7 n4}- r5c1{n4 .} => -6r5c4
whip[5]: r5c8{n9 n7}- r5c2{n7 n8}- r3c2{n8 n6}- c4n6{r3 r6}- r6n8{c4 .} => -9r6c9
Alignment: 9-r6-b5 => -9r5c5 -9r5c6
Naked pair: 24-r3c6-r5c6 => -4r1c6 -4r4c6 -2r9c6 -4r9c6
Single: 5r9c6
whip[5]: r3n6{c4 c2}- c2n8{r3 r5}- c4n8{r5 r4}- c4n1{r4 r1}- c4n5{r1 .} => -6r6c4
STTE

Hi Defise,
Good, you have fewer rule applications than in the simplest-first strategy (with the same max length of whips).
Can you remind me your criterion for choosing the next target (within a fixed Wn)? I can't find the post where you told it. Was it the maximum number of candidates that would be subsequently eliminated by Singles and ECP (or maybe also Whips[1] and Subsets) if the target was eliminated? Did you also consider the number of candidates turned into solution values?

Hi Denis,
Here is the link of my post :
robert-s-puzzles-2020-11-14-t38411-15.html#p297633

- Yes, my first criterion is the number of candidates that would be subsequently eliminated by basic techniques if the target was eliminated (here basics = singles + alignments + naked & hidden pairs + naked triplets).

- I don’t consider the number of candidates turned into solution values, because the placement of a candidate leads to a lot of deletions of other candidates. But I could easily add that as second criterion or even as first criterion.

- Note that I added a 3rd criterion which is a random number, which leads to different choices of "ex aequo" targets (modulo criteria 1 et 2) from one execution to another.
For example for this 4leaf puzzle, 20 executions gave:
1 solution with 5 whips [<= 5],
8 solutions with 4 whips [<= 5]
11 solutions with 3 whips [<= 5].

[denis_berthier]

- Yes, my first criterion is the number of candidates that would be subsequently eliminated by basic techniques if the target was eliminated (here basics = singles + alignments + naked & hidden pairs + naked triplets).
- I don’t consider the number of candidates turned into solution values, because the placement of a candidate leads to a lot of deletions of other candidates. But I could easily add that as second criterion or even as first criterion.

If I take this literally, it means that you try all the basics "in parallel" in the current resolution state minus the target under consideration. And you get the value of this target by adding the eliminations allowed by each of these basics, without iterating over these rules. Is this right?

- Note that I added a 3rd criterion which is a random number, which leads to different choices of "ex aequo" targets (modulo criteria 1 et 2) from one execution to another.
For example for this 4leaf puzzle, 20 executions gave:
1 solution with 5 whips [<= 5],
8 solutions with 4 whips [<= 5]
11 solutions with 3 whips [<= 5].

So, you have to explore 20 possible full resolution paths before deciding which is the best?

I asked you about all this because in my Forcing-T&E algorithm, I have similar decisions to make at each step; but, as of now, I only try to make local decisions and to avoid generating several paths. Of course, this can't guarantee an optimal solution (with the smallest number of steps).

I still have to do more exploration about the best local decisions. In the case of this 4-leaf clover puzzle, it was easy because a single step was enough.

[DEFISE]

If I take this literally, it means that you try all the basics "in parallel" in the current resolution state minus the target under consideration. And you get the value of this target by adding the eliminations allowed by each of these basics, without iterating over these rules. Is this right?

I wouldn't say "in parallel" but rather sequentially.
Let's take the example of my resolution and the resolution state after 6r5c4 suppression .
Then let’s consider the potential target 9r6c9. The deletion of 9r6c9 would allow the 3 following basics (sequentially but not in parallel):
Alignment: 9-r6-b5 => -9r5c5 -9r5c6
Naked pair: 24-r3c6-r5c6 => -4r1c6 -4r4c6 -2r9c6 -4r9c6
Single: 5r9c6
These 3 rules correspond to 12 candidates deleted.
So the 1st criterion for 9r6c9 is 12.

So, you have to explore 20 possible full resolution paths before deciding which is the best?

Yes most of the 20 resolutions are different because of the 3rd criterion which is a random number.
It's perhaps not very satisfactory, but the advantage is that the addition of this 3rd criterion (random number) only cost me the modification of a line in my program.

I asked you about all this because in my Forcing-T&E algorithm, I have similar decisions to make at each step; but, as of now, I only try to make local decisions and to avoid generating several paths. Of course, this can't guarantee an optimal solution (with the smallest number of steps).

To minimize the number of tries in the T&E, you can employ the same algorithm.
It is even simpler in this case since there is no constraint on the length of the chains.

[JPF]

I stopped the search when the number of puzzles was greater than 100,000...
Two new high ratings popped up:

Code: Select all

.12...34.3..2.4..15...3...6.7.....8...5...6...2.....1.7...5...42..6.9..8.59...76.    ED=9.3/1.2/1.2
.12...34.3..2.4..15...3...6.7.....8...5...6...2.....1.7...5...42..9.6..8.59...76.    ED=9.2/1.2/1.2


JPF

[denis_berthier]

I stopped the search when the number of puzzles was greater than 100,000...
Two new high ratings popped up:

Code: Select all

.12...34.3..2.4..15...3...6.7.....8...5...6...2.....1.7...5...42..6.9..8.59...76.    ED=9.3/1.2/1.2
.12...34.3..2.4..15...3...6.7.....8...5...6...2.....1.7...5...42..9.6..8.59...76.    ED=9.2/1.2/1.2


JPF

They are significantly harder than the previous list: they are in W12.

[denis_berthier]

So, you have to explore 20 possible full resolution paths before deciding which is the best?

Yes most of the 20 resolutions are different because of the 3rd criterion which is a random number.
It's perhaps not very satisfactory

.
That's what I thought about my first approach in Forcing-T&E, but I haven't yet found anything really smarter.

I asked you about all this because in my Forcing-T&E algorithm, I have similar decisions to make at each step; but, as of now, I only try to make local decisions and to avoid generating several paths. Of course, this can't guarantee an optimal solution (with the smallest number of steps).

To minimize the number of tries in the T&E, you can employ the same algorithm.
It is even simpler in this case since there is no constraint on the length of the chains.

I'm not trying to do this in T&E; the only interest of T&E is to check quickly that something is in T&E(1 or 2 or more for larger puzzles).
In Forcing-T&E, the problem is slightly different, as it requires comparing two different branches for each bivalue pair of candidates. I'm currently exploring several possibilities for estimating the "value" of each pair. But I want to avoid having to develop several full resolution paths.

[DEFISE]

Hi Denis,
OK, I understand. I was surprised that you wanted to optimize simple T&E !

[coloin]

I stopped the search when the number of puzzles was greater than 100,000...

Yes i am on 124,000 and have not yet come across 7/10 of the ones which I randomly found ... I might let it run on for a bit ..
And it seems I made an error which explains why
10 puzzles per 100,000 solution grids means that there may well be 500,000 per 5e9 solution grids !!