The New Sudoku Players' Forum

[denis_berthier]

.
REDUCING THE NUMBER OF STEPS


1) TOPIC OF THIS THREAD

This thread is about finding a resolution path with a reduced number of steps (compared e.g. to a resolution path obtained by the simplest-first strategy).

To make things clear: any well defined resolution rules should be totally independent of the strategy used to put them to work (which order you choose to apply them when several of them can be applied, according to which criteria...). This should be obvious from their definitions (and it should also be obvious to anyone using CSP-Rules and probably also any other interactive solver). Fortunately, this is true of all the resolution rules currently used on this forum.

Given a set of resolution rules T (= a resolution theory), my "standard" simplest-first strategy has the main advantage of computing the rating of a puzzle (wrt to this set of rules) but it tends to produce many steps, especially if various types of rules are activated. This may be seen as a second advantage (as it shows many possibilities a manual player could use) or as a disadvantage, depending on one's goals. It is NOT the purpose of this thread to start a discussion about this point.
Moreover, I've always said that the simplest-first strategy is for a computer program and that a human solver doesn't have to follow it (and in general will not); so please, don't waste our time by trying to push at open doors.


To re-iterate and elaborate, this thread is about the techniques allowing to reduce the number of steps wrt to a fixed, properly chosen set of resolution rules.


There are two special cases that can (more or less) be excluded from our considerations here: 1-step and 2-step solutions. In such cases, a systematic review of all the possible 1or2-step paths is possible (see all the puzzles in this forum where I and others have proposed such solutions; see also CSP-Rules user manual (https://github.com/denis-berthier/CSP-Rules-V2.1 or https://www.researchgate.net/profile/De ... r/research) for how to do it.

Unfortunately, in case no such 1or2-step solution exists, a systematic exploration of all the resolution paths is impossible in practice, due to combinatorial explosion. In this case, any "fewer steps" algorithm has to choose each step "randomly" among the "most promising ones" selected among all the available ones.
Being based on random choices, the final result depends on how many tries one makes and no one can ever be sure that a shorter path doesn't exist.

As a result of the above remarks, the heuristics for defining "promising steps" may in practice be the main topic of this thread. Illustrating how they work on particular examples is also part of this thread.

AFAIK, the idea of reducing the number of steps using some random choices among those selected as "promising" is due to François Defise.



2) THE GENERAL FRAMEWORK
Let me now make all this slightly more formal.
I'll consider two resolution theories T and T0, with T0 ≤ T (T0 included in T).
T is the set of rules we want to use to solve a puzzle.
T0 is the set of rules we consider as no-step.

<>Typical examples for T0:
BRT (basic resolution theory) = Singles + eliminations by direct contradictions between a decided value and a candidate
W1 = BRT + whips[1]
S2 = W1 + Subsets[2] (i.e. + Naked, Hidden and Supper-Hidden Pairs)
S3 = S2 + Subsets[3] (i.e. + Naked, Hidden and Supper-Hidden Triplets)
S= S4 = S3 + Subsets[4] (i.e. + Naked, Hidden and Supper-Hidden Quads)
(Super-Hidden = Fish)
Notice that I consider that only BRT and W1 can rationally be considered as no-step, especially as Subsets of any size tend to eliminate lots of candidates.

<>Typical examples for T:
T will be defined by a set of rule types and their maximal length.
To make it concrete, in CSP-Rules this means the following choices (the semi-colons mean rules that I don't usually consider, but that could be).

Code: Select all

(defglobal ?*all-chains-max-length* = 8)

 (bind ?*Bivalue-Chains* TRUE)
 (bind ?*z-Chains* TRUE)
 (bind ?*Whips* TRUE)
 (bind ?*Typed-Bivalue-Chains* TRUE)
 (bind ?*Typed-z-Chains* TRUE)
 (bind ?*Typed-Whips* TRUE)

; (bind ?*G-Whips* TRUE)
; (bind ?*Braids* TRUE)
; (bind ?*Typed-Braids* TRUE)
; (bind ?*G-Braids* TRUE)
; (bind ?*Oddagons* TRUE)

In case T0 contains Subsets, T must contain the same ones (this is what T0 ≤ T means)
; (bind ?*Subsets[2]* TRUE)
; (bind ?*Subsets[3]* TRUE)
; (bind ?*Subsets[4]* TRUE)

<> Maximum allowed value for all the chains:
The maximum allowed value for all the chains (?*all-chains-max-length*) must be selected carefully. If a puzzle has a solution using only bivalue-chains[3], it would be totally absurd to look for a shorter resolution path involving any chains of length 10.



3) COMMENTS
One problem about trying to "optimise" full resolution paths is, no rating of a full path has ever been defined in any rational way. Merely adding the lengths of each step (as this is done in some generators/solvers) is total nonsense. As the complexity of a step increases "exponentially" with its size (i.e. the length of a chain or the size of a Subset), it'd be more rational to consider a function such as (sum (exp(length, a)), where a is some parameter to be determined. Anyway, that'd be totally useless, as it is impossible to use it in practice for any path optimisation.

The (much more modest) approach considered here almost totally avoids such problems. By carefully selecting the allowed maximum length of all the chains (based on the simplest-first solution), only the number of steps has to be taken into account.
IMO, this allowed maximum length shouldn't be much more than the maximum length reached in the simplest-first solution (i.e. equal to it in the best case and not more than it +1 or +2 in any case).



4) EXAMPLES
First examples can be found here (one from Defise one from me)
http://forum.enjoysudoku.com/post299359.html?hilit=few%20steps#p299359
http://forum.enjoysudoku.com/pisces-9-0-t39227.html#p307092
More examples forthcoming.

