The New Sudoku Players' Forum

[denis_berthier]

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.

No, it does the same thing. The words "brute force" are misleading.
But, again, read the definitions.

[totuan]

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)

My two cent for your questions:
- To prove TH (tridgon) => require T&E(3)
- To prove impossiple patterns => require T&E(2)

You can refer on: http://forum.enjoysudoku.com/chromatic-patterns-t39885.html

totuan

[mith]

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.

"potential" is doing some heavy lifting in my statement, but I stand by it. The script really does find any combination of 12 cells and 3 digits meeting a few criteria:

a. The 12 cells are in a trivalue oddagon pattern (three from each of four boxes covering two bands and two stacks, such that within each box all three rows and columns are covered, and with parity such that the pattern is 4-chromatic)
b. The 3 digits are placeable in the three cells of each box (ruling out cases where one of the 12 cells already can't contain one of the digits, but also a case like 1 can go in either of r1c1 or r2c2, but 2 and 3 can only go in r3c3; each cell can contain a digit from 123, but not all three at the same time).
c. There's a bit more filtering on impossible sub-patterns (things like the only place for 1 in the pattern in box 1 is r1c1, and the only place for 1 in box 2 is r1c4).

And yes, the vast majority of these are totally useless. They are nevertheless valid (degenerate) trivalue oddagons, typically with a large number of guardians. That's why I separately find only the "special" case which is guaranteed non-degenerate in the T&E(3) puzzles. Any first pass on the T&E(2) puzzles would just be for the non-degenerate case.

[mith]

My two cent for your questions:
- To prove TH (tridgon) => require T&E(3)
- To prove impossiple patterns => require T&E(2)

You can refer on: http://forum.enjoysudoku.com/chromatic-patterns-t39885.html

totuan

Proving the trivalue oddagon is 4-chromatic is actually not even in T&E(singles,3), if I remember what Denis said previously. (My assumption would be that any other k-chromatic impossible pattern would require at least T&E(singles,k) to prove?)

There's no direct relationship between having a non-degenerate trivalue oddagon and being in T&E(3) specifically; it's just that it can't be resolved on its own in T&E(2) and the isolated nature of it allows in some cases for the puzzle to defeat T&E(2) entirely.

[Paquita]

Denis,

I read the definition on page 121 of PCS. You describe the algorithm there. I does, also, clarify what is done. Still, some of the theory is not so easy for me to understand. What in this definition is the depth? I mean, a depth of 3 (T&E(3)), does that mean 3 rounds of trying every remaining candidate to see if it can be eliminated?
That is how I understand it now, that one round is trying every candidate (and remove it if it leads to contradiction); if this solves the puzzle, it is T&E(1); if there is no solution, try all the then remaining candidates again, remove those who lead to contradiction, and with some candidates removed, try to solve; if it is solved, it is in T&E(2).
I also suppose that after every removal one tries to solve the puzzle so not necessary all the candidates have been tried (or tried again); if this happens in the second round it is still T&E(2).

Sorry if I bother you with what is to you a trivial question. I know many of you forum members know so much more about all this. I am better with writing scripts to generate puzzles, but not so good in designing patterns. You asked me how I knew my last update was all T&E(2), and for my own puzzles, I have no easy way to test that. ( Mith has tested his, hendriks and JPFs puzzles). I can't get SudokuMinLex to work so I thought, maybe I can write something that tests for this. Then I have to know what the meaning is of T&E exactly.

[denis_berthier]

I read the definition on page 121 of PCS. You describe the algorithm there. I does, also, clarify what is done. Still, some of the theory is not so easy for me to understand. What in this definition is the depth? I mean, a depth of 3 (T&E(3)), does that mean 3 rounds of trying every remaining candidate to see if it can be eliminated?

Hi Paquite
What you read is the definition of T&E(1). Even at depth 1, iteration on the candidates has to occur in order to guarantee that the result doesn't depend on the order you apply the Singles. But this is always only 1 candidate at a time.
If you want to learn about T&E(n), you have to read also section 11.3.2.

Forgetting about the specifics of the algorithm, T&E(n) means you have to consider contradictions arising by Singles only from up to n candidates. This is a universal definition and it defines an intrinsic property of a puzzle (in particular, independent of implementation or arbitrary choices - contrary to SER).

You asked me how I knew my last update was all T&E(2), and for my own puzzles, I have no easy way to test that.

You can use SudoRules. Its version of T&E is slow but it works. Hundreds of puzzles will not be a problem.

[denis_berthier]

Proving the trivalue oddagon is 4-chromatic is actually not even in T&E(singles,3), if I remember what Denis said previously. (My assumption would be that any other k-chromatic impossible pattern would require at least T&E(singles,k) to prove?)

The trivalue oddagon pattern (non-degenerate and with with no guardians) can be proven contradictory in T&E(3) - or even in restricted T&E(3), i.e. without using other candidates than the 12 in the pattern.
Any degenerate form can be proven contradictory in T&E(2).
All the other patterns found by eleven can be proven contradictory in restricted T&E(2), except one that requires either full T&E(2) or restricted T&E(3).

There's no direct relationship between having a non-degenerate trivalue oddagon and being in T&E(3) specifically; it's just that it can't be resolved on its own in T&E(2) and the isolated nature of it allows in some cases for the puzzle to defeat T&E(2) entirely.

Yes. It's important to insist on two points:
1) I think it's true of most patterns. A good example is Quads: the Quad elimination rule requires T&E(3) to be proven, but most puzzles with quads can be solved in T&E(1). The pattern can be bypassed by other rules.
2) the puzzles in T&E(3) were found based on the T&E-depth criterion. The fact that they all have a non-degenerate tridagon may result from different causes (such as the seeds being used + proximity search) or a general property of T&E(B2, 2) that we haven't yet discovered.
.

