Sudoku Players' Forum (clone)

RW wrote: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

RW, from a quick browsing of this thread, I get the impression that there is no obvious relationship between the difficulty of a puzzle and the number of bivalue+bilocation. Am I wrong?

denis wrote

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?

I hope you'll find herebelow a first set of answer allowing differed more detailed explainations.

denis wrote

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

It was really a tough job to solve it (forced to enter step 3 and 10 seconds solving time), but we are far from the toughest solved on my side : 42 seconds.
I think it would not be appropriate to publish any partial print before I could have prepared a new version of prints following local rules.

denis wrote

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

Here is the forum where your xyzt chain are under discussion. It is probably the best french forum investigating new tools.
http://www.sudoku-factory.com/forumsudoku/

I am personnaly working with a small group on the Figaro Sudoku forum mainly with puzzles at the level of step1.




re'born wrote:

Code: Select all

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

becomes
Code:
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.

This is OK, but I will add comments to comply with Denis view that rules have to be clearly stated. (I fully agree)

Here are three Alternate chains beginning and ending by a weak link.
Theese chain are defining a derived weak link (or distant weak link) between both ends.
eg: 9(r5c8) and 1(r9c8) can not be both in the solution.

The final shortcut can be written

9(r5c8)/1(r9c8)
9(r9c8)/1(r9c8)
9(r8c8)/1(r9c8)

9(r5c8);9(r9c8);9(r8c8) is a set of candidates (could be groups) in which at least one is valid.

If each component of such a set has a weak link with another candidate (or group of candidates) then that candidate (group of candidates) can be cleared.

In fact, up to now, i am only using sets with one and only one valid candidate/group.

re'born wrote

champagne wrote:
#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:
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

In principle, you got it. Let me describe the way I process the pattern in column 5.

Code: Select all

C5:  _   2345 12345 | 147 __ 13457 |247 2479 249

r4r7r8 147 247 2479 249 is an ALS (four cells digits 12479, one digit in excess)
complementary cells
r2r3r6 2345 12345 13457 (three cell digits 123457 digits 3 and 5 will be in the solution)
are forming what I call an "almost cell". Only one digit has still to be found.

all intances of the same digit in one of theese entities are groupped unless they are compulsory.

eg 2(r2c5 r3c5) is a group, but we forget digits 3,5,9.

Groups of the same digit are new strong links.

In the second entitie (Almost cell) each pair of groups is forming a weak-link.

By the way, a cell is the smallest "almost cell" and we are doing exactly what is done in a cell.


re'born wrote

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."

We could, but it's not in the philosophy of weak links and alternate chains. This is a pure weak link, thats it.

re'born wrote

Edit2A 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.

I am short in time, but i'll go deeper in your point.

The nice loop is also very impressive. One remark; if you do the clearing, you'll notice than regarding ALS/'Almost cells", all is done in "almost cells"

ronk wrote

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

I would only add comments on complexity, other comments are here above.

In fact, in that process, you are only keeping track of weak links. I'll clarify that point later on .

Here, in step one, there was 57 relevant weak links. Very often, they are about 20 which put the puzzle in a position to be solved easily in hand processing.
In step two, we have close to 2000 weak links.

The process in itself is not changed, but we have exceeded human capability to do it.

I have ways to enter partially in the process using the most relevant ALS.

champagne wrote:In fact, in that process, you are only keeping track of weak links. I'll clarify that point later on .

Here, in step one, there was 57 relevant weak links. Very often, they are about 20 which put the puzzle in a position to be solved easily in hand processing.
In step two, we have close to 2000 weak links.

That doesn't appear to be a "clarification", so by "later on" I guess you meant in a later post.

As I think it is strong inferences rather than weak inferences that make the sudoku world go around, I anxiously await your clarification.

denis_berthier wrote:RW, from a quick browsing of this thread, I get the impression that there is no obvious relationship between the difficulty of a puzzle and the number of bivalue+bilocation. Am I wrong?

Well, the problem in finding a relationship between the difficulty and the number of bivalue+bilocation cells is that we don't really know how to rate the hardest puzzles. Sure, by SE my puzzle with 8 strong links is easier than the Easter Monster that has a lot more strong links, but according to suexrat my puzzle is harder than the Easter Monster. If you compare the hardest puzzles with some considerably easier puzzles, you will see the difference.

