CSP-Rules, SudoRules, KakuRules...

Programs which generate, solve, and analyze Sudoku puzzles

Re: CSP-Rules, SudoRules, KakuRules...

Postby denis_berthier » Sun Dec 13, 2020 6:50 am

Following some remarks hidden in another thread:

Beware that, if need be (i.e. in case you have any problem with the CLIPS executables delivered with CSP-Rules) CLIPS must be compiled with the provided Makefile, i.e. with command "make". Using only "gcc" without the proper options would make it significantly slower.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: CSP-Rules, SudoRules, KakuRules...

Postby SpAce » Sun Dec 13, 2020 8:57 am

Another tip: read the installation instructions carefully, especially concerning the directory structure. It must be:

/<absolute path to your tools directory>/CSP-Rules/CSP-Rules-V2.1/

If you don't create the parent 'CSP-Rules' directory and unzip the file there, it won't work out of the box. It's also the directory you must specify in the config file:

(defglobal ?*CSP-Rules* = "/<absolute path to your tools directory>/CSP-Rules/")

I tried to use the unzipped version-directory directly, but that caused trouble. I got it to work that way too by editing some other file, but I knew it couldn't be the correct way to fix it. Then I reread the instructions and saw my mistake. No problems after that.
-SpAce-: Show
Code: Select all
   *             |    |               |    |    *
        *        |=()=|    /  _  \    |=()=|               *
            *    |    |   |-=( )=-|   |    |      *
     *                     \  ¯  /                   *   

"If one is to understand the great mystery, one must study all its aspects, not just the dogmatic narrow view of the Jedi."
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: CSP-Rules, SudoRules, KakuRules...

Postby denis_berthier » Tue Dec 15, 2020 5:54 am

SpAce is right about the above tips.

