Definition of typed-whips (2D-whips)

In Sudoku, considered as a Constraint Satisfaction Problem (CSP), there are 81 natural CSP-Variables, namely those corresponding to the cells of the grid. Let's say that these variables are of type rc. In a given puzzle, some of the CSP-Variables are decided but that doesn't change the fact that they do exist.

In the first edition of "The Hidden Logic of Sudoku" (HLS1, May 2007), I introduced an Extended Sudoku Board, with 3x81 more cells (rn-cells, cn-cells and bn-cells) and I introduced 3x81 more CSP-Variables, with each of the 3x81 new cells representing the possible content of one of the new CSP-Variables. Say these new CSP-Variables are of respective types rn, cn, and bn. Of course, there's an obvious relation between the possible values of the 4 types: rc=n <=> rn=c <=> ...

One of the main ideas of HLS1 was, any pattern defined in the rc-space can be transposed to each of the rn, cn and bn spaces (with some additional condition for the bn space). This was proven in HLS1 as a general meta-theorem and it was illustrated by many new chain patterns (in addition to the classical Subsets).

The starting point for all the chains I ever considered were the basic xy-chains (which totally reside in the rc space).

The second main idea of HLS1 was, knowledge is not depleted by using it (I didn't express it in these terms at that time, but I think it's a good summary). This led to the definition of t-candidates and chains based on this notion, such as xyt-chains. Similarly, I introduced z-candidates (linked to the target), an idea leading to xyz and xyzt-chains.

Combining the two main ideas, the transposed counterpart of the xyt-chains (resp. xyzt) were the hxyt-chains (resp. hyxzt).

Notice that any chain of any of the above defined families is mono-typed: all its CSP-Variables are of the same type. I called them globally 2D-chains.

I showed that 2D-chains (with only the chains defined at that time) were enough to solve 97% of the randomly generated puzzles (at that time, it meant generated by a top-down generator).

In the second edition (HLS2, Nov. 2007), I introduced the "fully-symmetric chains" or 3D-chains, a chain pattern that allowed to combine CSP-Variables of different types. As fully-supersymmetric chains are their own super-symmetric counterpart, they marked some final step in the development of these ideas and they significantly extended the resolution power of 2D-chains.

In "Constraint Resolution Theories" (CRT, Oct. 2011), still with the same general resolution paradigm, but extended to any finite binary CSP, I introduced new general chain patterns: whips, braids, g-whips, g-braids, ... , meaningfull in any CSP, and I recalled that they didn't replace the old chain patterns, but they subsumed them and I didn't reproduce in CRT what was already written in full detail in HLS, with many examples. Similarly, in my subsequent book "Pattern-Based Constraint Satisfaction" (HLS1 Nov. 2012 and HLS2 July 2015), I didn't speak of 2D-chains.

In parallel, I extended my SudoRules solver (developed at the time of HLS) to a general CSP-solver (CSP-Rules) and I almost completely recoded SudoRules in oder to make it a mere application of CSP-Rules (together with a lot of new ones: KakuRules, FutoRules, SlitherRules, ...). CSP-Rules didn't include specific rules for the old 2D-chains and they therefore no longer appeared in the resolution paths I proposed.

As early readers of HLS keep asking me about the 2D-chains, I've finally re-introduced them in CSP-Rules. Of course, it had to be in a slightly different form, because not any CSP relies on a grid and the rc, rn, cn or bn spaces may not be meaningful.

The way I re-introduced them is by allowing to give any CSP-Variable a type. Unsurprisingly, in Sudoku, the types will be rc, rn, cn and bn.

Definition: for any n>0, a typed-whip[n] is a whip[n] in which all the CSP-Variables are of the same type.

Remarks:

- Later, I may introduce similar more specific chain patterns, for the bivalue-chains or t-whips.

- Typed-whips are a special case of whips; they don't extend their resolution power, but they may be more enticing for people using my Extended Sudoku Board

- Whips[1] are always mono-typed

- In Sudoku, typed-whips will appear as whips, with the type appended to the pattern-name "whip", such as whip-rc[4], ... whip-bn[6]

- A natural question is: how powerful are typed-whips wrt whips? (see my next post.)

- New subtypes of whips introduce some diversity in the resolution paths. The more subtypes of whips there are in CSP-Rules, the more different resolution paths one can get by choosing different combinations of them.