The New Sudoku Players' Forum

[denis_berthier]

again that not completly clear.. end of which post in specific.

The post from which you extracted the truncated citation

[coloin]

Subsidiarily, it wouldn't be that stupid to rate puzzles that have no solution: how hard is it to prove they have no solution? For some puzzles, this can be as hard as finding solutions (if you don't use T&E). SudoRules can do this (not for all the puzzles). But I understand it isn't a concern for players.

It is a concern for raters though.

I believe gsfs -q2 function goes a way to to this at a bivalue/bilocal level.

In hard puzzles it is difficult to "rate" a puzzle with 2 wrong proposition clues. They can and commonly do need "advanced" techniques to show they are invalid.

I dont know if anyone has looked at a complete 60*59/2 list of all proposition pairs in a typical 21 clue hard puzzle.

I perhaps think it could indicate the "weak point" of a puzzle. Perhaps visable to Strmckr

C

[denis_berthier]

Subsidiarily, it wouldn't be that stupid to rate puzzles that have no solution: how hard is it to prove they have no solution? For some puzzles, this can be as hard as finding solutions (if you don't use T&E). SudoRules can do this (not for all the puzzles). But I understand it isn't a concern for players.

It is a concern for raters though.
[..]
In hard puzzles it is difficult to "rate" a puzzle with 2 wrong proposition clues. They can and commonly do need "advanced" techniques to show they are invalid.
[...]

I've seldom tried SudoRules on invalid puzzles, but if you have a small sample of moderately hard ones, I can check how SudoRules ranks them, i.e. what's the length of the longest chain necessary to prove invalidity.

[coloin]

Take any puzzle and add a wrong clue [or two] !

Code: Select all

+---+---+---+
|...|..1|2..|
|.3.|.4.|.5.|
|6.7|5..|8..|
+---+---+---+
|7..|...|1..|
|.5.|...|.6.|
|..9|...|..3|
+---+---+---+
|..2|..7|3.4|
|.7.|.9.|.8.|
|..4|8..|...|
+---+---+---+ SE 9.5

Code: Select all

+---+---+---+
|...|..1|2..|
|.31|.4.|.5.|
|6.7|5..|8..|
+---+---+---+
|7..|...|1..|
|.5.|...|.6.|
|..9|...|..3|
+---+---+---+
|..2|..7|3.4|
|.7.|.9.|.8.|
|..4|8..|...|
+---+---+---+  wrong clue at r2c3

C

[denis_berthier]

coloin
Notice that your initial puzzle can't be solved by SudoRules. I didn't even try: the max SER it ever solved is 9.3

Code: Select all

+---+---+---+
|...|..1|2..|
|.3.|.4.|.5.|
|6.7|5..|8..|
+---+---+---+
|7..|...|1..|
|.5.|...|.6.|
|..9|...|..3|
+---+---+---+
|..2|..7|3.4|
|.7.|.9.|.8.|
|..4|8..|...|
+---+---+---+ SE 9.5

As for the version with the wrong clue:

Code: Select all

+---+---+---+
|...|..1|2..|
|.31|.4.|.5.|
|6.7|5..|8..|
+---+---+---+
|7..|...|1..|
|.5.|...|.6.|
|..9|...|..3|
+---+---+---+
|..2|..7|3.4|
|.7.|.9.|.8.|
|..4|8..|...|
+---+---+---+  wrong clue at r2c3

I get the following resolution path, which shows that proving invalidity can be very far from obvious if one doesn't use T&E. Here an nrczt8-lasso is necessary. The rating of this invalid puzzle is thus NRCZT8.