Another tip about CLIPS (unnecessary if you follow strictly the user's manual) is: if, for some reason, the provided executables of CLIPS don't work, download only the core of CLIPS (this link ensures you get the last version: https://sourceforge.net/p/clipsrules/code/HEAD/tree/branches/63x/core/). If you download the pre-compiled full CLIPS app with its GUI, you will probably have problems with pasting anything into it. At least, I do have this problem on my MacBookPro.

One more tip: when you write (solve "puzzle-string"), you will generally not type the puzzle-string but paste it from some other place. Be careful not to include a space at the start of the string (an error was recently reported to me, but such a leading space was the error). Notice however that any characters after the 81st (or after the 16x16th / 25x25th for larger puzzles) are merely ignored.
Any number of spaces can be added anywhere as separators of expressions in CLIPS, but adding one inside a string is considered as a space being a part of the string: "I am a string" is a 13-character string (as in any other programming language).
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: CSP-Rules, SudoRules, KakuRules...

Postby SpAce » Tue Dec 15, 2020 9:17 am

One more thing. The manual instructs to rename the unzipped directory to "CSP-Rules-V2.1", which is correct, but the following '(i.e. delete the final "master" part, if any)' is not enough for the new version because it unzips to "CSP-Rules-V2-2.1-master". The config files seem to depend on "CSP-Rules-V2.1", so they will not work (out of the box) if the directory is "CSP-Rules-V2-2.1".

(Denis, I would suggest some kind of simplification to avoid confusion. Either change the zip name back to '*-V2.1' or update the files (and the BUM) to reflect the new version.)
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: CSP-Rules, SudoRules, KakuRules...

Postby denis_berthier » Tue Dec 15, 2020 9:52 am

SpAce wrote:One more thing. The manual instructs to rename the unzipped directory to "CSP-Rules-V2.1", which is correct, but the following '(i.e. delete the final "master" part, if any)' is not enough for the new version because it unzips to "CSP-Rules-V2-2.1-master". The config files seem to depend on "CSP-Rules-V2.1", so they will not work (out of the box) if the directory is "CSP-Rules-V2-2.1".
(Denis, I would suggest some kind of simplification to avoid confusion. Either change the zip name back to '*-V2.1' or update the files (and the BUM) to reflect the new version.)


I don't know what you have done but I've just tried to download it as instructed. It downloads as CSP-Rules-V2.1-master.zip and it unzips as CSP-Rules-V2.1-master.
Notice that the name is constructed automatically by GitHub from the CSP-Rules-V2.1 repository name and I have no means to control it.
There is no new version; since the first push into GitHub, there have been a few minor updates - no noticeable change that would deserve a new version numbering.

Anyway, the instruction is clear: rename the unzipped directory to "CSP-Rules-V2.1". (In an update of the BUM, I'll replace the following "i.e." by "in particular".)
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: CSP-Rules, SudoRules, KakuRules...

Postby denis_berthier » Fri Dec 18, 2020 5:10 am

.
A minor, but potentially useful improvement:
in case the set of resolution rules chosen by the user is not powerful enough to solve a Sudoku puzzle, the final resolution state is now automatically printed in a form compatible with the input of function solve-sukaku-as-list (i.e. in a form that can be pasted into it as its list of arguments).
This currently works only for Sudoku puzzles of size ≤ 25.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: CSP-Rules, SudoRules, KakuRules...

Postby denis_berthier » Sun Dec 20, 2020 7:07 am

.
The purpose of this post is to show how the above-mentioned new feature of SudoRules can be used concretely during the resolution of a puzzle and how it allows still more freedom of use than before.

The example I'll take is mith's puzzle from here: http://forum.enjoysudoku.com/tatooine-reflections-t38302.html
As Mith is known for proposing the best ever puzzles involving Naked, Hidden and Super-Hidden (Fish) Subsets, it is natural to try to find as many of them as possible.
In my solution for it in the above-mentioned thread, I said:
denis_berthier wrote:Subsets are not quite enough, but add short bivalue-chains and it's ok

This means the first thing I tried was a solution with only Subsets, but they were not enough; the next natural step in this context was to try adding bivalue-chains.

I therefore chose the following settings for SudoRules:
Code: Select all
(bind ?*Subsets* TRUE)
(bind ?*FinnedFish* TRUE)
(bind ?*Bivalue-Chains* TRUE)

and I gave the solution with the SudoRules default simplest-first strategy, mixing Subsets and bivalue-chains according to their ratings. For ease of reading, I repeat it here and I put in bold anything that is not a Subset, a single or a whip[1], i.e. any bivalue-chain:
Hidden Text: Show
(solve "......1....12....3.4..5..2..5..6..4...73....6.....73..2..........87....1.6..4..5.")
***********************************************************************************************
*** SudoRules 20.1.s based on CSP-Rules 2.1.s, config = BC+SFin
*** Using CLIPS 6.32-r770
***********************************************************************************************
243 candidates, 1790 csp-links and 1790 links. Density = 6.09%
naked-pairs-in-a-block: b7{r8c2 r9c3}{n3 n9} ==> r9c1 ≠ 9, r9c1 ≠ 3, r8c1 ≠ 9, r8c1 ≠ 3, r7c3 ≠ 9, r7c3 ≠ 3, r7c2 ≠ 9, r7c2 ≠ 3
hidden-pairs-in-a-block: b5{r5c6 r6c4}{n4 n5} ==> r6c4 ≠ 9, r6c4 ≠ 8, r6c4 ≠ 1, r5c6 ≠ 9, r5c6 ≠ 8, r5c6 ≠ 2, r5c6 ≠ 1
hidden-pairs-in-a-block: b3{r1c9 r2c7}{n4 n5} ==> r2c7 ≠ 9, r2c7 ≠ 8, r2c7 ≠ 7, r2c7 ≠ 6, r1c9 ≠ 9, r1c9 ≠ 8, r1c9 ≠ 7
finned-x-wing-in-rows: n3{r9 r3}{c6 c3} ==> r1c3 ≠ 3
finned-x-wing-in-columns: n3{c2 c5}{r1 r8} ==> r8c6 ≠ 3
biv-chain[2]: c2n3{r1 r8} - r9n3{c3 c6} ==> r1c6 ≠ 3
swordfish-in-columns: n3{c2 c5 c8}{r8 r1 r7} ==> r7c6 ≠ 3, r1c1 ≠ 3
swordfish-in-columns: n4{c3 c4 c9}{r7 r6 r1} ==> r7c7 ≠ 4, r6c1 ≠ 4, r1c6 ≠ 4
swordfish-in-columns: n7{c2 c5 c8}{r7 r2 r1} ==> r7c9 ≠ 7, r7c7 ≠ 7, r2c1 ≠ 7, r1c1 ≠ 7
swordfish-in-columns: n1{c2 c5 c8}{r6 r7 r5} ==> r7c6 ≠ 1, r7c4 ≠ 1, r6c1 ≠ 1, r5c1 ≠ 1
hidden-triplets-in-a-column: c1{n1 n3 n7}{r9 r4 r3} ==> r4c1 ≠ 9, r4c1 ≠ 8, r3c1 ≠ 9, r3c1 ≠ 8, r3c1 ≠ 6
hidden-triplets-in-a-row: r7{n1 n3 n7}{c2 c5 c8} ==> r7c8 ≠ 9, r7c8 ≠ 8, r7c8 ≠ 6, r7c5 ≠ 9, r7c5 ≠ 8
swordfish-in-rows: n5{r2 r5 r8}{c1 c7 c6} ==> r7c6 ≠ 5, r1c1 ≠ 5
biv-chain[3]: r9c3{n9 n3} - c2n3{r8 r1} - b1n2{r1c2 r1c3} ==> r1c3 ≠ 9
biv-chain[3]: c2n3{r1 r8} - b9n3{r8c8 r7c8} - r7n7{c8 c2} ==> r1c2 ≠ 7
biv-chain[3]: r1n7{c8 c5} - b2n3{r1c5 r3c6} - r3c1{n3 n7} ==> r3c7 ≠ 7, r3c9 ≠ 7

singles ==> r3c1 = 7, r9c1 = 1, r4c1 = 3, r7c2 = 7, r7c8 = 3, r7c5 = 1
biv-chain[3]: r1n2{c2 c3} - r4c3{n2 n9} - b7n9{r9c3 r8c2} ==> r1c2 ≠ 9
biv-chain[3]: r4c3{n9 n2} - r1n2{c3 c2} - b1n3{r1c2 r3c3} ==> r3c3 ≠ 9

jellyfish-in-columns: n8{c1 c8 c2 c5}{r6 r5 r2 r1} ==> r6c9 ≠ 8, r5c7 ≠ 8, r2c6 ≠ 8, r1c6 ≠ 8, r1c4 ≠ 8
naked-triplets-in-a-block: b2{r1c4 r1c6 r2c6}{n4 n6 n9} ==> r3c6 ≠ 9, r3c6 ≠ 6, r3c4 ≠ 9, r3c4 ≠ 6, r2c5 ≠ 9, r1c5 ≠ 9
whip[1]: r3n9{c9 .} ==> r1c8 ≠ 9, r2c8 ≠ 9
naked-triplets-in-a-column: c4{r3 r4 r9}{n8 n1 n9} ==> r7c4 ≠ 9, r7c4 ≠ 8, r1c4 ≠ 9
whip[1]: b2n9{r2c6 .} ==> r4c6 ≠ 9, r7c6 ≠ 9, r8c6 ≠ 9, r9c6 ≠ 9
whip[1]: r7n9{c9 .} ==> r8c7 ≠ 9, r8c8 ≠ 9, r9c7 ≠ 9, r9c9 ≠ 9
stte



Now, suppose you are a patented fisherman and you want to find all the possible fishes before you try anything else. The simplest-first strategy, the default strategy in CSP-Rules, doesn't allow this if other simpler patterns are activated. But you now have a way to do it nevertheless. It will take two steps:

Step 1:
Load SudoRules with the following settings (no bivalue-chains):
Code: Select all
(bind ?*Subsets* TRUE)
(bind ?*FinnedFish* TRUE)
;;; Don't put the finned-fish if you don't like to eat fins.

Now, run SudoRules for our puzzle:
Hidden Text: Show
(solve "......1....12....3.4..5..2..5..6..4...73....6.....73..2..........87....1.6..4..5.")
***********************************************************************************************
*** SudoRules 20.1.s based on CSP-Rules 2.1.s, config = SFin
*** Using CLIPS 6.32-r773
***********************************************************************************************
243 candidates, 1790 csp-links and 1790 links. Density = 6.09%
naked-pairs-in-a-block: b7{r8c2 r9c3}{n3 n9} ==> r9c1 ≠ 9, r9c1 ≠ 3, r8c1 ≠ 9, r8c1 ≠ 3, r7c3 ≠ 9, r7c3 ≠ 3, r7c2 ≠ 9, r7c2 ≠ 3
hidden-pairs-in-a-block: b5{r5c6 r6c4}{n4 n5} ==> r6c4 ≠ 9, r6c4 ≠ 8, r6c4 ≠ 1, r5c6 ≠ 9, r5c6 ≠ 8, r5c6 ≠ 2, r5c6 ≠ 1
hidden-pairs-in-a-block: b3{r1c9 r2c7}{n4 n5} ==> r2c7 ≠ 9, r2c7 ≠ 8, r2c7 ≠ 7, r2c7 ≠ 6, r1c9 ≠ 9, r1c9 ≠ 8, r1c9 ≠ 7
finned-x-wing-in-rows: n3{r9 r3}{c6 c3} ==> r1c3 ≠ 3
finned-x-wing-in-columns: n3{c2 c5}{r1 r8} ==> r8c6 ≠ 3
swordfish-in-columns: n3{c2 c5 c8}{r8 r1 r7} ==> r7c6 ≠ 3, r1c6 ≠ 3, r1c1 ≠ 3
swordfish-in-columns: n4{c3 c4 c9}{r7 r6 r1} ==> r7c7 ≠ 4, r6c1 ≠ 4, r1c6 ≠ 4
swordfish-in-columns: n7{c2 c5 c8}{r7 r2 r1} ==> r7c9 ≠ 7, r7c7 ≠ 7, r2c1 ≠ 7, r1c1 ≠ 7
swordfish-in-columns: n1{c2 c5 c8}{r6 r7 r5} ==> r7c6 ≠ 1, r7c4 ≠ 1, r6c1 ≠ 1, r5c1 ≠ 1
hidden-triplets-in-a-column: c1{n1 n3 n7}{r9 r4 r3} ==> r4c1 ≠ 9, r4c1 ≠ 8, r3c1 ≠ 9, r3c1 ≠ 8, r3c1 ≠ 6
hidden-triplets-in-a-row: r7{n1 n3 n7}{c2 c5 c8} ==> r7c8 ≠ 9, r7c8 ≠ 8, r7c8 ≠ 6, r7c5 ≠ 9, r7c5 ≠ 8
swordfish-in-rows: n5{r2 r5 r8}{c1 c7 c6} ==> r7c6 ≠ 5, r1c1 ≠ 5
jellyfish-in-columns: n8{c1 c8 c2 c5}{r6 r5 r2 r1} ==> r6c9 ≠ 8, r5c7 ≠ 8, r2c6 ≠ 8, r1c6 ≠ 8, r1c4 ≠ 8
naked-triplets-in-a-block: b2{r1c4 r1c6 r2c6}{n4 n6 n9} ==> r3c6 ≠ 9, r3c6 ≠ 6, r3c4 ≠ 9, r3c4 ≠ 6, r2c5 ≠ 9, r1c5 ≠ 9
naked-triplets-in-a-column: c4{r3 r4 r9}{n1 n8 n9} ==> r7c4 ≠ 9, r7c4 ≠ 8, r1c4 ≠ 9
whip[1]: b2n9{r2c6 .} ==> r4c6 ≠ 9, r7c6 ≠ 9, r8c6 ≠ 9, r9c6 ≠ 9
whip[1]: r7n9{c9 .} ==> r8c7 ≠ 9, r8c8 ≠ 9, r9c7 ≠ 9, r9c9 ≠ 9
jellyfish-in-rows: n9{r3 r9 r4 r7}{c9 c3 c4 c7} ==> r6c9 ≠ 9, r6c3 ≠ 9, r5c7 ≠ 9, r1c3 ≠ 9
naked-pairs-in-a-block: b6{r5c7 r6c9}{n2 n5} ==> r4c9 ≠ 2, r4c7 ≠ 2
PUZZLE 0 NOT SOLVED. 59 VALUES MISSING.


Hurrah! The puzzle is not solved (this is what I meant when I said Subsets are not enough) but we've found one more fish for dinner - and not a small one: a big Jellyfish (in bold). Yummy yummy!

But now, what? Indeed, the above resolution path is what you would have gotten before I added the new feature. After this point "NOT SOLVED", there was no documented way of going further.
Now, you get the following additional output:

Code: Select all
FINAL RESOLUTION STATE:
   689       23789     256       46        378       69        1         6789      45       
   5689      789       1         2         78        469       45        6789      3         
   37        4         369       18        5         138       6789      2         789       
   13        5         239       189       6         128       789       4         789       
   489       1289      7         3         1289      45        25        189       6         
   689       1289      246       45        1289      7         3         189       25       
   2         17        45        56        13        68        689       37        489       
   45        39        8         7         239       256       246       36        1         
   17        6         39        189       4         1238      278       5         278       



Even with our stomach full of fish, we still want to solve the puzzle. Easy:

Step 2:
Load SudoRules (in another instance of CLIPS) with the following settings (with bivalue-chains):
Code: Select all
(bind ?*Subsets* TRUE)
(bind ?*FinnedFish* TRUE)
(bind ?*Bivalue-Chains* TRUE)
;;; Don't put the finned-fish if you don't like to eat fins.

Now, run SudoRules starting for the previous resolution state (PM):
Code: Select all
(solve-sukaku-as-list
   689       23789     256       46        378       69        1         6789      45       
   5689      789       1         2         78        469       45        6789      3         
   37        4         369       18        5         138       6789      2         789       
   13        5         239       189       6         128       789       4         789       
   489       1289      7         3         1289      45        25        189       6         
   689       1289      246       45        1289      7         3         189       25       
   2         17        45        56        13        68        689       37        489       
   45        39        8         7         239       256       246       36        1         
   17        6         39        189       4         1238      278       5         278       
)


You can see that Subsets were not far from solving the puzzle. Only two short bivalue-chains[3] will do it:

Code: Select all
***********************************************************************************************
***  SudoRules 20.1.s based on CSP-Rules 2.1.s, config = BC+SFin
***  Using CLIPS 6.32-r773
***********************************************************************************************
165 candidates, 672 csp-links and 672 links. Density = 4.97%
biv-chain[3]: r1c4{n6 n4} - r6n4{c4 c3} - b4n6{r6c3 r6c1} ==> r1c1 ≠ 6
biv-chain[3]: r3c1{n7 n3} - b2n3{r3c6 r1c5} - b2n7{r1c5 r2c5} ==> r2c2 ≠ 7
naked-pairs-in-a-block: b1{r1c1 r2c2}{n8 n9} ==> r3c3 ≠ 9, r2c1 ≠ 9, r2c1 ≠ 8, r1c2 ≠ 9, r1c2 ≠ 8
whip[1]: r3n9{c9 .} ==> r1c8 ≠ 9, r2c8 ≠ 9
whip[1]: c8n9{r6 .} ==> r4c7 ≠ 9, r4c9 ≠ 9
naked-pairs-in-a-block: b6{r4c7 r4c9}{n7 n8} ==> r6c8 ≠ 8, r5c8 ≠ 8
stte



If you want to play with similar situations, here are three more:
http://forum.enjoysudoku.com/more-pi-3-t38247.html
http://forum.enjoysudoku.com/hamberder-t38188.html
http://forum.enjoysudoku.com/post299520.html#p299520

Of course, this can also be done with other rules than Subsets.
If you try examples that need z-chains, you may have to use 3 steps instead of 2.


[Edit]: better formatting for the intermediary resolution states.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: CSP-Rules, SudoRules, KakuRules...

Postby denis_berthier » Thu Dec 24, 2020 9:27 am

In order to take into account the new possibilities opened by the printing of the final resolution state when a puzzle is not fully solved, I've raised initialisation functions to the user level. I've also introduced better homogeneity in the naming of solve functions:

There are now 2x2x3 functions, depending on 3 factors:
- sudoku vs sukaku
- init vs solve
- data given as: a string vs a list vs a grid with nice looking formatting

Here are the functions:
init-sudoku-string (also named "init" for homogeneity with "solve")
solve-sudoku-string (also named "solve" for backwards compatibility)
init-sudoku-list
solve-sudoku-list (also named "solve-sudoku-as-list" for backwards compatibility)
init-sudoku-grid
solve-sudoku-grid

init-sukaku-string
solve-sukaku-string
init-sukaku-list
solve-sukaku-list
init-sukaku-grid
solve-sukaku-grid

The "list" versions are special cases of the "grid" versions and could be forgotten
Other user functions are unchanged.

Notice that the init functions don't apply any rule. They just read the data and prepare the grounds for rules application.

Apart from some computation times being recorder or not, "solve-xxx" is equivalent to "init-xxx" followed by (run).
If what you want is to solve a given puzzle with the current set of rules, you should continue to use the "solve" functions, without caring for the "init" ones.
However, combined with the printing of the final resolution states, making the "init" functions available to the user will allow more possibilities of dealing with a puzzle, as in my previous post - but I still have to update some other functions for this to reach its full intended effect.
Last edited by denis_berthier on Thu Mar 25, 2021 5:47 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: CSP-Rules, SudoRules, KakuRules...

Postby denis_berthier » Sun Dec 27, 2020 7:55 am

.
I've improved function "try-to-eliminate-candidates".
It now takes a single list of arguments (the candidates to be tried for elimination):
(try-to-eliminate-candidates cand1 cand2 cand3...)

It has no longer any string argument for specifying the puzzle. Instead it works in the current resolution state.
It has therefore to be used after some init or solve function.

Notice that, as before, active rules can only be whips, g-whips, braids, g-braids, forcing-whips, forcing-braids.
If other rules are active, their eliminations will not be focused.
For t-whips, they are merely not allowed.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: CSP-Rules, SudoRules, KakuRules...

Postby denis_berthier » Wed Dec 30, 2020 4:02 am

.
I corrected the way Hidden Subsets in blocks are printed: b{n1 n2}{r1c1 r2c2} (same order as for the other Hidden Subsets).
It seems this printing bug (before the correction, they were written as Naked Subsets: b{r1c1 r2c2}{n1 n2}) has been unnoticed for many years.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: CSP-Rules, SudoRules, KakuRules...

Postby denis_berthier » Mon Feb 08, 2021 8:47 am

.
Focused eliminations now work for bivalue-chains (typed or not).
As an example of application, see the Han Shot First puzzle:http://forum.enjoysudoku.com/han-shot-first-ser-7-1-t38695.html#p300909

Notice that, with the blocked version of bivalue-chains, the focus on a target Z means that Z can be eliminated by the chain, but it still allows other candidates to be eliminated by the SAME chain (and this is a deliberate choice). If you want only Z to be eliminated, choose the non-blocked version of bivalue-chains.

This new feature of CSP-Rules has been uploaded to GitHub: https://github.com/denis-berthier/CSP-Rules-V2.1
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: CSP-Rules, SudoRules, KakuRules...

Postby denis_berthier » Tue Feb 09, 2021 6:02 am

.
Focused eliminations now work also for z-chains (typed or not). I just made this available on GitHub.
I plan to extend it progressively to all the generic chain rules (except t-whips, for technical reasons).
As of now, it works for the following rules (in both their speed and memory versions):
Code: Select all
bivalue-chains (typed or not, blocked or not)
z-chains (typed or not)
oddagons
whips (untyped)
braids (untyped)
g-whips (untyped)
g-braids (untyped)
forcing-whips, forcing-braids, forcing-g-whips, forcing-g-braids (where the focus is not applied to eliminated or asserted candidates but to the bivalue starting points).

Remember that t-whips (typed or not) may not be active.

In my previous post, I took Mith's "Han Solo First" as an example: http://forum.enjoysudoku.com/post300904.html#p300904:
Code: Select all
..9......8....97...7..6..5..5..4..6.9....38....2.......6..5.17.2....84......1....

Now, let me make all this more precise.

Let me first recall that the semi-standard SudoRules solution is available here: http://forum.enjoysudoku.com/han-shot-first-ser-7-1-t38695.html#p300710. Because Mith makes puzzles with many Subsets, it tries to make the best of it by finding as many Subsets as possible before trying other rules.

However, in order to somehow follow the fad for one-step solutions, I recently introduced in CSP-Rules the possibilities of searching for T-anti-backdoors and for focused eliminations.
Here, T can be any resolution theory with the confluence property. But in practice, it willl be BRT (i.e. Singles), W1 (i.e. Singles + intersections) or S (i.e. W1 + all Subsets). It could also be Sk (i.e.W1 + Subsets restricted to length k).

For this puzzle, I decided to choose T = W1, i.e. the following settings in the config file:
Code: Select all
(bind ?*Whips[1]* TRUE)
(bind ?*Anti-Backdoors* TRUE)

W1-anti-backdoors are found by the command:
Code: Select all
(find-sudoku-anti-backdoors "..9......8....97...7..6..5..5..4..6.9....38....2.......6..5.17.2....84......1....")

giving the following result:
Code: Select all
13 W1-ANTI-BACKDOORS FOUND: (892 388 985 982 182 979 879 968 865 944 843 834 818)

This means that, if any of these candidates were eliminated, the solution could be found in W1, i.e. using only Singles and whips[1] (i.e. intersections).

If we want a one-step solution (modulo W1), we now only have to check which of these W1-anti-backdoors can be eliminated with some pattern in CSP-Rules.
Here again, we can choose what type of elimination we are looking for. And the new possibilities for focused eliminations enlarge the choices.

How to do?
Now that we have found all the W1-anti-backdoors, we launch a new instance of CLIPS and we select in the config file the rules we want to use. Whatever we choose, the command for checking if a candidate can be eliminated by them will be the same: first init the puzzle, then try-to-eliminate the candidate (say xxx)
Code: Select all
(init-sudoku-string "..9......8....97...7..6..5..5..4..6.9....38....2.......6..5.17.2....84......1....")
(try-to-eliminate-candidates xxx)

We shall do this for the 13 W1-anti-backdoors and for 3 choices of rules:

1) Let's first assume we allow only bivalue-chains. Among the above 13 candidates, we find that 7 lead to a single step solution (modulo W1):
Code: Select all
892: biv-chain[4]: c8n8{r9 r1} - c5n8{r1 r6} - c5n9{r6 r8} - b7n9{r8c2 r9c2} ==> r9c2 ≠ 8, r9c8 ≠ 9

879: biv-chain[4]: r3n8{c9 c4} - c5n8{r1 r6} - c5n9{r6 r8} - r7n9{c4 c9} ==> r7c9 ≠ 8, r3c9 ≠ 9

865: biv-chain[3]: c2n8{r6 r9} - b7n9{r9c2 r8c2} - c5n9{r8 r6} ==> r6c5 ≠ 8

944: biv-chain[3]: r4n8{c4 c3} - r7n8{c3 c9} - r7n9{c9 c4} ==> r4c4 ≠ 9

843: biv-chain[6]: r7n8{c3 c9} - r7n9{c9 c4} - c5n9{r8 r6} - c5n8{r6 r1} - c8n8{r1 r9} - c2n8{r9 r6} ==> r4c3 ≠ 8, r9c2 ≠ 8

834: biv-chain[5]: r4n8{c4 c3} - r7n8{c3 c9} - r7n9{c9 c4} - c5n9{r8 r6} - c5n8{r6 r1} ==> r3c4 ≠ 8, r6c5 ≠ 8

818: biv-chain[6]: r3n8{c9 c4} - r4n8{c4 c3} - r7n8{c3 c9} - r7n9{c9 c4} - c5n9{r8 r6} - c5n8{r6 r1} ==> r1c8 ≠ 8, r1c9 ≠ 8, r3c4 ≠ 8


2) Let's now assume we allow only z-chains (and the particular case of bivalue-chains). Among the above 13 candidates, we find that 10 lead to a single step solution (modulo W1):
Code: Select all
892: biv-chain[4]: c8n8{r9 r1} - c5n8{r1 r6} - c5n9{r6 r8} - b7n9{r8c2 r9c2} ==> r9c2 ≠ 8

985: z-chain[6]: c2n9{r8 r9} - c2n8{r9 r6} - r4n8{c3 c4} - c4n9{r4 r6} - c8n9{r6 r9} - r7n9{c9 .} ==> r8c5 ≠ 9

979: z-chain[4]: r7n8{c9 c3} - r4n8{c3 c4} - r4n9{c4 c7} - r3n9{c7 .} ==> r7c9 ≠ 9

879: biv-chain[4]: r3n8{c9 c4} - c5n8{r1 r6} - c5n9{r6 r8} - r7n9{c4 c9} ==> r7c9 ≠ 8

968: z-chain[5]: c5n9{r6 r8} - c2n9{r8 r9} - c2n8{r9 r6} - r4n8{c3 c4} - r4n9{c4 .} ==> r6c8 ≠ 9

865: biv-chain[3]: c2n8{r6 r9} - b7n9{r9c2 r8c2} - c5n9{r8 r6} ==> r6c5 ≠ 8

944: biv-chain[3]: r4n8{c4 c3} - r7n8{c3 c9} - r7n9{c9 c4} ==> r4c4 ≠ 9

843: biv-chain[6]: r7n8{c3 c9} - r7n9{c9 c4} - c5n9{r8 r6} - c5n8{r6 r1} - c8n8{r1 r9} - c2n8{r9 r6} ==> r4c3 ≠ 8

834: biv-chain[5]: r4n8{c4 c3} - r7n8{c3 c9} - r7n9{c9 c4} - c5n9{r8 r6} - c5n8{r6 r1} ==> r3c4 ≠ 8

818: biv-chain[6]: r3n8{c9 c4} - r4n8{c4 c3} - r7n8{c3 c9} - r7n9{c9 c4} - c5n9{r8 r6} - c5n8{r6 r1} ==> r1c8 ≠ 8

Notice that the previous chains are unchanged, but they could have been. This will be shown by the third case.

3) Let's now assume we allow whips (plus the special cases of z-chains and bivalue-chains). Among the above 13 candidates, we find that 11 lead to a single step solution (modulo W1), i;e. only one more than without whips. But we can also see that some of the solutions which whips are shorter than the solutions with bivalue-chains or z-chains:
Code: Select all
892: biv-chain[4]: c8n8{r9 r1} - c5n8{r1 r6} - c5n9{r6 r8} - b7n9{r8c2 r9c2} ==> r9c2 ≠ 8, r9c8 ≠ 9

