Typed-chains (2D-chains)

Advanced methods and approaches for solving Sudoku puzzles

Typed-chains (2D-chains)

Postby denis_berthier » Wed Apr 22, 2020 5: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.
Last edited by denis_berthier on Wed May 06, 2020 12:20 am, edited 8 times in total.
denis_berthier
2010 Supporter
 
Posts: 1997
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Wed Apr 22, 2020 5: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
(solve ".2.4..7......891.........65..48.....3..9....1.95..1.7..7.3...1263.........2.1...8")
***********************************************************************************************
*** SudoRules 20.1.s based on CSP-Rules 2.1.m, config = TyW+SFin
*** using CLIPS 6.31-r761
***********************************************************************************************
singles ==> r8c9 = 7, r8c3 = 1, r1c1 = 1, r3c4 = 1, r4c2 = 1, r8c6 = 8
174 candidates, 924 csp-links and 924 links. Density = 6.13912696830775%
whip[1]: c9n6{r6 .} ==> r6c7 ≠ 6, r4c7 ≠ 6, r5c7 ≠ 6
whip[1]: r1n5{c6 .} ==> r2c4 ≠ 5
whip[1]: c4n5{r9 .} ==> r7c5 ≠ 5, r7c6 ≠ 5, r8c5 ≠ 5, r9c6 ≠ 5
whip[1]: b4n6{r5c3 .} ==> r5c6 ≠ 6, r5c5 ≠ 6
finned-x-wing-in-columns: n8{c8 c2}{r5 r1} ==> r1c3 ≠ 8
hidden-single-in-a-row ==> r1c8 = 8
whip-bn[4]: b8n5{r9c4 r8c4} - b8n2{r8c4 r8c5} - b8n9{r8c5 r7c5} - b7n9{r7c1 .} ==> r9c1 ≠ 5
whip-bn[4]: b7n5{r7c1 r9c2} - b8n5{r9c4 r8c4} - b8n2{r8c4 r8c5} - b8n9{r8c5 .} ==> r7c1 ≠ 9
whip-rn[5]: r8n4{c8 c5} - r7n4{c6 c1} - r7n5{c1 c7} - r8n5{c8 c4} - r8n2{c4 .} ==> r9c8 ≠ 4
whip-rn[5]: r8n4{c8 c5} - r7n4{c6 c1} - r7n5{c1 c7} - r8n5{c8 c4} - r8n2{c4 .} ==> r9c7 ≠ 4
whip-bn[5]: b7n8{r7c3 r7c1} - b7n5{r7c1 r9c2} - b8n5{r9c4 r8c4} - b8n2{r8c4 r8c5} - b8n9{r8c5 .} ==> r7c3 ≠ 9
naked-single ==> r7c3 = 8
hidden-single-in-a-block ==> r9c1 = 9
whip-bn[6]: b1n9{r3c3 r1c3} - b3n9{r1c9 r3c7} - b3n2{r3c7 r2c8} - b3n4{r2c8 r2c9} - b3n3{r2c9 r1c9} - b2n3{r1c5 .} ==> r3c3 ≠ 3
whip-cn[7]: c7n8{r6 r5} - c2n8{r5 r3} - c1n8{r3 r6} - c1n2{r6 r4} - c7n2{r4 r3} - c8n2{r2 r5} - c6n2{r5 .} ==> r6c7 ≠ 4
whip-rn[4]: r6n3{c9 c5} - r6n4{c5 c9} - r6n6{c9 c4} - r4n6{c5 .} ==> r4c9 ≠ 3
whip-rn[7]: r6n4{c5 c9} - r6n3{c9 c7} - r6n8{c7 c1} - r6n2{c1 c4} - r2n2{c4 c8} - r5n2{c8 c7} - r5n8{c7 .} ==> r6c5 ≠ 6
whip-rn[6]: r1n5{c5 c6} - r1n6{c6 c3} - r2n6{c3 c4} - r6n6{c4 c9} - r6n3{c9 c7} - r3n3{c7 .} ==> r1c5 ≠ 3
whip-rn[7]: r6n6{c4 c9} - r6n4{c9 c5} - r6n3{c5 c7} - r6n8{c7 c1} - r5n8{c2 c7} - r5n2{c7 c8} - r5n4{c8 .} ==> r6c4 ≠ 2
singles ==> r6c4 = 6, r4c9 = 6, r1c9 = 9, r3c3 = 9
whip[1]: r2n6{c3 .} ==> r1c3 ≠ 6
naked-single ==> r1c3 = 3
whip[1]: b2n3{r3c6 .} ==> r3c7 ≠ 3
whip-rc[4]: r3c7{n2 n4} - r3c2{n4 n8} - r3c1{n8 n7} - r4c1{n7 .} ==> r4c7 ≠ 2
whip-rn[5]: r7n5{c7 c1} - r2n5{c1 c2} - r2n6{c2 c3} - r5n6{c3 c2} - r5n8{c2 .} ==> r5c7 ≠ 5
whip-rc[5]: r6c9{n4 n3} - r2c9{n3 n4} - r3c7{n4 n2} - r5c7{n2 n8} - r6c7{n8 .} ==> r5c8 ≠ 4
whip-rc[5]: r9c8{n3 n5} - r5c8{n5 n2} - r6c7{n2 n8} - r5c7{n8 n4} - r6c9{n4 .} ==> r4c8 ≠ 3
whip-rc[5]: r2c9{n4 n3} - r2c8{n3 n2} - r2c4{n2 n7} - r9c4{n7 n5} - r9c2{n5 .} ==> r2c2 ≠ 4
whip-cn[6]: c6n2{r5 r3} - c4n2{r2 r8} - c4n5{r8 r9} - c4n7{r9 r2} - c5n7{r3 r5} - c3n7{r5 .} ==> r4c5 ≠ 2
whip-rn[6]: r8n4{c8 c5} - r8n2{c5 c4} - r2n2{c4 c8} - r2n3{c8 c9} - r2n4{c9 c1} - r3n4{c1 .} ==> r7c7 ≠ 4
whip[1]: b9n4{r8c8 .} ==> r8c5 ≠ 4
whip-rn[6]: r6n8{c7 c1} - r6n2{c1 c5} - r8n2{c5 c4} - r2n2{c4 c8} - r5n2{c8 c7} - r5n8{c7 .} ==> r6c7 ≠ 3
naked-pairs-in-a-row: r6{c1 c7}{n2 n8} ==> r6c5 ≠ 2
naked-triplets-in-a-column: c7{r3 r5 r6}{n2 n4 n8} ==> r8c7 ≠ 4
singles ==> r8c8 = 4, r4c8 = 9
whip-cn[3]: c1n8{r3 r6} - c7n8{r6 r5} - c7n4{r5 .} ==> r3c1 ≠ 4
hidden-pairs-in-a-column: c1{n4 n5}{r2 r7} ==> r2c1 ≠ 7
finned-x-wing-in-columns: n7{c1 c5}{r3 r4} ==> r4c6 ≠ 7
whip-rn[4]: r3n3{c6 c5} - r6n3{c5 c9} - r2n3{c9 c8} - r2n2{c8 .} ==> r3c6 ≠ 2
whip[1]: c6n2{r5 .} ==> r5c5 ≠ 2
whip-rn[4]: r3n3{c6 c5} - r3n2{c5 c7} - r6n2{c7 c1} - r4n2{c1 .} ==> r4c6 ≠ 3
hidden-single-in-a-column ==> r3c6 = 3
x-wing-in-rows: n7{r3 r4}{c1 c5} ==> r5c5 ≠ 7
whip-rn[4]: r4n5{c6 c7} - r4n3{c7 c5} - r4n7{c5 c1} - r5n7{c3 .} ==> r5c6 ≠ 5
whip-rn[4]: r3n2{c7 c5} - r3n7{c5 c1} - r3n8{c1 c2} - r5n8{c2 .} ==> r5c7 ≠ 2
whip-cn[4]: c7n4{r5 r3} - c7n2{r3 r6} - c1n2{r6 r4} - c6n2{r4 .} ==> r5c6 ≠ 4
whip[1]: c6n4{r9 .} ==> r7c5 ≠ 4
whip-rn[4]: r5n5{c5 c8} - r5n2{c8 c6} - r5n7{c6 c3} - r4n7{c1 .} ==> r4c5 ≠ 5
whip-rn[4]: r9n6{c7 c6} - r1n6{c6 c5} - r1n5{c5 c6} - r4n5{c6 .} ==> r9c7 ≠ 5
whip-rc[4]: r3c7{n4 n2} - r2c8{n2 n3} - r9c8{n3 n5} - r9c2{n5 .} ==> r3c2 ≠ 4
stte
123456789
456789123
789123465
214875396
367942851
895631274
578364912
631298547
942517638



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
(solve ".2.4..7......891.........65..48.....3..9....1.95..1.7..7.3...1263.........2.1...8")
***********************************************************************************************
*** SudoRules 20.1.s based on CSP-Rules 2.1.m, config = W+SFin
*** using CLIPS 6.31-r761
***********************************************************************************************
.2.4..7......891.........65..48.....3..9....1.95..1.7..7.3...1263.........2.1...8
singles ==> r8c9 = 7, r8c3 = 1, r1c1 = 1, r3c4 = 1, r4c2 = 1, r8c6 = 8
174 candidates, 924 csp-links and 924 links. Density = 6.13912696830775%
whip[1]: c9n6{r6 .} ==> r6c7 ≠ 6, r4c7 ≠ 6, r5c7 ≠ 6
whip[1]: r1n5{c6 .} ==> r2c4 ≠ 5
whip[1]: c4n5{r9 .} ==> r7c5 ≠ 5, r7c6 ≠ 5, r8c5 ≠ 5, r9c6 ≠ 5
whip[1]: b4n6{r5c3 .} ==> r5c6 ≠ 6, r5c5 ≠ 6
finned-x-wing-in-columns: n8{c8 c2}{r5 r1} ==> r1c3 ≠ 8
hidden-single-in-a-row ==> r1c8 = 8
biv-chain[3]: r9c2{n4 n5} - r7n5{c1 c7} - b9n6{r7c7 r9c7} ==> r9c7 ≠ 4
biv-chain[4]: r9c2{n4 n5} - r7n5{c1 c7} - b9n6{r7c7 r9c7} - b9n3{r9c7 r9c8} ==> r9c8 ≠ 4
whip[4]: r7n5{c1 c7} - c7n6{r7 r9} - r9n9{c7 c8} - r9n3{c8 .} ==> r9c1 ≠ 5
biv-chain[4]: b7n5{r7c1 r9c2} - b8n5{r9c4 r8c4} - r8n2{c4 c5} - b8n9{r8c5 r7c5} ==> r7c1 ≠ 9
biv-chain[4]: b7n9{r9c1 r7c3} - b7n8{r7c3 r7c1} - r7n5{c1 c7} - b9n6{r7c7 r9c7} ==> r9c7 ≠ 9
whip[4]: r2n2{c4 c8} - r5n2{c8 c7} - c7n8{r5 r6} - r6c1{n8 .} ==> r6c4 ≠ 2
singles ==> r6c4 = 6, r4c9 = 6, r1c9 = 9
whip[1]: r2n6{c3 .} ==> r1c3 ≠ 6
naked-single ==> r1c3 = 3
whip[1]: b2n3{r3c6 .} ==> r3c7 ≠ 3
whip[4]: r8n4{c8 c5} - r8n2{c5 c4} - r2n2{c4 c8} - r3c7{n2 .} ==> r7c7 ≠ 4
whip[1]: b9n4{r8c8 .} ==> r8c5 ≠ 4
biv-chain[4]: b9n4{r8c8 r8c7} - r3c7{n4 n2} - r2n2{c8 c4} - r8c4{n2 n5} ==> r8c8 ≠ 5
whip[4]: r6n8{c7 c1} - r6n2{c1 c5} - c6n2{r4 r3} - r3c7{n2 .} ==> r6c7 ≠ 4
biv-chain[5]: r7c3{n8 n9} - b8n9{r7c5 r8c5} - b8n2{r8c5 r8c4} - b8n5{r8c4 r9c4} - b7n5{r9c2 r7c1} ==> r7c1 ≠ 8
singles ==> r7c3 = 8, r9c1 = 9, r3c3 = 9
biv-chain[3]: r5n8{c7 c2} - r3c2{n8 n4} - r3c7{n4 n2} ==> r5c7 ≠ 2
whip[3]: c6n2{r5 r3} - r2n2{c4 c8} - r5n2{c8 .} ==> r6c5 ≠ 2
naked-pairs-in-a-row: r6{c5 c9}{n3 n4} ==> r6c7 ≠ 3
biv-chain[3]: c1n8{r3 r6} - r6n2{c1 c7} - r3c7{n2 n4} ==> r3c1 ≠ 4
hidden-pairs-in-a-column: c1{n4 n5}{r2 r7} ==> r2c1 ≠ 7
finned-x-wing-in-columns: n7{c1 c5}{r3 r4} ==> r4c6 ≠ 7
biv-chain[3]: b6n9{r4c8 r4c7} - c7n3{r4 r9} - r9c8{n3 n5} ==> r4c8 ≠ 5
whip[3]: c6n2{r5 r3} - r2n2{c4 c8} - r5n2{c8 .} ==> r4c5 ≠ 2
biv-chain[4]: r3c7{n2 n4} - c9n4{r2 r6} - r6c5{n4 n3} - b2n3{r3c5 r3c6} ==> r3c6 ≠ 2
whip[1]: c6n2{r5 .} ==> r5c5 ≠ 2
biv-chain[4]: r3n2{c7 c5} - r2c4{n2 n7} - c3n7{r2 r5} - r4c1{n7 n2} ==> r4c7 ≠ 2
biv-chain[4]: r9n4{c6 c2} - r3n4{c2 c7} - c7n2{r3 r6} - r5n2{c8 c6} ==> r5c6 ≠ 4
whip[1]: c6n4{r9 .} ==> r7c5 ≠ 4
biv-chain[4]: c7n2{r6 r3} - r3n4{c7 c2} - r9c2{n4 n5} - c8n5{r9 r5} ==> r5c8 ≠ 2
hidden-single-in-a-row ==> r5c6 = 2
whip[1]: b5n7{r5c5 .} ==> r3c5 ≠ 7
biv-chain[3]: r4n7{c5 c1} - r3n7{c1 c6} - c6n3{r3 r4} ==> r4c5 ≠ 3
biv-chain[3]: r6c9{n3 n4} - r5c8{n4 n5} - r9c8{n5 n3} ==> r4c8 ≠ 3
biv-chain[3]: r5c8{n5 n4} - r8c8{n4 n9} - b6n9{r4c8 r4c7} ==> r4c7 ≠ 5
whip[1]: b6n5{r5c8 .} ==> r5c5 ≠ 5
biv-chain[4]: c9n4{r2 r6} - r6c5{n4 n3} - r3c5{n3 n2} - r3c7{n2 n4} ==> r2c8 ≠ 4
biv-chain[4]: r8n5{c7 c4} - c4n2{r8 r2} - r2c8{n2 n3} - r9c8{n3 n5} ==> r7c7 ≠ 5
stte



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
(solve ".2.4..7......891.........65..48.....3..9....1.95..1.7..7.3...1263.........2.1...8")
***********************************************************************************************
*** SudoRules 20.1.s based on CSP-Rules 2.1.s, config = W+SFin
*** using CLIPS 6.31-r761
***********************************************************************************************
.2.4..7......891.........65..48.....3..9....1.95..1.7..7.3...1263.........2.1...8
singles ==> r8c9 = 7, r8c3 = 1, r1c1 = 1, r3c4 = 1, r4c2 = 1, r8c6 = 8
174 candidates, 924 csp-links and 924 links. Density = 6.13912696830775%
whip[1]: c9n6{r6 .} ==> r6c7 ≠ 6, r4c7 ≠ 6, r5c7 ≠ 6
whip[1]: r1n5{c6 .} ==> r2c4 ≠ 5
whip[1]: c4n5{r9 .} ==> r7c5 ≠ 5, r7c6 ≠ 5, r8c5 ≠ 5, r9c6 ≠ 5
whip[1]: b4n6{r5c3 .} ==> r5c6 ≠ 6, r5c5 ≠ 6
finned-x-wing-in-columns: n8{c8 c2}{r5 r1} ==> r1c3 ≠ 8
hidden-single-in-a-row ==> r1c8 = 8
whip[3]: r8n4{c8 c5} - r7c6{n4 n6} - c7n6{r7 .} ==> r9c7 ≠ 4
whip-bn[4]: b8n5{r9c4 r8c4} - b8n2{r8c4 r8c5} - b8n9{r8c5 r7c5} - b7n9{r7c1 .} ==> r9c1 ≠ 5
whip-bn[4]: b7n5{r7c1 r9c2} - b8n5{r9c4 r8c4} - b8n2{r8c4 r8c5} - b8n9{r8c5 .} ==> r7c1 ≠ 9
whip[4]: r8n4{c8 c5} - r7c6{n4 n6} - r9n6{c6 c7} - r9n3{c7 .} ==> r9c8 ≠ 4
whip[4]: c6n4{r9 r5} - c8n4{r5 r2} - r2n2{c8 c4} - r8n2{c4 .} ==> r8c5 ≠ 4
whip[1]: r8n4{c8 .} ==> r7c7 ≠ 4
whip[4]: r2n2{c4 c8} - r5n2{c8 c7} - c7n8{r5 r6} - r6c1{n8 .} ==> r6c4 ≠ 2
singles ==> r6c4 = 6, r4c9 = 6, r1c9 = 9
whip[1]: r2n6{c3 .} ==> r1c3 ≠ 6
naked-single ==> r1c3 = 3
whip[1]: b2n3{r3c6 .} ==> r3c7 ≠ 3
whip[4]: r6n8{c7 c1} - r6n2{c1 c5} - c6n2{r4 r3} - r3c7{n2 .} ==> r6c7 ≠ 4
whip[4]: b9n4{r8c8 r8c7} - r3c7{n4 n2} - b2n2{r3c5 r2c4} - r8c4{n2 .} ==> r8c8 ≠ 5
whip[4]: r9n6{c7 c6} - r7c6{n6 n4} - r7c5{n4 n9} - b7n9{r7c3 .} ==> r9c7 ≠ 9
whip-bn[5]: b7n8{r7c3 r7c1} - b7n5{r7c1 r9c2} - b8n5{r9c4 r8c4} - b8n2{r8c4 r8c5} - b8n9{r8c5 .} ==> r7c3 ≠ 9
singles ==> r7c3 = 8, r9c1 = 9, r3c3 = 9
whip[3]: r3c7{n2 n4} - r3c2{n4 n8} - r5n8{c2 .} ==> r5c7 ≠ 2
whip-rn[3]: r8n2{c5 c4} - r2n2{c4 c8} - r5n2{c8 .} ==> r6c5 ≠ 2
naked-pairs-in-a-row: r6{c5 c9}{n3 n4} ==> r6c7 ≠ 3
whip-rn[3]: r8n2{c5 c4} - r2n2{c4 c8} - r5n2{c8 .} ==> r4c5 ≠ 2
whip[3]: c1n8{r3 r6} - r6c7{n8 n2} - r3c7{n2 .} ==> r3c1 ≠ 4
hidden-pairs-in-a-column: c1{n4 n5}{r2 r7} ==> r2c1 ≠ 7
finned-x-wing-in-columns: n7{c1 c5}{r3 r4} ==> r4c6 ≠ 7
whip[3]: r9c8{n5 n3} - c7n3{r9 r4} - r4n9{c7 .} ==> r4c8 ≠ 5
whip-rc[4]: r4c1{n2 n7} - r3c1{n7 n8} - r3c2{n8 n4} - r3c7{n4 .} ==> r4c7 ≠ 2
whip-rn[4]: r2n6{c2 c3} - r2n7{c3 c4} - r9n7{c4 c6} - r9n4{c6 .} ==> r2c2 ≠ 4
whip-rn[4]: r3n3{c6 c5} - r6n3{c5 c9} - r2n3{c9 c8} - r2n2{c8 .} ==> r3c6 ≠ 2
whip[1]: c6n2{r5 .} ==> r5c5 ≠ 2
whip[4]: r1c6{n5 n6} - r9n6{c6 c7} - r9n3{c7 c8} - c8n5{r9 .} ==> r5c6 ≠ 5
whip[4]: r7n5{c7 c1} - r9c2{n5 n4} - r3c2{n4 n8} - r5n8{c2 .} ==> r5c7 ≠ 5
naked-triplets-in-a-column: c7{r3 r5 r6}{n2 n4 n8} ==> r8c7 ≠ 4
singles ==> r8c8 = 4, r4c8 = 9
whip[3]: r3c6{n3 n7} - c1n7{r3 r4} - r4n2{c1 .} ==> r4c6 ≠ 3
hidden-single-in-a-column ==> r3c6 = 3
x-wing-in-rows: n7{r3 r4}{c1 c5} ==> r5c5 ≠ 7
whip[3]: b5n2{r5c6 r4c6} - r4c1{n2 n7} - r5n7{c3 .} ==> r5c6 ≠ 4
whip[1]: c6n4{r9 .} ==> r7c5 ≠ 4
whip[3]: r4c6{n5 n2} - r5n2{c6 c8} - r5n5{c8 .} ==> r4c5 ≠ 5
whip[3]: r9n6{c7 c6} - r1c6{n6 n5} - r4n5{c6 .} ==> r9c7 ≠ 5
whip-rc[4]: r3c7{n4 n2} - r2c8{n2 n3} - r9c8{n3 n5} - r9c2{n5 .} ==> r3c2 ≠ 4
stte
Last edited by denis_berthier on Mon Apr 27, 2020 1:34 pm, edited 2 times in total.
denis_berthier
2010 Supporter
 
