Sudoku Players' Forum (clone)

.
Now analysing mith's new database of 375,759 minimal puzzles not in T&E(2):
http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1299.html
and the corresponding databases of 63,137 min-expands and 15,606 max-expands:
http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1304.html

1) How many puzzles can be solved with only Subsets + FinnedFish + the tridagon rule defined in this thread:
(I consider this as the minimum meaningful set of rules to consider, because Subsets are often essential before the basic tridagon rule becomes available.
Conversely, more rules may be necessary before they appear, and this may increase the following numbers, but that's another point.)
- max-expands : 4,926 = 31.6%
- all the minimals : 75,286 = 20%
- min-expands : 8,196 = 13%
Of course, the percentages are decreasing, as the puzzles get harder in the mean.

2) Puzzles having either the pattern of the tridagon rule (whether it is enough for reaching a solution or not) or a tridagon link; i.e. puzzles having a trivalue oddagon pattern with only 1 or 2 additional candidates (possibly after Subsets + FinnedFish):
- max-expands : 13,280 = 85.1 %
- min-expands : 38,551 = 61%

I'm currently running a check for guardian cell counts (after basics - subsets and locked candidates) on all min-expands. Some preliminary testing of this script gave counts as high as 9, for example:

Code: Select all

........1..1..2.34..4.1325....2....5.5..34.1..6...5.2..453.6...7.6.....28.9....6.

This particular grid reduces to a count of 3 after a short chain, like:

Code: Select all

(9=2)r5c1 - (2=1)r7c1 - r46c1 = 1r4c2 => -9r4c2

I'll be curious to see what the max is for the whole set, and which of these is the hardest to reduce.

Here's the first grid I've seen where the pattern can't be uniquely determined:

Code: Select all

.234..7..45.....2.7.82....4...963..7...817.5..87524....74..2..883...5..2.....83..

Box 3's diagonal could be either r1c8/r2c9/r3c7 or r1c9/r2c7/r3c8. This holds even up to the first brute force step in YZF.

And here's a max-expand with guardians in all boxes... I picked this particular one because the guardian candidates are all different, and none of the cells see each other:

Code: Select all

.......12..1.2345..2451...6...36..4.4..2.5.616...4...3..7....3..89...1..54.1.2...

And another:

Code: Select all

........1..2.13.4...15.6.32....523.4.2...4.56.4.36.2...67..5...23....16.8.96.....

This one has no house with a 789 triple (other than box 7, where they are given), so it can't use the relabel trick.

[edit]Not actually that hard to solve using TH, despite the 4 guardians:[/edit]

mith wrote:And another:

Code: Select all

........1..2.13.4...15.6.32....523.4.2...4.56.4.36.2...67..5...23....16.8.96.....

No need for pre-basic steps, just one step to solve the puzzle.

Code: Select all

Triplet Oddagon Forcing Chain: Each true guardian of Triplet Oddagon will all lead To: r1c13<>5,r1c13,r2c7,r4c1<>6,r12c1<>7,r1c3,r4c2<>8,r12c1<>9
4r3c5 - (4=57896)b1p24578
5r2c9 - 5r8c9 = (5-4)r8c3 = 4r7c1 - (4=57896)b1p24578
1r4c4 - 1r5c4 = 1r5c1 - (1=4)r7c1 - (4=57896)b1p24578
1r6c6 - (1=7894)r2458c4 - 4r8c3 = 4r7c1 - (4=57896)b1p24578
1r4c8 - 1r4c2 = 1r9c2 - (1=4)r7c1 - (4=57896)b1p24578

Oh, I hadn't seen that you had added this to your software. Very cool

Finished finding triple cell counts for all the min-expands and max-expands. Here are the most complicated after basics by this metric.

max-expands, 4 boxes, 5 triple cells (7 guardian cells):

Code: Select all

........1..2..3....4156...2.......75...35.2.61.5...89...6.3542.25.4.....3.42.65..;187422  ED=10.5/8.4/2.6
........1..2..3....4156...2.......75...35.2.61.5...89...4.3652.25.4.....3.62.54..;187423  ED=10.5/8.4/2.6