985: whip[5]: r7n9{c4 c9} - c8n9{r9 r6} - r4n9{c9 c4} - r4n8{c4 c3} - r7n8{c3 .} ==> r8c5 ≠ 9

982: whip[4]: c5n9{r8 r6} - c8n9{r6 r9} - c8n8{r9 r1} - c5n8{r1 .} ==> r8c2 ≠ 9

979: z-chain[4]: r7n8{c9 c3} - r4n8{c3 c4} - r4n9{c4 c7} - r3n9{c7 .} ==> r7c9 ≠ 9

879: biv-chain[4]: r3n8{c9 c4} - c5n8{r1 r6} - c5n9{r6 r8} - r7n9{c4 c9} ==> r7c9 ≠ 8, r3c9 ≠ 9

968: whip[4]: r4n9{c9 c4} - r7n9{c4 c9} - r7n8{c9 c3} - r4n8{c3 .} ==> r6c8 ≠ 9

865: biv-chain[3]: c2n8{r6 r9} - b7n9{r9c2 r8c2} - c5n9{r8 r6} ==> r6c5 ≠ 8

944: biv-chain[3]: r4n8{c4 c3} - r7n8{c3 c9} - r7n9{c9 c4} ==> r4c4 ≠ 9

843: whip[5]: c2n8{r6 r9} - c8n8{r9 r1} - c5n8{r1 r6} - c5n9{r6 r8} - c2n9{r8 .} ==> r4c3 ≠ 8