[denis_berthier]

.
THE HEURISTICS USED IN CSP-RULES FOR EVALUATING THE CANDIDATES

The global strategy used by SudoRules to reduce the number of steps is given by the following pseudo-code (with an infamous GOTO):

1) Initialise the puzzle with the givens
2) - apply all the rules in T0, until none can be applied (as T0 has the confluence property, this results in a uniquely defined resolution state RS)
- define step=0
3)
- step = step+1
- find all the candidates in RS that could be deleted by the application of a single rule in T (this doesn't change RS)
- evaluate* each of these "erasable candidates" (this doesn't change RS)
- randomly choose one of these erasable candidates among those with the best score, say C (this doesn't change RS)
- apply the simplest rule in T that allows to eliminate C (the simplest-first strategy is not completely discarded); this changes RS
- apply all the rules in T0 until none can be applied (same remark as before); this changes RS (unless the C score was only 1)
- if the puzzle is solved, report it, report the value of variable step and stop, else GOTO 3.

This defines one try and produces a single resolution path (generally already shorter than the simplest-first one in T); in order to reduce more significantly the number of steps, several tries have to be made.

(*) There remains to say how an erasable candidate C is evaluated in a resolution state RS. In my current implementation, it's very straightforward: the score of a candidate C is defined as the total number of deletions the instantiation of the rule that deletes C (and the candidates associated to it) plus the rules in T0 allow. For ease of understanding, you can imagine this evaluation process is done for each candidate in a copy of the current resolution state RS and it starts by applying the rule that deletes C in this copy. After the evaluation is done, the copy is merely discarded.
Notice that, If, in the evaluation process, a candidate is asserted as a decided value, it is counted as deleted as a candidate and the other deletions it implies by direct contradictions are also counted; as a result, there's no reason to make any special proviso for values that are decided in this evaluation process in the copy.
The obvious heuristic justification for defining the score this way is, if many candidates considered as 0-step are eliminated after one that has to be counted as a step, there will remain fewer candidates to eliminate, hopefully requiring fewer steps. Unfortunately this is not always true and this is the main limitation of this approach.
As far as I understand it, Defise has an additional criterion for selection: giving priority to bivalue candidates. He'll probably explain his strategy better than I can do. I haven't retained such a criterion because my experience is, concentrating on (3D-) bivalue cells is rarely useful.

[Edit] corrected an ambiguous formulation of the score (in blue). Thanks DEFISE

[DEFISE]

...
As far as I understand it, Defise has an additional criterion for selection: giving priority to bivalue candidates. He'll probably explain his strategy better than I can do. I haven't retained such a criterion because my experience is, concentrating on (3D-) bivalue cells is rarely useful.

Not exactly:
I do have a secondary criterion (let's say C2), but which is, more precisely, this one:
it is the number of candidates of the smallest CSP variable containing the candidate.
To summarize:
if several candidates have the same criterion C (the one you described above), the candidate with the smallest C2 is chosen.
And if several candidates have the same C and the same C2, the candidate is chosen randomly.

N.B: Intuitively, the goal is to try to obtain CSP variables of 2 candidates as quickly as possible, hoping that one of them can be deleted.
But I am absolutely not convinced of the effectiveness of that criterion C2.
Anyway it doesn't cost much to try it out (neither in lines of code nor in runtime) and I can very easily inhibit it.

N.B: for your puzzle Pisces9.0 (Jul 17) I did 50 tests with C only and 50 tests with C + C2.
So you were luckier than me unless there is a small problem in my code.

[denis_berthier]

.
This is another illustration of the fewer-steps approach, this one involving Subsets (it involves an update to CSP-Rules to be published soon).
The puzzle I'll use has been defined by mith here: http://forum.enjoysudoku.com/tatooine-tosche-station-t39029.html.
I chose it because it can be solved by Subsets without any other rule (except of course whips[1]) and it was obviously designed to be solved that way:

Code: Select all

+-------+-------+-------+
| . . . | . . . | . . . |
| . . 1 | 2 . . | . . 3 |
| . 4 . | . 5 . | . 6 . |
+-------+-------+-------+
| . 5 . | . 6 . | . 7 . |
| . . 3 | 8 . . | . . 2 |
| . . . | . . 7 | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . 2 | 3 . . | . 9 8 |
| . 6 . | . 7 . | . 5 . |
+-------+-------+-------+
...........12....3.4..5..6..5..6..7...38....2.....7..............23...98.6..7..5.
SER = 4.0

The resolution state after Singles (and whips[1]) is:

Code: Select all

   +-------------------------+-------------------------+-------------------------+
   ! 2356789 23789   56789   ! 14679   13489   134689  ! 1245789 1248    14579   !
   ! 56789   789     1       ! 2       489     4689    ! 45789   48      3       !
   ! 23789   4       789     ! 179     5       1389    ! 12789   6       179     !
   +-------------------------+-------------------------+-------------------------+
   ! 12489   5       489     ! 149     6       12349   ! 13489   7       149     !
   ! 14679   179     3       ! 8       149     1459    ! 14569   14      2       !
   ! 124689  1289    4689    ! 1459    12349   7       ! 1345689 1348    14569   !
   +-------------------------+-------------------------+-------------------------+
   ! 1345789 13789   45789   ! 14569   12489   1245689 ! 123467  1234    1467    !
   ! 1457    17      2       ! 3       14      1456    ! 1467    9       8       !
   ! 13489   6       489     ! 149     7       12489   ! 1234    5       14      !
   +-------------------------+-------------------------+-------------------------+
265 candidates, 2088 csp-links and 2088 links. Density = 5.97%

In the above mentioned thread, I gave a solution using only Subsets, based on the default "simplest-first" strategy of SudoRules, in 16 steps:

Hidden Text: Show

hidden-pairs-in-a-block: b5{n2 n3}{r4c6 r6c5} ==> r6c5 ≠ 9, r6c5 ≠ 4, r6c5 ≠ 1, r4c6 ≠ 9, r4c6 ≠ 4, r4c6 ≠ 1
swordfish-in-columns: n7{c3 c4 c9}{r7 r3 r1} ==> r7c7 ≠ 7, r7c2 ≠ 7, r7c1 ≠ 7, r3c7 ≠ 7, r3c1 ≠ 7, r1c7 ≠ 7, r1c2 ≠ 7, r1c1 ≠ 7
swordfish-in-columns: n3{c2 c5 c8}{r7 r1 r6} ==> r7c7 ≠ 3, r7c1 ≠ 3, r6c7 ≠ 3, r1c6 ≠ 3, r1c1 ≠ 3
swordfish-in-columns: n6{c3 c4 c9}{r6 r1 r7} ==> r7c7 ≠ 6, r7c6 ≠ 6, r6c7 ≠ 6, r6c1 ≠ 6, r1c6 ≠ 6, r1c1 ≠ 6
hidden-pairs-in-a-block: b9{n6 n7}{r7c9 r8c7} ==> r8c7 ≠ 4, r8c7 ≠ 1, r7c9 ≠ 4, r7c9 ≠ 1
swordfish-in-rows: n2{r3 r4 r9}{c7 c1 c6} ==> r7c7 ≠ 2, r7c6 ≠ 2, r6c1 ≠ 2, r1c7 ≠ 2, r1c1 ≠ 2
naked-pairs-in-a-block: b9{r7c7 r9c9}{n1 n4} ==> r9c7 ≠ 4, r9c7 ≠ 1, r7c8 ≠ 4, r7c8 ≠ 1
hidden-pairs-in-a-block: b1{n2 n3}{r1c2 r3c1} ==> r3c1 ≠ 9, r3c1 ≠ 8, r1c2 ≠ 9, r1c2 ≠ 8
swordfish-in-rows: n5{r2 r5 r8}{c1 c7 c6} ==> r7c6 ≠ 5, r7c1 ≠ 5, r6c7 ≠ 5, r1c7 ≠ 5, r1c1 ≠ 5
hidden-pairs-in-a-block: b1{n5 n6}{r1c3 r2c1} ==> r2c1 ≠ 9, r2c1 ≠ 8, r2c1 ≠ 7, r1c3 ≠ 9, r1c3 ≠ 8, r1c3 ≠ 7
hidden-pairs-in-a-block: b6{n5 n6}{r5c7 r6c9} ==> r6c9 ≠ 9, r6c9 ≠ 4, r6c9 ≠ 1, r5c7 ≠ 9, r5c7 ≠ 4, r5c7 ≠ 1
hidden-pairs-in-a-block: b8{n5 n6}{r7c4 r8c6} ==> r8c6 ≠ 4, r8c6 ≠ 1, r7c4 ≠ 9, r7c4 ≠ 4, r7c4 ≠ 1
hidden-triplets-in-a-column: c1{n5 n6 n7}{r8 r2 r5} ==> r8c1 ≠ 4, r8c1 ≠ 1, r5c1 ≠ 9, r5c1 ≠ 4, r5c1 ≠ 1
singles ==> r8c5 = 4, r8c2 = 1
hidden-pairs-in-a-block: b7{n5 n7}{r7c3 r8c1} ==> r7c3 ≠ 9, r7c3 ≠ 8, r7c3 ≠ 4
finned-x-wing-in-rows: n4{r5 r2}{c6 c8} ==> r1c8 ≠ 4
hidden-triplets-in-a-row: r1{n5 n6 n7}{c9 c3 c4} ==> r1c9 ≠ 9, r1c9 ≠ 4, r1c9 ≠ 1, r1c4 ≠ 9, r1c4 ≠ 4, r1c4 ≠ 1
whip[1]: c4n4{r6 .} ==> r5c6 ≠ 4
stte

It is noticeable that the resolution path remains totally unchanged if whips of length ≤4 are allowed.


In the same thread, I also mentioned that there are lots of 1-step solutions, but using absurdly long chains (considering the puzzle can be solved with patterns of size 4). Here are the simplest two of them:

Hidden Text: Show

whip-rn[14]: r2n5{c7 c1} - r2n6{c1 c6} - r8n6{c6 c7} - r5n6{c7 c1} - r5n7{c1 c2} - r2n7{c2 c7} - r8n7{c7 c1} - r8n5{c1 c6} - r8n4{c6 c5} - r2n4{c5 c8} - r5n4{c8 c6} - r1n4{c6 c4} - r1n7{c4 c3} - r1n6{c3 .} ==> r5c7 ≠ 5
stte

OR:
whip-rn[14]: r5n5{c6 c7} - r2n5{c7 c1} - r2n6{c1 c6} - r8n6{c6 c7} - r5n6{c7 c1} - r5n7{c1 c2} - r2n7{c2 c7} - r8n7{c7 c1} - r8n4{c1 c5} - r2n4{c5 c8} - r5n4{c8 c6} - r1n4{c6 c4} - r1n7{c4 c3} - r1n6{c3 .} ==> r8c6 ≠ 5
stte

Obviously, no human solver could find such solutions.



The questions remaining untouched as of now are:
1) are there solutions using only Subsets but with fewer steps than above?
2) does allowing chains of length ≤ 4 in addition to Subsets allow to find solutions with still fewer steps than above?
As the simplest-first strategy is known for generating many steps, some of which could be avoided, the answer is a priori "yes" to the first question.
But the pragmatic "fewer steps" approach will allow to answer both questions more quantitatively. My purpose here is not to provide the minimum number of steps (with the stated restrictions on the rules used); such a problem is exponentially harder than finding a solution with the shortest chains, as it would require a systematic exploration of all the possible resolution paths.
My purpose is only to illustrate how the "fewer-steps" approach can significantly reduce the number of steps (with a fixed set of resolution rules), even by exploring a very limited number of resolution paths.

1) Solution using only Subsets with only 8 steps (obtained after a single try - second try also gives 8 steps, next 3 tries give more steps - resp. 11, 10, 11)

Code: Select all

=====> STEP #1
swordfish-in-columns: n7{c3 c4 c9}{r7 r3 r1} ==> r1c2 ≠ 7, r7c7 ≠ 7, r7c2 ≠ 7, r7c1 ≠ 7, r3c7 ≠ 7, r3c1 ≠ 7, r1c7 ≠ 7, r1c1 ≠ 7

=====> STEP #2
swordfish-in-columns: n6{c3 c4 c9}{r6 r1 r7} ==> r7c7 ≠ 6, r7c6 ≠ 6, r6c7 ≠ 6, r6c1 ≠ 6, r1c6 ≠ 6, r1c1 ≠ 6

=====> STEP #3
hidden-pairs-in-a-block: b5{n2 n3}{r4c6 r6c5} ==> r4c6 ≠ 4, r6c5 ≠ 9, r6c5 ≠ 4, r6c5 ≠ 1, r4c6 ≠ 9, r4c6 ≠ 1

=====> STEP #4
swordfish-in-rows: n5{r2 r5 r8}{c1 c7 c6} ==> r1c1 ≠ 5, r7c6 ≠ 5, r7c1 ≠ 5, r6c7 ≠ 5, r1c7 ≠ 5

=====> STEP #5
hidden-triplets-in-a-row: r1{n5 n6 n7}{c9 c3 c4} ==> r1c9 ≠ 1, r1c9 ≠ 9, r1c9 ≠ 4, r1c4 ≠ 9, r1c4 ≠ 4, r1c4 ≠ 1, r1c3 ≠ 9, r1c3 ≠ 8

=====> STEP #6
hidden-triplets-in-a-column: c7{n5 n6 n7}{r2 r5 r8} ==> r2c7 ≠ 4, r8c7 ≠ 4, r8c7 ≠ 1, r5c7 ≠ 9, r5c7 ≠ 4, r5c7 ≠ 1, r2c7 ≠ 9, r2c7 ≠ 8

=====> STEP #7
hidden-triplets-in-a-column: c1{n5 n6 n7}{r8 r2 r5} ==> r5c1 ≠ 4, r8c1 ≠ 4, r8c1 ≠ 1, r5c1 ≠ 9, r5c1 ≠ 1, r2c1 ≠ 9, r2c1 ≠ 8
whip[1]: r8n4{c6 .} ==> r7c4 ≠ 4, r7c5 ≠ 4, r7c6 ≠ 4, r9c4 ≠ 4, r9c6 ≠ 4
whip[1]: c4n4{r6 .} ==> r5c5 ≠ 4, r5c6 ≠ 4
hidden-single-in-a-row ==> r5c8 = 4
naked-single ==> r2c8 = 8
hidden-single-in-a-block ==> r1c7 = 4
whip[1]: b3n9{r3c9 .} ==> r3c1 ≠ 9, r3c3 ≠ 9, r3c4 ≠ 9, r3c6 ≠ 9

=====> STEP #8
hidden-pairs-in-a-column: c6{n4 n6}{r2 r8} ==> r2c6 ≠ 9, r8c6 ≠ 5, r8c6 ≠ 1
stte

2) Solutions using chains of length ≤ 4 in addition to Subsets but with only 8 steps (obtained after a single try - next 2 tries gave resp. 10 and 8 steps)