***** SudoRules version 13.7 *****
.....12...31.4..5.6.75..8..7.....1...5.....6...9.....3..2..73.4.7..9..8...48.....
interaction column c7 with block b6 for number 4 ==> r6c8 <> 4, r4c8 <> 4
hidden-pairs-in-a-column {n3 n4}{r1 r3}c8 ==> r3c8 <> 9, r3c8 <> 1
hidden-single-in-a-block ==> r3c9 = 1
hidden-pairs-in-a-column {n3 n4}{r1 r3}c8 ==> r1c8 <> 9, r1c8 <> 7
nrct2-chain n1{r8c4 r8c1} - n1{r9c2 r6c2} ==> r6c4 <> 1
nrc3-chain n9{r3c6 r3c2} - n2{r3c2 r2c1} - n8{r2c1 r2c6} ==> r2c6 <> 9
nrczt3-chain n8{r6c5 r1c5} - n8{r1c3 r4c3} - n8{r6c2 r6c6} ==> r5c6 <> 8
nrczt3-chain n8{r6c5 r1c5} - n8{r1c3 r5c3} - n8{r6c2 r6c6} ==> r4c6 <> 8
nrczt4-chain {n6 n1}r7c4 - n1{r8c4 r8c1} - n1{r5c1 r6c2} - n6{r6c2 r6c6} ==> r4c4 <> 6
nrc5-chain {n3 n8}r5c3 - n8{r5c9 r4c9} - n5{r4c9 r6c7} - {n5 n6}r8c7 - n6{r8c3 r4c3} ==> r4c3 <> 3
interaction row r4 with block b5 for number 3 ==> r5c6 <> 3, r5c5 <> 3, r5c4 <> 3
nrct5-chain {n6 n5}r8c7 - n5{r6c7 r4c9} - n8{r4c9 r5c9} - {n8 n3}r5c3 - {n3 n6}r8c3 ==> r8c9 <> 6, r8c6 <> 6
nrct5-chain {n6 n5}r8c7 - n5{r6c7 r4c9} - n8{r4c9 r5c9} - {n8 n3}r5c3 - {n3 n6}r8c3 ==> r8c4 <> 6
nrct5-chain {n2 n5}r8c9 - {n5 n6}r8c7 - {n6 n3}r8c3 - {n3 n8}r5c3 - n8{r5c9 r4c9} ==> r4c9 <> 2
nrczt7-lr-lasso {n2 n9}r4c8 - {n9 n1}r7c8 - {n1 n6}r7c4 - {n6 n5}r7c5 - n5{r9c6 r6c6} - n6{r6c6 r2c6} - n8{r2c6 r6c6} ==> r4c6 <> 2
nrczt8-lr-lasso {n6 n1}r7c4 - n1{r8c4 r8c1} - n1{r5c1 r5c5} - n1{r9c5 r9c8} - n7{r9c8 r6c8} - n7{r6c5 r1c5} - n6{r1c5 r2c6} - n8{r2c6 r1c5} ==> r6c4 <> 6
nrczt6-lr-lasso {n2 n7}r6c8 - {n7 n4}r6c4 - n4{r4c4 r4c2} - n2{r4c2 r3c2} - n9{r3c2 r3c6} - {n9 n4}r5c6 ==> r6c6 <> 2
nrczt6-lr-lasso {n2 n7}r6c8 - {n7 n4}r6c4 - n4{r4c4 r4c2} - n2{r4c2 r3c2} - n9{r3c2 r3c6} - {n9 n4}r5c6 ==> r6c5 <> 2
nrczt7-lr-lasso {n7 n2}r6c8 - {n2 n4}r6c4 - n4{r4c6 r4c2} - n2{r4c2 r5c1} - n2{r6c2 r3c2} - n9{r3c2 r3c6} - {n9 n4}r5c6 ==> r6c5 <> 7
nrczt7-lr-lasso n7{r5c5 r1c5} - n7{r1c4 r6c4} - n7{r6c8 r9c8} - n1{r9c8 r7c8} - {n1 n6}r7c4 - n6{r1c4 r2c6} - n8{r2c6 r1c5} ==> r5c7 <> 7
xyzt5-chain {n4 n9}r5c7 - {n9 n2}r4c8 - {n2 n7}r6c8 - {n7 n2}r6c4 - {n2 n4}r5c6 ==> r5c4 <> 4
nrct6-chain n4{r5c7 r6c7} - n5{r6c7 r4c9} - n8{r4c9 r5c9} - n7{r5c9 r6c8} - {n7 n2}r6c4 - n2{r5c6 r5c1} ==> r5c1 <> 4
nrczt3-chain n4{r6c1 r1c1} - n5{r1c1 r1c3} - n8{r1c3 r5c3} ==> r6c1 <> 8
nrczt5-chain n4{r4c4 r8c4} - n1{r8c4 r8c1} - n1{r5c1 r6c2} - n8{r6c2 r6c5} - n6{r6c5 r6c6} ==> r6c6 <> 4
nrczt6-lr-lasso n4{r5c7 r5c6} - n4{r8c6 r8c4} - n1{r8c4 r8c1} - {n1 n2}r6c1 - {n2 n7}r6c4 - {n7 n2}r6c8 ==> r6c7 <> 4
hidden-single-in-a-block ==> r5c7 = 4
xyz3-chain {n2 n3}r3c5 - {n3 n9}r3c6 - {n9 n2}r5c6 ==> r2c6 <> 2
nrc3-chain {n2 n9}r5c6 - n9{r3c6 r3c2} - n2{r3c2 r2c1} ==> r5c1 <> 2
nrczt4-lr-lasso {n7 n2}r6c8 - {n2 n4}r6c4 - n4{r4c6 r4c2} - n2{r4c2 r6c1} ==> r6c7 <> 7
naked and hidden singles ==> r6c7 = 5, r8c7 = 6, r4c3 = 6
naked-pairs-in-a-column {n6 n8}{r2 r6}c6 ==> r9c6 <> 6
nrc3-chain n6{r9c2 r9c5} - {n6 n1}r7c4 - n1{r8c4 r8c1} ==> r9c2 <> 1
nrc4-chain n4{r8c6 r4c6} - n5{r4c6 r4c5} - n5{r7c5 r7c1} - {n5 n3}r8c3 ==> r8c6 <> 3
nrczt5-lr-lasso n2{r5c6 r5c9} - n2{r8c9 r8c6} - n4{r8c6 r4c6} - {n4 n8}r4c2 - n8{r4c9 r5c9} ==> r4c4 <> 2
nrczt5-lr-lasso {n8 n3}r5c3 - {n3 n1}r5c1 - n1{r5c4 r6c5} - n6{r6c5 r6c6} - n8{r6c6 r6c5} ==> r4c2 <> 8
nrc4-chain {n4 n2}r4c2 - {n2 n9}r4c8 - {n9 n1}r7c8 - n1{r7c2 r6c2} ==> r6c2 <> 4
nrc6-chain n8{r4c9 r5c9} - n8{r5c3 r1c3} - n5{r1c3 r1c1} - n4{r1c1 r6c1} - {n4 n2}r4c2 - {n2 n9}r4c8 ==> r4c9 <> 9
naked-single ==> r4c9 = 8
nrczt5-lr-lasso n1{r6c2 r7c2} - {n1 n6}r7c4 - n6{r7c5 r1c5} - n8{r1c5 r5c5} - n7{r5c5 r1c5} ==> r6c5 <> 1
interaction row r6 with block b4 for number 1 ==> r5c1 <> 1
naked-pairs-in-a-block {n3 n8}{r5c1 r5c3} ==> r6c2 <> 8
interaction row r6 with block b5 for number 8 ==> r5c5 <> 8
nrczt5-chain n7{r1c5 r5c5} - n1{r5c5 r5c4} - {n1 n6}r7c4 - n6{r1c4 r2c6} - n8{r2c6 r1c5} ==> r1c5 <> 3
hxyzt-rn6-chain r4n5{c6 c5} - r7n5{c5 c1} - r7n8{c1 c2} - r7n9{c2 c8} - r4n9{c8 c4} - r4n3{c4 c6} ==> r4c6 <> 4
hidden-single-in-a-column ==> r8c6 = 4
nrczt2-chain n2{r8c4 r8c9} - n2{r5c9 r5c6} ==> r6c4 <> 2
nrczt5-chain {n2 n3}r3c5 - {n3 n5}r4c5 - n5{r7c5 r7c1} - n5{r8c3 r8c9} - n2{r8c9 r8c4} ==> r9c5 <> 2
nrct3-chain n9{r3c2 r3c6} - {n9 n2}r5c6 - n2{r4c5 r3c5} ==> r3c2 <> 2
naked and hidden singles ==> r2c1 = 2, r2c6 = 8, r6c6 = 6, r6c5 = 8
nrc3-chain n2{r6c8 r6c2} - n1{r6c2 r7c2} - n1{r7c8 r9c8} ==> r9c8 <> 2
interaction column c8 with block b6 for number 2 ==> r5c9 <> 2
interaction row r5 with block b5 for number 2 ==> r4c5 <> 2
hidden-pairs-in-a-column {n2 n5}{r8 r9}c9 ==> r9c9 <> 9, r9c9 <> 7
nrczt3-chain n4{r4c4 r4c2} - {n4 n9}r3c2 - n9{r3c6 r5c6} ==> r4c4 <> 9
nrct3-chain n9{r3c2 r3c6} - n9{r4c6 r4c8} - n9{r9c8 r9c7} ==> r9c2 <> 9
naked-single ==> r9c2 = 6
xy4-chain {n1 n4}r6c1 - {n4 n2}r4c2 - {n2 n9}r4c8 - {n9 n1}r7c8 ==> r7c1 <> 1
xyzt4-chain {n1 n6}r7c4 - {n6 n5}r7c5 - {n5 n3}r4c5 - {n3 n1}r9c5 ==> r8c4 <> 1
hidden-single-in-a-row ==> r8c1 = 1
naked-singles ==> r6c1 = 4, r4c2 = 2, r6c2 = 1, r4c8 = 9, r5c9 = 7, r6c8 = 2, r7c8 = 1, r9c8 = 7, r9c7 = 9, r2c7 = 7, r7c4 = 6, r2c4 = 9, r2c9 = 6, r1c9 = 9, r7c5 = 5, r4c5 = 3, r3c5 = 2, r5c5 = 1
GRID 0 HAS NO SOLUTION : NO CANDIDATE FOR r9c5


