CSP-Rules, SudoRules, KakuRules...

Programs which generate, solve, and analyze Sudoku puzzles

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

Postby denis_berthier » Tue Apr 06, 2021 6:04 am

.
Today's update on GitHub contains:


- all the rules and functions necessary to look for 1-step and 2-step solutions. Most of it is written in generic form, but the applications are currently only for Sudoku.
Notice that this shows (for those who might still be confused about it) that the same resolution rules used in the standard CSP-Rules simplest-first strategy work in a way totally independent of it.


- an updated version of the User manual with detailed explanations of how to use these new features. I've already given examples in the "Puzzles" forum, but the updated Manual gives the reference procedure.

- an updated version of the graphics in this Manual and their explanations, so as to avoid confusion about what is part of the definition of a whip and what is not part of it (and only plays a momentarily role when checking the whip property in a particular resolution state).



- A few more goodies:

- shuffle functions (see the Goodies folder of SudoRules): permute rows, columns, floors, towers, digits.


- pretty-print functions. Examples should make it clear:

(pretty-print-sudoku-string "1..5....2.2.7...3...3.6.1..........8.4..5..9.6.2........6...4...5...3.7.8....4..9")
gives:
Code: Select all
     +-------+-------+-------+
     ! 1 . . ! 5 . . ! . . 2 !
     ! . 2 . ! 7 . . ! . 3 . !
     ! . . 3 ! . 6 . ! 1 . . !
     +-------+-------+-------+
     ! . . . ! . . . ! . . 8 !
     ! . 4 . ! . 5 . ! . 9 . !
     ! 6 . 2 ! . . . ! . . . !
     +-------+-------+-------+
     ! . . 6 ! . . . ! 4 . . !
     ! . 5 . ! . . 3 ! . 7 . !
     ! 8 . . ! . . 4 ! . . 9 !
     +-------+-------+-------+


(pretty-print-sukaku-list
1 6 4789 5 3 89 789 48 2 459 2 4589 7 1489 189 5689 3 456 4579 789 3 2489 6 289 1 458 457 3579 1379 1579 12349 1249 12679 2367 1246 8 37 4 178 1238 5 12678 2367 9 1367 6 13789 2 13489 1489 1789 357 145 13457 2379 1379 6 1289 12789 5 4 128 13 249 5 149 12689 1289 3 268 7 16 8 137 17 126 127 4 2356 1256 9)
gives:
Code: Select all
   +-------------------+-------------------+-------------------+
   ! 1     6     4789  ! 5     3     89    ! 789   48    2     !
   ! 459   2     4589  ! 7     1489  189   ! 5689  3     456   !
   ! 4579  789   3     ! 2489  6     289   ! 1     458   457   !
   +-------------------+-------------------+-------------------+
   ! 3579  1379  1579  ! 12349 1249  12679 ! 2367  1246  8     !
   ! 37    4     178   ! 1238  5     12678 ! 2367  9     1367  !
   ! 6     13789 2     ! 13489 1489  1789  ! 357   145   13457 !
   +-------------------+-------------------+-------------------+
   ! 2379  1379  6     ! 1289  12789 5     ! 4     128   13    !
   ! 249   5     149   ! 12689 1289  3     ! 268   7     16    !
   ! 8     137   17    ! 126   127   4     ! 2356  1256  9     !
   +-------------------+-------------------+-------------------+

Width is automatically adapted to the largest number of candidates in a cell.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Sun Apr 11, 2021 5:02 am

.
Today's update on GitHub includes only the better detection of Finned Fish. Some unnecessary restrictions have been raised from my old code.
(Other Subsets, including normal Fish, are unchanged.)
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Mon Apr 19, 2021 7:20 am

.
Today's update on GitHub includes:

<> better control for printing the resolution state; independent control variables now allow to print it:
- after Singles;
- after Singles and whips[1] (in my experience, this has proved to be more useful than just after Singles, the only possibility before these changes);
- at the end of the resolution path, if a full solution is not found;
- never.

<> updated Sudoku examples (in particular, a few file names that might have been a problem for Windows have been changed).
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Thu Apr 29, 2021 6:27 am

.
Today's update on GitHub includes:

- renaming of old Oddagon examples that had names not compatible with Windows; I hope this way there remains no incompatibility with Windows; thanks to the users who pointed this problem to me;

- addition of the CLIPS toy Sudoku solver in the CLIPS folder; it doesn't have much resolution power, but it was interesting for me to compare the resolution times and memory requirements with those of SudoRules;