Code: Select all

=====> STEP #1
swordfish-in-columns: n7{c3 c4 c9}{r7 r3 r1} ==> r3c1 ≠ 7, r7c7 ≠ 7, r7c2 ≠ 7, r7c1 ≠ 7, r3c7 ≠ 7, r1c7 ≠ 7, r1c2 ≠ 7, r1c1 ≠ 7

=====> STEP #2
biv-chain[4]: r5n7{c2 c1} - r5n6{c1 c7} - c9n6{r6 r7} - b9n7{r7c9 r8c7} ==> r8c2 ≠ 7
naked-single ==> r8c2 = 1
naked-single ==> r8c5 = 4

=====> STEP #3
swordfish-in-columns: n6{c3 c4 c9}{r6 r1 r7} ==> r1c6 ≠ 6, r7c7 ≠ 6, r7c6 ≠ 6, r6c7 ≠ 6, r6c1 ≠ 6, r1c1 ≠ 6

=====> STEP #4
swordfish-in-rows: n2{r3 r4 r9}{c7 c1 c6} ==> r7c6 ≠ 2, r7c7 ≠ 2, r6c1 ≠ 2, r1c7 ≠ 2, r1c1 ≠ 2

=====> STEP #5
swordfish-in-rows: n5{r2 r5 r8}{c1 c7 c6} ==> r1c7 ≠ 5, r7c6 ≠ 5, r7c1 ≠ 5, r6c7 ≠ 5, r1c1 ≠ 5

