DEFINITION of NRC-, NRCT- and NRCZT- NETSLet it be clear that I don't like nets and I consider that the nrczt-nets I'm going to define below are not really useable patterns for a human player, at least in their most general form. But are the most general chains of ALSs (and other AAAAAHHHHAAAHHAAAHHHH LSs) really useable?
Anyway, as this may be a matter of taste and I already spoke of them several times, saying that it is easy to define them, the least I can do is give such a definition. Although this is intuitively obvious, we need a few technicalities if we want to formalise it unambiguously.
Remarks:
-
as was the case for nrczt-chains, nrczt-nets do not rely on subsets and on links between subsets;
- given a candidate C, nrczt-chains were the most general first order chain patterns that could justify the elimination of C; nrczt-nets are the most general first order net patterns that can justify the elimination of C; ("first order" means not relying on subsets);
- the following definitions can be restricted to nrct or nrc nets; they can also be restricted to any of their 2D counterparts.
If you don't know the basics of graph theory, it may be appropriate to start by reading the following elementary introduction:
http://en.wikipedia.org/wiki/Graph_%28mathematics%29An nrczt-chain was defined as a sequence (i.e. a completely or linearly ordered set) of 2D-cells (each in either of the rc-, rn-, cn- or bn- spaces). It can also be seen as a sequence of (alternatively left and right linking) candidates, but the easiest way to generalise to nets is using the cell view.
Now, as an informal introduction to the following definitions, let me just say that they provide for the possibility for having several right linking candidates in some of the cells and they explain how they can be dealt with. This is very far in spirit from allowing subsets in chains (such as in Grouped NLs).
Definition: an oriented 2D-cell is a 2D-cell whose candidates are labelled according to the rules:
- it has one and only one left-linking candidate (or llc)
- it has one or more right-linking candidates (or rlc)
- it has zero or more additional candidates
(given a 2D-cell in a real puzzle, its candidates can be labelled in different ways as llc, rlc or additional, but a choice has to be made for a net to be completely specified; notice that, at this stage, additional candidates are NOT labelled as t or z)
Definition: a 3D-net is a partially ordered set (called a poset by mathematicians) of oriented 2D cells from any of the 2D-spaces, i.e. either rc-, rn-, cn- or bn- spaces (notice that, as I speak of a set and not a bag, these cells are different); this structure must satisfy the following conditions:
- if an oriented 2D-cell has more than one right-linking candidate, it is called branching,
- if an oriented 2D-cell has more than one immediate predecessor in the poset, it is called merging,
(notice that a cell can be both merging and branching)
- if an oriented 2D-cell has no predecessor in the poset it is called a source,
- if an oriented 2D-cell has no successor in the poset it is called a sink ,
- if an oriented 2D-cell is neither branching nor merging nor a source nor a sink, it is called regular,
- for every oriented 2D-cell C1 (but those in the sinks), each of its right-linking candidates has a unique distinguished nrc-link to the left linking candidate of an immediate successor of C1 in the poset;
(notice that any candidate may have several nrc-links (e.g; along a row and a block) to another given oriented 2D-cell , but one has to be chosen for a net to be completely specified);
(this is the main connectivity condition);
- if different right-linking candidates in possibly different oriented 2D-cells have their distinguished nrc-links pointing to the (unique) left-linking candidate of the same oriented 2D-cell C2, then C2 is a merging cell;
- notice that it is not necessary to add a condition on left-linking candidates being nrc-linked to right-linking ones: this is already part of the definition of 2D-cells;
With a 3D-net, one can associate a directed acyclic graph (DAG):
- edges: the edges of the graph are all the couples (oriented 2D-cell C, left-linking candidate of C) and (oriented 2D-cell C, right-linking candidate of C)
(instead of taking merely all the left- and all the right- linking candidates, these technicalities provide for the possibility for a candidate to appear several times, but only in different paths);
- vertices:
- for every oriented 2D-cell with left-linking candidate C1 and for each of its right-linking candidates C2, the graph has a vertex with head C1 and tail C2;
- for every oriented 2D-cell C, for each of its right-linking candidates C1 and for the distinguished nrc-link of C1 to an oriented 2D-cell C2, the graph has a vertex with head C1 and tail the left-linking candidate of C2;
- the graph has no vertex other than those defined in the above three clauses.
With these definitions, only left-linking candidates are merging points and branching occurs only with the existence of several right-linking candidates.
Notice that the additional candidates are not considred as belonging to this graph.
Definitions: a target of a 3D-net is any candidate that is nrc-linked to the left-linking candidates of all its sources and to all the right-linking candidates of all its sinks.Remarks:
- as was the case for the other 2D- or 3D- chains I have introduced, the target does not belong to the net;
- a 3D-chain is a 3D-net with a single source, a single sink and no branching or merging; said otherwise, its branching factor is 1;
- 2D chains implied a restriction on their first cell: it had to be bilocal or bivalue (this is not an arbitrary restriction, it is a consequence of the 2D constraints); nrczt-chains somehow relax this restriction, as their first cell may contain additional z-candidates, although they are rarely needed in practice; with nrczt-nets, multiple right-linking candidates (branching) allow to use any cell as a first cell, and having a set of sources allows having several first cells.
Definition: path, maximal path, initial path. Given a 3D-net,
- a path between two left- or right- linking candidates C1 and Cn is any path in the associated graph;
- a maximal path is a path in the associated graph, between the left-linking candidate of a source and the right-linking candidate of a sink
- given a candidate C, an initial path to C is any path with head the left-linking candidate of a source and with tail C.
A path thus defined is a 3D-chain.
Given a path, a right-linking candidate in a cell that has more than one is called a branched candidate.
Given 2 candidates, in a 3D-chain there is a single path between them. But in a 3D-net, there may be 0, 1 or more paths beween them. This is the main structural difference between a chain and a net.
Given a candidate, there may be 1 or several initial paths to it.
As was the case for for 2D- or 3D- chains, only some types of 3D-nets are interesting (those that lead to a contradiction on the target). These conditions are generalisations of the condition on nrc(z)(t) chains: the nrc-bivalue (bivalue/bilocation) condition modulo the previous right-linking candidates and target.We just have to be careful when we formalise them.
Definition: an nrczt-net built on a candidate Z is a 3D-net admitting Z as a target (in the general sense defined above) and which satisfies the nrczt condition:
- for any cell in the net, for any right-linking candidate C in this cell, for ANY initial path to C, this 3D-chain would be an nrczt-chain or an nrczt-lasso if, at any branching point in this chain, we forgot the other right-linking candidates.Notice that, as there may be several initial paths to C, each additional candidate may have different justifications along each of these paths (it may appear as a t-candidate in some paths and as a z-candidate in others). This is why additional candidates were not a priori labelled as t or z.
Theorem (nrczt-net theorem): given an nrczt-net based on a target Z, Z can be eliminated.
Notice that nrczt-nets are
non-anticipative patterns.
Enough for one day.
In a next post, I'll prove that nrczt-nets (together with ECP and Singles) subsume all the rules defined in my book and programmed in SudoRules:
- Subsets (Naked, Hidden and Super-Hidden),
- elementary interactions row/block and column/block
- all the (h)xy(z)(t) and nrc(z)(t) chains
But, remember the first sentence of this post: this is not to mean that nrczt-nets should replace all the other patterns.
Edited 02/04/08: improved the definition of a 3D-net.
Edited 02/05/08: added the possibility of lassos in nrczt-nets.