All the current hardest I have looked at have <15 strong links. Compare that to for example Vidar's Monster #3 (once considered one of the hardest puzzles, but very easy compared to the current hardest) which has a total of 26 bivalue+bilocation units after the first trivial steps. Another hard but not extreme puzzle I looked at, this pearl by gurth, has 34 bivalue+bilocation units after the the first two swordfishes. Vidar's puzzle has ER 9.3 and Gurth's is 9.1. I don't think you can find a puzzle with more than 30 b/b-units and ER>10.5. Similarily, I don't think you can find a <15 b/b-units puzzle with ER<9.5.

RW

Ronk wrote

That doesn't appear to be a "clarification", so by "later on" I guess you meant in a later post.

As I think it is strong inferences rather than weak inferences that make the sudoku world go around, I anxiously await your clarification

.

Sorry ronk, as I mentioned yesterday, I am leaving this afternoon for about a fortnight.

I can not start a structured answer now so "later on" means "when coming back".


Nervertheless, I confirm that in "full tagging", strong links can be forgotten searching alternate chains. What you need is only the list of "relevant weak-links" with appropriate description.

For sure, strong links play the main role establishing the list of "relevant weak links".

edit 1 :

Likely, structured answer request leaving this thread an opening a new one.

I woul be glad if anybody would accept to receive in private message a draft of the post I have to prepare to come ot an acceptable wording before publishing it.

SPOTTING NRC(Z)(T)-CHAINS: NRC(Z)(T)-TAGGING

Prerequisites and references:
- my opening post in the "fully supersymmetric chains" thread
- my opening post in the "concept of a resolution rule…" thread


As I already indicated:

- there are resolution rules, which are mathematical theorems in the "condition-action" form; these theorems guarantee that asserting a value or (more often) deleting of a candidate, is legitimate. As such, resolution rules are invaluable: without them (or any other form of formal theorem that might appear some day in their stead), Sudoku can only be ad hoc reasoning; as I already said also, but it is useful to repeat it, FOL is the ultimate scientifc form of this rules, but most of the time, using the auxiliary predicates that I have already be proven to be writtable as FOL formulæ, a non ambiguous English formulation guarantees that they can be expressed as resolution rules; There is another reason why resolution rules are invaluable: only precise formulations of such rules allow to prove subsumption relationships between different rules;

- and there are resolution techniques associated to such rules, whose purpose is to answer the practical question: how do we apply the rules on a real grid, i.e. how do we find the patterns (defining the condition part of a rule) on a real grid; I already gave an example for which two different resolution techniques can be associated to a given resolution rule .

(There may also be resolution techniques that cannot be associated to a resolution rule, such as T&E or tabling, but I'm not considering them here).


As nrc-chains are "basic" AICs or "basic" NLs (viewed in a different perspective), I'll skip this case.
Let me consider the case of the nrcz, nrct and nrczt chains I introduced recently.
Notice that the first methods defined below are the straightforward transposition of the methods already introduced for xy(z)t chains and are also no more than an expansion of a short section in the introductory post. But nrc(z)(t) tagging is different.

Remember that I defined "nrc-conjugate" (or "nrc-bivalue", as you prefer - in 3D space these concepts are equivalent) as ordinary bivalue OR odinary bilocation.
Remember that an nrc(z)(t) chain is first a particular sequence of 2n candidates and that it can also be considered as a sequence of n cells. As these chains are 3D generalisations of xy-chains, odd candidates are named left-linking candidates, even candidates are named right-linking candidates.

nrc(z)t chains can be found by using two different methods, which both build the chain from first to last candidate and both start with two candidates that are linked by an nrc-bivalue link. Let's call these two candidates as the seed of the chain. In either method, the chain is progressively extended to the right, in steps that add two candidates. Suppose we already have an nrc(z)t chain on 2(n-1) candidates and let's try to extend it with two more candidates.

For simplicity, in case we deal with an nrczt chain, suppose a target candidate TC has been chosen.



FIRST RESOLUTION TECHNIQUE: SIMPLE ARROWS
Initialisation:
- initialise the procedure by drawing a red arrow between the first and second candidates;
Next steps:
- find a candidate that is nrc-linked to candidate 2(n-1), it is the new left-linking candidate;
- draw a blue arrow from candidate 2(n-1) to this new candidate;
- find a candidate that is nrc-conjugate with the previous one modulo any previous right-linking (i.e. even) candidate in the chain in case the t-extension is used and modulo TC in case the z-extension is used); it is the new right-linking candidate; the fact that this candidate is OK is checked on the fly, noting that the previous right linking candidates are the arrival points of the red arrows;
- draw a red arrow from candidate 2(n-1)+1 to this new candidate.
(in folk language, red arrows support "strong inferences" and blue arrows support "weak" ones).


