The New Sudoku Players' Forum

[re'born]

If you think there is no problem is stating that we have a solution when the rule we claim to use in it isn't even defined, that's a strange conception of "logical reasoning".

"Strange" in the same way that accusing ronk and I of being the same person is a strange form of ethical behavior? The upshot is your consistency. You're wrong in both cases. Ron presented you with a grouped nice loop, a perfectly well defined extension of nice loops, used for quite some time by the members of this forum.

But I figured, "maybe he needs everything written in the form of rules corresponding to the ones he is using." So, in response to what I thought were questions you legitmately wanted to have answered, I tried to write up some rules using your notation that would extend your nrc-chains to grouped nrc-chains, and eventually to grouped nrctz-chains.

But,

This is not the way I work.

Well now you've got me confused. What is the way you work? When I posted on almost xy-chains in a thread that was not intended to be a treatise, but a tutorial, you wrote

Generally speaking, saying which tricks we used to solve one or two puzzles and providing comments as to a generalisation, is very far from having formulated a general rule.

But when I post a general setup, you refuse to respond to what I did except to call them "imaginary rules".

Do you not like to collaborate? If you find my definitions lacking, please point out where they might be improved. I've made no claims about them being the correct definitions (in fact, I think Mike Barker would find some improvements).

I leave to participants in this forum the freedom to judge by themselves whether my rules and examples are interesting or not.

You're missing the bloody point. We're not questioning whether what you're doing is interesting. We're only trying to understand, perhaps suggest improvements or alternatives, and most of all have fun.

Speaking of fun, welcome to the forum champagne. That puzzle you just posted is going to have me scratching my head for some time (I do all of my solving by computer-aided hand). I'll be very interested to see how your program cracks it so fast. I just noticed that your "step 1" includes a group extension to Bon Hanson's techniques. Presumably, this means that your solver uses grouped 3D-chains. Is that accurate? If so, perhaps you might offer Denis a definition of the corresponding rules as he doesn't seem to think they exist and ronk and I (who most assuredly are not the same person) have not been up to the challenge of properly defining things for Denis.

[denis_berthier]

Champagne, consider this only as a quick answer.
I'm aware that I should have answered you sooner, but I haven't yet had time for trying your examples and I therefore don't have much to say. But I'll do.
If you have efficient well defined resolution rules, that's great.
I'm currently thinking of what should be added to my solver in order to deal with cases that it cannot yet solve (1/10,000 of the random puzzles).

My main interest is in explicit resolution rules that do not require any additional ad hoc reasoning to glue pieces together.

What's the French Forum you are speaking of? I was not aware of anything like that. Anyway, I'm not sure many people here look at the French forum and I think you should post here more about your solver.

The grid I gave here as a hard example (#707) is one of the hardest but it is still far away from being THE hardest.

[champagne]

re'born wrote

Speaking of fun, welcome to the forum champagne.
That puzzle you just posted is going to have me scratching my head for some time (I do all of my solving by computer-aided hand).
I'll be very interested to see how your program cracks it so fast.
I just noticed that your "step 1" includes a group extension to Bon Hanson's techniques.
Presumably, this means that your solver uses grouped 3D-chains. Is that accurate?

Thank you first for welcoming.

1) I don't know precisely what is behind 3D-chains, but what I am doing in step one is very simple.

In Bob Hanson's logic, strong links of the same digit are limited to two candidates of the same digit in one object (row,colum,box).
Extension to group considers sets of candidates of one digit common to two objects (row/box, column box).
New strong links appear when you have two groups or one group and one isolated digit in one object.

It seems very simple, but the additionnal power is huge and this is still managable by hand (my step one is designed to be a kind of coach to skill manual solvers.)

I assume altenate chains produced out of groups are what you call 3D_chains. Anyway, solving the grid I posted request use of groups, so we will check.

2) Cracking of the puzzle, can I use my print with "chess notation" which is the normal way used in FRANCE.

This puzzle enter step 2, but not step 3.

[denis_berthier]

If you find my definitions lacking, please point out where they might be improved. I've made no claims about them being the correct definitions
(…)
We're not questioning whether what you're doing is interesting. We're only trying to understand, perhaps suggest improvements or alternatives, and most of all have fun.
(…)
perhaps you might offer Denis a definition of the corresponding rules as he doesn't seem to think they exist and ronk and I (who most assuredly are not the same person) have not been up to the challenge of properly defining things for Denis.