834: whip[4]: c5n8{r1 r6} - c2n8{r6 r9} - c2n9{r9 r8} - c5n9{r8 .} ==> r3c4 ≠ 8

818: whip[4]: c5n8{r1 r6} - c2n8{r6 r9} - c2n9{r9 r8} - c5n9{r8 .} ==> r1c8 ≠ 8


Note that for chains that have a blocked version (here bivalue-chains), not only the candidates focused on are eliminated, but also the other targets of the SAME chain. This is a deliberate choice. If you want to eliminate only the candidates on focus, choose the non-blocked version of these rules.

A final remark: with the focused elimination, the simplest-first strategy still applies.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: CSP-Rules, SudoRules, KakuRules...

Postby denis_berthier » Thu Feb 11, 2021 11:05 am

.
I've pushed to GitHub an updated version of the Basic User Manual, including how to use the recently introduced new functionalities (backdoors, anti-backdoors and focused search).
This is not yet complete (Forcing-T&E is not yet included), but it will allow you to try them.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: CSP-Rules, SudoRules, KakuRules...

Postby denis_berthier » Thu Mar 11, 2021 8:57 am

.
I've just pushed to GitHub a few new functionalities of SudoRules:

===> an addition to backdoors and anti-backdoors: anti-backdoor-pairs, for which I've already given many examples in other threads, allowing in particular the search for 2-step solutions. The new command is:
Code: Select all
(find-anti-backdoor-pairs)