SECOND RESOLUTION TECHNIQUE: NRC(Z)(T)-COLOURING:
(this method was inspired by the xyt-colouring algorithm first defined by John MacLeod to spot the xyt-chains, and was corrected by me).
Initialisation:
In case the z-extension is used, the algorithm must be initialised by colouring in blue any candidate that is nrc-linked to the target. In case the t-extension is used, the algorithm must be initialised by colouring in blue any candidate that is nrc-linked to the second candidate. These two colouring processes must be combined for nrczt-chains. The extension step is:
Next steps:
- find a candidate that is nrc-linked to candidate 2(n-1), it is the new left-linking candidate; notice that colouring MUST NOT BE TAKEN INTO ACCOUNT HERE (that was the bug in John's algorithm);
- draw an arrow from candidate 2(n-1) to this new candidate;
- find a candidate that is nrc-conjugate with the previous one modulo any candidate already coloured in blue (i.e. ignore any blue candidate); it is the new right-linking candidate;
- draw an arrow from candidate 2(n-1)+1 to this new candidate;
- colour in blue any candidate that is nrc-linked to this new candidate.

Notice that, in either of these techniques, no value is tentatively asserted and no candidate is tentatively eliminated (i.e. none of these techniques introduces anything that could reasonably be called T&E).

For either technique, after each such step,
- if the z-extension is used, eliminate TC if it linked to both first and current last candidates; (things could be made a little more general, but this is simpler for a beginner);
- if the z-extension is not used, eliminate any candidate that is nrc-linked to both first and current last candidates.



WHAT HAPPENS IF?
- what happens if there is not target (or if the predefined target, in case the z-exetension is used)? Answer: nothing happens. You may continue extending your chain. BTW; if an elimination is done, you may also continue extending your chain (except if the z-extension is used: if TC is eliminated, there's no reason for wanting to eliminate it again

- waht happens if, at some point, the extension step cannot be done? First, this will occur mainly when looking for right linking candidates - but that's a secondary matter. At the levl of the values and the candidates present on the grid, NOTHING will happen. As for ANY type of chain, you'll just have to find a better one. How can this be done? The answer is very standard: go one step backwards in the chain and try another extension. Here the two methods behave very differently.
For the first method, you just have to erase the last arrow.
For the second method, you must erase all the colouring (and all the arrows) and restart from nought. This is a debilitating point for nrc(z)(t)-colouring.



A NEW TECHNIQUE FOR SPOTTING NRC(Z)(T)-CHAINS: NRC(Z)(T)-TAGGING
Can nrc(z)(t) colouring be saved? Answer: yes, by nrc(z)(t) tagging.
Choose a sequence of letters.
Follow the same procedure as for nrc(z)(t) colouring, but, instead of colouring the candidates, tagg them with letters; a candidate needs be tagged with only one letter (if it is already tagged, don't tagg it again). Of course, in any new step of the technique described above for colouring, the next letter in the sequence must be used.
When you have to "backtrack" to the previous step, just erase the instances of the last letter used.

Theorem: Finned and sashimi fish are subsumed by nrcz-chains.

Preliminaries: standard x-wing on rows is the following special case of nrc-chains: n1{r1c2 r1c1} - n1{r2c1 r2c2}, where:
- the two nrc-conjugate links are along rows r1 and r2,
- the mere central nrc-link is along column c1,
- the targets are considered as linked to both endpoints of this chain along column c2;
(Notice that, for the eliminations on column c1, chain n1{r1c1 r1c2} - n1{r2c2 r2c1} must be considered instead.)

Proof for finned fish: In the corresponding finned fish, additional candidate n1 may appear in the same row and block as the last candidate (n1r2c2) of this chain. But, any candidate n1rc such that rc is in the intersection of the column and the block containing the last candidate, makes the n1{r1c2 r1c1} - n1{r2c1 r2c2} chain into an nrcz-chain wrt the target n1rc, and the additional candidates on row r2 are exactly what the z-extension allows to disregard.

Proof for sashimi fish: In the corresponding sashimi fish, additional candidate n1 may appear in the same row and block as the last candidate (n1r2c2) of this chain and candidate n1 may be absent from r2c2. But, any candidate n1rc such that rc is in the intersection of the column and the block containing the last candidate, still makes the n1{r1c2 r1c1} - n1{r2c1 r2c2} chain into an nrcz-chain wrt the target n1rc, and the additional candidates on row r2 are exactly what the z-extension allows to disregard.

The same considerations apply to x-wing on columns, by row-column symmetry.
Their generalisation to swordfish and jellyfish is straightforward: if the last cell is still the one around which the modifications are made, consider respectively the associated nrc-chains (and their z-extension for the proof):
n1{r2c3 r2c2} - n1{r1c2 r1c1} - n1{r3c1 r3c4}
and
n1{r3c4 r3c3} - n1{r2c3 r2c2} - n1{r1c2 r1c1} - n1{r4c1 r4c4}

As a result, nrcz-chains are a way of integrating finned and sashimi fish into chains.

erratum:
in the previous post, in the proof for sashimi, the last candidate in each of the 3 chains used:
n1{r1c2 r1c1} - n1{r2c1 r2c2}
n1{r2c3 r2c2} - n1{r1c2 r1c1} - n1{r3c1 r3c4}
and
n1{r3c4 r3c3} - n1{r2c3 r2c2} - n1{r1c2 r1c1} - n1{r4c1 r4c4}
does not exist.
It should be replaced by candidates in the fin, resp.: n1r2c+, n1r3c+, n1r4c+

denis_berthier wrote:Their generalisation to swordfish and jellyfish is straightforward: if the last cell is still the one around which the modifications are made, consider respectively the associated nrc-chains (and their z-extension for the proof):
n1{r2c3 r2c2} - n1{r1c2 r1c1} - n1{r3c1 r3c4}
and
n1{r3c4 r3c3} - n1{r2c3 r2c2} - n1{r1c2 r1c1} - n1{r4c1 r4c4}

As your proofs are for the 2x2x2(x2) cases of swordfish and jellyfish, would you elaborate on how it works with, say, a 3x3x3 swordfish?

I've not been careful enough in the generalisations to Swordfish and Jellyfish. Here are the correct theorems.

1) x-wing:

Theorem: Any finned x-wing, with or without sashimi, is subsumed by an nrcz2-chain.


2) Swordfish

After re-ordering of the rows and columns, the most general Swordfish on rows for number n1 looks like:

..1a === 1b === (1c)
(1d) === 1e === 1f
..1g == (1h) === 1i
===========1x

where (1c), (1d) and (1h) are optional and 1x is a target in the same column as 1i

The most general Swordfish on rows for number n1, with fin (and sashimi), looks like:

..1a === 1b === (1c)
(1d) === 1e === 1f
..1g == (1h) === [1i] === 1fin
===========1x

1+ is a candidate in the fin
1fin is any candidate in the fin
[1i] is the potentially missing candidate in the sashimi
1x is a target in column and block of the last candidate: [1i]

Consider the chain 1f-1e-1b-1a-1g-(1i if present, 1fin otherwise). It is an nrczt-chain wrt 1x, If 1d is absent.

- additional candidates 1c and 1fin (if present) are justified by the z extension
- additional candidate 1h i(if present) s justified by the t extension

Theorem: Any 2x2x2 finned swordfish with or without sashimi is subsumed by an nrcz3-chain
Theorem: Any other finned swordfish with or without sashimi is subsumed by an nrczt3-chain, provided that it has a missing candidate in a row and a column different from that of the base for the fin/sashimi.

For the only remaining case, I need something I haven't yet spoken of. I haven't yet found time to write it down properly, so be patient.


3) Jellyfish