min-expands, 4 boxes, 2 triple cells (10 guardian cells):

Code: Select all

........1..1..2.34..4.1325....2....5.5..34.1..6...5.2..453.6...7.6....4.839.....2;144441  ED=10.9/7.1/6.6
........1..1..2.34..4.1325....2....5.5..34.1..6...5.2..453.....7.6......839....62;150580  ED=10.9/7.1/6.6
........1..2..3....4.56...2.......75...35.2.61.5...89...6.354...5.4.....3.42.65..;194607  ED=10.5/6.7/6.6
........1..2..3....4.56...2.......75...35.2.61.5...89...4.365...5.4.....3.62.54..;194608  ED=10.5/6.7/6.6
.......12....345...67...348..9.....4.753...9.6...79....569......9..5.6..7.3.6....;295950  ED=10.4/7.3/2.6
.......12....345...67...348..9.....4.563...9.7...69....759......9..5.7..6.3.7....;295951  ED=10.4/7.3/2.6

The middle min-expands are sub-puzzles of the max-expands (the two trees are transforms of one another, with 456 flipped in the bottom band). The other pairs of min-expands (again transforms) have max-expands with only two or three guardian cells.

For the 10.4s, YZF isn't able to find a TOFC until after applying an AIC and a finned swordfish, but after that, oh boy:

Code: Select all

Triplet Oddagon Forcing Chain: Each true guardian of Triplet Oddagon will all lead To: r1c12346,r457c5,r2c4<>8,r1c5<>9
3r4c2 - (3=124895)b1p234567 - (5=1298)b2p2789
4r5c1 - 4r5c5 = 4r7c5 - (4=12789)r14567c7 - (9=8)r1c5
4r6c3 - (4=12895)b1p34567 - (5=1298)b2p2789
6r5c6 - (6=13579)r56789c9 - 9r9c7 = 9r1c7 - (9=8)r1c5
4r6c4 - (4=12589)r9c24689 - 9r9c7 = 9r1c7 - (9=8)r1c5
5r6c4 - (5=12387)b6p14789 - (7=9)r1c7 - (9=8)r1c5
4r7c1 - (4=12789)r14567c7 - (9=8)r1c5
4r8c3 - (4=12895)b1p34567 - (5=1298)b2p2789
4r7c5 - (4=12789)r14567c7 - (9=8)r1c5
4r8c4 - (4=12589)r9c24689 - 9r9c7 = 9r1c7 - (9=8)r1c5
7r8c4 - (7=1289)r2c1234 - 9r2c9 = 9r1c7 - (9=8)r1c5

I've found two (closely related) min-expands with guardians exactly corresponding to the TO 4-cycle:

Code: Select all

........1..2..134...3.452.6...16.......2.3..523..5.....21....64.7.5.....89.4.....  ED=11.0/10.5/2.6
........1..2..134...3.452.6...16.......3.2..523..5....3.1....647..5.....89.4.....  ED=11.0/10.5/2.6

YZF needs brute force for these (even with uniqueness enabled, and after a couple TOFC deductions). There are probably more; I am currently looking at puzzles with no full triples anywhere in the grid, so no relabeling available.

.
This is not directly related to the Tridagon rule or to Tridagon Forcing Whips, but see here my global classification results related to the above database (in short: all the known 9x9 sudoku puzzles in T&E(3) are indeed in T&E(W2, 2) or less):
http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1321.html
These results are all the more surprising that the examples mentioned in the previous posts show that some puzzles in mith database are quite far from the Trivalue Oddagon contradictory pattern - and IMO totally impossible to find by a real player without the additional knowledge (what I call an oracle) that something related to this pattern has to be found.
.

I disagree with the notion that it would be impossible for a real player to find something related to the trivalue oddagon in these puzzles. All of these puzzles have two things in common:

1. Exactly three digits appear at most once each in the puzzle. (Either all three appear once, or two appear once and the other not at all.)
2. Those three digits, if they appear at all, are found in the same box.

These conditions are common to relabel/replacement (replacing the last word with "house", which often also applies in these puzzles.

If these conditions are met, we can then look for potential TO patterns by considering the four boxes which do not see the box specified in condition 2. Such patterns have further conditions in common:

3. A TO pattern is always row- and column- spanning within each box.
4. A TO pattern always includes any cell which is limited to the three digits specified by condition 1.

In the vast majority of the min-expands, these conditions are sufficient to identify a single impossible pattern of cells, and the guardians determined in this way can then be the target of analysis for forcing chains/nets. (In some cases, the pattern is ambiguous in a box - sometimes resulting in deductions for *each* possible pattern.)

It's not so much that the puzzles are far from the TO pattern - the pattern exists in every single one of them - but rather that in some cases the number of guardian cells is so large as to be prohibitive in finding an elimination based on the pattern. That is, we can always make a deduction of the form "at least one of these candidates is true", but such a deduction may not be useful in making progress in the puzzle.

I'm hoping with further research to nail down some statistics on the following:

a. How many of these puzzles can be solved via replacement with depth < 3 (whether or not TO is useful)? (Denis, this may be something you are already set up to determine? In the case where one digit is entirely absent, the grid(s) after replacement will be sukaku, but we can still determine the depth of these.)
b. For puzzles with no replacement (so guardians in all four boxes) - or those where replacement does not reduce depth, if any - what depth of T&E is sufficient for solving the puzzle after taking into account the TO pattern? It should be possible for any level of T&E and set of techniques within that T&E process to generate the pencilmark grid after assuming each guardian candidate in turn, and then compare the results for eliminations. (This is sort of a region-forcing generalization of T&E, I guess?)

.
Hi mith,
It seems we have the same situation as with exocets: a set of insufficient (and here not even necessary) conditions. Based on a vague and incomplete definition of exocets, David P. Bird has precisely defined a true resolution rule: J-Exocets.
The way you use the expression "TO Pattern" is ambiguous. For me, "TO" or "Trivalue Oddagon" means and only means the well defined contradictory pattern - with no "guardians" or whatever. As it is never present in a consistent puzzle, it will never be useful per se. It certainly doesn't not "exist in every single one of them" (TE3 puzzles). What possibly exists is an imaginary pattern with additional candidates.
The abstract "TO Pattern" becomes useful when one can define resolution rules based on it. That's why I've started this thread with the definition of the simplest such rule (and then added more complex rules) and I've given them specific names. And I've given pseudo-stats for each of these rules (more elaborated on the 972 database).
One could define more forcing rules in the same way, based on more than 2 "guardians".

But if a would-be "rule" is presented as: "check some criteria and then try to prove a contradiction between some candidates", then for me it's merely not a resolution rule at all and I have no easy way to define it in SudoRules.

a. I hadn't planned to check eleven's replacement technique on the full min-expands database. I have checked it on the 972 and the answer was positive. But if you're interested, I can launch these calculations. BTW, the grids after replacement are always sukakus - and replacement itself occurs in the resolution state after some rules have already been applied (typically Subsets), i.e. in sukaku grids.

b. I've already shown that eleven's replacement can be understood as a very specific form of T&E(3). So, a priori, any puzzle in T&E(3) where replacement is applicable could be reduced to T&E(0 or 1); but this remains to be checked. What you describe at the end is Forcing-T&E, which is of course totally possible on more than 2 candidates. However, what you propose as a possible starting point is ill-defined. What you consider as a potential TO Pattern could be almost anything.

denis_berthier wrote:But if a would-be "rule" is presented as: "check some criteria and then try to prove a contradiction between some candidates", then for me it's merely not a resolution rule at all and I have no easy way to define it in SudoRules.

I agree with that. The way I had hoped you would introduce TOs to your theory was in the form of TO-Braids, which could contain the two 11-cell patterns defined at the beginning of this thread (with possible missing candidates of TO-digits) alongside CSP-variables.

A possible "more human-like" approach would require a modification of the pencilmarking system used – special pencilmarks for TO-guardians, which could then be used in arbitrary patterns.
This makes the "rule" simple – a potential TO => pencilmark for guardians.
As you wrote, "a potential TO" has to be defined.
A set of 12 cells that could be restricted to TO-digits creating a TO without creating an obvious contradiction. But what does obvious mean?
A contradiction within one of the TO houses? A contradiction with singles?
An advantage of this approach is that it would allow for simple implementation of remote triples within one of the 11-cell patterns and the remote quadruple in these puzzles (emerges after eliminating 789r5c12 and 46r1c3 when assuming 23r7c12 and eventually leads to a contradiction with gB2 steps, later can also be used to eliminate 789r1c67):

mith wrote:

Code: Select all

........1..2..134...3.452.6...16.......2.3..523..5.....21....64.7.5.....89.4.....  ED=11.0/10.5/2.6
........1..2..134...3.452.6...16.......3.2..523..5....3.1....647..5.....89.4.....  ED=11.0/10.5/2.6

Marek

You can indeed define some sort of Chromatic-Forcing-T&E which is very broad:

1. Given any pattern of cells which is not k-chromatic, and any k digits such that every cell in the pattern has at least one of these digits as a candidate: let the "guardian candidates" be all candidates in those cells which are not among the k digits specified. (Note: the restriction of every cell containing at least one of the k digits is to prevent the degenerate case of a trivial guardian cell. Not strictly necessary for the definition, but you're looking at a simple Cell Forcing or Forcing-T&E analogue in this case.)
2. Trivially, at least one guardian candidate is true.
3. We can therefore eliminate any candidate such that, for all guardian candidates, the assumption of the guardian candidate true leads to the target candidate being false (under whatever resolution rules specified for T&E). Likewise, we can assert any candidate such that, for all guardian candidates, the assumption of the guardian candidate true leads to the target candidate being true.

Obviously, this is far too broad to be useful - there are too many potential patterns of cells to check, and for some patterns too many choices of k digits as well. But it is clearly well-defined as a resolution rule, with the last being an extension of your Forcing-T&E and Forcing{3}-T&E from bivalue or trivalue cells (rc-, rn-, cn-, or bn-) to a more general case of a set of candidates at least one of which must be true. (In fact, while we have so far really only considered rc-cells when discussing chromatic patterns, there's no particular reason to limit the definition in this way.)

The TO pattern I'm discussing - specifically the impossible 12-cell 4-box row-/column-spanning 4-chromatic kind used in your tridagon and tridagon-links resolution rules - is not nearly so broad. Note: When I say TO pattern here, I am not talking about the contradictory/impossible pattern of those 12-cells only containing 3 candidates; I am talking about the 4-chromatic pattern of 12-cells itself. Such patterns are obviously *always* present in sudoku grids, and in large numbers (5832 of them, if I've got my counting right). We could even just check all of these possible patterns (the majority of which could be skipped due to already containing givens - in this case, I believe something simpler is always available) and combinations of digits within them (again subject to the restriction that every cell in the pattern contains at least one of these digits). This may even be what YZF_Sudoku does in its implementation?

However, here we can further motivate the choice of cells and digits by first considering the grid as a whole - if the first two conditions of my previous post are met, we have our choice of digits and boxes, and the remaining conditions further limit the cells of the pattern (there is an unwritten condition 5. here - that the pattern chosen has to be 4-chromatic; I've seen a handful of cases where the parity in one box is not forced directly by the pattern of givens, but must be chosen such that there is an odd number of boxes with each parity). Here, I am not defining a new resolution rule - the resolution rule remains the same as defined above. I am only narrowing down the choices of patterns and digits which merit further consideration. We don't necessarily have to narrow them down quite so far - it's certainly possible that there could be TO-Forcing-T&E() eliminations in a grid not meeting condition 1 of the previous post, say - but the focus here is on the puzzles known to be in depth 3, all of which meet these conditions.

Anyway, we are very far from my original comment, which had nothing to do with well-defined resolution rules, and instead was focused on real players. This is how I, as a real player, think about looking for TO patterns and TO-Forcing deductions. I happen to know in looking at this set of puzzles that such patterns are relevant, but having that "oracle" is not at all necessary for me (or others) to use them - much like MSLS/SET or Exocets, human players develop tools to identify where such techniques might be useful, and how to find them when they exist. In the case of MSLS/SET, it's recognizing a pattern of aligned given. For replacement/relabel, it's seeing a full house and givens/filled digits missing outside of that house. Here, it's digits missing outside of a box (specifically) which is not necessarily full.

Whether you can code that human process into SudoRules, I don't know - but it's certainly possible to find these algorithmically (again refer to YZF_Sudoku's implementation; or my own scripts finding which puzzles have certain properties in terms of guardian counts and the like).

.
First, just a few points that may show we are not speaking of the same things. For me:
- having 11 (or any number of) candidates related by an OR relation doesn't make a CSP-Variable (2 or more of them can be True).
- a pattern is well defined if it can only be either present or absent in a resolution state. If you have to add conditions or processes to find it, it's not a pattern.
- I'm not interested in patterns that do not support any resolution rule.
- I'm not interested in algorithmic solutions of Sudoku; there's already a perfect one: DFS. I'm interested in 100% pattern-based solutions. I'm not saying that no one may have different interests.

I agree that what I've defined as Tridagon-links and Tridagon-Forcing-Whips based on them could be extended to be based on more than two candidates. Defining Tridagon-k-Forcing-Whips would raise no technical problem (apart possibly a problem of computational complexity for a large number k of "guardians". However, the problem would remain of defining in a 100% pattern-based way these Tridagons-k-links for large k. None of the above suggestions provides a definition.

I am not sure which of these points are related to mith's post and which are related to mine.

denis_berthier wrote:having 11 (or any number of) candidates related by an OR relation doesn't make a CSP-Variable (2 or more of them can be True).

I believe that this reacts to my description of TO-Braids. I admit that I had forgotten B2B notation for a moment.
Initially I expected you to implement TO-Braids, where the two 11-cell patterns (or just the 12-cell contradiction pattern, at the very end) would also be used as rlcs.

denis_berthier wrote:a pattern is well defined if it can only be either present or absent in a resolution state. If you have to add conditions or processes to find it, it's not a pattern.

The conditions proposed by mith and me aren't necessary, they aim to filter out useless patterns.
There are a few things to be careful about:
If the TO leads to a contradiction with singles, it doesn't change the T&E depth and can be ignored, but only if only the contradictory pattern is used in the T&E (it could always be substituted by said contradiction with singles; if the 11-cell patterns are used as well, it may reduce the depth in some cases). It might not be a suitable filter for some applications.

mith wrote:When I say TO pattern here, I am not talking about the contradictory/impossible pattern of those 12-cells only containing 3 candidates; I am talking about the 4-chromatic pattern of 12-cells itself. Such patterns are obviously *always* present in sudoku grids, and in large numbers (5832 of them, if I've got my counting right). We could even just check all of these possible patterns (the majority of which could be skipped due to already containing givens - in this case, I believe something simpler is always available)...

This might be true, depending on how one defines "simpler", however I doubt that any of the TO-with-one-given patterns are checked for (unless we consider B2B simpler than TO).
(The number is correct, if we also take into account the 84 combinations of three digits, we are just short of half a milion.)

denis_berthier wrote:I'm not interested in patterns that do not support any resolution rule.

This might react to my suggestion of extending the pencilmarking.
In that case adding such a pencilmark would mean progress in the resolution process much like an elimination of a candidate does – there is only a finite amount of these pencilmarks you could have (as there is a finite amount of TOs they could come from), therefore it wouldn't produce any convergence issues (unlike for example relabeling back and forth) – provided other rules would be capable of using these pencilmarks.

Marek