Sudoku Players' Forum (clone)

by **denis_berthier** » Wed Apr 22, 2020 2:30 am

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.

by **denis_berthier** » Wed Apr 22, 2020 2:31 am

A simple example with typed-whips (2D-whips)

This is the 9th puzzle in the gsf-cb collection, a moderately difficult one (SER = 8.3):

Code: Select all: .2.4..7.. ....891.. .......65 ..48..... 3..9....1 .95..1.7. .7.3...12 63....... ..2.1...8 .2.4..7......891.........65..48.....3..9....1.95..1.7..7.3...1263.........2.1...8

I chose this example because it has typed whips of all 4 types.

It is interesting to compare the paths in 3 different cases.
Notice that the hardest step of the 3 paths are different.

1) Only typed-whips are activated; typed-whips of length 7 are required
(bivalue-chains are not activated, because they are 3D.)

Hidden Text: Show

2) Only whips are activated; whips of length 5 are enough. It shouldn't be a surprise that, whips being more powerful than typed-whips, they lead to a smaller rating

Hidden Text: Show

3) Both typed-whips and whips are activated, with typed-whip[n] given a higher priority than whips[n] (otherwise they would never appear)
Typed-whips do not appear as often as whips, but they do appear

Hidden Text: Show

by **denis_berthier** » Wed Apr 22, 2020 2:32 am

The resolution power of typed-whips (2D-whips)

Remember the result in HLS: all the 2D-chains defined at that time were enough to solve 97% of the randomly generated puzzles (with a top-down generator).

In this post, I'll consider solutions obtained with typed-whips only. Typed whips can be considered a generalisation of the the 2D-chains introduced in HLS, so that one should expect the 97% result to be improved.

In fact, it is strongly improved.

Instead of considering puzzles generated by a top-down generator, I'll consider puzzles generated by the controlled-bias generator (from my gsf-cb collection of about 6M puzzles), which are harder in the mean. The first batch of puzzles has size 21375. Of these, 21346 are solved with typed-whips (remember that all are solved with whips).
99.86% of the controlled-bias generated puzzles can be solved by typed-whips.

Note that in general, the TyW rating is larger than the W rating (i.e. one needs longer typed-whips), as illustrated in the previous example.

by **denis_berthier** » Wed Apr 22, 2020 5:30 am

Long typed-whips (2D-whips)

One might think that typed whips being restricted to a single type of CSP-Variables, they will be rather short in general. Here is an example with a very long one (length 24).
Let me take another puzzle from the gsf-cb collection:

Code: Select all: ....5..89 ..718.... .....25.. 2....4..3 8..5...2. 9.1.2.... .1....46. ..274.... ...6.8.5. ....5..89..718.........25..2....4..38..5...2.9.1.2.....1....46...274.......6.8.5. SER 9.0

It has very long typed-whips, including one of length 24.

Hidden Text: Show

This puzzle is also an extreme case of the difference in resolution power between whips and typed-whips. It requires typed-whips of length 24, but whips of length only 6.

Hidden Text: Show

by **DEFISE** » Wed Apr 22, 2020 7:33 am

Hello Denis Berthier,
It’s my first post on this forum, excuse my approximate English language (I’m french).
For some time I have been reading your puzzle resolutions on this forum and in your book (« Pattern-Based Constraint Satisfaction and Logic Puzzles » Nov 2012 Edition). Each of your resolutions is made up of alternating whips and other rules. Let’s call these other rules “basic rules”. For example, your last resolution contains a: « finned-swordfish-in-columns », so you consider it as a basic rule.
I don’t remember where you specify what you mean by basic rule, in your book.
Could you remind me ?

Sincerely.

by **Mauriès Robert** » Fri Apr 24, 2020 7:14 am

Hi Denis,
I read with interest your retrospective introduction of this thread. It makes me better understand the role of the rc, rn, cn, and bn spaces, and thus the notions of 2D and 3D chains.
But the subject remains, for me and a friend who is interested in your theories, still full of questions. So here is a new question:
In your resolutions with whips (or here with typed whips), how come you use wings and other classical models for some eliminations. Can't their eliminations be done by whips, like for example eliminations linked to alignments (whip [1])?
No doubt you gave the answer in your voluminous books without us finding out where.
Thank you for your explanations.
Robert