=====> STEP #6
hidden-triplets-in-a-row: r1{n5 n6 n7}{c9 c3 c4} ==> r1c9 ≠ 1, r1c9 ≠ 9, r1c9 ≠ 4, r1c4 ≠ 9, r1c4 ≠ 4, r1c4 ≠ 1, r1c3 ≠ 9, r1c3 ≠ 8
whip[1]: c4n4{r6 .} ==> r4c6 ≠ 4, r5c6 ≠ 4

=====> STEP #7
hidden-triplets-in-a-column: c1{n5 n6 n7}{r8 r2 r5} ==> r5c1 ≠ 9, r5c1 ≠ 4, r5c1 ≠ 1, r2c1 ≠ 9, r2c1 ≠ 8
whip[1]: r5n4{c8 .} ==> r4c7 ≠ 4, r4c9 ≠ 4, r6c7 ≠ 4, r6c8 ≠ 4, r6c9 ≠ 4
whip[1]: c9n4{r9 .} ==> r7c7 ≠ 4, r7c8 ≠ 4, r9c7 ≠ 4

=====> STEP #8
whip[4]: r2c8{n8 n4} - c7n4{r2 r5} - b6n6{r5c7 r6c9} - b6n5{r6c9 .} ==> r2c5 ≠ 8
stte