Notice that, as usual in the resolution paths I give, all the rules are displayed, except the elementary constraints propagations that can occur only after a single and can easily be done by hand.

I think SE could easily be modified to rate invalid puzzles as well.

This said, I can't see why, in practice, one wouldn't use a much faster T&E algorithm for checks during puzzle generation.
Did you think of any circumstance in which rating the complexity of invalidity proofs is important?

[gsf]

I believe gsfs -q2 function goes a way to to this at a bivalue/bilocal level.

In hard puzzles it is difficult to "rate" a puzzle with 2 wrong proposition clues. They can and commonly do need "advanced" techniques to show they are invalid.

I dont know if anyone has looked at a complete 60*59/2 list of all proposition pairs in a typical 21 clue hard puzzle.

define bivalue/bilocation candidates to be degree 2
this generalizes to degree n

-q2 outline

Code: Select all

for constraints in FNB # { singles + locked candidates }
{

  # phase 1: singleton propositions

  for d in 1 .. 9
  {
    for each degree-d candidate set A
    {
       for each candidate a in A
       {
         assert the candidate a value
         apply constraints
         record contradictions and/or solutions
      }
      examine all d results and record contradictions and/or solutions
    }
    if any solutions found then done
    apply all recorded contradictions
    apply constraints
    if solution then done
  }

  # phase 2: paired propositions

  for d in 1 .. 9
  {
    for each degree-d candidate set A
    {
      for each degree-d candidate set B, B != A
      {
        for each candidate a in A
        {
          for each candidate b in B, b != a
          {
            assert candidate a value
            assert candidate b value
            apply constraints
            record contradictions and/or solutions
          }
        }
        examine all d^2 results and record contradictions and/or solutions
      }
    }
    if any solutions found then done
    apply all recorded contradictions
    apply constraints
    if solution then done
  }
}


this shows that all candidates of all degrees are examined
contradictions are only applied as a batch when stepping to the next degree

in this model puzzles that go deeper into the loops are harder
e.g., a puzzle that requires all degree-4 singleton propositions is harder
all know hardest puzzles are solved by the above
i.e., the hardest known puzzles require { singles + locked candidate } paired propositions

I think this covers coloin's [i]wrong assertion[/b] experiments
in that the hardest puzzles will require high degree paired propositions
and in the hardest of the hardest only a few of the many paired combinations yield contradictions/solutions

the current highest -q2 is 99480 for easter monster
it requires 2 rounds of degree-5 paired propositions
and yields only 9 contradictions over 299373 propositions

some may balk at using just { singles + locked candidates }
you can use -q in my solver to strengthen the constraints in scope
but that will definitely slow down the process for the hardest puzzles

my view is that this is one technique in a spectrum
-q2 being on the fast but less-accurate end

[denis_berthier]

pNRCZT, THE PURE NRCZT RATING

In the second post of this thread, I introduced the NRCZT rating, based on the rules defined in my book and in various threads here. Remember that this rating is based on 5 different families of rules:
1) ECP (elementary constraints propagation)
2) NS+HS (naked and hidden singles)
3) basic interaction rules
4) subset rules (basic naked, hidden and super-hidden rules for pairs, triplets and quadruplets)
5) the xy to nrczt family
(see the aforementioned post for details)