by **denis_berthier** » Fri Apr 24, 2020 8:25 am

Mauriès Robert wrote:Hi Denis,
I read with interest your retrospective introduction of this thread. It makes me better understand the role of the rc, rn, cn, and bn spaces, and thus the notions of 2D and 3D chains.
But the subject remains, for me and a friend who is interested in your theories, still full of questions. So here is a new question:
In your resolutions with whips (or here with typed whips), how come you use wings and other classical models for some eliminations. Can't their eliminations be done by whips, like for example eliminations linked to alignments (whip [1])?

After Singles, whips[1] are the most elementary patterns. They rely on only one CSP-Variable.
In HLS, I've shown in great detail, with examples for the 4 cases, that whips[1] are equivalent to intesections/interactions/claiming+pointing - whichever name you want to give them. But there is a major difference: whips[1] have a universal meaning and they appear in all the other logic games I study in PBCS. It is therefore natural to use the universal name instead of unrelated, application-specific ones.

My general resolution framework doesn't support or exclude any type of resolution rules.
Similarly CSP-Rules is a general pattern-based CSP-Solver. It is not limited to using whips or their variants.
CSP-Rules doesn't have generic rules for Subsets. They would be much too inefficient in terms of both memory and speed.

But, in addition to the generic rules, CSP-Rules has application-specific ones, such as rules in Sudoku for (Naked, Hidden, or Super-Hidden - i.e. fish) Subsets, sk-loops, J-Exocets, Uniqueness.
For Slitherlink, CSP-Rules has still many more application-specific rules.
For any application, both the generic and the application-specific rules may be used. The user can choose to activate whichever combination of them he wants*. There are rules for uniqueness in SudoRules, but I never use them; I prefer to prove uniqueness. Subset and Finned Subsets are another topic; they are very familiar in Sudoku and, for this reason, I usually keep them activated; they introduce some variety in the resolution paths.

What remains true however is, whips/braids/... make the backbone of the classification hierarchy. Any other rule is introduced in this hierarchy in comparison with the generic chains.
You asked specifically about X-Wings. I could totally forget them: all the Subsets[2] are subsumed by whips[2]. For larger Subsets, there are rare cases that are not subsumed by whips, braids...

For the 2D-chains, as I explained at the beginning, I had almost discarded them in the transition from the old SudoRules to the SudoRules that is only a part of CSP-Rules, but I have continued requests from people using my Extended Sudoku Board for not forgetting them. So, I think I'll progressively re-introduce all those that were defined in HLS, but in a generic form.

(*) restricted only by consistency conditions (automatically guaranteed).

by **denis_berthier** » Sat Apr 25, 2020 6:20 am

Typed-bivalue-chains (2D-bivalue-chains)

Continuing with my programme of re-introducing into CSP-Rules/SudoRules the old 2D-chains (that I first introduced in HLS), I coded the bivalue chains.
As should be expected:
Definition: a typed-bivalue-chain[n] is a bivalue-chain[n] in which all the csp-variables have the same type

I'll take an easy example, namely puzzle Royle17#17265, from section XIV.3.6 of HLS2:

Code: Select all: .38.5.... ...4..2.. ......... ....815.. 46.....7. 2........ 7..6....4 ......3.. .......9.

The four resolution paths I'll give below have the same obvious start (though the order of the rule applications may be different in HLS2):

Hidden Text: Show

Let's first see what I wrote about it in HLS2:

denis_berthier in HLS2 wrote:;;; Resolution state R1 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
xy11-chain {n3 n9}r4c1 – {n9 n1}r3c1 – {n1 n7}r3c5 – {n7 n3}r3c6 – {n3 n6}r2c6 – {n6 n4}r6c6 – {n4 n5}r9c6 – {n5 n9}r5c6 – {n9 n3}r5c5 – {n3 n9}r7c5 – {n9 n3}r7c3 ==> r9c1 ≠ 3
naked and hidden singles ==> r7c3 = 3, r7c5 = 9, r5c5 = 3, r5c4 = 5, r8c4 = 1, r9c4 = 3, r5c6 = 9, r4c1 = 3
xy7-chain {n1 n7}r3c5 – {n7 n3}r3c6 – {n3 n6}r2c6 – {n6 n4}r6c6 – {n4 n5}r9c6 {n5 n8}r9c9 – {n8 n1}r9c1 ==> r3c1 ≠ 1
stte