I didn't make more tries, because it is difficult to beat Subsets in the number of candidates they eliminate (which is the criterion for choosing the next elimination).

[DEFISE]

Hi Denis,
I see your algorithm is much more general than mine.
For now I'm just minimizing the number of whips [>= 2] of a given maximum length (without worrying about the number of whips [1] and subsets that I consider basic).
So for the above "Tatooine-Tosche" grid, I can only do "simplest first".

[denis_berthier]

I see your algorithm is much more general than mine.
For now I'm just minimizing the number of whips [>= 2] of a given maximum length (without worrying about the number of whips [1] and subsets that I consider basic).
So for the above "Tatooine-Tosche" grid, I can only do "simplest first".

Hi François,
In my algorithm, which patterns are considered as 0-step is a parameter. But the only possibilities I consider as meaningful are Singles and Whips[1].
Previously, I couldn't use Subsets in this algorithm, because they couldn't be focused (probably as what you're describing).

The recent possibility of using Subsets in this algorithm results from my recent modifications to the target part of all my Subset rules (a long and boring, but not difficult, manual editing work, for each application having Subsets), making them compatible with the general focusing-on-targets mechanism.
All this works for all the CSP-Rules applications.
I still have some checking and cleaning to do before I publish all, but that shouldn't be too long.

The only problem is, this fewer-steps algorithm is rather slow.

[DEFISE]

.
My purpose here is not to provide the minimum number of steps (with the stated restrictions on the rules used); such a problem is exponentially harder than finding a solution with the shortest chains, as it would require a systematic exploration of all the possible resolution paths.

However, I tried to explore all the possible resolution paths and I noticed that the combinatorial explosion remains practicable as long as the whips are not used (with this puzzle and some others of "Mith" of the same kind).
I got the following 4 resolutions of 7 steps:
Sol 1 : 3L-5L258C167, 3L-6L258C167, 2B-56B8p16, 3L-7L258C127, 3B-567L1C349, 3B-567C1L258, 3B-567C7L258
Sol 2 : 3L-5L258C167, 3L-6L258C167, 3L-7L258C127, 3B-567L1C349, 3B-567C1L258, 3B-567C7L258, 2B-46C6L28
Sol 3 : 3L-5L258C167, 3L-6L258C167, 3L-7L258C127, 3B-567L1C349, 3B-567C1L258, 3B-567C7L258, 3B-456C6L258
Sol 4 : 3L-5L258C167, 3L-6L258C167, 3L-7L258C127, 3B-567L1C349, 3B-567C1L258, 3B-567C7L258, 3B-456B8p156

(3L = Swordfish in rows, 2B = Hidden pair, 3B = Hidden triplet)
N.B 1: there are 498 possible paths of length 7, after eliminating 1092 duplicates path.
N.B 2: at the beginning, and probably afterwards, swordfish in columns produce the same eliminations as swordfish in rows. So swordfish in columns are eliminated.
N.B 3 : run time = 0,5s
N.B 4: I don't use the "finned" paterns.

[DEFISE]

And if I take into account all subsets, but only the best whip[<=4] at each step, I get only one resolution path of length 5:
3L-6L258C167, 4W-7L8C2, 4W-4L1C4, 4W-4L5C1, 3W-4L5C7

(3L = swordfish in rows, 4W-7L8C2 = whip[4] of target 7r8c2)

N.B 1 : there are 464 possible paths of length 5 after eliminating 591 duplicates path.
N.B 2 : run time = 22s.
N.B 3 : here nothing proves that there is not an even shorter resolution path.

[denis_berthier]

.My purpose here is not to provide the minimum number of steps (with the stated restrictions on the rules used); such a problem is exponentially harder than finding a solution with the shortest chains, as it would require a systematic exploration of all the possible resolution paths.

I tried to explore all the possible resolution paths and I noticed that the combinatorial explosion remains practicable as long as the whips are not used (with this puzzle and some others of "Mith" of the same kind).

Yes, patterns such as Subsets and bivalue-chains that may have many eliminations allow to reduce the number of paths because several candidates have equivalent consequences. I haven't tried this; it's good you did it.

[denis_berthier]

.
Following a private discussion in French with Defise, it seems there is some erroneous or unclear point in my description of the score of a candidate in the first posts of this thread.
Here is a revised version of the whole process, more faithful to the code I published on GitHub two months ago (unchanged as of today and with no plan to change it). The general framework is unchanged.

The basic idea of the whole process is due to François Defise: instead of using the simplest elimination at each step (arbitrarily chosen among all the available ones of equal complexity), as in the simplest-first strategy, one can choose the “most promising” one among all those available in T. If several eliminations are equally “promising”, one chooses randomly which to apply.

This amounts to using a global “steepest descent” method, given by the following pseudo-code (with an infamous GOTO):

Code: Select all

1) initialise the puzzle with the givens;
2) apply all the rules in T0, until none can be applied (as T0 has the confluence property, this results in a uniquely defined resolution state RS);
3) define variable step = 0;
4) bind step = step + 1;
5) find all the candidates in RS that could be deleted by the application of a single rule in T (this does not change RS);
6) evaluate (according to the method defined below) each of these “erasable candidates” (this does not change RS);
7) randomly choose one of these erasable candidates among those with the best score, say C (this does not change RS);
8) apply the simplest rule in T that allows to eliminate C (as appears here, the simplest-first strategy is not completely discarded); this changes RS;
9) apply all the rules in T0 until none can be applied; this changes RS (unless the C score was only 1);
10) if the puzzle is not solved, then GOTO 4, else report it as solved, report the value of variable “step” and stop.