It has to be used in the current resolution state, e.g. after a "init" function.


===> an addition to the way the resolution state can be displayed. Until now, it was only the rc-view. I've now introduced the possibility of printing the rn, cn and bn representations. Use the new commands:
Code: Select all
(print-current-resolution-state) for the standard rc-view
(print-current-resolution-state-rn-view) for the rn-view
(print-current-resolution-state-cn-view) for the cn-view
(print-current-resolution-state-bn-view) for the bn-view
(print-current-resolution-state-all-views) for the four views


As an example of application, take a puzzle recently proposed as having no bivalue pairs after Singles:
Code: Select all
.86.79..54.985.76.75...698..9.5..8765.768..2986..975..9.871.65.6.59.8..7.7..65.98

If you choose a config with only Singles and type the following two commands:
Code: Select all
(solve ".86.79..54.985.76.75...698..9.5..8765.768..2986..975..9.871.65.6.59.8..7.7..65.98")
(print-current-resolution-state-all-views)

you will get the following output:
Code: Select all
standard rc-view:
Physical rows are rows, physical columns are columns. Data are digits.
   123       8         6         1234      7         9         1234      134       5         
   4         123       9         8         5         123       7         6         123       
   7         5         123       1234      234       6         9         8         1234     
   123       9         1234      5         234       1234      8         7         6         
   5         134       7         6         8         134       134       2         9         
   8         6         1234      1234      9         7         5         134       134       
   9         234       8         7         1         234       6         5         234       
   6         1234      5         9         234       8         1234      134       7         
   123       7         1234      234       6         5         1234      9         8         