Using the fully-supersymmetric bivalue-chains of CSP-Rules, one finds a solution in BC4.
In my fully super-symmetric approach, which makes no difference between the rc, rn, cn and bn spaces, bivalue-chains are made of bivalue or bilocal cells. They are the basic AICs (but "AIC" has been extended so much that no one knows what it means when it i used). The bivalue-chains were named nrc-chains in HLS2. In the generic approach of CSP-Rules, I can't keep the name with nrc, as it depends on the grid structure.

Hidden Text: Show

This is very different from the solution in HLS2. But, if we use instead the newly-coded typed-bivalue-chains, we get another solution, in TyBC6.

Hidden Text: Show

You can notice that each of the bivalue-chains is mono-typed, but the resolution path itself has two different types of mono-typed bivalue-chains.
This solution is still very different from that of HLS2.

However, one can go still further in restricting the types of chains one wants to use: one can select his preferred allowed types. Here, we shall allow only bivalue-chains in the rc-space, i.e. the most classical xy-chains.
The list of allowed-types in SudoRules is pre-defined by global variable ?*allowed-csp-types*: (defglobal ?*allowed-csp-types* = (create$ rc rn cn bn)).
By changing this variable in the SudoRules configuration file, one can change the allowed types. The change will apply to all the typed-chains (typed-whips, typed bivalue-chains and typed-t-whips (to be added later))

Hidden Text: Show

Now, we have exactly the same resolution path as in HLS2, modulo the translations: xy11-chain -> biv-chain-rc[11], ...

by **denis_berthier** » Mon Apr 27, 2020 10:58 am

Typed-t-whips
I've now finished coding the typed t-whips into CSP-Rules.
Let's take again the previous puzzle.
Here is what I wrote about it in HLS2, about an alternative resolution path after resolution state RS1, using xyt -chains in addition to the xy and hxy ones.

denis_berthier in HLS2 wrote:2) Resolution path in L5 using chains of more complex types (hxy and xyt):
Continuation of the resolution path in L5 for the L4_0 (or L2) elaboration of Royle17-17265:
xyt4-chain {n1 n5}r8c4 – {n5 n4}r9c6 – {n4 n2}r9c5 – {n2 n1}r9c2 ==> r9c4 ≠ 1
hidden-single-in-a-block ==> r8c4 = 1
hxy-cn4-chain {r9 r8}c5n2 – {r8 r3}c5n7 – {r3 r2}c5n1 – {r2 r9}c2n1 ==> r9c2 ≠ 2
hidden-single-in-a-row ==> r9c5 = 2
hxy-rn5-chain {c2 c5}r2n1 – {c5 c6}r2n6 – {c6 c5}r6n6 – {c5 c6}r6n4 – {c6 c2}r9n4 ==> r9c2 ≠ 1
stte

And here is what I get when I activate typed-bivalue-chains and typed-t-whips

Hidden Text: Show

The resolution path of HLS2 has been found, modulo the translation :
xyt4-chain -> t-whip-rc[4]
hxy-cn4-chain -> biv-chain-cn[4]
hxy-rn5-chain -> biv-chain-rn[5]

Now, suppose you want to work only with chains that lie completely in rc-space. Of course, longer chains will be required:

Hidden Text: Show

by **denis_berthier** » Tue May 05, 2020 9:32 pm

DEFISE wrote:Hello Denis Berthier,
It’s my first post on this forum, excuse my approximate English language (I’m french).
For some time I have been reading your puzzle resolutions on this forum and in your book (« Pattern-Based Constraint Satisfaction and Logic Puzzles » Nov 2012 Edition). Each of your resolutions is made up of alternating whips and other rules. Let’s call these other rules “basic rules”. For example, your last resolution contains a: « finned-swordfish-in-columns », so you consider it as a basic rule.
I don’t remember where you specify what you mean by basic rule, in your book.
Could you remind me ?Sincerely.

