The New Sudoku Players' Forum

[daj95376]

Just consider all morphs of a puzzle ...

The key point seems to be that you are using the givens in the puzzle and not the solution in your canonical process. The secondary point is that you are looking for the largest value -- instead of the smallest. This would explain (to me) why all of your puzzles in the "02 index.txt" file have <9> in r1c1 and why the givens in [row 1] for each puzzle are assigned by decreasing value -- treating non-given cells as <0>.

[champagne]

Just consider all morphs of a puzzle ...

The key point seems to be that you are using the givens in the puzzle and not the solution in your canonical process. The secondary point is that you are looking for the largest value -- instead of the smallest. This would explain (to me) why all of your puzzles in the "02 index.txt" file have <9> in r1c1 and why the givens in [row 1] for each puzzle are assigned by decreasing value -- treating non-given cells as <0>.

right in all your remarks,

but a canonical form on the solution has no definition if the puzzle has anything else that one solution and could not be defined on a partial puzzle at generation time
same for the study of symmetries in morphs, it must be done on the given pattern.

champagne

[daj95376]

right in all your remarks,

but a canonical form on the solution has no definition if the puzzle has anything else that one solution and could not be defined on a partial puzzle at generation time
same for the study of symmetries in morphs, it must be done on the given pattern.

I'm not versed enough on partial puzzles to contribute to that portion of your discussion. However, I do see a distinction when a puzzle does have a single solution.

I believe these two puzzles will give distinct results when processed with your algorithm:

Code: Select all

9876..5..4...9..6......8...3...6..9....2..7.......5..21.........46.3.....391...4.
9876..5..4...9..6......8...3...6..9....21.7.......5..21.........46.3.....391...4.


However, row MinLex sees their solutions as being equivalent:

Code: Select all

123456789456789123789132564298614375341527896675893241512948637864371952937265418
123456789456789123789132564298614375341527896675893241512948637864371952937265418


Of the 31,804 puzzles in your "02 index.txt" file, there are only 26,491 distinct row MinLex solutions.

[champagne]

I'm not versed enough on partial puzzles to contribute to that portion of your discussion. However, I do see a distinction when a puzzle does have a single solution.

I believe these two puzzles will give distinct results when processed with your algorithm:

Code: Select all

9876..5..4...9..6......8...3...6..9....2..7.......5..21.........46.3.....391...4.
9876..5..4...9..6......8...3...6..9....21.7.......5..21.........46.3.....391...4.


However, row MinLex sees their solutions as being equivalent:

Code: Select all

123456789456789123789132564298614375341527896675893241512948637864371952937265418
123456789456789123789132564298614375341527896675893241512948637864371952937265418


Of the 31,804 puzzles in your "02 index.txt" file, there are only 26,491 distinct row MinLex solutions.

Nothing to object to the fact that several "given puzzles" can have the same solution.

I have in mind tarx104 and tarx105 for example. Both are a minimal form of the same puzzle with one more given if you just add a single.
and they have a different canonical minlex form as well if you take the most common definition of the minlex form (on given).

Just another question to be clear

your 2 puzzles don't have the same number of given.
How could it be that the canonical form of the given would be the same, whatever is the canonicalization process


It looks as if you were glued in your concept of canonical form of the solution

champagne





-

[ronk]

Reviewing the defining post and taking the various points on board, will this re-work pass muster?

A few recommendations:

The different cell pairs occur in different boxes in the same band (the JExcoet band). The three cross-lines intercept this band as shown, passing through the target cell pairs but not the base cell pair.
...
2) Target pairs must have one cell that contains at least one base candidate (the target cell) and the other that contains none of them (the empty companion cell)

The "target pair" term should be reserved for the 'T pair." That the target pair is comprised of one each of the "Q pair" and "R pair" is a minor property of the pattern. BTW my geometry teacher might have given me a "D-" for using "intercept" instead of "intersect."

3) Outside the JExocet band no base digit should be capable of simultaneously occupying more than two of the cross-line cells . This is satisfied when the all occurrences of a digit in these external cells ...

Writing "External to the JExocet band ..." would clarify the connection between the two sentences. That "no base digit should" refers to the base digits individually rather than collectively is unclear; instead use "each base digit cannot". Furthermore, "occupying" conjures up visions of givens and placements, but not candidates; "appearing in" might be better.

a digit in these external cells, including any that are given or solved, can be covered by no more than two lines.

With "line" here meaning 1) two lines each intersecting the cross-lines, 2) one cross-line and one such intersecting line, or 3) two cross-lines, I think it's safe to say the "lines" terms is overused. As a result, IMO the scope of the JExocet term should be downsized to case 1) only. After all, early on that included all but 45 or 46 of champagne's 24,000+ exocets IIRC. Why complicate things for just a few more?

