Sudoku Players' Forum (clone)

.
Small update today:
- addition of Forcing2-Whips (equivalent to Forcing-Whips) and Forcing3-Whips, based on the general ORk-Forcing-Whips and with (3D) bivalue or trivalue cells as starting points (see 2nd post here: http://forum.enjoysudoku.com/or-k-forcing-whips-t40189.html)
- corresponding update of the User Manual

[Edit]: I also added rules for automatically applying eleven's replacement method in relation with tridagons. (It seems I had forgotten to post this before.)
[EDit2]: I also added examples of ORk-Forcing-Whips based on anti-tridagons in the Sudoku/Tridagons folder of https://github.com/denis-berthier/CSP-Rules-Examples

.
Today's update is again for advanced users.
It allows to use functions "solve-k-digit-pattern-string", "solve-n-grids-after-first-p-from-k-digit-pattern-string-file" and "solve-n-grids-after-first-p-from-k-digit-pattern-string-file-excluding" in combination with DFS instead of T&E(n).
This may be useful if one only wants to prove that a k-digit pattern is contradictory instead of wanting to prove this in a specific T&E(n). But, contrary to what we get by using T&E, the proof with DFS can't be used to provide ideas for a simpler proof.
Notice that if both k and the number of k-cells are large (k ≥ 4), computation time may become very long - though it is still drastically improved wrt standard DFS.
An example of application is the following 3-digit pattern from eleven:

Code: Select all

+-------------------------------+-------------------------------+-------------------------------+
! 123456789 123456789 123456789 ! 123456789 123456789 123       ! 123456789 123456789 123       !
! 123456789 123456789 123       ! 123456789 123456789 123456789 ! 123456789 123       123456789 !
! 123456789 123       123456789 ! 123456789 123       123456789 ! 123       123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123456789 123456789 123456789 ! 123456789 123       123456789 ! 123456789 123456789 123       !
! 123456789 123456789 123       ! 123456789 123456789 123       ! 123       123456789 123456789 !
! 123456789 123       123456789 ! 123       123456789 123456789 ! 123456789 123       123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+

000001001001000010010010100000010001001001100010100010

As I have shown previously, it is the only one in his list of 380 contradictory 3-digit patterns that may require depth 3 of T&E for the proof that it is contradictory.
If one only wants a proof of contradiction, DFS is much faster.

.
Today's update on GitHub https://github.com/denis-berthier/CSP-Rules-V2.1 is all about the impossible trivalue oddagon pattern, the general anti-tridagon pattern that avoids it and the rules one may use to take advantage of it.
It mainly includes additions to the generic part of CSP-Rules:
- addition of OR6-Forcing-Whips (ORk-Forcing-Whips, k=1,...5, were already available)
- addition of ORk-Contrad-Whips, k=2,...6 (http://forum.enjoysudoku.com/ork-forcing-whips-and-ork-contrad-whips-t40189.html)
- technical update of some generic files (irrelevant to the standard user).

The SudoRules part allowing to use it (i.e. the identification of anti-tridagons and the corresponding ORk relations) were already available.
Parts in the SudoRules config file have been added for allowing to activate the above rules.

What's missing in this update is one of the Basic User Manual (but it's coming soon)

.
After recently adding the generic ORk-Contrad-Whips and the possibility to use them based on Tridagon-based ORk relations, I've just added on GitHub a corresponding set of preferences TRIDAGON-ORk-CW, allowing to apply them before any other rule (apart from Subsets), when one uses function "solve-with-preferences" / "solve-w-prefs".
See http://forum.enjoysudoku.com/post325129.html#p325129 for an example of use.
.

.
The update of the Basic User Manual promised in a previous post and explaining how to use the new ORk-Forcing and ORk-Contrad Whips is published on GitHub.
It also includes the classification results mentioned here: http://forum.enjoysudoku.com/the-tridagon-rule-t39859-105.html

.

CSP-Rules user wrote:Do you plan to make your new ORk-whip rules public?

Yes.
I'm preparing an update to CSP-Rules that will include them. It will also include:
- some cleaning and polishing of any previous tridagon thing;
- more flexibility in the way to use all the new ORk-chain rules;
- ultra-persistency of the OR-relations;
- new sets of tridagon-related preferences to use with function "solve-w-prefs";
- a new, largely re-structured version of the user manual.

About the manual: the SudoRules chapter had grown much too large; it will be reduced to its elementary part; and two new chapters ("dealing with requirements on the number of steps" and "tridagon ...." will appear at the end of the book.
Moreover, some other parts will be largely re-written/extended.
An extended version of the classification results for ORk-chains (http://forum.enjoysudoku.com/the-tridagon-rule-t39859-105.html and next posts) will be included (some additional calculations are still running). I consider such results as a useful guide for choosing which ORk rules to activate and with which length.

All this takes time (the 1st edition of the manual was 100 p.; the 2nd 170; the 3rd is expected about to be 250). My best estimate is early November ± 1 week.

.
I published on GitHub (https://github.com/denis-berthier/CSP-Rules-Examples) an enlarged list of tridagon-related examples.
Many of them are revisited versions of the examples I proposed in the "puzzles" section.

(The updates mentioned in the previous posts are not yet fully ready, but they are not far.)

.
I've published a main update of CSP-Rules on GitHub (https://github.com/denis-berthier/CSP-Rules-V2.1).

It allows to use ORk-Whips, for k ≤ 6.
It has new control variables, including two for the priority of ORk-chains:
- ?*use-high-Tridagon-salience* : if TRUE (the default), the Tridagon elimination rule and the anti-tridagon detection rule will be applied immediately after Triplets; (otherwise, priority is pushed down to the chains of length 12, because the pattern relies on 12 CSP-Variables).
- ?*ORk-Forcing-Whips-before-ORk-Whips* : it TRUE (the default), ORk-Forcing-Whips have higher priority than ORk-Whips (and ORk-Contrad-Whips) of same length. I added this because there's no real reason to prefer the ones over the others.

I've also added sets of preferences for the Tridagon related rules, to be used with function "solve-w-preferences". Beware that this may be interesting only in relatively rare cases where tridagon chain rules don't need to be intermingled with regular chain rules.

I've also added a file "UPDATES.md" summarising the main updates since the first publication on August 19th, 2020.
(Minor updates, such as improving some print functions, are not mentioned.)

Another major change is the user manual; it's no longer the "Basic User Manual", but the "Augmented User Manual (AUM)".
As mentioned in a previous post, a less elementary part has been added at the end, in order not to overload the SudoRules chapter.
It includes anything about requirements on the length of the resolution path.
It also includes the complete results of my detailed studies of mith's 63,137 min-expand puzzles in T&E(3).
The "Augmented User Manual" is included in the Publications and Docs folders of CSP-Rules. If you don't want to download CSP-Rules, you can also read it on ResearchGate or download it from there: https://www.researchgate.net/publication/365186265_Augmented_User_Manual_for_CSP-Rules-V21
.

.
Minor update to SudoRules on GitHub:
- fix some abbreviations for 1-step or 2-step solutions
- add functions "solve-sukaku-list-by-eleven-replacement2" and "solve-sukaku-grid-by-eleven-replacement2"
Similar functions already existed for 3 or 4 digits in 3 or 4 cells, but I thought 2 wouldn't be very useful (I still think the same, but I added these functions for completeness). You can see an example of using it here: http://forum.enjoysudoku.com/hard-no-2-t40541-6.html

.
Today's update on GitHub is about having faster ORk-whips for k > 3. They are about 30% to 50% faster (depending on k and on many contextual factors) and they also use less memory.
For technical reasons, these improvements work only when ORk-forcing-whips are not active. Which version is used is automatic: new fast one if ORk-forcing-whips not active, original one otherwise.

.
Today's update on GitHub has two unrelated parts:

1) All the ORk-relations of size ≤ 20 are now ultra-persistent.
Previously, size for applying persistency was limited to 12, but there are rare anti-tridagons with 20 guardians (though I have no example where ultra-persistency of ORk-relations with so many guardians would ultimately lead to any elimination).

2) Add Forcing2-T&E and Forcing3-T&E.
For a long time, I had hesitated tp publish them because they are very inelegant ways of solving a puzzle. I had finally mentioned them in the User Manual several months ago, but I had forgotten to post the code at that time - a typical Freudian slip, now fixed.

.
Today's update on GitHub is again about ORk-chains: addition of ORk-Contrad-G-Whips (for k ≤ 5), examples of which, I've given
here: http://forum.enjoysudoku.com/9025-in-mith-63137-t-e-3-min-expands-t40658.html
and here: http://forum.enjoysudoku.com/9025-in-mith-63137-t-e-3-min-expands-t40658.html

P.S.: I've also coded the full ORk-G-Whips (of which ORk-Contrad-G-Whips are a special case). You can already find an example here: http://forum.enjoysudoku.com/436-in-63137-min-expands-t40664.html. But but I'm still testing them. They'll be published later.
.

.

CSP-Rules user wrote:In the "Augmented User Manual", you list the ORk-Forcing-Whips, ORk-Contrad-Whips and ORk-Whips among the generic chains. But how can they be generic if they depend on the Sudoku pattern you call "anti-tridagon""?

To be more precise, I consider that ORk-chains are generic parametric chain rules.
Generic means that they can be formulated in general CSP terms (according to the CSP logic language introduced in [CRT] and unchanged in [PBCS]), with no application-specific reference. You can check their abstract definition, you can check their CSP-Rules code: you won't find any reference to Sudoku, Kakuro... (e.g. to rows, columns, blocks, numbers...).
Parametric means their actual use depends on some application-specific ORk-relation - an anti-tgridagon pattern in the case currently under study on this forum, but it could also be some UR pattern or Shye's pattern...
Granted, the "parameter" in question in the ORk-chains is not of the most usual type for a parameter, i.e. numeric. It's an abstract logical ORk-relation. But this idea shouldn't be too surprising for programmers who heard of parametric data types.

So, to be still more precise, CSP-Rules has ban abstract "template" (same as a C struct) ORk-relation, with fixed "slots" (i.e. C fields) independent of any application:

Code: Select all

(deftemplate ORk-relation
    (slot OR-name (type SYMBOL)) ; example: Trid;
    (slot OR-size (type INTEGER) (default 0)) ; k
    (multislot OR-candidates) ; the set of candidates related by an ORk relation
)

The ORk-chain rules are written in such a way that each chain may use such an abstract template once in a place where a CSP-Variable would normally appear. In the rule formulation, the ORk template appears no more and no less abstract than the CSP-Variables. And all of this is totally useless if not fed with the proper fuel, i.e. application-specific data.

In the case of CSP-Variables, they are defined by each application (in Sudoku, I've always defined them as abstraction for the 2D-cells (rc-, rn-, cn- and bn- cells) I introduced in [HLS 2007]). They are the same for any puzzle for that application (for fixed size parameters).
In the case of ORk-relations, they can't be defined a priori:
- they depend on which type of ORk-relation one wants to consider;
- they depend on each puzzle and, contrary to fixed CSP-Variables, they appear "dynamically", i.e. during resolution.

Which ORk-relation you want to consider is defined in the application configuration file. Currently, there's only one possibility: anti-tridagons. You allow it by setting:

Code: Select all

 (bind ?*Anti-Tridagons* TRUE)

When you do this, the rules that allow to detect anti-tridagon relations and to assert them as ORk-templates (with the conventional name "Trid" will be loaded.

If you also load some of the ORk-chains rules, e.g.

Code: Select all

;;; 2.3.3) Use ORk-Forcing-Whips in combination with Anti-Tridagons:
 (bind ?*OR5-Forcing-Whips* True)
;;; 2.3.3) Use ORk-Contrad-Whips in combination with Anti-Tridagons:
 (bind ?*OR5-Contrad-Whips* True)
;;; 2.3.4) Use ORk-Whips in combination with Anti-Tridagons:
;;; (Remember that ORk-Whips[n] => ORk-Contrad-Whips[n] => Tridagons)
 (bind ?*OR5-Whips* True)
;;; 2.3.5) Use ORk-Contrad-G-Whips in combination with Anti-Tridagons:
 (bind ?*OR5-Contrad-G-Whips* True)