Posts: 1997
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Wed Apr 22, 2020 5: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.
Last edited by denis_berthier on Mon Apr 27, 2020 1:32 pm, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1997
Joined: 19 June 2007
Location: Paris

Long typed-whips

Postby denis_berthier » Wed Apr 22, 2020 8: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
(solve "....5..89..718.........25..2....4..38..5...2.9.1.2.....1....46...274.......6.8.5.")
***********************************************************************************************
*** SudoRules 20.1.s based on CSP-Rules 2.1.s, config = TyW+SFin
*** using CLIPS 6.31-r761
***********************************************************************************************
singles ==> r7c4 = 2, r6c9 = 5
187 candidates, 1098 csp-links and 1098 links. Density = 6.31361048818354%
whip[1]: c1n7{r9 .} ==> r9c2 ≠ 7
whip[1]: c9n8{r8 .} ==> r8c7 ≠ 8
finned-swordfish-in-columns: n9{c4 c8 c3}{r3 r4 r8} ==> r8c2 ≠ 9
whip-rn[5]: r7n9{c6 c3} - r7n8{c3 c9} - r8n8{c9 c2} - r8n6{c2 c1} - r8n5{c1 .} ==> r8c6 ≠ 9
whip[1]: r8n9{c8 .} ==> r9c7 ≠ 9
whip-rc[6]: r7c5{n9 n3} - r7c6{n3 n5} - r8c6{n5 n1} - r8c9{n1 n8} - r7c9{n8 n7} - r7c1{n7 .} ==> r7c3 ≠ 9
whip[1]: r7n9{c6 .} ==> r9c5 ≠ 9
whip-rc[6]: r7c5{n3 n9} - r7c6{n9 n5} - r7c1{n5 n7} - r9c1{n7 n4} - r9c3{n4 n9} - r9c2{n9 .} ==> r7c3 ≠ 3
whip-rc[7]: r1c4{n3 n4} - r3c4{n4 n9} - r2c6{n9 n6} - r1c6{n6 n7} - r6c6{n7 n3} - r6c4{n3 n8} - r4c4{n8 .} ==> r3c5 ≠ 3
whip-rc[9]: r1c4{n4 n3} - r1c3{n3 n6} - r1c1{n6 n1} - r3c1{n1 n3} - r2c1{n3 n5} - r7c1{n5 n7} - r7c9{n7 n8} - r7c3{n8 n5} - r4c3{n5 .} ==> r1c2 ≠ 4
whip-rc[10]: r2c8{n3 n4} - r6c8{n4 n7} - r3c8{n7 n1} - r4c8{n1 n9} - r4c4{n9 n8} - r6c4{n8 n3} - r6c6{n3 n6} - r2c6{n6 n9} - r3c4{n9 n4} - r1c4{n4 .} ==> r2c7 ≠ 3
whip-cn[13]: c2n8{r3 r8} - c3n8{r7 r3} - c3n9{r3 r9} - c2n9{r9 r2} - c2n5{r2 r4} - c3n5{r4 r7} - c1n5{r8 r2} - c1n4{r2 r9} - c3n4{r9 r5} - c3n3{r5 r1} - c3n6{r1 r4} - c2n6{r6 r1} - c2n2{r1 .} ==> r3c2 ≠ 4
whip-rc[14]: r2c8{n3 n4} - r6c8{n4 n7} - r3c8{n7 n1} - r4c8{n1 n9} - r4c4{n9 n8} - r6c4{n8 n3} - r1c4{n3 n4} - r1c3{n4 n6} - r4c3{n6 n5} - r7c3{n5 n8} - r7c9{n8 n7} - r3c9{n7 n6} - r2c9{n6 n2} - r2c7{n2 .} ==> r1c7 ≠ 3
whip[1]: c7n3{r9 .} ==> r8c8 ≠ 3
whip-rn[10]: r2n5{c1 c2} - r2n9{c2 c6} - r7n9{c6 c5} - r7n3{c5 c6} - r1n3{c6 c4} - r6n3{c4 c2} - r6n4{c2 c8} - r2n4{c8 c9} - r2n2{c9 c7} - r2n6{c7 .} ==> r2c1 ≠ 3
whip-cn[15]: c6n1{r5 r8} - c5n1{r9 r4} - c8n1{r4 r3} - c9n1{r3 r9} - c9n2{r9 r2} - c7n2{r2 r9} - c7n3{r9 r8} - c7n9{r8 r4} - c7n8{r4 r6} - c7n7{r6 r1} - c7n6{r1 r2} - c9n6{r2 r5} - c5n6{r5 r3} - c5n7{r3 r5} - c6n7{r5 .} ==> r5c7 ≠ 1
whip-rc[22]: r1c4{n3 n4} - r1c3{n4 n6} - r4c3{n6 n5} - r7c3{n5 n8} - r7c9{n8 n7} - r7c1{n7 n5} - r2c1{n5 n4} - r3c3{n4 n9} - r3c4{n9 n3} - r1c6{n3 n7} - r3c5{n7 n6} - r2c6{n6 n9} - r7c6{n9 n3} - r9c5{n3 n1} - r9c9{n1 n2} - r2c9{n2 n6} - r2c7{n6 n2} - r1c7{n2 n1} - r3c9{n1 n4} - r5c9{n4 n1} - r5c6{n1 n6} - r6c6{n6 .} ==> r1c1 ≠ 3
whip-rc[24]: r9c5{n1 n3} - r7c5{n3 n9} - r7c6{n9 n5} - r7c3{n5 n8} - r7c9{n8 n7} - r9c7{n7 n2} - r2c7{n2 n6} - r3c9{n6 n4} - r2c8{n4 n3} - r2c6{n3 n9} - r3c4{n9 n3} - r6c4{n3 n8} - r6c7{n8 n7} - r5c9{n7 n6} - r5c7{n6 n9} - r4c8{n9 n1} - r3c8{n1 n7} - r3c5{n7 n6} - r4c5{n6 n7} - r5c5{n7 n1} - r5c6{n1 n3} - r5c3{n3 n4} - r9c3{n4 n9} - r3c3{n9 .} ==> r9c9 ≠ 1
whip-rn[6]: r1n1{c1 c7} - r9n1{c7 c5} - r4n1{c5 c8} - r8n1{c8 c9} - r8n8{c9 c2} - r8n6{c2 .} ==> r1c1 ≠ 6
whip-cn[12]: c2n8{r3 r8} - c3n8{r7 r3} - c3n9{r3 r9} - c3n3{r9 r5} - c3n4{r5 r1} - c1n4{r3 r9} - c1n7{r9 r7} - c1n3{r7 r8} - c1n5{r8 r2} - c1n6{r2 r3} - c3n6{r1 r4} - c2n6{r4 .} ==> r3c2 ≠ 3
whip-rc[15]: r7c9{n7 n8} - r8c9{n8 n1} - r8c8{n1 n9} - r8c7{n9 n3} - r9c7{n3 n2} - r2c7{n2 n6} - r3c9{n6 n4} - r2c8{n4 n3} - r2c6{n3 n9} - r3c4{n9 n3} - r1c4{n3 n4} - r1c1{n4 n1} - r3c1{n1 n6} - r8c1{n6 n5} - r8c6{n5 .} ==> r9c9 ≠ 7
naked-single ==> r9c9 = 2
whip-rc[7]: r9c5{n3 n1} - r9c7{n1 n7} - r7c9{n7 n8} - r7c3{n8 n5} - r4c3{n5 n6} - r1c3{n6 n4} - r5c3{n4 .} ==> r9c3 ≠ 3
whip-bn[7]: b4n4{r6c2 r5c3} - b7n4{r9c3 r9c1} - b7n7{r9c1 r7c1} - b9n7{r7c9 r9c7} - b9n3{r9c7 r8c7} - b7n3{r8c2 r9c2} - b4n3{r5c2 .} ==> r2c2 ≠ 4
whip-rn[8]: r3n8{c2 c3} - r7n8{c3 c9} - r7n7{c9 c1} - r9n7{c1 c7} - r1n7{c7 c6} - r1n6{c6 c7} - r6n6{c7 c6} - r2n6{c6 .} ==> r3c2 ≠ 6
whip-cn[18]: c6n1{r8 r5} - c9n1{r5 r3} - c7n1{r1 r4} - c7n8{r4 r6} - c4n8{r6 r4} - c4n9{r4 r3} - c3n9{r3 r9} - c2n9{r9 r2} - c6n9{r2 r7} - c6n5{r7 r8} - c2n5{r8 r4} - c3n5{r4 r7} - c3n8{r7 r3} - c2n8{r3 r8} - c9n8{r8 r7} - c9n7{r7 r5} - c9n4{r5 r2} - c9n6{r2 .} ==> r8c8 ≠ 1
naked-single ==> r8c8 = 9
whip-rc[8]: r1c1{n1 n4} - r1c4{n4 n3} - r1c3{n3 n6} - r4c3{n6 n5} - r7c3{n5 n8} - r7c9{n8 n7} - r9c7{n7 n3} - r8c7{n3 .} ==> r1c7 ≠ 1
hidden-single-in-a-row ==> r1c1 = 1
whip-bn[5]: b9n7{r7c9 r9c7} - b3n7{r1c7 r3c8} - b3n1{r3c8 r3c9} - b9n1{r8c9 r8c7} - b9n3{r8c7 .} ==> r5c9 ≠ 7
whip-rc[7]: r2c8{n3 n4} - r2c9{n4 n6} - r2c7{n6 n2} - r1c7{n2 n7} - r1c6{n7 n6} - r6c6{n6 n7} - r6c8{n7 .} ==> r2c6 ≠ 3
whip-rn[9]: r4n8{c7 c4} - r4n9{c4 c5} - r7n9{c5 c6} - r2n9{c6 c2} - r2n5{c2 c1} - r7n5{c1 c3} - r4n5{c3 c2} - r4n7{c2 c8} - r4n1{c8 .} ==> r4c7 ≠ 6
whip-rn[9]: r4n8{c7 c4} - r4n9{c4 c5} - r7n9{c5 c6} - r2n9{c6 c2} - r2n5{c2 c1} - r7n5{c1 c3} - r7n8{c3 c9} - r7n7{c9 c1} - r9n7{c1 .} ==> r4c7 ≠ 7
whip-rc[10]: r4c4{n9 n8} - r6c4{n8 n3} - r1c4{n3 n4} - r3c4{n4 n9} - r2c6{n9 n6} - r6c6{n6 n7} - r5c6{n7 n1} - r5c5{n1 n6} - r5c9{n6 n4} - r2c9{n4 .} ==> r4c5 ≠ 9
hidden-pairs-in-a-row: r4{n8 n9}{c4 c7} ==> r4c7 ≠ 1
whip[1]: c7n1{r9 .} ==> r8c9 ≠ 1
singles ==> r8c9 = 8, r7c9 = 7, r9c1 = 7, r7c3 = 8, r3c2 = 8, r4c3 = 5
whip[1]: c1n4{r3 .} ==> r1c3 ≠ 4, r3c3 ≠ 4
hidden-single-in-a-row ==> r1c4 = 4
naked-pairs-in-a-row: r9{c5 c7}{n1 n3} ==> r9c2 ≠ 3
whip-rn[3]: r2n9{c6 c2} - r2n5{c2 c1} - r7n5{c1 .} ==> r7c6 ≠ 9
hidden-single-in-a-block ==> r7c5 = 9
finned-x-wing-in-rows: n3{r7 r1}{c6 c1} ==> r3c1 ≠ 3
whip[1]: c1n3{r8 .} ==> r8c2 ≠ 3
whip-rc[4]: r2c8{n3 n4} - r2c9{n4 n6} - r2c6{n6 n9} - r3c4{n9 .} ==> r3c8 ≠ 3
hidden-single-in-a-block ==> r2c8 = 3
hidden-pairs-in-a-row: r3{n3 n9}{c3 c4} ==> r3c3 ≠ 6
finned-x-wing-in-columns: n6{c3 c9}{r5 r1} ==> r1c7 ≠ 6
whip-rn[4]: r4n6{c2 c5} - r3n6{c5 c9} - r3n1{c9 c8} - r4n1{c8 .} ==> r1c2 ≠ 6
whip-rn[4]: r4n6{c2 c5} - r3n6{c5 c9} - r3n1{c9 c8} - r4n1{c8 .} ==> r2c2 ≠ 6
whip-rn[5]: r4n6{c2 c5} - r4n1{c5 c8} - r3n1{c8 c9} - r3n6{c9 c1} - r8n6{c1 .} ==> r5c2 ≠ 6
whip-rn[5]: r4n6{c2 c5} - r4n1{c5 c8} - r3n1{c8 c9} - r3n6{c9 c1} - r8n6{c1 .} ==> r6c2 ≠ 6
whip-rc[4]: r6c8{n7 n4} - r6c2{n4 n3} - r1c2{n3 n2} - r1c7{n2 .} ==> r6c7 ≠ 7
finned-x-wing-in-columns: n7{c7 c6}{r1 r5} ==> r5c5 ≠ 7
whip-rc[4]: r2c6{n6 n9} - r3c4{n9 n3} - r6c4{n3 n8} - r6c7{n8 .} ==> r6c6 ≠ 6
stte
123456789
457189236
689372541
275964813
836517924
941823675
318295467
562741398
794638152


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
(solve "....5..89..718.........25..2....4..38..5...2.9.1.2.....1....46...274.......6.8.5.")
***********************************************************************************************
*** SudoRules 20.1.s based on CSP-Rules 2.1.s, config = W+SFin
*** using CLIPS 6.31-r761
***********************************************************************************************
singles ==> r7c4 = 2, r6c9 = 5
187 candidates, 1098 csp-links and 1098 links. Density = 6.31361048818354%
whip[1]: c1n7{r9 .} ==> r9c2 ≠ 7
whip[1]: c9n8{r8 .} ==> r8c7 ≠ 8
finned-swordfish-in-columns: n9{c4 c8 c3}{r3 r4 r8} ==> r8c2 ≠ 9
whip[4]: r7n9{c6 c3} - r7n8{c3 c9} - r8c9{n8 n1} - b8n1{r8c6 .} ==> r9c5 ≠ 9
whip[4]: r9n9{c3 c7} - r9n2{c7 c9} - b9n7{r9c9 r7c9} - r7n8{c9 .} ==> r7c3 ≠ 9
whip[1]: r7n9{c6 .} ==> r8c6 ≠ 9
whip[1]: r8n9{c8 .} ==> r9c7 ≠ 9
whip[4]: c1n4{r3 r9} - c1n7{r9 r7} - r7c9{n7 n8} - c3n8{r7 .} ==> r3c3 ≠ 4
whip[4]: b2n7{r3c5 r1c6} - b2n6{r1c6 r2c6} - r6c6{n6 n3} - b8n3{r7c6 .} ==> r3c5 ≠ 3
whip[5]: r3n8{c2 c3} - c3n9{r3 r9} - r9c2{n9 n3} - b4n3{r6c2 r5c3} - c3n4{r5 .} ==> r3c2 ≠ 4
whip[5]: r3n8{c2 c3} - c3n9{r3 r9} - r9c2{n9 n4} - b4n4{r6c2 r5c3} - b4n3{r5c3 .} ==> r3c2 ≠ 3
whip[5]: r7n8{c3 c9} - r8n8{c9 c2} - r8n6{c2 c1} - b7n5{r8c1 r7c1} - r7n7{c1 .} ==> r7c3 ≠ 3
whip[6]: r9n9{c3 c2} - b1n9{r2c2 r3c3} - c3n8{r3 r7} - r7c9{n8 n7} - r9n7{c9 c1} - r9n4{c1 .} ==> r9c3 ≠ 3
whip[4]: b4n4{r6c2 r5c3} - r9c3{n4 n9} - r9c2{n9 n3} - b4n3{r5c2 .} ==> r2c2 ≠ 4
whip[4]: b4n4{r6c2 r5c3} - r9c3{n4 n9} - r9c2{n9 n3} - b4n3{r5c2 .} ==> r1c2 ≠ 4
whip[6]: r1c4{n3 n4} - r3c4{n4 n9} - c3n9{r3 r9} - c3n4{r9 r5} - r6n4{c2 c8} - r2c8{n4 .} ==> r2c6 ≠ 3
whip[4]: c8n3{r3 r8} - c8n9{r8 r4} - c4n9{r4 r3} - b2n3{r3c4 .} ==> r1c7 ≠ 3
whip[4]: c7n8{r4 r6} - r6c4{n8 n3} - b2n3{r3c4 r1c6} - r1n7{c6 .} ==> r4c7 ≠ 7
whip[5]: r3n8{c2 c3} - b1n9{r3c3 r2c2} - r2c6{n9 n6} - b3n6{r2c7 r1c7} - r6n6{c7 .} ==> r3c2 ≠ 6
whip[5]: r2n9{c6 c2} - r2n5{c2 c1} - r7n5{c1 c3} - c3n8{r7 r3} - r3c2{n8 .} ==> r7c6 ≠ 9
hidden-single-in-a-block ==> r7c5 = 9
whip[2]: b4n3{r6c2 r5c3} - c5n3{r5 .} ==> r9c2 ≠ 3
naked-pairs-in-a-block: b7{r9c2 r9c3}{n4 n9} ==> r9c1 ≠ 4
whip[1]: c1n4{r3 .} ==> r1c3 ≠ 4
biv-chain[3]: c8n9{r8 r4} - b5n9{r4c4 r5c6} - c6n1{r5 r8} ==> r8c8 ≠ 1
whip[3]: r7n3{c1 c6} - r6n3{c6 c4} - b2n3{r1c4 .} ==> r8c2 ≠ 3
whip[1]: b7n3{r9c1 .} ==> r1c1 ≠ 3, r2c1 ≠ 3, r3c1 ≠ 3
biv-chain[4]: r5n9{c7 c6} - r2c6{n9 n6} - r3c5{n6 n7} - r1n7{c6 c7} ==> r5c7 ≠ 7
whip[4]: r1c3{n6 n3} - b2n3{r1c4 r3c4} - r3n9{c4 c2} - r3n8{c2 .} ==> r3c3 ≠ 6
whip[5]: r5n9{c7 c6} - r2c6{n9 n6} - r3c5{n6 n7} - c8n7{r3 r6} - c6n7{r6 .} ==> r4c8 ≠ 9
hidden-single-in-a-column ==> r8c8 = 9
whip[1]: b9n3{r9c7 .} ==> r2c7 ≠ 3
hidden-pairs-in-a-row: r4{n8 n9}{c4 c7} ==> r4c7 ≠ 6, r4c7 ≠ 1
whip[6]: b9n7{r9c9 r9c7} - r9c1{n7 n3} - c5n3{r9 r5} - b4n3{r5c2 r6c2} - r6n7{c2 c6} - r1n7{c6 .} ==> r5c9 ≠ 7
whip[6]: c3n6{r5 r1} - r4n6{c3 c5} - r3c5{n6 n7} - r5n7{c5 c6} - c6n6{r5 r2} - c6n9{r2 .} ==> r5c2 ≠ 6
whip[6]: r9c1{n7 n3} - c5n3{r9 r5} - b4n3{r5c2 r6c2} - r6n4{c2 c8} - r6n7{c8 c6} - r1n7{c6 .} ==> r9c7 ≠ 7
whip[1]: b9n7{r9c9 .} ==> r3c9 ≠ 7
whip[4]: r3c5{n7 n6} - r4c5{n6 n1} - c8n1{r4 r3} - r3n7{c8 .} ==> r5c5 ≠ 7
whip[4]: b6n6{r5c9 r6c7} - c7n7{r6 r1} - b2n7{r1c6 r3c5} - c5n6{r3 .} ==> r5c6 ≠ 6
whip[5]: r1n4{c4 c1} - r1n1{c1 c7} - r1n7{c7 c6} - r3c5{n7 n6} - r3c9{n6 .} ==> r3c4 ≠ 4
hidden-single-in-a-block ==> r1c4 = 4
naked-triplets-in-a-row: r3{c2 c3 c4}{n9 n8 n3} ==> r3c8 ≠ 3
hidden-single-in-a-block ==> r2c8 = 3
whip[5]: c6n1{r8 r5} - c7n1{r5 r1} - r1c1{n1 n6} - r8n6{c1 c2} - r8n8{c2 .} ==> r8c9 ≠ 1
singles ==> r8c9 = 8, r7c9 = 7, r9c1 = 7, r7c3 = 8, r3c2 = 8, r4c3 = 5
finned-x-wing-in-columns: n6{c3 c9}{r5 r1} ==> r1c7 ≠ 6
biv-chain[4]: c6n1{r8 r5} - r5n7{c6 c2} - r4c2{n7 n6} - r8c2{n6 n5} ==> r8c6 ≠ 5
singles ==> r7c6 = 5, r7c1 = 3
biv-chain[4]: r4n6{c2 c5} - c5n7{r4 r3} - r1n7{c6 c7} - r1n2{c7 c2} ==> r1c2 ≠ 6
whip[4]: r1c1{n1 n6} - c3n6{r1 r5} - b6n6{r5c7 r6c7} - c7n7{r6 .} ==> r1c7 ≠ 1
hidden-single-in-a-row ==> r1c1 = 1
whip[4]: b3n6{r2c9 r3c9} - r3n1{c9 c8} - r4c8{n1 n7} - r4c2{n7 .} ==> r2c2 ≠ 6
whip[4]: r2n4{c9 c1} - r3c1{n4 n6} - c9n6{r3 r5} - c3n6{r5 .} ==> r2c9 ≠ 2
hidden-single-in-a-column ==> r9c9 = 2
whip[1]: b9n1{r9c7 .} ==> r5c7 ≠ 1
whip[4]: r5c7{n6 n9} - c6n9{r5 r2} - c6n6{r2 r1} - c3n6{r1 .} ==> r5c5 ≠ 6
naked-pairs-in-a-column: c5{r5 r9}{n1 n3} ==> r4c5 ≠ 1
singles ==> r4c8 = 1, r3c9 = 1
whip[1]: b3n6{r2c9 .} ==> r2c1 ≠ 6, r2c6 ≠ 6
singles ==> r2c6 = 9, r3c4 = 3, r3c3 = 9, r9c3 = 4, r9c2 = 9, r6c4 = 8, r4c4 = 9, r4c7 = 8, r5c7 = 9
whip[1]: b6n7{r6c8 .} ==> r6c2 ≠ 7, r6c6 ≠ 7
finned-x-wing-in-columns: n6{c6 c3}{r1 r6} ==> r6c2 ≠ 6
biv-chain[3]: r6c6{n3 n6} - r4n6{c5 c2} - r5c3{n6 n3} ==> r5c5 ≠ 3
singles ==> r5c5 = 1, r9c5 = 3, r8c6 = 1, r8c7 = 3, r9c7 = 1
biv-chain[3]: r6c6{n3 n6} - r4n6{c5 c2} - r5c3{n6 n3} ==> r5c6 ≠ 3
stte
Last edited by denis_berthier on Mon Apr 27, 2020 1:34 pm, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1997
Joined: 19 June 2007
Location: Paris