[denis_berthier]

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.

"potential" is doing some heavy lifting in my statement, but I stand by it. The script really does find any combination of 12 cells and 3 digits meeting a few criteria:

a. The 12 cells are in a trivalue oddagon pattern (three from each of four boxes covering two bands and two stacks, such that within each box all three rows and columns are covered, and with parity such that the pattern is 4-chromatic)

OK, this is the cells criterion. Basically, this gives only 1 pattern of cells, modulo isos.

c. There's a bit more filtering on impossible sub-patterns (things like the only place for 1 in the pattern in box 1 is r1c1, and the only place for 1 in box 2 is r1c4).

OK also. This is fixing some of the isos as I did in the tridagon thread (http://forum.enjoysudoku.com/the-tridagon-rule-t39859.html).

b. The 3 digits are placeable in the three cells of each box (ruling out cases where one of the 12 cells already can't contain one of the digits, but also a case like 1 can go in either of r1c1 or r2c2, but 2 and 3 can only go in r3c3; each cell can contain a digit from 123, but not all three at the same time).

There must be some misunderstanding here. For me "The 3 digits are placeable in the three cells of each box" means that the 3 candidates are present in all the 12 cells - i.e. the pattern is non-degenerate.
I don't understand: "each cell can contain a digit from 123, but not all three at the same time". Do you mean some cyclic condition like a 12 23 31 pattern in each block? I've tried this, but I found it difficult to manage the inter-block conditions.
.

[Paquita]

Denis

Yes I know I can use SudoRules. I think I figured out how to give a file with puzzles as command line argument, but then I have another question : is there a way to redirect the output to a file? Right now when I use it I get output, but when I do more puzzles I have to scroll in the Clip window to see the output per puzzle. You also mentioned the result is in a variable but I don't know how to ask for its value in Clip, even for a single puzzle, let alone when I process a file of puzzles.

I will certainly use SudoRules as a check for my own program - I am simply having fun writing it.

[denis_berthier]

Yes I know I can use SudoRules. I think I figured out how to give a file with puzzles as command line argument, but then I have another question : is there a way to redirect the output to a file?

The general way for this is

Code: Select all

(dribble-on "full_path_to_your_file")

. All output is redirected to your_file.

Code: Select all

(dribble-off)

will redirect the output to the Terminal.

Right now when I use it I get output, but when I do more puzzles I have to scroll in the Clip window to see the output per puzzle. You also mentioned the result is in a variable but I don't know how to ask for its value in Clip, even for a single puzzle, let alone when I process a file of puzzles.

When you solve puzzles in string format in a file, at the end, global variable ?*solved-puzzles* contains the list of line numbers whose puzzles have been completely solved.

Let's say you have selected ?*TE2* as the only technique to be applied (and therefore de-selected the default rules in the config file).

Code: Select all

(solve-n-grids-after-first-p-from-text-file "my_puzzles_file" p n)

will solve the n puzzles after skipping the first p.
At the end, global variable ?*solved-puzzles* will contain puzzles solved in T&E(2) (and those solved in T&E(1) or T&E(0), if any).
To get this list, merely type:

Code: Select all

?*solved-puzzles*

and return/enter.

Note that if you want to get the exact T&E-depth, you have to run T&E(1), T&E(2) and T&E(3) separately.
But if you only want to exclude puzzle in T&E(3), running T&E(2) is enough.

One more useful function is "not-in-list$"
Suppose, as before, you got a list of puzzles in at most T&E(2), where total file length is n.

Code: Select all

(not-in-list$ ?*solved-list* n)

will give you the line numbers, up to n, of those that are not in T&E(2).

[Edit]: if you don't want to see all the details of the T&E calculations, type the following,g before launching function solve-n-grids...

Code: Select all

(bind ?*print-actions* FALSE)
(bind ?*print-RS-after-Singles* FALSE)
(bind ?*print-RS-after-whips[1]* FALSE)
(bind ?*print-solution* FALSE)
(bind ?*print-final-RS* FALSE)
(bind ?*print-hypothesis* FALSE)

PS. To avoid hijacking this thread, if you have more questions about SudoRules, it's better to ask in the CSP-Rules... thread (http://forum.enjoysudoku.com/csp-rules-sudorules-kakurules-t38200.html).
.

[mith]

The trivalue oddagon pattern (non-degenerate and with with no guardians) can be proven contradictory in T&E(3) - or even in restricted T&E(3), i.e. without using other candidates than the 12 in the pattern.

Thanks, I was misremembering.

[mith]

There must be some misunderstanding here. For me "The 3 digits are placeable in the three cells of each box" means that the 3 candidates are present in all the 12 cells - i.e. the pattern is non-degenerate.
.

Replied in the other thread: link

[denis_berthier]

Denis,
This is the new version of the non-T&E(3) puzzles.
Most of the puzzles are from mith or hendrik, some from me and JPF, and mith checked those for T&E(3). All in this file are not in miths collection of T&E(3). The only ones that have not been checked are my recent puzzles. So in theory it is possible that some of those are T&E(3), but they are not in miths collection either. It is unlikely that I did find some new T&E(3) puzzles, but not impossible. I will check those with your tool, that will take some time.
https://drive.google.com/file/d/1e2eVXOCkoU51NNbJtOY60DJk6khpO6Tl/view?usp=sharing

Hi Paquita,

1) I passed part of your collection through T&E-depth.
All the SER 11.9 ones are depth 2, but some of the 11.8s and 11.7s are depth 3.


2) The last 3 of the 13 SER 11.9 have PGX=11.8