- updates of the CLIPS-puzzles folder in the Examples/Sudoku-examples folder. Each example compares the CLIPS and SudoRules solutions. I have also added functions to the CLIPS toy solver allowing it to take a string as input instead of the original complicated CLIPS input. This way, it's easy to find puzzles not solvable by the CLIPS toy solver;

- updating of the README file in the Sudoku-examples folder; it now provides more informations about all the examples (including the forthcoming cbg-000 one).


Forthcoming in one or two weeks, depending on how much time I can find to finish preparing it:
- a cbg-000 folder with the first 21,375 puzzles from my controlled-bias collection (of 5,926,343 puzzles) and with a detailed comparison of all their ratings (W, B, gW, S+W, S+gW, SFin+W, SFin+gW).
(The full collection and the controlled-bias generator can be found here: https://github.com/denis-berthier/Controlled-bias_Sudoku_generator_and_collection, together with the full W and SER ratings; but it doesn't have the other ratings.)
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Sat May 01, 2021 6:22 am

.
Today's small update on GitHub includes minor changes for (future) compatibility with CLIPS 6.4. BUT CLIPS 6.3 (as delivered within the CLIPS folder of CSP-Rules) remains the recommended version to use.
(CLIPS 6.4 is still under testing - e.g. I found a very serious bug yesterday, which the developer has immediately corrected.)
You don't have to bother to download this update.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Thu May 06, 2021 11:52 am

.
Today's update on GitHub (https://github.com/denis-berthier/CSP-Rules-V2.1) is about the detailed comparisons of ratings I announced in a previous post.
A description of these comparisons is available here: http://forum.enjoysudoku.com/pattern-based-constraint-satisfaction-2nd-edition-t32567.html
All the results (detailed ratings and comparisons of ratings) are available on GitHub in the Examples/Sudoku-examples/cbg-000 folder.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Sun May 09, 2021 9:37 am

.
Today's update on GitHub (https://github.com/denis-berthier/CSP-Rules-V2.1) includes mainly additional examples of Map colouring.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Tue May 11, 2021 7:27 am

.
Today's update on GitHub (https://github.com/denis-berthier/CSP-Rules-V2.1) includes
- additional examples of Map colouring, including one for a larger map;
- additional comparisons of ratings (exotic patterns and uniqueness). For details, see http://forum.enjoysudoku.com/pattern-based-constraint-satisfaction-2nd-edition-t32567.html#p303970
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Tue Jun 01, 2021 7:07 am

.
Today's update on GitHub (https://github.com/denis-berthier/CSP-Rules-V2.1) includes functions for the fully automated search of 1 or 2 step solutions (modulo the rules in a resolution theory ?RT that are considered as no-step). Syntax:
- (find-sudoku-1-steppers-wrt-resolution-theory ?RT ?sudoku-string)
- (find-sudoku-2-steppers-wrt-resolution-theory ?RT ?sudoku-string)

?RT can be
- BRT (Basic Resolution Theory, i.e. only direct contradictions and Singles)
- W1 (BRT + whips[1])
- S2, S3, S4, S (W1 + Subsets of length ≤ 2, 3, or 4)
But the only values that really make sense are BRT and W1. I can't see how a Pair could reasonably be considered as no-step.


The search for 1 or 2 steppers already existed in the previous release, but it required several steps from the user. With these new functions, finding 1 or 2 step solutions becomes very easy. Notice however that such solutions can be totally absurd when a simpler one exists with much shorter chains. Examples of such absurdities are not hard to find in the Puzzles section.

The recommended way of using these functions is first finding a solution with the simplest first strategy and then deciding a reasonable maximum length allowed for chains in 1 or 2 step solutions. Reasonable means, IMO, not longer than the W-rating + 2.

Notice that, for the puzzles currently proposed in the "Puzzles" section:
- computation times for 1-step solutions may take 10 to 20 seconds
- computation times for 2-step solutions can be large (I mean several minutes, not several hours).
Precise times depend on the puzzle and the maximum length allowed for chains.


The update also contains an update of the Basic User Manual, with all the details about these user functions.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Fri Jun 25, 2021 3:42 am

.
I've just published on GitHub the extension I recently added to LatinRules, allowing to deal with Pandiagonal Latin Squares.
I don't think this variant will ever become a popular logic puzzle, but it may serve as an example of how to easily introduce variants of an existing puzzle in CSP-Rules.
Of course, generic rules such as bivalue-chains, z-chains, whips,... are straightforwardly applicable.

The update includes in particular all the specific Subsets rules, such as Naked or Hidden Triplets on a diagonal or Swordfish in diagonals with transverse columns. It doesn't include exotic Fish relying on base sets of different types or cover sets of different types.
Beware that this variant has a very high branching factor and chains of length ≥ 5 (depending on how much RAM you have) may lead to memory overflow, especially for large grid sizes.
Note that, complexity-wise, grid size closer of Sudoku(9) is 7.

Examples are available in the Examples/LatinSquares folder.

The User Manual has also been updated to reflect this new variant.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Thu Jul 29, 2021 4:47 am

.
Today's update on GitHub (https://github.com/denis-berthier/CSP-Rules-V2.1) consists of:
- the addition of the fewer steps technique, described here: http://forum.enjoysudoku.com/reducing-the-number-of-steps-t39234.html
- associated examples
- associated update of the Basic User Manual

The command is very simple:
(solve-sudoku-with-fewer-steps-wrt-resolution-theory ?RT ?sudoku-string),
with ?RT and ?sudoku-string as in the 1-step and 2-step functions.

There's also an abbreviation for the most natural cases of ?RT:
(solve-sudoku-with-fewer-steps-wrt-BRT ?sudoku-string),
(solve-sudoku-with-fewer-steps-wrt-W1 ?sudoku-string).

There are similar functions when starting from a sukaku.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Fri Aug 06, 2021 8:17 am

.
Today's update on GitHub is all about Subsets. For each of the applications that have Subsets - namely SudoRules, LatinRules (including the recently added Pandiag variant), KakuRules, HidatoRules (which also deals with Numbrix), FutoRules - the following changes have been made:

- the code of the unblocked version has been merged with that of the blocked one (this doesn't change anything for the user: in the default blocked version, a Subset rule R can't be interrupted by a simpler rule becoming available after the first eliminations made by R); I've spent quite a lot of time checking that it didn't imply significant changes in computation times.

- Subset rules become compatible with focusing; i.e. if you type "(try-to eliminate-candidates n1r1c1 n2r2c2 ...)" and the Subset rules are loaded, they will apply only to targets in the n1r1c1 n2r2c2 ... list.
More precisely, if the blocked version of Subsets is selected, the first candidate eliminated by the Subset rule must be in the list, but additional eliminations by the same Subset will be obtained. For allowing only the elimination of targets in the list, choose the non-blocked version of Subsets.
(This is the same general principle as for the other rules that have a blocked and an unblocked versions, such as bivalue-chains. Both behaviours are useful, depending on one's goals. )
This allows more freedom of use of the rules. It will also be useful in forthcoming more advanced functions.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Wed Aug 11, 2021 7:15 am

.
Only two small changes today:

- following some remarks from readers of [PBCS], the printing of all the eliminations and assertions is now more compact: r1c2≠3 instead of previous r1c2 ≠ 3 and r1c2=3 instead of previous r1c2 = 3
- in FutoRules, resolution states can now be printed (in the same form as in LatinRules and SudoRules).
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Tue Aug 17, 2021 5:55 am

.
Today's update on GitHub includes:

- minor changes in the rule-activation rules, allowing more freedom in disabling/re-enabling all the generic resolution rules. The resolution rules themselves are totally unchanged. In and of itself, this is totally transparent to the user. But it makes the following change easier.

- update of the fewer-steps solving function, allowing to find shorter resolution paths (as described here: http://forum.enjoysudoku.com/reducing-the-number-of-steps-t39234.html). It can now take into account all the generic chain rules and all the Subsets and Finned Fish. Obviously, this is today's main change. You should be warned that this can be very slow and care must be taken in selecting a reasonable value for ?*all-chains-max-length* (i.e. no more than the puzzle rating + 1 or 2).

- examples of using this new function.

- new function for reconstructing a full resolution path from its main steps (i.e. steps not considered as 0-steps).

- update of the Basic User Manual, to take into account all the above changes; plus some re-organising of the SudoRules chapter and a more formal definition of what can be considered as 0-step.

- in SudoRules, addition of a function allowing to output in the standard PM format a Sukaku puzzle given in the (totally illegible) 729-character string format.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Sun Sep 19, 2021 5:20 am

.
Minor update today. I was tired of typing functions with long names for 1-step or 2-step solutions, so I introduced 2 abbreviations for the most usual case (i.e. when only Singles and whips[1] are considered as 0-steps):
"find-1-steppers" abbreviates "find-sudoku-1-steppers-wrt-W1"
"find-2-steppers" abbreviates "find-sudoku-2-steppers-wrt-W1"
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Previous

Return to Software