Apart from the families 1 and 2, for which it is difficult to imagine that they would not be included in any set of resolution rules, there remains 3 families of rules based on different "logics", i.e. that are usually based on different proofs.
When I defined the NRCZT rating, I knew that most rules in family 4 are subsumed by nrczt-chains, but I didn't know yet that family 3 is completely subsumed by nrczt1-chains.
With this new knowledge and with an additional knowledge about what "most" means in the previous sentence (see my forthcoming post (*) in the "fully supersymmetric chains" thread (http://forum.enjoysudoku.com/viewtopic.php?t=5591), it is now natural to define a priori the following pNRCZT or pure NRCZT rating.


Rules allowed at the different levels of the pNRCZT rating:
pNRCZT0: ECP (no unsolved puzzle can be solved at this level)
pNRCZT1_0 : rules in pNRCZT0 + NS + HS
pNRCZT1: pNRCZT1_0 + rules for nrczt chains and lassos of length 1 (equivalent to rules in pNRCZT1_0 + elementary interactions)
pNRCZT2 : rules in pNRCZT1 + rules for nrczt chains and lassos of length 2
....
pNRCZTn : pNRCZTn-1 + rules for nrczt chains and lassos of length n


Let T(pNRCZTn) be the first order logic theory with the set of rules in pNRCZTn
What I said of the T(NRCZTn) can be repeated here for the T(pNRCZTn):
- they are a sequence of logical theories of increasing strength;
- each of them is invariant under symmetry and supersymmetry; this entails that the pNRCZTn stratification and the pNRCZT rating are invariant under symmetry;
- each of them has the confluence property; i.e. any couple of resolution paths will lead to the same final state, for any puzzle (with 0, 1 or more solutions); this very important property has been proven in my book; in practice, this entails that you can superimpose on these theories any precedence ordering of the rules you like; for the player, it means that he doesn't have to care about the order in which he applies the rules;
- none of them is complete; i.e. none of them can solve any valid puzzle with a unique solution; (notice that this is the case for any currently known set of resolution rules);
- nevertheless, pNRCZT7 is enough to solve 99,99% of the minimal puzzles.

Notice that the SudoRules implementation of these logical theories is complete wrt to each of the T(pNRCZTn), i.e. for any puzzle that can be solved within T(pNRCZTn), SudoRules will find a solution using only rules from pNRCZTn.


The pNRCZT rating:
- has well defined groundings in first order logic,
- is defined in a purely logical way, independent of any implementation and of any solver,
- is invariant under symmetry (legal permutations of rows, columns, floors, towers, row-column symmetry),
- is based on a single homogeneous family of fully super-symmetric rules, the rules for nrczt chains and lassos (apart from basic constraints propagation and singles), which are the most general first order chain rules,
- is naturally defined by a single parameter: the length of the longest nrczt chain or lasso necessary to solve a puzzle,
- is able to rate more than 99.99% of the minimal puzzles
Notice that (see my previous post here) it is also able to rate the difficulty of proving that an invalid puzzle has no solution.

Moreover, the pNRCZT rating is equal to the less homogeneous NRCZT rating for all but less than 1/1000 minimal puzzles (see my forthcoming post in the "fully supersymmetric chains" thread). As a result:

All the correlation results stated in the previous posts in this thread for the NRCZT rating remain unchanged for the pNRCZT rating.
Using one rating instead of the other in correlation studies is empirically justified on a statistical basis.
The reason is that the proportion of puzzles for which the two ratings are different is so small that it can't change the correlations.


This new definition has a very practical impact: a new solver/rater could be written, that contains only nrczt-chain rules and is optimised for them (which is not the case for SudoRules).


There is also a more theoretical interest in the pNRCZT rating: it defines a very homogeneous scale along which any new resolution rule can be measured.
For instance, somehow reversing things wrt to the original NRCZT rating, we can now ask questions such as: what is the impact of adding the (naked, hidden and super-hidden) subset rules in the pure nrczt hierarchy (thus getting the previously defined - should I say impure? - NRCZT rating)? And we can answer (modulo the forthcoming post already mentioned) that the impact is very small (i.e. pNRCZT = NRCZT for more than 99.9% of the minimal puzzles).
If Paul finishes the C++ implementation of his new solver (here: http://forum.enjoysudoku.com/viewtopic.php?t=6323), we'll also be able to answer questions such as: what is the impact of allowing ALS inserts within the nrczt chains?

added 09/14/08:
(*) the post referred to above is the first post in this page:
http://forum.enjoysudoku.com/viewtopic.php?t=5591&start=135

[denis_berthier]

The classification results of the full Sudogen0 random collection of 10,000 minimal puzzles for the pNRCZT rating are available at the bottom of this page: http://www.carva.org/denis.berthier/HLS/HLS-Supplements.html

Number of puzzles by level:

pNRCZT1_0: 4247
pNRCZT1: 1135
pNRCZT2: 1408
pNRCZT3: 1659
pNRCZT4: 1241
pNRCZT5: 239
pNRCZT6: 56
pNRCZT7: 10
pNRCZT8: 2
pNRCZT9: 1
pNRCZT10: 1
pNRCZT11: 0
pNRCZT12: 1

[denis_berthier]

THE B-NRCZT RATING

As a result of the definition of nrczt-braids (see http://forum.enjoysudoku.com/viewtopic.php?t=5591&start=150), one can introduce a new rating, the B-NRCZT rating. It is defined as the previous p-NRCZT rating, but with nrczt-braids repalcing nrczt- chains and lassos (or equivalently nrczt-whips).
It can be shown that it has all the good properties of the previous nrczt ratings.
As result of the theorem on T&E vs nrczt-braids (see same thread as above), we can say precisely for which puzzles the B-NRCZT rating can be computed: exactly for those that are solvable by T&E(ECP+NS+HS) - a condition very easy to check by a very simple program.

[denis_berthier]

Classification of puzzles according to the B-NRCZT RATING

In the previous post, I defined the B-NRCZT rating, based on nrczt-braids - in the same way as I had defined previously the NRCZT-rating based on nrczt-whips (or chains and lassos, if you prefer the previous style).
(Remember that nrczt-chains and braids have been defined and discussed in the following threads:
- FULLY SUPERSYMMETRIC CHAINS : http://forum.enjoysudoku.com/viewtopic.php?t=5591
- ABOMINABLE T&E and LOVELY BRAIDS : http://forum.enjoysudoku.com/viewtopic.php?t=6390
- THE CONCEPT OF A RESOLUTION RULE AND ITS APPLICATIONS : http://forum.enjoysudoku.com/viewtopic.php?t=5600
while corresponding ratings have been defined in the present thread)

Due to both a lack of time for Sudoku and inefficiencies in the SudoRules implementation of braid rules at the time of that post, I couldn't provide B-NRCZT classification results for large collections of puzzles.
I still have almost no time for Sudoku but I found a few hours to make optimisations I had had in mind for some time. As a result, I can now run the braid rules on the full sudogen0 collection (10.000 random minimal puzzles).

It appears that, if braids are given lower priority than whips of the same length but still higher prioriry than longer whips (a natural combination of options that reflects their slightly greater structural complexity), braids appear much more rarely than whips in the resolution paths.

Moreover, it appears that, for almost all the random puzzles, the B-NRCZT rating is equal to the NRCZT-rating.
More precisely, only 19 puzzles among the 10.000 have a different (of course, smaller) B-NRCZT rating.
Eighteen of these cases have B-NRCZT = NRCZT - 1 and one case has b-NRCZT = NRCZT - 2.

As a result, all the correlation results that were given for the NRCZT-rating can be straightforwardly transferred to the B-NRCZT-rating.

[denis_berthier]

Here is an example of a puzzle (sudogen0 #4177) with NRCZT-rating = 8 but B-NRCZT-rating = 7.

Code: Select all

+-------+-------+-------+
| x 9 1 | x x 7 | 3 x x |
| x 2 7 | x 5 x | 6 x x |
| 5 x x | x 4 x | x x x |
+-------+-------+-------+
| x x x | x x 9 | x x 5 |
| x 7 x | 2 x x | x 4 x |
| 9 x x | 5 x x | 2 1 x |
+-------+-------+-------+
| 1 4 x | x 9 x | x 2 x |
| 7 x x | 1 x 2 | x x x |
| x 3 x | x x x | x x x |
+-------+-------+-------+


The two versions start in the same obvious way :

hidden-singles ==> r1c8 = 5, r3c9 = 2, r1c5 = 2, r5c3 = 5, r8c2 = 5, r4c2 = 1, r5c5 = 1
interaction column c7 with block b9 for number 4 ==> r9c9 <> 4, r8c9 <> 4
hidden-single-in-a-row ==> r8c7 = 4
interaction column c3 with block b4 for number 4 ==> r4c1 <> 4
nrczt-whip-cn[2] n3{r6c5 r8c5} - {n3r8c8 .} ==> r4c4 <> 3
nrc-chain[5] n9{r3c4 r2c4} - {n9 n8}r2c8 - {n8 n4}r1c9 - n4{r1c1 r2c1} - n3{r2c1 r3c3} ==> r3c4 <> 3
nrczt-whip-cn[4] n3{r6c5 r8c5} - n3{r7c4 r2c4} - n3{r2c1 r4c1} - {n3r4c8 .} ==> r5c6 <> 3

At this point, the PM is:

Code: Select all

+-------------------------+-------------------------+-------------------------+
|468     9       1        |68      2       7        |3       5       48       |
|348     2       7        |389     5       138      |6       89      1489     |
|5       68      368      |689     4       1368     |1789    789     2        |
+-------------------------+-------------------------+-------------------------+
|2368    1       23468    |4678    3678    9        |78      3678    5        |
|368     7       5        |2       1       68       |89      4       3689     |
|9       68      3468     |5       3678    3468     |2       1       3678     |
+-------------------------+-------------------------+-------------------------+
|1       4       68       |3678    9       3568     |578     2       3678    |
|7       5       689      |1       368     2        |4       3689    3689     |
|268     3       2689     |4678    678     4568     |15789   6789    16789    |
+-------------------------+-------------------------+-------------------------+


The version with whips continues with:
A : nrczt-whip-rn[7] {n8 n7}r4c7 - {n7 n5 n8*}r7c7 - n5r9{c7 c6} - n4r9{c6 c4} - n7{r9 r7 r4#n7r4c7}c4 - n7{r7 r9 r4#n7r4c7 r6#n7r4c7}c9 - n1r9{c9 . c7*} ==> r9c7 <> 8

;;; chains of length 8 appear here:
nrct-chain[8] {n9 n8}r5c7 - {n8 n7}r4c7 - {n7 n5}r7c7 - n5{r9{c7 r9c6} - n4{r9c6 r9c4} - n7{r9c4 r7c4} - n3{r7c4 r2c4} - n9{r2c4 r3c4} ==> r3c7 <> 9
nrct-chain[8] {n9 n8}r5c7 - {n8 n7}r4c7 - {n7 n1}r3c7 - n1{r9c7 r9c9} - n7{r9c9 r7c9} - n7{r7c4 r9c4} - n4{r9c4 r9c6} - n5{r9c6 r9c7} ==> r9c7 <> 9
hidden-single-in-a-column ==> r5c7 = 9
nrct-chain[6] n3{r3c3 r2c1} - n4{r2c1 r2c9} - n1{r2c9 r9c9} - n9{r9c9 r8c9} - n9{r9c8 r9c3} - n2{r9c3 r4c3} ==> r4c3 <> 3
nrczt-whip-rn[6] n4{r2c1 r2c9} - {n4 n8}r1c9 - {n8 n9}r2c8 - n9{r3c8 r3c4} - n8{r3c4 r3c6} - {n8r5c6 .} ==> r2c1 <> 8
nrczt-whip-rc[6] n3{r3c3 r2c1} - n4{r2c1 r2c9} - n1{r2c9 r9c9} - n9{r9c9 r8c9} - {n9 n8}r8c3 - {n8r7c3 .} ==> r3c3 <> 6
nrczt-whip-cn[6] {n4 n3}r2c1 - {n3 n8}r3c3 - {n8 n6}r7c3 - {n6 n9}r8c3 - n9{r8c9 r9c9} - {n1r9c9 .} ==> r2c9 <> 4
hidden-singles ==> r1c9 = 4, r2c1 = 4, r3c3 = 3
nrczt-whip-rn[4] {n8 n6}r5c6 - {n6 n1}r3c6 - n1{r3c7 r9c7} - {n5r9c7 .} ==> r9c6 <> 8
nrczt-whip-rn[4] {n6 n8}r5c6 - {n8 n1}r3c6 - n1{r3c7 r9c7} - {n5r9c7 .} ==> r9c6 <> 6
nrczt-whip-cn[5] {n6 n8}r5c6 - {n8 n1}r3c6 - n1{r3c7 r9c7} - n5{r9c7 r9c6} - {n4r9c6 .} ==> r6c6 <> 6
nrczt-whip-rn[5] n3{r5c1 r4c1} - n3{r4c8 r8c8} - n3{r8c5 r6c5} - n7{r6c5 r6c9} - {n6r6c9 .} ==> r5c1 <> 6
nrczt-whip-cn[5] {n8 n6}r5c6 - {n6 n1}r3c6 - n1{r3c7 r9c7} - n5{r9c7 r9c6} - {n4r9c6 .} ==> r6c6 <> 8
nrct-chain[5] n2{r4c1 r4c3} - n4{r4c3 r6c3} - {n4 n3}r6c6 - n3{r6c5 r8c5} - n3{r8c8 r4c8} ==> r4c1 <> 3
hidden-single-in-a-block ==> r5c1 = 3
nrc-chain[3] n8{r5c6 r5c9} - {n8 n7}r4c7 - n7{r6c9 r6c5} ==> r6c5 <> 8
nrczt-whip-bn[5] n4{r4c3 r6c3} - {n4 n3}r6c6 - n3{r6c5 r8c5} - n8{r8c5 r9c5} - {n8r9c3 .} ==> r4c3 <> 8
nrczt-whip-rn[5] n4{r4c4 r9c4} - {n4 n5}r9c6 - n5{r9c7 r7c7} - n7{r7c7 r7c9} - {n7r6c9 .} ==> r4c4 <> 7
interaction column c4 with block b8 for number 7 ==> r9c5 <> 7
nrc-chain[4] {n3 n4}r6c6 - n4{r4c4 r9c4} - n7{r9c4 r7c4} - n3{r7c4 r2c4} ==> r2c6 <> 3
hidden-singles ==> r2c4 = 3, r3c4 = 9
naked-triplets-in-a-column {n8 n1 n6}{r2 r3 r5}c6 ==> r7c6 <> 8, r7c6 <> 6
nrc-chain[2] n6{r6c2 r3c2} - n6{r3c6 r5c6} ==> r6c5 <> 6
nrc-chain[3] n1{r9c9 r2c9} - {n1 n8}r2c6 - n8{r5c6 r5c9} ==> r9c9 <> 8
nrczt-whip-cn[3] n6{r9c3 r9c1} - n6{r9c8 r8c8} - {n6r8c5 .} ==> r4c3 <> 6
nrc-chain[4] {n7 n8}r4c7 - n8{r5c9 r5c6} - {n8 n1}r2c6 - n1{r3c6 r3c7} ==> r3c7 <> 7
hidden-single-in-a-block ==> r3c8 = 7
naked-quads-in-a-row {n6 n2 n9 n8}r9{c1 c3 c8 c5} ==> r9c9 <> 9, r9c9 <> 6, r9c4 <> 8, r9c4 <> 6
nrc-chain[4] n7{r4c7 r4c5} - {n7 n3}r6c5 - n3{r6c6 r7c6} - n5{r7c6 r7c7} ==> r7c7 <> 7
xyzt-chain[4] {n8 n5}r7c7 - {n5 n3}r7c6 - {n3 n6}r8c5 - {n6 n8}r9c5 ==> r7c4 <> 8
interaction block b8 with column c5 for number 8 ==> r4c5 <> 8
nrc-chain[4] n2{r4c1 r4c3} - n4{r4c3 r4c4} - n8{r4c4 r1c4} - n6{r1c4 r1c1} ==> r4c1 <> 6
interaction block b4 with row r6 for number 6 ==> r6c9 <> 6
nrc-chain[4] {n8 n2}r4c1 - n2{r9c1 r9c3} - n9{r9c3 r9c8} - {n9 n8}r2c8 ==> r4c8 <> 8
nrc-chain[4] {n5 n4}r9c6 - {n4 n7}r9c4 - n7{r7c4 r7c9} - n3{r7c9 r7c6} ==> r7c6 <> 5
naked and hidden singles
GRID 4177 SOLVED. LEVEL = NRCZT8, MOST COMPLEX RULE = NRCT8
691827354
427351689
583946172
214679835
375218946
968534217
146793528
759182463
832465791




The version with braids continues with:
A' : nrczt-braid-rn[6] n5r9{c7 c6} - n4r9{c6 c4} - {n8 n7}r4c7 - n7{r4 r7 r9#n4r9c4}c4 - n7{r6 r9 r7#n7r7c4}c9 - n1r9{c9 . c7*} ==> r9c7 <> 8
;;; This is the most interesting part, where we can see a braid[6] replacing the whip[7] above


;;; after that, the two resolution paths diverge and can't be compared
nrczt-braid-cn[6] n6{r3c4 r3c6} - {n6 n8}r3c2 - {n6 n8}r7c3 - {n6 n8}r5c6 - n8{r1c1 r4c1} - {n8r3c7 .} ==> r7c4 <> 6
nrczt-whip-cn[5] n4{r4c3 r4c4} - n4{r9c4 r9c6} - n5{r9c6 r7c6} - n6{r7c6 r7c9} - {n6r9c8 .} ==> r4c3 <> 6
;;; braids of length 7 appear here:
nrczt-braid-rn[7] n3{r5c1 r2c1} - n4{r2c1 r2c9} - n1{r2c9 r9c9} - n2{r4c3 r9c3} - n9{r9c3 r8c3} - n9{r2c9 r5c9} - {n3r5c9 .} ==> r4c3 <> 3
nrczt-braid-cn[7] n4{r6c6 r6c3} - n3{r6c3 r3c3} - {n8 n6}r5c6 - {n8 n1}r3c6 - n1{r3c7 r9c7} - n5{r9c7 r9c6} - {n4r9c6 .} ==> r6c6 <> 8, r6c6 <> 6
nrct-chain[5] n2{r4c1 r4c3} - n4{r4c3 r6c3} - {n4 n3}r6c6 - n3{r6c5 r8c5} - n3{r8c8 r4c8} ==> r4c1 <> 3
nrczt-whip-cn[6] n7{r6c9 r6c5} - n7{r9c5 r9c4} - n4{r9c4 r4c4} - {n4 n3}r6c6 - n3{r7c6 r7c4} - {n3r8c5 .} ==> r7c9 <> 7
nrc-chain[4] {n9 n8}r5c7 - {n8 n7}r4c7 - n7{r6c9 r9c9} - n1{r9c9 r9c7} ==> r9c7 <> 9
nrc-chain[4] n5{r7c7 r9c7} - n1{r9c7 r9c9} - n7{r9c9 r6c9} - {n7 n8}r4c7 ==> r7c7 <> 8
nrczt-whip-cn[2] n8{r6c2 r3c2} - {n8r3c7 .} ==> r6c9 <> 8
nrczt-whip-rc[3] n8{r6c3 r6c5} - n7{r6c5 r6c9} - {n7r4c7 .} ==> r4c1 <> 8
nrczt-whip-rc[3] n8{r6c3 r6c5} - n7{r6c5 r6c9} - {n7r4c7 .} ==> r4c3 <> 8
nrc-chain[4] n6{r1c4 r1c1} - {n6 n2}r4c1 - {n2 n4}r4c3 - n4{r4c4 r9c4} ==> r9c4 <> 6
nrc-chain[4] n9{r3c4 r2c4} - n3{r2c4 r7c4} - n7{r7c4 r7c7} - n7{r3c7 r3c8} ==> r3c8 <> 9
nrc-chain[5] n1{r2c6 r3c6} - n1{r3c7 r9c7} - n5{r9c7 r7c7} - n7{r7c7 r7c4} - n3{r7c4 r2c4} ==> r2c6 <> 3
nrc-chain[3] n9{r3c4 r2c4} - n3{r2c4 r3c6} - n1{r3c6 r3c7} ==> r3c7 <> 9
hidden-singles ==> r5c7 = 9, r3c4 = 9
nrczt-whip-cn[3] n8{r3c7 r4c7} - n8{r5c9 r5c1} - {n8r6c2 .} ==> r3c6 <> 8
nrczt-whip-bn[3] {n8 n6}r3c2 - n6{r3c6 r1c4} - {n8r1c4 .} ==> r2c1 <> 8
nrczt-whip-rn[4] n1{r9c9 r2c9} - {n1 n8}r2c6 - n8{r5c6 r5c1} - {n8r1c1 .} ==> r9c9 <> 8
nrct-chain[5] n8{r4c7 r3c7} - n1{r3c7 r2c9} - {n1 n8}r2c6 - n8{r1c4 r1c1} - n8{r5c1 r5c9} ==> r4c8 <> 8
nrct-chain[5] n4{r9c4 r4c4} - n4{r6c6 r9c6} - n5{r9c6 r7c6} - {n5 n7}r7c7 - n7{r7c4 r9c4} ==> r9c4 <> 8
nrczt-whip-rc[5] {n8 n7}r4c7 - n7{r6c9 r9c9} - {n7 n4}r9c4 - {n4 n6}r4c4 - {n6r5c6 .} ==> r4c5 <> 8
nrczt-whip-rc[4] n8{r8c5 r6c5} - n8{r6c3 r5c1} - n3{r5c1 r2c1} - {n3r2c4 .} ==> r7c4 <> 8
nrc-chain[4] n4{r6c6 r4c4} - {n4 n7}r9c4 - {n7 n3}r7c4 - n3{r2c4 r3c6} ==> r6c6 <> 3
naked and hidden singles ==> r6c6 = 4, r9c4 = 4, r4c3 = 4, r4c1 = 2, r9c3 = 2, r8c3 = 9
interaction block b5 with column c5 for number 3 ==> r8c5 <> 3
interaction row r8 with block b9 for number 3 ==> r7c9 <> 3
naked-pairs-in-a-row {n6 n8}r7{c3 c9} ==> r7c6 <> 8, r7c6 <> 6
hidden-pairs-in-a-column {n1 n9}{r2 r9}c9 ==> r9c9 <> 7
naked and hidden singles ==> r6c9 = 7, r4c7 = 8
interaction column c4 with block b2 for number 8 ==> r2c6 <> 8
naked and hidden singles
GRID 4177 SOLVED. LEVEL = B-NRCZT7, MOST COMPLEX RULE = B-NRCZT7
691827354
427351689
583946172
214679835
375218946
968534217
146793528
759182463
832465791

[denis_berthier]

Here is now an example of a puzzle (sudogen0 #9586) with NRCZT-rating = 8 but B-NRCZT-rating = 6 (the only such case among the 10.000 sudogen0 puzzles)

Code: Select all

+-------+-------+-------+
| 5 8 x | 7 x x | x x 4 |
| x 1 x | x 9 x | x x x |
| x x 4 | x x 8 | x 3 9 |
+-------+-------+-------+
| x 5 x | x x x | 7 x x |
| x x x | 9 x x | x x x |
| x x x | 6 5 2 | x x x |
+-------+-------+-------+
| x x x | x x 1 | 8 x x |
| x 7 x | x x 5 | 3 x x |
| 8 x x | x x x | x x 2 |
+-------+-------+-------+


The two resolution paths start with:
hidden-singles ==> r1c3 = 9, r3c1 = 7, r6c3 = 7, r9c6 = 9, r6c7 = 9, r4c1 = 9, r7c2 = 9, r8c8 = 9, r5c6 = 7
interaction row r6 with block b6 for number 8 ==> r5c9 <> 8, r5c8 <> 8, r4c9 <> 8, r4c8 <> 8
interaction column c6 with block b2 for number 6 ==> r3c5 <> 6, r1c5 <> 6
interaction row r1 with block b2 for number 3 ==> r2c6 <> 3, r2c4 <> 3
hidden-pairs-in-a-row {n7 n8}r2{c8 c9} ==> r2c9 <> 6, r2c9 <> 5, r2c8 <> 6, r2c8 <> 5
interaction block b3 with column c7 for number 5 ==> r9c7 <> 5, r5c7 <> 5
hidden-pairs-in-a-row {n7 n8}r2{c8 c9} ==> r2c8 <> 2
nrczt-whip-cn[2] n4{r8c1 r9c2} - {n4r9c7 .} ==> r5c1 <> 4
nrc-chain[3] {n3 n4}r9c4 - n4{r2c4 r2c6} - {n4 n3}r4c6 ==> r4c4 <> 3
interaction column c4 with block b8 for number 3 ==> r9c5 <> 3, r7c5 <> 3
nrct-chain[3] {n6 n1}r8c9 - n1{r9c8 r9c3} - n5{r9c3 r9c8} ==> r9c8 <> 6
nrczt-whip-cn[3] n2{r2c3 r3c2} - n6{r3c2 r3c7} - {n5r3c7 .} ==> r2c7 <> 2
nrc-chain[4] n1{r4c4 r3c4} - {n1 n2}r3c5 - n2{r3c2 r5c2} - n2{r4c3 r4c8} ==> r4c8 <> 1
nrct-chain[4] n4{r5c7 r9c7} - {n4 n3}r9c4 - {n3 n6}r9c2 - n6{r3c2 r3c7} ==> r5c7 <> 6
nrct-chain[4] {n6 n1}r8c9 - n1{r9c8 r9c3} - n5{r9c3 r7c3} - n5{r7c9 r5c9} ==> r5c9 <> 6
nrczt-whip-rc[4] n3{r6c2 r9c2} - {n3 n4}r9c4 - n4{r2c4 r2c6} - {n4r4c6 .} ==> r4c3 <> 3
nrczt-whip-rn[4] n1{r9c3 r8c1} - {n1 n6}r8c9 - n6{r4c9 r4c8} - {n2r4c8 .} ==> r4c3 <> 1
nrct-chain[5] n8{r5c3 r4c3} - n2{r4c3 r4c8} - n6{r4c8 r4c9} - {n6 n1}r8c9 - n1{r9c8 r9c3} ==> r5c3 <> 1
interaction column c3 with block b7 for number 1 ==> r8c1 <> 1
nrczt-whip-rc[5] {n4 n3}r9c4 - {n3 n6}r9c2 - {n6 n2}r3c2 - n2{r2c3 r2c4} - {n2r7c4 .} ==> r9c5 <> 4

At this point, the PM is:

Code: Select all

+-------------------------+-------------------------+-------------------------+
|5       8       9        |7       123     36       |126     126     4        |
|236     1       236      |245     9       46       |56      78      78       |
|7       26      4        |125     12      8        |1256    3       9        |
+-------------------------+-------------------------+-------------------------+
|9       5       268      |148     1348    34       |7       246     136      |
|1236    2346    2368     |9       1348    7        |124     12456   135      |
|134     34      7        |6       5       2        |9       148     138      |
+-------------------------+-------------------------+-------------------------+
|2346    9       2356     |234     2467    1        |8       4567    567      |
|246     7       126      |248     2468    5        |3       9       16       |
|8       346     1356     |34      67      9        |146     1457    2        |
+-------------------------+-------------------------+-------------------------+


and, apart from one or two hard steps, the puzzle is almost solved.

The path with whips continues:
nrczt-whip-rn[7] {n4 n3}r9c4 - {n3 n2 n4*}r7c4 - {n2 n8 n4*}r8c4 - n4r8{c4 c1 c5*} - {n4 n6 n3#n3r9c4}r9c2 - {n6 n2}r3c2 - n2r2{c3 . c1#n2r3c2 c4#n2r7c4} ==> r7c5 <> 4
nrczt-whip-cn[8] n5r9{c8 c3} - n1r9{c3 c7 c8*} - n4{r9 r5}c7 - n4{r6 r7 r4#n4r5c7 r5#n4r5c7 r9*}c8 - n5{r7 r5 r9*}c8 - n2{r5c8 r4c8 r5c7#n4r5c7} - n6{r4 r1 r5#n5r5c8 r7#n4r7c8}c8 - n6{r3 . r1#n6r1c8 r2#n6r1c8 r9#n1r9c7}c7 ==> r9c8 <> 7
hidden-single-in-a-row ==> r9c5 = 7
nrc-chain[4] n6{r7c5 r8c5} - {n6 n1}r8c9 - n1{r8c3 r9c3} - n5{r9c3 r7c3} ==> r7c3 <> 6
nrczt-whip-bn[5] {n6 n1}r8c9 - {n1 n3}r4c9 - {n3 n4}r4c6 - n4{r4c5 r8c5} - {n6r8c5 .} ==> r7c9 <> 6
nrczt-whip-cn[6] n6{r7c5 r8c5} - n6{r8c9 r9c7} - n6{r3c7 r3c2} - n6{r2c3 r2c6} - n4{r2c6 r4c6} - {n4r5c5 .} ==> r7c1 <> 6
nrczt-whip-cn[6] {n1 n6}r8c9 - {n6 n3}r4c9 - n3{r4c6 r1c6} - n6{r1c6 r2c6} - n6{r2c1 r5c1} - {n1r5c1 .} ==> r6c9 <> 1
nrczt-whip-rn[5] n4{r8c1 r9c2} - n4{r9c8 r7c8} - n7{r7c8 r2c8} - n8{r2c8 r6c8} - {n1r6c8 .} ==> r6c1 <> 4
;;; the end is easy and can be seen on my web pages
GRID 9590 SOLVED. LEVEL = NRCZT8, MOST COMPLEX RULE = NRCZT8
589736214
613294578
724518639
958143726
236987145
147652983
395421867
472865391
861379452



After the above PM, the path with braids continues:
nrczt-braid-rc[6] n5r9{c8 c3} - n1r9{c3 c7 c8*} - n4{r9 r5}c7 - n1{r1c7 r1c8 r3c7#n1r9c7} - {n7 n8}r2c8 - {n8 . n1#n1r1c8 n4#n4r5c7}r6c8 ==> r9c8 <> 7
;;; notice that we get the same elimination of n7r9c8 as after the first two steps in the path with whips, but with a braid[6] instead of a whip[8]
;;; notice that, in this braid:
;;; - the left-linking candidate of the fourth cell (n1r1c7) is not nrc-linked to the right-linking candidate of the third cell (n4r5c7), as should be the case for a whip, but is nrc-linked to the right-linking candidate of the second cell (n1r9c7)
;;; - the left-linking candidate of the fifth cell (n7r2c8) is not nrc-linked to the right-linking candidate of the fourth cell (n1r1c8), as should be the case for a whip, but is nrc-linked to the target (n7r9c8)

hidden-single-in-a-row ==> r9c5 = 7
nrc-chain[4] n6{r7c5 r8c5} - {n6 n1}r8c9 - n1{r8c3 r9c3} - n5{r9c3 r7c3} ==> r7c3 <> 6
nrczt-whip-cn[6] n2{r4c8 r4c3} - n6{r4c3 r4c9} - {n6 n1}r8c9 - {n1 n6}r8c3 - n6{r9c2 r9c7} - {n4r9c7 .} ==> r4c8 <> 4
interaction row r4 with block b5 for number 4 ==> r5c5 <> 4
nrct-chain[6] n2{r5c2 r3c2} - n2{r2c1 r2c4} - {n2 n1}r3c5 - {n1 n3}r1c5 - {n3 n8}r5c5 - n8{r5c3 r4c3} ==> r4c3 <> 2
;;; the end is easy and can be seen on my web pages
GRID 9590 SOLVED. LEVEL = B-NRCZT6, MOST COMPLEX RULE = B-NRCZT6

[StrmCkr]

nice to see you back at it again denis

[denis_berthier]

nice to see you back at it again denis

Thanks, StrmCkr,

but I'm not really back at it - I'm lacking time for it. I just had some technical idea about improving my implementation of braids in SudoRules and I found a few hours to let them "materialise" into code.

I'm really surprised by the results above. They show that whips are almost as powerful as braids, although they have a much nicer, non branching, structure.
One could say that braids are an interesting theoretical tool (because of the T&E vs braid theorem, which makes it very easy to know in advance which puzzles they can solve) and whips are a very good approximation of their solving power.

Another conclusion is that, as whips are much easier to implement efficiently, if I hadn't done it yet, I wouldn't care for implementing braids. (But I had to do it before I could reach this conclusion !!!)

BTW, Paul, can you give some news of your implementation of whips/braids with ALS inserts ?

[StrmCkr]

i have some very intesting ideas for coding as well.

ive been working with paul for some of it..

i do have something of intrest too show if you wish pm me.
its mathmatically based.

and ive have a back burner project
paired propagation .

i can pm some details on the idea if youd like.

its a projected linked set off a fixed points

which links digit sets stemming from the fixed points using the interaction of the digits in the linked points to form a invalid
subgraph state.

via permation of groupd possible sets.