Code: Select all

98.76.5..7.5.946....45.8...64.......5.96......784.9.6..9.....5....8.7..........32;11.9/1.2/1.2 monh ED=11.8/1.2/1.2
98.76.54.7.58..6...46......5.9...76..7....8.5.68....94.94..........394......2....;11.9/1.2/1.2 monh ED=11.8/1.2/1.2
98.76.5..7.5.496....45.8...64.......5.869.....798.4.6..9.....5......7..........32;11.9/1.2/1.2 monh ED=11.8/1.2/1.2

3) Where in your unusual format does the following puzzle appear:

Code: Select all

.2...67..4...8......9.......3.....7.5.8....4..1.3....2....9..5....6.1..3...2..6.7

.

[Paquita]

Denis,

Puzzle .2...67..4...8......9.......3.....7.5.8....4..1.3....2....9..5....6.1..3...2..6.7 is

98.7.....6..85......4..3...7..6..5....9...6....2....41.9..8.7.......1.2.........3;11.80;1.20;1.20;dob;12_12_03;247964;22;
(I put all puzzles in maxlex so I can check for doubles)

I am now passing my own newest puzzles in the collection through SudoRules to test T&E, and indeed, many are T&E(3). I did not expect this but it seems there still are more T&E(3) puzzles to be found. These are the puzzles that end with PAQ, but not those with PAQ that were in the ph2010 database and have extended specifications from there. When I have passed them all through SudoRules I will update. (it takes quite some time).

I did have a discussion with Hendrik (monh) about his 11.9's. In maxlex they are all but one PGX 11.8. That lead to a discussion about when to rate a puzzle 11.9; He proposed that if maxlex, minlex, maxlex solution and minlex solution are all 11.9 it is 11.9; I proposed that if a puzzle is 11.9 in any form (to be delivered by the contributor) it will be considered 11.9

[denis_berthier]

Puzzle .2...67..4...8......9.......3.....7.5.8....4..1.3....2....9..5....6.1..3...2..6.7 is
98.7.....6..85......4..3...7..6..5....9...6....2....41.9..8.7.......1.2.........3;11.80;1.20;1.20;dob;12_12_03;247964;22;
(I put all puzzles in maxlex so I can check for doubles)

OK. I didn't understand, because I had it in my records as a puzzle by eleven in his old "tamagotchi" collection.
It happens to be one of the rare puzzles with BpB = 7.
I now wonder if it was found independently by eleven and dob.

I am now passing my own newest puzzles in the collection through SudoRules to test T&E, and indeed, many are T&E(3). I did not expect this but it seems there still are more T&E(3) puzzles to be found. These are the puzzles that end with PAQ, but not those with PAQ that were in the ph2010 database and have extended specifications from there. When I have passed them all through SudoRules I will update. (it takes quite some time).

OK, I'm not doing more with it now. When it's updated, I may compute a few of the BpB.

I did have a discussion with Hendrik (monh) about his 11.9's. In maxlex they are all but one PGX 11.8. That lead to a discussion about when to rate a puzzle 11.9; He proposed that if maxlex, minlex, maxlex solution and minlex solution are all 11.9 it is 11.9; I proposed that if a puzzle is 11.9 in any form (to be delivered by the contributor) it will be considered 11.9

My view is different. Considering all the arbitrary thresholds in SER, ± 0.1 doesn't mean much.
I think in any case, the lowest level computed is more meaningful than the highest: the highest only means that some possibility that was available in a morph has been missed.
I'm now using GPXplainer, which is not perfect but provides more consistent results.
I think the new version of the T&E(2) database should use only GPXplainer.

I also think, we should use it with the -M option, i.e. without uniqueness rules. These rules are the cause of many inconsistencies in the SER ratings. In particular, in the T&E(3) database, all the low SER puzzles I've tried has some uniqueness rule applied and got very much larger PGX without uniqueness.

.