Hi DEFISE.
My apologies for not answering before, but I hadn't seen your post.
Welcome to the forum.
What I consider as basic rules are those of BRT (Singles+ECP), whips[1] (=intersections) and sometimes also Subsets. There's no definition of a basic rule. But I usually keep the previous ones active as they are the rules of SSTS (Simple Sudoku).
If you see such an alternance in my resolution paths, it's only the result of the simple-first strategy + the choice to say that a subset[k] is simpler than a chain[k] (otherwise Subsets would almost never appear).
SudoRules also contains rules that are neither whip-like nor basic at all, such as sk-loops, J-Exocets, uniqueness rules (UR, BUG) that you don't see in my resolution paths because i rarely activate them and they are rarely useful in a puzzle. The set of rules is open: you can add your own.

by **DEFISE** » Wed May 06, 2020 8:59 am

Hello Denis Berthier,
It’s not your fault because my post was approved by administrator only yesterday.
Thank you for your answer.
I’m very intersted in whips and braids, because they are mere and efficient objects for non-extreme puzzle (you said for SER < 9,5 I believe). So I recently wrote a computer program to get the shortest at any resolution state, as you do.
Perhaps I'll have an other question about this subject…

Sincerely

by **denis_berthier** » Fri May 08, 2020 11:09 pm

DEFISE wrote:I’m very intersted in whips and braids, because they are mere and efficient objects for non-extreme puzzle (you said for SER < 9,5

The limit is not absolute. SER has arbitrary boundaries. Up to 9.1, it's highly likely there'll be a whip-only solution. Between 9.1 and 9.5, g-whips, braids or g-braids may be necessary. At 9.5, it's likely none of these will be enough.
Notice that, anyway, these levels are generally much above what a human solver would want to deal with (unless some exotic pattern lowers the level, as in EasterMonster).

by **denis_berthier** » Sat Jun 06, 2020 2:51 am

Typed-z-chains (2D z-chains)

Remember that I defined a z-chain as a bivalue-chain modulo the target z (and in my super-symmetric view "bivalue" means "bivalue/bilocal"

.
As the other chain patterns in CSP-Rules, z-chains now have their typed (or 2D for Sudoku) version:
a typed-z-chain is merely a z-chain in which all the CSP-Variables have the same type (i.e. rc, rn, cn or bn).

You can see them in action in an example in another thread: http://forum.enjoysudoku.com/jun-05-2020-t38024.html

Here is also the completed table for the correspondance between the old HLS names and the new PBCS/CSP-Rules names:

Code: Select all: Name in HLS: Name in PBCS: Remarks: xy5-chain biv-chain-rc[5] hxy-uu5-chain biv-chain-uu[5] uu = rn, cn or bn nrc5-chain biv-chain[5] xyz6-chain z-chain-rc[6] hxyz-uu6-chain z-chain-uu[6] uu = rn, cn or bn nrcz6-chain z-chain[6] xyt-rc6-chain t-whip-rc[6] hxyt-uu6-chain t-whip-uu[6] uu = rn, cn or bn nrct6-chain t-whip[6] t-whips are slightly more general than nrct-chains xyzt-rc8-chain whip-rc[8] whips-rc are slightly more general than xyzt-chains hxyzt-uu8-chain whip-uu[8] uu = rn, cn or bn; whips-uu are slightly more general than xyzt-uu-chains nrczt8-chain whip[8] whips are slightly more general than nrczt-chains

by **denis_berthier** » Mon Jun 15, 2020 3:07 am

TYPED-CHAINS in KAKURO

Typed-chains are not limited to Sudoku. See here how they can be used in Kakuro: http://forum.enjoysudoku.com/typed-chains-in-kakuro-t38048.html

Sudoku Players' Forum (clone)

Typed-chains (2D-chains)

Typed-chains (2D-chains)

A simple example with typed-whips (2D-whips)

The resolution power of typed-whips (2D-whips)

Long typed-whips

Re: Typed-whips (2D-whips)

Re: Typed-whips (2D-whips)

Re: Typed-whips (2D-whips)

Typed-bivalue-chains (2D-bivalue-chains)

Typed-t-whips (2D-t-whips)

Re: Typed-whips (2D-whips)

Re: Typed-chains (2D-chains)

Re: Typed-chains (2D-chains)

Typed-z-chains (2D z-chains)

TYPED-CHAINS in KAKURO

Who is online