;;; 2.3.6) Use ORk-G-Whips in combination with Anti-Tridagons:
 (bind ?*OR5-G-Whips* True)

they will eventually have some concrete anti-tridagon relation to fill up their abstract ORk-templates.

Note: in order to use ORk-chains in an application (e.g. SudoRules), you need both the generic ORk-chains and some application-specific rules that allow to assert concrete ORk-relations.

One additional remark. ORk-relations are ultra-persistent and this is a generic property. It means that the rules for guaranteing ultra-persistency are expressed in a way independent of any application.
.

.
Small addition to SudoRules today, to allow dealing with k,l patterns:
I wrote a function similar to solve-k-digit-pattern-string: solve-kl-digit-pattern-string.

Example of use:
(solve-kl-digit-pattern-string 2 3 ".3...3...3..3.......2.2....3....3.......2.....3.3....."

(Dots can also be 0s).

Note that k and l in the pattern string stand respectively for candidates 1...k and 1...l in the corresponding cell.
As was the case for function solve-k-digit-pattern-string, "incomplete" strings (i.e. shorter than 81) are automatically completed with 0s.

See example of use here: http://forum.enjoysudoku.com/18913-in-mith-s-63137-t-e-3-min-expands-t40683-7.html and the next post.

.
Today's large update on GitHUb (https://github.com/denis-berthier/CSP-Rules-V2.1) contains:
- Addition of the ORk-contrad-g-whips, for k = 6 (before, they were limited to k ≤ 5)
- Addition of the full ORk-g-Whips, for k ≤ 6.
- Addition of the ORk-forcing-g-whips, for k ≤ 6.
- Addition of the proper global variables in the SudoRules config file for selecting the above new rules.
- Update of the Augmented User Manual, to take the previous additions into account.

This completes my set of ORk chain and g-chain rules, now all defined for 2 ≤ k ≤ 6.

For examples of all these rules, see the Puzzles section of this forum (all the puzzles I proposed under titles such as "#xxx in mith's 63,137 T&E(3) min-expands". See also the Sudoku Examples in the separate GitHub project: https://github.com/denis-berthier/CSP-Rules-Examples
.