The folloiwng representations may be used e.g. to more easily spot
rn-, cn- or bn- bivalue pairs (also named bilocal pairs), mono-typed-chains,
hidden subsets and fishes (which will appear as naked subsets in the proper space.

rn-view:
Physical rows are rows, physical columns are digits. Data are columns.
   1478      147       1478      478       9         3         5         2         6         
   269       269       269       1         5         8         7         4         3         
   349       3459      3459      459       2         6         1         8         7         
   136       1356      1356      356       4         9         8         7         2         
   267       8         267       267       1         4         3         5         9         
   3489      34        3489      3489      7         2         6         1         5         
   5         269       269       269       8         7         4         3         1         
   278       257       2578      2578      3         1         9         6         4         
   137       1347      1347      347       6         5         2         9         8         

cn-view:
Physical rows are columns, physical columns are digits. Data are rows.
   149       149       149       2         5         8         3         6         7         
   258       278       2578      578       3         6         9         1         4         
   3469      3469      3469      469       8         1         5         7         2         
   136       1369      1369      1369      4         5         7         2         8         
   7         348       348       348       2         9         1         5         6         
   245       247       2457      457       9         3         6         8         1         
   1589      189       1589      1589      6         7         2         4         3         
   168       5         168       168       7         2         4         3         9         
   236       237       2367      367       1         4         8         9         5         

bn-view:
Physical rows are blocks, physical columns are digits. Data are positions in a block.
   159       159       159       4         8         3         7         2         6         
   167       1678      1678      178       5         9         2         4         3         
   1269      169       1269      129       3         5         4         8         7         
   1359      139       1359      359       4         8         6         7         2         
   367       237       2367      2367      1         4         9         5         8         
   489       5         489       489       7         3         2         1         6         
   579       2579      2579      259       6         4         8         3         1         
   2         357       357       357       9         8         1         6         4         
   457       347       3457      3457      2         1         6         9         8


First, what this shows clearly is, digits 5, 6, 7, 8 and 9 are decided in all the rows, all the columns and all the blocks (a very special situation).

In the rc-space alone, there is no bivalue cell. But, if you consider the rn-space, you can see that there is an rn-cell, namely r6c2, with only two values (34, i.e. c3 and c4), meaning that on row 6, number 2 can only be in columns c3 and c4 (rn-cell r6c2 is rn-bivalue or it is bilocal in the usual Sudoku jargon); still another way of saying this is: candidates n2r6c3 and n2r6c4 make a (rn-)bivalue pair.

Note: Beware how the rn, cn and bn spaces are represented: all the n coordinates correspond to physical columns. In a sequential presentation as here, this proved to be easier to use than the representation given by the Extended Sudoku Board (where the c and n coordinates are exchanged in the cn-space).


===> I've also updated the Basic User Manual, to reflect all these changes. You will find more details there.


===> Note that I haven't yet included Forcing-T&E and Forcing{3}-T&E, as I'm not yet very convinced of the "beauty" of solutions obtained that way.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: CSP-Rules, SudoRules, KakuRules...

Postby denis_berthier » Fri Mar 12, 2021 6:01 am

.
This is mainly for the readers of [HLS] who told me they like using the hidden chains.
As another example of how the rn, cn and bn representations can be used, in line with what was described in [HLS, 2007], here is puzzle Royle17#211, already considered in section XV.3.1:
Code: Select all
+-------+-------+-------+
! . . . ! . . . ! . 3 1 !
! . 8 . ! . 4 . ! . . . !
! . 7 . ! . . . ! . . . !
+-------+-------+-------+
! 1 . 6 ! 3 . . ! . 7 . !
! 3 . . ! . . . ! . . . !
! . . . ! . 8 . ! . . . !
+-------+-------+-------+
! 5 4 . ! . . . ! 8 . . !
! . . . ! 6 . . ! 2 . . !
! . . . ! 1 . . ! . . . !
+-------+-------+-------+

.......31.8..4.....7.......1.63...7.3............8....54....8.....6..2.....1.....
SER = 7.1

After 36 singles, the resolution state is:
Code: Select all
   4         6         5         8         279       29        79        3         1
   29        8         1         2579      4         3         6         259       2579
   29        7         3         259       1         6         59        8         4
   1         29        6         3         29        5         4         7         8
   3         259       8         4         6         7         1         259       259
   7         259       4         29        8         1         3         6         259
   5         4         279       279       3         29        8         1         6
   8         1         79        6         579       4         2         59        3
   6         3         279       1         2579      8         579       4         579

The next steps are three whips[1] and two more Singles
Code: Select all
whip[1]: r1n2{c6 .} ==> r3c4 ≠ 2, r2c4 ≠ 2
hidden-single-in-a-row ==> r3c1 = 2
naked-single ==> r2c1 = 9
whip[1]: b3n9{r3c7 .} ==> r9c7 ≠ 9
whip[1]: b9n7{r9c9 .} ==> r9c5 ≠ 7, r9c3 ≠ 7

(Notice how what was called interactions in [HLS] now appears as whips[1], in conformance with the generic whip pattern.
For anyone who wants to understand whips, understanding that whips[1] and interactions/intersections/pointing+claiming are the same thing (which was demonstrated at length in [HLS]) is an essential first step.)

At this point, the resolution state is:
Code: Select all
   4         6         5         8         279       29        79        3         1
   9         8         1         57        4         3         6         25        257
   2         7         3         59        1         6         59        8         4
   1         29        6         3         29        5         4         7         8
   3         259       8         4         6         7         1         259       259
   7         259       4         29        8         1         3         6         259
   5         4         279       279       3         29        8         1         6
   8         1         79        6         579       4         2         59        3
   6         3         29        1         259       8         57        4         579

For the player not yet used to spot conjugated digits but knowing the most basic chains, i.e. the xy-chains, there's no obvious chain.
But the cn-view:
Code: Select all
cn-view:
Physical rows are columns, physical columns are digits. Data are rows.
  4         3         5         1         7         9         6         8         2
  8         456       9         7         56        1         3         2         456
  2         79        3         6         1         4         78        5         789
  9         67        4         5         23        8         27        1         367
  3         149       7         2         89        5         18        6         1489
  6         17        2         8         4         3         5         9         17
  5         8         6         4         39        2         19        7         13
  7         25        1         9         258       6         4         3         58
  1         256       8         3         2569      7         29        4         569

shows what looks like an xy-chain[3] and is therefore a bivalue-chain-cn[3]:
Code: Select all
biv-chain-cn[3]: c7n7{r9 r1} - c5n7{r1 r8} - c5n5{r8 r9} ==> r9c7 ≠ 5
stte
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Software