The above procedure defines one try and produces a single resolution path in T (generally already shorter than the simplest-first one in T); in order to reduce more significantly the number of steps, several tries have to be made, in the hope that some of the combined random choices will lead to a path with still fewer steps. As in any steepest-decent method, no guarantee can be given that the smallest number of steps will ever be found, even if many tries are made.

There remains to state how an erasable candidate C is evaluated in a resolution state RS during step 6. The most natural way of doing it is very simple; the score of C is defined as the total number of deletions that result from applying in RS the simplest rule that allows to delete C and then applying all the rules in T0.

For ease of understanding, one can imagine this evaluation process is done for each candidate C in a copy RS’ of the current resolution state RS and it starts by applying in RS’ the simplest rule that deletes C (together with possibly other targets of the same rule instantiation, when the same rule can eliminate more than one candidate, as when the “blocked” version of resolution rules is selected) and then applying the rules in T0, resulting in a final state RS’’.
The score is the difference in the numbers of candidates between RS and the final RS’’.
Notice that, if, in this evaluation process, a candidate is asserted as a decided value, it is counted as deleted as a candidate and the other deletions the new decided value implies by direct contradictions are also counted; as a result, there is no reason to make any special proviso for values that are decided in the process.

The obvious heuristic justification for defining the score this way is, if many candidates are eliminated by applying one step that has to be counted, plus all the 0-step rules, there will remain fewer candidates to eliminate, hopefully requiring fewer additional steps. Unfortunately, this hope is not always verified and this is the main limitation of the approach, a limitation typical of any steepest descent algorithm.