Re: Typed-whips (2D-whips)

Postby DEFISE » Wed Apr 22, 2020 10: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.
DEFISE
 
Posts: 69
Joined: 16 April 2020
Location: France

Re: Typed-whips (2D-whips)

Postby Mauriès Robert » Fri Apr 24, 2020 10: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
Mauriès Robert
 
Posts: 463
Joined: 07 November 2019
Location: France

Re: Typed-whips (2D-whips)

Postby denis_berthier » Fri Apr 24, 2020 11: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).
denis_berthier
2010 Supporter
 
Posts: 1997
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Sat Apr 25, 2020 9: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
***********************************************************************************************
*** SudoRules 20.1.s based on CSP-Rules 2.1.s, config = BC+S
*** using CLIPS 6.32-r763
***********************************************************************************************
singles ==> r6c2 = 8, r4c8 = 4, r1c7 = 4, r4c9 = 6, r5c9 = 2, r4c4 = 2, r1c6 = 2, r5c7 = 8, r7c7 = 1, r6c7 = 9, r5c3 = 1, r6c3 = 5
212 candidates, 1303 csp-links and 1303 links. Density = 5.83%
whip[1]: r5n3{c6 .} ==> r6c6 ≠ 3, r6c4 ≠ 3, r6c5 ≠ 3
singles ==> r6c4 = 7, r1c9 = 7, r3c7 = 6, r1c8 = 1, r1c4 = 9, r1c1 = 6, r6c8 = 3, r6c9 = 1, r9c7 = 7, r9c3 = 6, r8c8 = 6, r7c8 = 2, r7c6 = 8, r3c4 = 8, r3c8 = 5, r2c8 = 8,r7c2 = 5, r2c1 = 5
whip[1]: c4n1{r9 .} ==> r8c5 ≠ 1, r9c5 ≠ 1
;;; naked-pairs are a special kind of typed-bivalue-chain[2]
naked-pairs-in-a-column: c5{r5 r7}{n3 n9} ==> r9c5 ≠ 3, r8c5 ≠ 9, r3c5 ≠ 3, r2c5 ≠ 3
whip[1]: b2n3{r3c6 .} ==> r5c6 ≠ 3, r9c6 ≠ 3
;;; hidden-pairs are a special kind of typed-bivalue-chain[2]
hidden-pairs-in-a-column: c3{n2 n4}{r3 r8} ==> r8c3 ≠ 9, r3c3 ≠ 9, r3c3 ≠ 7
hidden-pairs-in-a-row: r3{n2 n4}{c2 c3} ==> r3c2 ≠ 9, r3c2 ≠ 7, r3c2 ≠ 1
whip[1]: r3n7{c6 .} ==> r2c5 ≠ 7, r2c6 ≠ 7
;;; Resolution state R1 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<


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
***********************************************************************************************
*** SudoRules 20.1.s based on CSP-Rules 2.1.s, config = BC+S
*** using CLIPS 6.32-r763
***********************************************************************************************
...
;;; Resolution state R1 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
biv-chain[3]: c1n8{r8 r9} - r9n3{c1 c4} - b8n1{r9c4 r8c4} ==> r8c1 ≠ 1
biv-chain[4]: r5c4{n5 n3} - r9n3{c4 c1} - b7n8{r9c1 r8c1} - r8c9{n8 n5} ==> r8c4 ≠ 5
naked-single ==> r8c4 = 1
biv-chain[4]: c5n7{r8 r3} - r3n1{c5 c1} - b7n1{r9c1 r9c2} - r9n2{c2 c5} ==> r8c5 ≠ 2
hidden-single-in-a-block ==> r9c5 = 2
biv-chain[4]: r3n1{c5 c1} - b7n1{r9c1 r9c2} - r9n4{c2 c6} - r8c5{n4 n7} ==> r3c5 ≠ 7
stte
638952417
517463289
924817653
379281546
461539872
285746931
753698124
892174365
146325798



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
***********************************************************************************************
*** SudoRules 20.1.s based on CSP-Rules 2.1.s, config = TyBC+S
*** using CLIPS 6.32-r763
***********************************************************************************************
...
;;; Resolution state RS1 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
biv-chain-bn[4]: b7n8{r8c1 r9c1} - b7n3{r9c1 r7c3} - b8n3{r7c5 r9c4} - b8n1{r9c4 r8c4} ==> r8c1 ≠ 1
biv-chain-rc[6]: r5c4{n5 n3} - r5c5{n3 n9} - r7c5{n9 n3} - r7c3{n3 n9} - r8c1{n9 n8} - r8c9{n8 n5} ==> r8c4 ≠ 5
naked-single ==> r8c4 = 1
biv-chain-cn[4]: c2n1{r9 r2} - c5n1{r2 r3} - c5n7{r3 r8} - c5n2{r8 r9} ==> r9c2 ≠ 2
hidden-single-in-a-row ==> r9c5 = 2
biv-chain-rn[5]: r8n7{c5 c6} - r3n7{c6 c5} - r3n1{c5 c1} - r9n1{c1 c2} - r9n4{c2 c6} ==> r8c5 ≠ 4
stte

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
(bind ?*allowed-csp-types* (create$ rc))
(solve ".38.5.......4..2...............815..46.....7.2........7..6....4......3.........9.")
***********************************************************************************************
*** SudoRules 20.1.s based on CSP-Rules 2.1.s, config = TyBC+S
*** using CLIPS 6.32-r763
***********************************************************************************************
...
;;; Resolution state RS1 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
biv-chain-rc[11]: r4c1{n3 n9} - r3c1{n9 n1} - r3c5{n1 n7} - r3c6{n7 n3} - r2c6{n3 n6} - r6c6{n6 n4} - r9c6{n4 n5} - r5c6{n5 n9} - r5c5{n9 n3} - r7c5{n3 n9} - r7c3{n9 n3} ==> r4c3 ≠ 3
singles ==> r4c1 = 3, r7c3 = 3, r7c5 = 9, r5c5 = 3, r5c4 = 5, r5c6 = 9, r8c4 = 1, r9c4 = 3
biv-chain-rc[7]: r2c9{n9 n3} - r2c6{n3 n6} - r6c6{n6 n4} - r9c6{n4 n5} - r9c9{n5 n8} - r9c1{n8 n1} - r3c1{n1 n9} ==> r3c9 ≠ 9
stte