[David P Bird]

Reviewing the defining post and taking the various points on board, will this re-work pass muster?

A few recommendations:...

Thanks for your time in providing a critique. As I was pitching this definition for players who had passed the novice stage, I wanted to make it as concise as possible. This is why I prefer to use "line" rather than "row or column" and "band" rather than "tier or stack".

I've considered all your points and have actioned those that I consider most pertinent as you will see <here> .

I chose to use "outside the JExocet band" and follow it with "in these external cells" for the benefit of those with English as a second language, as the "external" adjective is effectively superfluous.

The problem with down-grading the pattern to covering just one distribution of the candidates in the S cells is that it would then spawn off two sub-types to handle the others. Considering that the search pattern has now been extended, we don't know for sure how frequent each one will be.

[daj95376]

Nothing to object to the fact that several "given puzzles" can have the same solution.

I have in mind tarx104 and tarx105 for example. Both are a minimal form of the same puzzle with one more given if you just add a single.
and they have a different canonical minlex form as well if you take the most common definition of the minlex form (on given).

Just another question to be clear

your 2 puzzles don't have the same number of given.
How could it be that the canonical form of the given would be the same, whatever is the canonicalization process


It looks as if you were glued in your concept of canonical form of the solution

It appears that we have an apples and oranges perspective on canonicalization. This quote seems to explain our differences.

most of the sudoku canonicalization algorithms are row-order minlex based on some property of the 81-char grid

row-order means that the grid is read by row, top to bottom

minlex means minimum lexical value of the 81-char string

valid sudoku transformations (row/col within band/stack, band<->band, stack<->stack, values)

sort all possible transformations for the 81-char string for one puzzle and select the lexicographic smallest, and you have the row-order minlex canonical representation for the puzzle

the two canonicalization forms provided by my solver are:
%c row-order minlex based on the solution grid (benefit: fast, drawback: puzzle must have one solution)
%#mc row-order minlex of puzzle grid (benefit: works on pseudo puzzles, drawback: slower as #clues increase)

Rudd (sic) also has a pattern based minlex canonicalization that has two stages:
treat the clues as value 1 and determine the minlex pattern
then add in the clue values and determine the minlex string that has the same clue positions as the minlex pattern
I have not implemented this yet

I've always concentrated on the blue way of canonicalizing a puzzle. This form of canonicalization will consider the two example puzzles as equivalent.

Your approach seems to be a maxlex variant of Ruud's teechnique mentioned in gsf's quote. This form of canonicalization will consider the two example puzzles as non-equivalent.

Then there's this perspective:

To determine if one puzzle is a scrambled version of another and they are essentially the same, we must first canonicalise the two solution grids and secondly, if they match, then canonicalise the puzzle grids to see if the givens match too.

[Edit: removed incorrect paraphrase of above statement.]

I did this to your 31,804 puzzles and it resulted in the same number of unique puzzles.

[ronk-Moderator]

I apologize for asking "what is 'maxtext' canonicalization" in this thread. I expected little more than a single post answer. Instead this topic has taken on a life of its own, so ... so much for expectations. As a result, unless there is a convincing objection, I'll split out this topic into a new thread ... in whatever sub-forum already contains c14n threads.

[champagne]

I've always concentrated on the blue way of canonicalizing a puzzle. This form of canonicalization will consider the two example puzzles as equivalent.

Your approach seems to be a maxlex variant of Ruud's teechnique mentioned in gsf's quote. This form of canonicalization will consider the two example puzzles as non-equivalent.

Then there's this perspective:

To determine if one puzzle is a scrambled version of another and they are essentially the same, we must first canonicalise the two solution grids and secondly, if they match, then canonicalise the puzzle grids to see if the givens match too.

This can be viewed as partitioning the puzzles by the number of givens, and then performing canonicalization on each partition.

I did this to your 31,804 puzzles and it resulted in the same number of unique puzzles.

First of all, I agree on ronk's proposal to switch all that in a specific thread.

To make it short, (nothing against your writing)

the main target is to eliminate morphs of a puzzle (seen as given)
surely, they would give the same solution if there is one

believe me, there is no need for that to know whether the puzzle have no, one or many solutions
you just have to work on valid permutations

These puzzles must have the same number of given and they share all valid permutations.

The canonicalization of the solution is quite another issue.

champagne

[daj95376]

Here's what I suggest for labeling JExocet puzzles with any additional constraints.

Hidden Text: Show