After re-ordering of the rows and columns, the most general Jellyfish on rows for number n1 looks like:

..1a === 1b === (1c) == (1d)
(1e) === 1f ==== 1g == (1h)
(1i) === (1j) === 1k === 1l
1m === (1n) == (1o) == 1p
==================1x
with similar conventions.


The most general Jellyfish on rows for number n1, with fin (and sashimi), looks like:
..1a === 1b === (1c) == (1d)
(1e) === 1f ==== 1g == (1h)
(1i) === (1j) === 1k === 1l
1m === (1n) == (1o) == [1p] === 1fin
==================1x

Consider the chain: 1l-1k-1g--1f-1b-1a-1m-(1p if present, 1fin otherwise). It is an nrczt-chain if 1e, 1i and 1j are absent:
- additional candidates 1d, 1h and 1fin (if present) are justified by the Z extension
- additional candidates 1c, 1n and 1o (if present) are justified by the t-extension

Theorem: Any 2x2x2x2 finned jellyfish with or without sashimi is subsumed by an nrcz4-chain
Theorem: Any other finned jellyfish with or without sashimi is subsumed by an nrczt4-chain, provided that it has:
- a row different from that of the fin/sashimi base with a missing candidate in a column different from that of the fin/sashimi base
- another row different from that of the fin/sashimi base with a missing candidate in the previous column and a missing candidate in another column also different from that of the fin/sashimi base