The question is not whether the rules exist or not. I have no doubt that grouped nrc(z)(t) chains can easily be defined (and, of course, you can try to write them).
All the rules we are speaking of are extensions of NLs / "basic" AICs / nrc-chains. As appears from comparisons done in the Eureka forum, there is much overlap between all these extensions. Moreover, each of these extensions is very likely to be enough to solve any puzzle a human being will ever be able to solve (I mean unaided by a computer).
When we combine all of them, we also combine their complexities.
Before doing so, I'm looking for examples for which it is necessary. Just a question of priorities. Rules based on subsets are not high in my priorities, but I understand it may be different for other people.

[re'born]

If you think there is no problem is stating that we have a solution when the rule we claim to use in it isn't even defined...

The question is not whether the rules exist or not.

Well, that clears it up.

[champagne]

Hello re'born,

You didn't tell me if I can use my "chess notation".
Unhappily, I'll have to disappear for nearly a fortnight starting to-morrow afternoon.
I think it's fair to answer quickly to how my computer solved the puzzle, giving room for questions.


Some preliminary remarks:

1) Processing of that puzzle lasted 4.7 seconds. This normally reflects puzzles of the family "hardest puzzles".
Looking at the track print, I noticed a strong discrepancy. I was waiting for a long print and it wasn't.
There was something special in that puzzle.

2) We have a quick end. This is not the standard for my program which is designed to follow a very progressive path, doing all possible clearing in each step.
In fact,
- we are jumping directly in step two,
- two chains are extremely active in solving.

3) When I had a look to the start, I saw nearly no "bivalue cell" which is not in favour of xyzt chains, that's why I thought of a kind of "worst case".

Here is the print of candidates (tagged, but we can forget tags) at the start after basic cleaning.

Code: Select all

__ A________ B____ C_____ |D______ E______ F_____ |G________ H_____ I
1||23567____ 23567 256___ |35å6___ _______ 1a2S6e |_________ 1A37
2||234Á5689b 23568 ______ |3456Ê9B 2345___ ______ |2358_____ 3k8K__ 2V35j
3||2345789__ 23578 24â589 |3459___ 1o2345_ 1249__ |1q2W35é78 1378

4||16789____ 1678_ ______ |_______ 147____ 148g9_ |4h6H_____ ______ 179
5||12c579___ _____ 2C59__ |3x5æ79_ _______ 1l9L__ |1378d____ 1378D9 1379
6||156789___ 15678 5689__ |34579__ 13À45È7 148G9_ |4H6h_____ ______ 13x79

7||1m23y45__ _____ 245___ |46e7___ 247____ 2u46E_ |1235ç7___ 1347
8||23468____ 23z68 2468__ |_______ 247ì9f_ ______ |237______ 346i79 2379
9||12456____ 1n256 ______ |_______ 249F___ ______ |125______ 146I9_ 1P25J9

and here what did the solver ( |*H7H8H9 means inside H7H8H9 which is the "Almost cell" complementary to ALS H1H2H3H4)

#1H9
[]9H5/9F5_1F5/1F1_1H1/1H9
[]9H9/1H9
[]9H8/6H8_6H9/1H9

#4(E2E3E6)
[]4(E2E3E6)/1(E3E6)|*E2E3E6 _1E4/1F5_9F5/9H5_9(H8H9)/4(H8H9)|*H8H9 _4H7/4(D7F7)_4(E7E8E9)/4(E2E3E6)

#1H7
[]1H7/9(H8H9)|*H7H8H9_9H5/9F5_1F5/1F1_1H1/1H7

The key chain is the second one leading to 49 pair in A2D2 and

1 B2=6 L
some additionnal cleaning in row2 and uniqueness applied to
=H2=38 G2=2358 H5=13789 G5=1378 lead to

Code: Select all

__ A______ B____ C_____ |D_____ E_____ F_____ |G_______ H_______ I
1||2357___ 2357_ 2m5M__ |35ê6b_ ______ 1a2T6B |________ 1A37
2||4c9C___ _____ ______ |4C9c__ 2u3y5Ë ______ |2358d___ 3d8D____ 2X35l
3||2345789 23578 24æ589 |3459__ 1p235_ 124è9_ |1Q2u35Ë7 137