Defise raised another interesting point: if a candidate C can be eliminated by several rules, how is this case dealt with?
In the implementation I published two months ago, it is very simple: this case is merely discarded; only the simplest rule eliminating C is considered (and I have no plan to change this). Why do I proceed that way?
1) it is simpler and consistent with keeping some residue of the basic simplest-first strategy; even if longer than necessary chains are allowed in T, this will guarantee that the simplest will be used when possible;
2) if you consider the rules that may eliminate several candidates at a time, i.e. mainly whips[1] (if not included in T0), Subsets and bivalue-chains, it is unlikely that a larger/longer one will eliminate more candidates than the smaller/shorter one, unless one allows degenerate patterns (such as 2 NP forming a NQ); I don't want to have degenerate patterns in CSP-Rules.
3) even if this happens, one should not forget the nature of the whole process: steepest descent. This process can provide no guarantee of finding a minimum (it is even very easy to find counter-examples - think of a hike in the mountains); introducing in this process some rare possibly-not-really-steepest step doesn't in my view fundamentally change its heuristic nature.
.

[DEFISE]

.
...The basic idea of the whole process is due to François Defise...
...Defise raised another interesting point: if a candidate C can be eliminated by several rules, how is this case dealt with?

Amazing ! So I am a little genius !

[denis_berthier]

.
...The basic idea of the whole process is due to François Defise...
...Defise raised another interesting point: if a candidate C can be eliminated by several rules, how is this case dealt with?

Amazing ! So I am a little genius !

Well, the results (in terms of reducing the number of steps) are noticeable, aren't they? I think it should be remembered as your method, in the same way as variables replacement should be remembered as eleven's method.
I wanted to give proper credit for this technique. Let me know if you want anything to be corrected in my previous post, which is also how I plan to modify the presentation of this technique in the next update of the User Manual.

It may be the case that your own implementation is slightly different in choosing the rule instantiation or candidate. As for me, I prefer to keep some remnant of the simplest-first strategy.
It might be interesting to see examples where the two variants lead to different results.

[DEFISE]

Well, the results (in terms of reducing the number of steps) are noticeable, aren't they?

Yes of course !