Code: Select all

Puzzle: Platinium Blonde

.......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6...

 +--------------------------------------------------------------------------------+
 |  35678   34589   34679   |  4679    5689    4578    |  679     1       2       |
 |  15678   14589   4679    |  124679  125689  124578  |  679     56789   3       |
 |  15678   1589    2       |  3       15689   1578    |  4       56789   6789    |
 |--------------------------+--------------------------+--------------------------|
 |  237     2349    1       |  8       236     234     |  23679   679-234 5       |
 |  235     6       349     |  124     7       12345   |  8       2349    149     |
 |  23578   23458   347     |  1246    12356   9       |  12367   23467   1467    |
 |--------------------------+--------------------------+--------------------------|
 |  1236    123     8       |  5       1239    1237    |  123679  4679-23 4679-1  |
 |  9       123     36      |  127     4       12378   |  5       23678   1678    |
 |  4       7       5       |  129     12389   6       |  1239    2389    189     |
 +--------------------------------------------------------------------------------+
 # 192 eliminations remain

 ### -679- JExocet + SL   Base = r12c7   Target = r4c8,(4)r7c89


Code: Select all

Puzzle: #3323 in "02 index.txt"

98.7..6....5.6.......9.4...4..3..9..37...8.....6.9......2.1.3.........52........1

 +-----------------------------------------------------------------------------------------+
 |  9        8        134      |  7        235      1235     |  6        1234     345      |
 |  127      1234     5        |  128      6        123      |  12478    4789-123 4789-3   |
 |  1267     1236     137      |  9        2358     4        |  12578    12378    3578     |
 |-----------------------------+-----------------------------+-----------------------------|
 |  4        125      18       |  3        257      12567    |  9        12678    5678     |
 |  3        7        9        |  12456    245      8        |  1245     1246     456      |
 |  1258     125      6        |  1245     9        1257     |  124578   123478   34578    |
 |-----------------------------+-----------------------------+-----------------------------|
 |  5678     4569     2        |  4568     1        5679     |  3        4789-6   4789-6   |
 |  1678     13469    13478    |  468      3478     3679     |  478      5        2        |
 |  5678     34569    3478     |  24568    234578   235679   |  478      46789    1        |
 +-----------------------------------------------------------------------------------------+
 # 183 eliminations remain

 ### -478- JExocet + SLs   Base = r89c7   Target = (9)r2c89,(3)r6c89


Code: Select all

Puzzle: #4593 in "02 index.txt"

98.7..6..5...94.....3......4...3..9..2.8..1....9..5..6..7.829.........61.........

 +--------------------------------------------------------------------------------+
 |  9       8       124     |  7       125     13      |  6       12345   2345    |
 |  5       167     126     |  1236    9       4       |  2378    12378   2378    |
 |  1267    1467    3       |  1256    1256    8       |  2457    12457   9       |
 |--------------------------+--------------------------+--------------------------|
 |  4       1567    1568    |  126     3       167     |  2578    9       2578    |
 |  367     2       56      |  8       467     9       |  1       3457    3457    |
 |  1378    137     9       |  124     1247    5       |  23478   23478   6       |
 |--------------------------+--------------------------+--------------------------|
 |  136     13456   7       |  13456   8       2       |  9       345     345     |
 |  238     3459    2458    |  3459    457     37      |  234578  6       1       |
 |  12368   3459-16 124568  |  3459-16 14567   1367    |  234578  234578  234578  |
 +--------------------------------------------------------------------------------+
 # 167 eliminations remain

 ### -345- Jexocet + X-Wing   Base = r7c89   Target = (9)r89c24


And then, there's this interesting double JExocet. The only one that I encountered among all 31,804 puzzles in the file.

Hidden Text: Show

Code: Select all

Puzzle: #33780 in "02 index.txt"

98.7..6..7......9.....5....6.45...7...86..45.......3...6...2..4.1.........78...6.

 +--------------------------------------------------------------------------------+
 |  9       8       1235    |  7       1234    134     |  6       1234    1235    |
 |  7       2345    12356   |  1234    123468  13468   |  1258    9       12358   |
 |  1234    234     1236    |  12349   5       134689  |  1278    12348   12378   |
 |--------------------------+--------------------------+--------------------------|
 |  6       239     4       |  5       12389   1389    |  1289    7       1289    |
 |  123     2379    8       |  6       12379   1379    |  4       5       129     |
 |  125     2579    1259    |  1249    124789  14789   |  3       128     6       |
 |--------------------------+--------------------------+--------------------------|
 |  358     6       359     |  139     1379    2       |  15789   138     4       |
 |  23458   1       2359    |  349     34679   345679  |  25789   238     235789  |
 |  2345    23459   7       |  8       1349    13459   |  1259    6       12359   |
 +--------------------------------------------------------------------------------+
 # 184 eliminations remain

 ### -1234- JExocet + SL   Base = r1c56   Target = r3c8==r2c2,(6)r23c3

 ### -1234- JExocet        Base = r3c12   Target = r1c8,r2c4==r1c9