4||16e789_ 178__ ______ |______ 14Ç7__ 148k9_ |4e6E____ ________ 179
5||12f579_ _____ 2F59__ |3z5ì79 ______ 1n9N__ |178D____ 1Q3Å78d9 1379
6||156789_ 1578_ 56i89_ |34579_ 13Â5Î7 148K9_ |4E6e____ ________ 13z79

7||1g23À45 _____ 245___ |46B7__ 247___ 2w46b_ |1G235í7_ 347
8||23468__ 23Á8_ 246I8_ |______ 2479j_ ______ |237_____ 346h79__ 2379
9||12456h_ 1o25_ ______ |______ 249J__ ______ |125_____ 46H9____ 1R25L9

two small cleaning sequences

#5C3
[]5D5-ì/5D1_5(A1B1C1)/5C3
[]5C5/5C3
[]5A5/2A5_2C5/2C1_5C1/5C3

#2A7
[]5G7-í/1G7-G_1A7-g/2A7
[]5C7/5C1-M_2C1-m/2C5_2A5-f/2A7
[]5A7/2A7

(I didn't check whether they can be skipped)

and this extraordinary efficient loop :

Code: Select all

__ A______ B____ C____ |D_____ E_____ F_____ |G_______ H_______ I
1||2357___ 2357_ 2m5M_ |35ê6b_ ______ 1a2T6B |________ 1A37
2||4c9C___ _____ _____ |4C9c__ 2u3y5Ë ______ |2358d___ 3d8D____ 2X35l
3||2345789 23578 24æ89 |3459__ 1p235_ 124è9_ |1Q2u35Ë7 137

4||16e789_ 178__ _____ |______ 14Ç7__ 148k9_ |4e6E____ ________ 179
5||12f579_ _____ 2F59_ |3z5ì79 ______ 1n9N__ |178D____ 1Q3Å78d9 1379
6||156789_ 1578_ 56i89 |34579_ 13Â5Î7 148K9_ |4E6e____ ________ 13z79

7||1g3À45_ _____ 245__ |46B7__ 247___ 2w46b_ |1G235í7_ 347
8||23468__ 23Á8_ 246I8 |______ 2479j_ ______ |237_____ 346h79__ 2379
9||12456h_ 1o25_ _____ |______ 249J__ ______ |125_____ 46H9____ 1R25L9

[]9H5/9(A5C5D5)_9(F5H5I5)/9C5_9(C3C6)B/5(C6C7)|*C3C6C7C8 _5(C1C5)/5C7_5(A7G7)/3(A7G7)|*A7G7_3H7/3(H1H2H3H5)_3(H7H8)/9(H8H9)|*H7H8H9

(followed by that chain likely useless)

[]4(D7E7F7)/4H7_4(A7C7)/4(D7E7F7)

It's nearly done.

[re'born]

Hello re'born,
You didn't tell me if I can use my "chess notation".

I'm sorry. While chess notation is not the standard around here, I think we can all cope with it.

Unhappily, I'll have to disappear for nearly a fortnight starting to-morrow afternoon.

Whatever the reason is for your disappearance, have a safe journey.

One quick observation:

3) When I had a look to the start, I saw nearly no "bivalue cell" which is not in favour of xyzt chains, that's why I thought of a kind of "worst case".

I would have thought this as well, but many of the chains in Denis' output are using very few bivalue cells. It seems that the z-extension is very powerful in that regard.

I'll have to get back to you on your solution. It will take me a little time to decipher the notation. But I am very excited to see how it works.

Cheers

[ronk]

Hello re'born,

You didn't tell me if I can use my "chess notation".

Unless you're only expecting one listener, wouldn't it be more efficient for the sole speaker of a foreign language to be the one to hire the translator

[champagne]

ronk wrote

Unless you're only expecting one listener, it would obviously be more efficient for the sole speaker of a foreign language to be the one to hire the translator

I am not sure I caught your point

If your message is that I have to prepare a print following your rules in case I would have to post other messages, I fully agree.

[denis_berthier]

champagne
As a complement to ronk's answer about bivalues:
- xyzt chains need at least one bivalue,
- nrczt chains need at least one bivalue OR one conjugate pair; I have no example of a puzzle which has none of these (even EasterMonster); anybody got one?

Forget anything I said about this puzzle:
000080904
001007000
000000006
003200050
040060000
000000020
090000008
000105000
007803000
I was so sure you were speaking of Sudogen0 #707 that I didn't check, but now I realise you were speaking about quite another puzzle. I don't know where it comes from. Anyway, SudoRules cannot solve it.

About your solution, I don't understand any step in it.
I can see lots of tags on your candidates. You say we can forget tags. But is it so sure? If we can forget them, why do you have to put them? Aren't you using some form of tagging/colouring, i.e. some form of uncontrolled constraints propagation which would amount to T&E? (I must say that the algorithm you described so succinctly in your first post gave me that impression and this may be an unconscious reason for my late answer).
To make this clear, could you state the rules you are using?
Could you give a complete step by step sequence of eliminations for this puzzle, each justified by a precise rule?

Finally, what does your solver give for the following puzzle:
260000001
719000030
043007200
006503080
000060000
000700060
100004900
030908000
007000300

Finally bis, what's the address of the French forum?

Have nice holidays.

[RW]

- nrczt chains need at least one bivalue OR one conjugate pair; I have no example of a puzzle which has none of these (even EasterMonster); anybody got one?

AFAIK noone has found such a puzzle yet, although they are theoretically possible and I hope that we one day will find one. At the moment I believe the lowest known number of conjugate pairs in a puzzle is 8:

Code: Select all

1.......9.2..6..7...3...5...8.42.......61.......8.7.4...9...1...6..7..8.5.......3

RW

[re'born]

About your solution, I don't understand any step in it.

I think I've cracked what champagne is doing. Here for example is a translation of his first step

#1H9
[]9H5/9F5_1F5/1F1_1H1/1H9
[]9H9/1H9
[]9H8/6H8_6H9/1H9

becomes

Code: Select all

r5c8=9 => r5c6=1 => r1c6<>1 => r1c8=1 => r9c8<>1
r9c8=9 => r9c8<>1
r8c8=9 => r8c8<>6 => r9c8=6 => r9c8<>1


Since 9 can only appear in rows 5,8,9 in column 8, we conclude that r9c8<>1.

We'll see if this interpretation holds up when we get to the ALS steps.

Edit: Here is step 2:

#4(E2E3E6)
[]4(E2E3E6)/1(E3E6)|*E2E3E6 _1E4/1F5_9F5/9H5_9(H8H9)/4(H8H9)|*H8H9 _4H7/4(D7F7)_4(E7E8E9)/4(E2E3E6)

First note the almost hidden set in r2346c5 with hidden candidates 1,3,5. A 4 in r234c5 will force the hidden candidates into the other cells of r2346c5, and hence we would have r4c5=1. Next note that r89c8 is an almost hidden set with hidden candidate 6. Therefore if, for instance r89c8=9, then we would have r89c8=<69>. We can now write down champagne's forcing chain:

Code: Select all

r236c5=4 => r4c5=1 => r5c6=9 => r5c8<>9 => r89c8=9 => r89c8=<69> => r7c8=4 => r7c46<>4 => r789c5=4 => r236c5<>4

and therefore, r236c5<>4.
To paraphrase what champagne already said, whenever he uses the notation |*A, the set A of cells is an almost hidden set, i.e., it contains n cells and n-1 hidden candidates. This way when he writes something like

4(E2E3E6)/1(E3E6)|*E2E3E6

I imagine we are supposed to be saying "if 4 is in r236c5, then due to the almost hidden set in r236c5 (and the placement of the hidden candidates in that set) we can exclude 1 from r36c5."

Edit2:(A different ending) After step 2 and cleaning up the grid we get the following ALS xz-rule application, which we state in terms of subset counting.

Code: Select all

*--------------------------------------------------------------------------------------*
 | 2357     2357     25A      | 356      8        126      | 9        137B     4        |
 | 49       6        1        | 49       235      7        | 2358     38B      235      |
 | 2345789  23578    24589-   | 3459     1235     1249     | 12357    137B     6        |
 |----------------------------+----------------------------+----------------------------|
 | 16789    178      3        | 2        147      1489     | 46       5        179      |
 | 12579-   4        259A     | 3579-    6        19-      | 1378     13789B   1379-    |
 | 156789   1578     5689-    | 34579    1357     1489     | 46       2        1379     |
 |----------------------------+----------------------------+----------------------------|
 | 12345-   9        245A     | 467-     247-     246-     | 12357    1347B    8        |
 | 23468    238      2468-    | 1        2479     5        | 237      34679-   2379     |
 | 12456    125      7        | 8        249      3        | 125      469      1259     |
 *--------------------------------------------------------------------------------------*


A={2,4,5,9} on r157c3
B={1,3,4,7,8,9} on r12357c8
The collection of all cells in A \/ B forms a 1-set, that is, each of the 8 candidate numbers occur in A \/ B with max multiplicity 1. Thus we can remove any candidate that would reduce the max multiplicity of a candidate in A \/ B to 0.
r38c3<>2
r8c8<>3
r7c1456<>4
r36c3<>5
r8c8<>7
r5c1469<>9
This will effectively solve the puzzle, which is to say, if you've made it this far, the ending is well within your reach (but think remote naked pairs if you get stuck).

[ronk]

#4(E2E3E6)
[]4(E2E3E6)/1(E3E6)|*E2E3E6 _1E4/1F5_9F5/9H5_9(H8H9)/4(H8H9)|*H8H9 _4H7/4(D7F7)_4(E7E8E9)/4(E2E3E6)

re'born translated the first step, so I'll do the second.
[edit: I now see re'born edited his post to include the second step as well, but I'll let this post stand.]

Code: Select all

 23567   23567   256     | 356     8       126     | 9      C137     4
 2345689 23568   1       | 34569   235-4   7       | 2358   C38      235
 2345789 23578   24589   | 3459    1235-4  1249    | 123578 C1378    6
-------------------------+-------------------------+------------------------
 16789   1678    3       | 2      A147     1489    | 46      5       179
 12579   4       259     | 3579    6      B19      | 1378   C13789   1379
 156789  15678   5689    | 34579   1357-4  1489    | 46      2       1379
-------------------------+-------------------------+------------------------
 12345   9       245     |D467   EA247    D246     | 12357  C1347    8
 23468   2368    2468    | 1     EA2479    5       | 237     34679   2379
 12456   1256    7       | 8     EA249     3       | 125     469     1259

              A           B                          C           D        E
{ALS:r4789c5=4|1=r4c5}-1-r5c6-9-{ALS:[r5c8,r1237c8]=9|4=r7c8}-4-r7c46=4=r789c5

implies r236c5<>4

That's a complex, but very clever step. It has two almost-locked-sets (ALSs), grouped candidates, and overlapping endpoints of the chain.

The =4|1= notation indicates the strong inference of the ALS, i.e., the ALS must contain at least one of the two indicated digits. The overall inference of the chain is ... r4789c5 =4= r789c5 ... which reduces to ... r4c5 =4= r789c5.

[denis_berthier]

- nrczt chains need at least one bivalue OR one conjugate pair; I have no example of a puzzle which has none of these (even EasterMonster); anybody got one?

AFAIK noone has found such a puzzle yet, although they are theoretically possible and I hope that we one day will find one. At the moment I believe the lowest known number of conjugate pairs in a puzzle is 8:

Code: Select all

1.......9.2..6..7...3...5...8.42.......61.......8.7.4...9...1...6..7..8.5.......3

RW

RW, thanks for your answer and the example (BTW, SudoRules can't solve it). You got me puzzled. When you say "they are theoretically possible", do you mean (as I believe) that it hasn't been proven that such a puzzle cannot exist, or that it has been positively proven that there must exist such a puzzle?

[RW]

RW, thanks for your answer and the example (BTW, SudoRules can't solve it). You got me puzzled. When you say "they are theoretically possible", do you mean (as I believe) that it hasn't been proven that such a puzzle cannot exist, or that it has been positively proven that there must exist such a puzzle?

Actually, nothing has been proven yet. Maybe it would be more accurate to say that I cannot see a reason why they couldn't exist. It is possible to place 20+ clues in a grid in such a way that no two units in the same chute are empty and that no bivalue cells or conjugate pairs are formed:

Code: Select all

 *-----------*
 |2..|...|..7|
 |.1.|..6|.9.|
 |..3|...|5..|
 |---+---+---|
 |.4.|1.3|...|
 |...|.9.|...|
 |...|4.5|.2.|
 |---+---+---|
 |..9|...|1..|
 |.5.|7..|.8.|
 |6..|...|..3|
 *-----------*
13026 solutions

Unfortunately no such puzzle with an unique solution has been found yet.

No extensive research has been made in this field. I found the 8 quite easily when I did one try to create puzzles with few strong links here. I'm sure some of the coding geniuses around could at least get the number down a lot if some effort was put into it.

RW