Now, we have exactly the same resolution path as in HLS2, modulo the translations: xy11-chain -> biv-chain-rc[11], ...
denis_berthier
2010 Supporter
 
Posts: 1997
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Mon Apr 27, 2020 1:58 pm

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
;;; Resolution state RS1 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
biv-chain-bn[4]: b7n8{r8c1 r9c1} - b7n3{r9c1 r7c3} - b8n3{r7c5 r9c4} - b8n1{r9c4 r8c4} ==> r8c1 ≠ 1
t-whip-rc[4]: r8c4{n1 n5} - r9c6{n5 n4} - r9c5{n4 n2} - r9c2{n2 .} ==> r8c2 ≠ 1, r9c4 ≠ 1
hidden-single-in-a-block ==> r8c4 = 1
biv-chain-cn[4]: c2n1{r9 r2} - c5n1{r2 r3} - c5n7{r3 r8} - c5n2{r8 r9} ==> r9c2 ≠ 2
hidden-single-in-a-row ==> r9c5 = 2
biv-chain-rn[5]: r2n1{c2 c5} - r2n6{c5 c6} - r6n6{c6 c5} - r6n4{c5 c6} - r9n4{c6 c2} ==> r9c2 ≠ 1
stte

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
;;; Resolution state RS1 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
t-whip-rc[4]: r8c4{n1 n5} - r9c6{n5 n4} - r9c5{n4 n2} - r9c2{n2 .} ==> r8c1 ≠ 1, r8c2 ≠ 1, r9c4 ≠ 1
hidden-single-in-a-block ==> r8c4 = 1
t-whip-rc[7]: r9c6{n5 n4} - r9c5{n4 n2} - r8c5{n2 n7} - r3c5{n7 n1} - r3c1{n1 n9} - r8c1{n9 n8} - r8c9{n8 .} ==> r9c9 ≠ 5, r8c6 ≠ 5
singles ==> r9c9 = 8, r8c9 = 5
hidden-single-in-a-row ==> r8c1 = 8
biv-chain-rc[3]: r3c1{n9 n1} - r9c1{n1 n3} - r7c3{n3 n9} ==> r2c3 ≠ 9
singles ==> r2c3 = 7, r4c2 = 7
t-whip-rc[6]: r9c1{n1 n3} - r9c4{n3 n5} - r9c6{n5 n4} - r9c5{n4 n2} - r8c5{n2 n7} - r3c5{n7 .} ==> r3c1 ≠ 1
stte
denis_berthier
2010 Supporter
 
Posts: 1997
Joined: 19 June 2007
Location: Paris

Re: Typed-whips (2D-whips)

Postby denis_berthier » Wed May 06, 2020 12:32 am

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.
denis_berthier
2010 Supporter
 
Posts: 1997
Joined: 19 June 2007
Location: Paris

Re: Typed-chains (2D-chains)

Postby DEFISE » Wed May 06, 2020 11: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
DEFISE
 
Posts: 69
Joined: 16 April 2020
Location: France

Re: Typed-chains (2D-chains)

Postby denis_berthier » Sat May 09, 2020 2:09 am

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).
denis_berthier
2010 Supporter
 
Posts: 1997
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Sat Jun 06, 2020 5: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
denis_berthier
2010 Supporter
 
Posts: 1997
Joined: 19 June 2007
Location: Paris

TYPED-CHAINS in KAKURO

Postby denis_berthier » Mon Jun 15, 2020 6: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
denis_berthier
2010 Supporter
 
Posts: 1997
Joined: 19 June 2007
Location: Paris


Return to Advanced solving techniques