[ronk]

Here's what I suggest for labeling JExocet puzzles with any additional constraints.
...
### -679- JExocet + SL Base = r12c7 Target = r4c8,(4)r7c89
...
### -478- JExocet + SLs Base = r89c7 Target = (9)r2c89,(3)r6c89
...
### -345- Jexocet + X-Wing Base = r7c89 Target = (9)r89c24

Looking at them as a single exocets is a big improvement IMO. The possible positions for the strong links is rather limited, however, (as opposed to Mike Barker's AURs, for example) so being more specific wouldn't hurt. For instance, I see "triple targets" and "quad targets." Also, the x-wing POV doesn't lead to any additional exclusions, so naming it differently than the general 2 SL cases doesn't help AFAICS.

And then, there's this interesting double JExocet. The only one that I encountered among all 31,804 puzzles in the file.

Another nice find, a "twin double exocet", I suppose.

[David P Bird]

There's sense in these notations and they may suit the purposes of those using forcing chains or Nice Loops.
-679- JExocet + SL Base = r12c7 Target = r4c8,(4)r7c89
-478- JExocet + SLs Base = r89c7 Target = (9)r2c89,(3)r6c89
-345- Jexocet + X-Wing Base = r7c89 Target = (9)r89c24

Translated into a Eureka style these could condense to:
(679)JE:r12c7,r4c8,(4)r7c89
(478)JE:r89c7,(9)r2c89,(3)r6c89
(345)JE:r7c89,(9)r89c24

There is a set order for defining the base cells before the target cells, so these don't need spelling out.
When a target is shown as a cell pair with an extra digit, its also self evident what is happening so it doesn't need the "+ SL"

That doesn't mean that writing walk throughs wouldn't benefit from having suitable adjectives for describing different conditions which I believe was one of champagne's aims.

When compatibility checks show that the base cells must contain one or other pair of digits we can also get inferences such as
(1)r1c6 - (12=34)JE:r1c23,r2c4,r3c7 – (4)r1c7

There can also be Almost JE's that would be established if a digit could be eliminated from the base cells (making it a non-member) or when a member digit can be eliminated from a cross-line cell so that it would comply with condition 3.

It will be a matter of style how much explanation should be provided in justifying the eliminations that the pattern provides both when it is first identified and later when the true base digits are identified, as this depends somewhat on configuration of the target cells. I'll say this though, once the topic is no longer current, it will be difficult to remember just how may inferences are available. For example see <here>.

It's also easy to overlook knock-on inferences in the mini-lines holding the target cells when the valid options are restricted.

[champagne]

That doesn't mean that writing walk throughs wouldn't benefit from having suitable adjectives for describing different conditions which I believe was one of champagne's aims.

sure

telling we have an exocet does not describe it.

same for "twin exocet" "quad exocet" or whatever could be the final name.

regarding writing rules to describe it, I generally use sentences, but I am not a regular player.
I must confess that I have some difficulties to decipher paths described with such writing rules

but oher have as well some difficulties to decipher my solutions

[ronk]

I run the same test on my 2.4 GHz labtop
24411 puzzles 0.973 second
it seems that we are not in the same order of magnitude.

That's impressive. I may be using gsf's program in an inefficient manner. I'll ask him via PM.

I am not so sure this comes from a bad use of gsf's program. I had similar results with the prior version. Dobrichev pushed me to revise my code. Gridchecked was much better, (but in "pattern" mode)

Turns out I was using gsf's program improperly. With options "-q- -f%#mc", the (edit: clue) canonicalization rate is about 14,000 puzzles/sec/GHz, rather than my previously reported 280 puzzles/sec/GHz.

That's 24,411 puzzles in approx 0.63 sec on my 2.8 GHz desktop.

[champagne]

Hi leren,

Welcome here with that terrific entry.

It's clear that nobody thought of revising that list for twin exocets, not identified when the list was created.
.
Later to-day, i'll go deeper to cross check your results

[ronk-moderator edit: This reply to Leren's post and follow-on discussion moved here, with "book-keeping" type posts deleted. Selective restoration is possible, if requested via PM. However, David P Bird, I accidentally lost your post to daj95376 during the move, sorry.]