denis_berthier wrote:For the only remaining case, I need something I haven't yet spoken of. I haven't yet found time to write it down properly, so be patient.

While we await this, let me ask you an unrelated question. Are you familiar with Rod Hagglund's Broken Wing? It uses the principle of conjugacy modulo a set as your nrczt-chains do. However, in broken wings, you build loops of odd length and the "target candidate" is generally not seen by the candidates in the loop. Do you see a nice way of either subsuming broken wings into nrczt-chains, or melding them into a even slightly bigger theory? In case you haven't seen them, I recommend the threadA revival of Broken Wings for a plethora of examples.

re'born wrote:Are you familiar with Rod Hagglund's Broken Wing? It uses the principle of conjugacy modulo a set as your nrczt-chains do. However, in broken wings, you build loops of odd length and the "target candidate" is generally not seen by the candidates in the loop. Do you see a nice way of either subsuming broken wings into nrczt-chains, or melding them into a even slightly bigger theory? In case you haven't seen them, I recommend the threadA revival of Broken Wings for a plethora of examples.

Re'born Thanks for this interesting reference.
It points to that one, which is also worth reading:
http://forum.enjoysudoku.com/viewtopic.php?t=2666&highlight=

I wasn't familiar with Broken Wings, which seems to be a very interesting technique. I can't see any reference there to conjugacy modulo a set. What I see there is the notion of guardian cells. The way these cells are used seems to be completely different from the way the additional candidates allowed by the t-extension is used.
I don't think broken wings can be subsumed by nrczt. But who knows.

As for "melding them into a even slightly bigger theory", I don't believe in a "theory of eveything" or "rule of everything". Even supposing such a rule existed, it'd probably be very cumbersome. "Let thousand flowers…"

denis_berthier wrote:I can't see any reference there to conjugacy modulo a set. What I see there is the notion of guardian cells. The way these cells are used seems to be completely different from the way the additional candidates allowed by the t-extension is used.
I don't think broken wings can be subsumed by nrczt. But who knows.

No, for sure Rod doesn't use the language of conjugacy modulo a set. But if you take an example where the guardian candidates all see the target candidate, then a broken wing is a loop of odd length with all adjacent candidates conjugate modulo the target candidate. So it feels like your z-extension, except for the fact that the loop candidates don't see the target candidate.

denis_berthier wrote:As for "melding them into a even slightly bigger theory", I don't believe in a "theory of eveything" or "rule of everything". Even supposing such a rule existed, it'd probably be very cumbersome. "Let thousand flowers…"

Fair enough, though there may still be some space between nrczt-chains and a cumbersome theory of everything.

re'born wrote:

denis_berthier wrote:I can't see any reference there to conjugacy modulo a set. What I see there is the notion of guardian cells. The way these cells are used seems to be completely different from the way the additional candidates allowed by the t-extension is used.
I don't think broken wings can be subsumed by nrczt. But who knows.

No, for sure Rod doesn't use the language of conjugacy modulo a set. But if you take an example where the guardian candidates all see the target candidate, then a broken wing is a loop of odd length with all adjacent candidates conjugate modulo the target candidate. So it feels like your z-extension, except for the fact that the loop candidates don't see the target candidate.

A difference that is enough for making me unable to see any straightforward means of applying my chains in this case.

re'born wrote:there may still be some space between nrczt-chains and a cumbersome theory of everything.

Sure, but, as of now, I don't know what the interesting extensions are.

Denis,

When you wrote your new version of SudoRules, all of the (h)xy(z)(t)-chains went away, and were replaced by nrc(z)(t)-chains (at least in the solutions I've seen). Of course, xyt, xyzt and hxy-chans are all subsumed by nrczt-chains (as I think you mentioned earlier), but what happens to hxyt and hxyzt chains? It seems that these should still be giving you something extra. Do you have any such examples? Are hxy(z)(t)-chains still implemented in SudoRules? And have you tried going one step further and implementing hnrc(z)(t)-chains?