yes, of course: it's one. more step to a full proof.
I'm not saying you should do the same, but I have ORk splitting rules that explain why an OR4 relation can be split into 2 OR3 relations.
How to deal with large numbers of patterns
45 posts
• Page 3 of 3 • 1, 2, 3
Re: How to deal with large numbers of patterns
by denis_berthier » Tue Feb 28, 2023 1:13 pm
yes, of course: it's one. more step to a full proof.
I'm not saying you should do the same, but I have ORk splitting rules that explain why an OR4 relation can be split into 2 OR3 relations.
- denis_berthier
- 2010 Supporter
- Posts: 4233
- Joined: 19 June 2007
- Location: Paris
Re: How to deal with large numbers of patterns
by denis_berthier » Wed Mar 01, 2023 8:02 am
denis_berthier wrote:
yes, of course: it's one. more step to a full proof.
I'm not saying you should do the same, but I have ORk splitting rules that explain why an OR4 relation can be split into 2 OR3 relations.
On second thoughts, combining this with what you stated before (your graph is the graph of cells, not of candidates), I don't see how a proof mentioning only the cells (as in your example) could be correct.
- denis_berthier
- 2010 Supporter
- Posts: 4233
- Joined: 19 June 2007
- Location: Paris
Re: How to deal with large numbers of patterns
by ryokousha » Wed Mar 01, 2023 10:54 am
A long form would be "The nodes r2c6, r5c4, r4c6, r6c6 of the sudoku graph S induce a diamond-subgraph D with edges (r2c6, r4c6), (r2c6, r6c6), (r4c6,r6c6), (r4c6, r5c4), (r6c6, r5c4). In any 3-coloring of D, the nodes r2c6 and r5c4 have the same color, so in S, they can be contracted to a single node (r2c6=r5c4), the edge-set of which is the union of the edge-sets of r2c6 and r5c4."
Probably this is still too imprecise.
But I don't want to write the Principia Sudokuka and give a quick, readable coloring-proof instead.
Probably this is still too imprecise.
But I don't want to write the Principia Sudokuka and give a quick, readable coloring-proof instead.
- ryokousha
- Posts: 37
- Joined: 30 April 2022
Re: How to deal with large numbers of patterns
by denis_berthier » Wed Mar 01, 2023 11:18 am
ryokousha wrote:A long form would be "the cells r2c6, r5c4, r4c6, r6c6 induce a diamond-subgraph with edges (r2c6, r4c6), (r2c6, r6c6), (r4c6,r6c6), (r4c6, r5c4), (r6c6, r5c4). In any 3-coloring of that subgraph, the nodes r2c6 and r5c4 have the same color, so they can be contracted to a single node (r2c6=r5c4)".
Probably this is still too imprecise.
But I don't want to write the Principia Sudokuka and give a quick readable coloring-proof instead.
That's good for me in this case. A long way though from the mere statement "r2c6=r5c4 as both see r4c6 and r6c6".
I think I understand your goals better now. Much work remaining !
- denis_berthier
- 2010 Supporter
- Posts: 4233
- Joined: 19 June 2007
- Location: Paris
Re: How to deal with large numbers of patterns
by ryokousha » Wed Mar 01, 2023 12:34 pm
Indeed.
Maybe I should quickly explain what the main principle of these proofs is:
If we have a (simple, finite) graph G and want to know whether it is 3-colorable, we can do a reverse Hajós-construction:
1) check whether G contains the complete graph K_4 as subgraph, if so, it has chromatic number > 3
2) find a node a and an edge (b,c), a≠b, a≠c such that the edges (a,b) and (a,c) do not exist
3) if we can't find such nodes, the graph is 3-colorable
4) make two new graphs: G' by adding the edge (a,b) and G'' by adding the edge (a,c). Input both into 1) (bifurcate)
Since we are only adding edges this is guaranteed to terminate.
There is no good heuristic known for the choice of a and (b,c), so these proofs by Hajós bifurcation are often very long and appear arbitrary.
But we can apply certain "shortcuts" by matching known subgraphs to G. One of them would be the mentioned diamond graph. In case of a match we can contract the tips in G.
Another one would be an odd-length wheel graph which corresponds to a bi-value oddagon and is known to be 4-chromatic.
A third one are the "circular ladder graphs with satellites" appearing in the proofs. For these it is possible to add certain edges.
A very similar thing holds for "Möbius ladders with satellites".
As long as we only add edges, contract nodes or terminate right away, the process is still guaranteed to terminate.
A whole other topic I won't talk about here is how to find short proofs, rather than any proof.
In principle, the Hajós bifurcation works for higher chromatic numbers χ by checking for K_χ in 1)
The diamonds, as well as the odd-wheels have generalizations that work for higher χ. I'm not yet entirely sure for all the other structures. There are certain permutation-parity related deductions that may only work for χ=3.
When all of this works satisfyingly, the next task is to find sets of cells within a puzzle (say given as candidate array) to check for chromaticity in the first place. This then also delivers potential guardian candidates. I have not thought about how to do that efficiently. Maybe it can even be stated in graph-theoretic terms, a flow-problem maybe?
I do not plan to do anything with the guardians, other than stating the OR-k relation for now.
Maybe I should quickly explain what the main principle of these proofs is:
If we have a (simple, finite) graph G and want to know whether it is 3-colorable, we can do a reverse Hajós-construction:
1) check whether G contains the complete graph K_4 as subgraph, if so, it has chromatic number > 3
2) find a node a and an edge (b,c), a≠b, a≠c such that the edges (a,b) and (a,c) do not exist
3) if we can't find such nodes, the graph is 3-colorable
4) make two new graphs: G' by adding the edge (a,b) and G'' by adding the edge (a,c). Input both into 1) (bifurcate)
Since we are only adding edges this is guaranteed to terminate.
There is no good heuristic known for the choice of a and (b,c), so these proofs by Hajós bifurcation are often very long and appear arbitrary.
But we can apply certain "shortcuts" by matching known subgraphs to G. One of them would be the mentioned diamond graph. In case of a match we can contract the tips in G.
Another one would be an odd-length wheel graph which corresponds to a bi-value oddagon and is known to be 4-chromatic.
A third one are the "circular ladder graphs with satellites" appearing in the proofs. For these it is possible to add certain edges.
A very similar thing holds for "Möbius ladders with satellites".
As long as we only add edges, contract nodes or terminate right away, the process is still guaranteed to terminate.
A whole other topic I won't talk about here is how to find short proofs, rather than any proof.
In principle, the Hajós bifurcation works for higher chromatic numbers χ by checking for K_χ in 1)
The diamonds, as well as the odd-wheels have generalizations that work for higher χ. I'm not yet entirely sure for all the other structures. There are certain permutation-parity related deductions that may only work for χ=3.
When all of this works satisfyingly, the next task is to find sets of cells within a puzzle (say given as candidate array) to check for chromaticity in the first place. This then also delivers potential guardian candidates. I have not thought about how to do that efficiently. Maybe it can even be stated in graph-theoretic terms, a flow-problem maybe?
I do not plan to do anything with the guardians, other than stating the OR-k relation for now.
- ryokousha
- Posts: 37
- Joined: 30 April 2022
Re: How to deal with large numbers of patterns
by denis_berthier » Wed Mar 01, 2023 1:16 pm
ryokousha wrote:When all of this works satisfyingly, the next task is to find sets of cells within a puzzle (say given as candidate array) to check for chromaticity in the first place. This then also delivers potential guardian candidates. I have not thought about how to do that efficiently. Maybe it can even be stated in graph-theoretic terms, a flow-problem maybe?
That's the hard point. In the standard approach, we try to match predefined patterns (Subsets, various types of chains, tridagons,...) against the resolution state. But if the patterns are not predefined, one has to devise another way of starting the whole search. An intermediate solution would be to have partially defined patterns, but that raises hard problems of computational complexity. Even the simpler problem of allowing degenerate patterns may lead to something much harder wrt pattern matching.
ryokousha wrote:I do not plan to do anything with the guardians, other than stating the OR-k relation for now.
As soon as an ORk-relation is found, whichever way it has been found, the generic ORk-chain rules can be applied in any type of puzzle. So, no real problem here.
- denis_berthier
- 2010 Supporter
- Posts: 4233
- Joined: 19 June 2007
- Location: Paris
Re: How to deal with large numbers of patterns
by denis_berthier » Wed Mar 08, 2023 7:58 am
.
As I mentioned in a previous post, I have written a rule generator that can automatically generate all the rules producing ORk-relations from any of eleven's 630 impossible patterns.
I have now thoroughly tested the corresponding rules.
I have also tried to spot the most useful ones. The method I finally used for this is different from what I reported before (the manual part of it was too slow):
In terms of relative frequencies, I found no significant differences between the last two variables. I therefore concentrated on the first.
I think I found interesting results. There's a small group of rules that are much more frequent than the rest; most of them (but not all) are degenerate versions of tridagon with added cells (this may be due to the way mith's collection was generated, but we have no other collection to test it):
These results were obtained on the first 8000 puzzles in mith's list. The above list is not final, but it is quite stable when increasing the list of puzzles progressively from 2000 to 8000 by steps of 2000.
I'm continuing to extend the computations to more puzzles.
After these results, what I should publish is now clearer to me: I'll publish all the rules, but with different possibilities of selection.
The relevant part of SudoRules config file will look like this (again, this is not the exact final version):
That is, the user will be able to select:
[Added:]
1) You may have noticed that EL15c97 is not on the most frequent list, but it is in the "specific" list. Indeed, I allow in the specific list the most frequent patterns + those that are close to tridagon.
If you find some of the second kind, let me know and I may add them (if they appear in at least a few examples).
2) Note that the prorities order in the "specific" list maybe due in part to the priorities assigned to the general list: fewer cells first.
.
As I mentioned in a previous post, I have written a rule generator that can automatically generate all the rules producing ORk-relations from any of eleven's 630 impossible patterns.
I have now thoroughly tested the corresponding rules.
I have also tried to spot the most useful ones. The method I finally used for this is different from what I reported before (the manual part of it was too slow):
- - I run the whole collection of rules on a part of mith's 158,276 collection of T&E(3) min-expand puzzles;
- for each puzzle, any ORk-chain rule that is effectively applied (eliminating a candidate or asserting a decided value) is listed in a new global variable (with no redundancies, i.e. an ORk-relation is counted only once, even if it is used in several ORk-chains): ?*ORk-relations-used*; (in order to do this, I had to make a small modification to the ORk-chain rules so that they allow to record the ORk-variables they use - to be published soon on GitHub);
- when solving a collection of puzzles, two new global variables ?*all-ORk-relations-used-in-list* and ?*all-ORk-relations-used-in-solved-list* collect all the previous individual variables, the first for all the puzzles, the second one only for the puzzles that are solved; both can (are designed to) have redundancies;
- at the end, I check which ORk-relations appear most frequently in each of these two variables.
In terms of relative frequencies, I found no significant differences between the last two variables. I therefore concentrated on the first.
I think I found interesting results. There's a small group of rules that are much more frequent than the rest; most of them (but not all) are degenerate versions of tridagon with added cells (this may be due to the way mith's collection was generated, but we have no other collection to test it):
- Code: Select all
Trid
EL13c290
EL14c30
EL14c159
EL14c13
EL14c1
EL10c28
EL13c30
EL13c176
EL13c234
EL13c179
EL10c6
EL13c175
EL13c172
EL13c259
EL13c187
EL13c171
EL13c168
These results were obtained on the first 8000 puzzles in mith's list. The above list is not final, but it is quite stable when increasing the list of puzzles progressively from 2000 to 8000 by steps of 2000.
I'm continuing to extend the computations to more puzzles.
After these results, what I should publish is now clearer to me: I'll publish all the rules, but with different possibilities of selection.
The relevant part of SudoRules config file will look like this (again, this is not the exact final version):
- Code: Select all
;;; 2.3.2) Use eleven's 630-38 impossible patterns
;;; Note that ?*Tridagons* and ?*Anti-Tridagons* must still be independently set to TRUE:
;;; they are given higher salience and they are not included in the following lists.
;;; Restrict all the rules that produce ORk relations between "guardians" to a maximum number of guardians:
; (bind ?*max-guardians* 6) ; default is 8
;;; Allow the use of (the most frequently found) specific impossible patterns,
;;; by order of decreasing priorities:
;;; - either all at a time:
; (bind ?*Selected-Imp630* TRUE)
;;; - or one by one:
; (bind ?*EL13c290* TRUE)
; (bind ?*EL14c30* TRUE)
; (bind ?*EL14c13* TRUE)
; (bind ?*EL14c159* TRUE)
; (bind ?*EL14c1* TRUE)
; (bind ?*EL13c176* TRUE)
; (bind ?*EL13c30* TRUE)
; (bind ?*EL10c28* TRUE)
; (bind ?*EL13c234* TRUE)
; (bind ?*EL13c179* TRUE)
; (bind ?*EL13c187* TRUE)
; (bind ?*EL13c168* TRUE)
; (bind ?*EL13c175* TRUE)
; (bind ?*EL13c259* TRUE)
; (bind ?*EL15c97* TRUE)
;;; Notice that selecting any of the above patterns will not only load the corresponding rules;
;;; it will also set their priorities higher than those of all the other Imposs630 rules
;;; (only useful when the following patterns are simultaneously activated).
;;; Allow all the rules for impossible patterns in two bands or two stacks.
; (bind ?*Imposs630-all* TRUE)
;;; Or allow independently all the rules for each sub-family with n cells.
; (bind ?*Imposs630-10c* TRUE)
; (bind ?*Imposs630-12c* TRUE)
; (bind ?*Imposs630-13c* TRUE)
; (bind ?*Imposs630-14c* TRUE)
; (bind ?*Imposs630-15c* TRUE)
; (bind ?*Imposs630-16c* TRUE)
That is, the user will be able to select:
- - all the rules at once,
- only those with specific number of cells,
- all the "specific" ones,
- only his preferred ones among the "specific" ones.
[Added:]
1) You may have noticed that EL15c97 is not on the most frequent list, but it is in the "specific" list. Indeed, I allow in the specific list the most frequent patterns + those that are close to tridagon.
If you find some of the second kind, let me know and I may add them (if they appear in at least a few examples).
2) Note that the prorities order in the "specific" list maybe due in part to the priorities assigned to the general list: fewer cells first.
.
- denis_berthier
- 2010 Supporter
- Posts: 4233
- Joined: 19 June 2007
- Location: Paris
Re: How to deal with large numbers of patterns
by denis_berthier » Thu Mar 09, 2023 7:14 am
.
As a few specific patterns from eleven's 630 list deserve special attention, the question arose how to introduce them in a user-friendly manner that shows their proximity with the tridagon pattern.
Each of them will be presented in 3 equivalent forms in the Augmented User Manual [AUM]:
1) eleven's original form, standardised for use in SudoRules, i.e.:
Example for EL13c290 (the most frequent one after tridagon):
2) The corresponding pretty-print form, with o's marking the free cells (i.e. the cells that can accept a given); the notion of free cells is important as it allowed to eliminate 38 patterns as a priori impossible in a real puzzle.
3) The manually arranged form making it look closest to one of the 3 forms of tridagon:
The whole pattern description will be preceded by its name and its relation to tridagon:
EL13c290: 2 cells missing, 3 added
Note that (as a check), as tridagon has 12 cells, the following must always hold: for any pattern EL<xx>c<yy> with p cells missing and q cells added:
xx = 12 - p + q
Reminder: the 3 selected isomorphic forms of tridagon referred to above are:
As a few specific patterns from eleven's 630 list deserve special attention, the question arose how to introduce them in a user-friendly manner that shows their proximity with the tridagon pattern.
Each of them will be presented in 3 equivalent forms in the Augmented User Manual [AUM]:
1) eleven's original form, standardised for use in SudoRules, i.e.:
- - extended to length 81
- with dots and X's instead of 0s and 1s
Example for EL13c290 (the most frequent one after tridagon):
- Code: Select all
........X..X..X.X...X.X.X.......XX......X..X...X.....X...........................
2) The corresponding pretty-print form, with o's marking the free cells (i.e. the cells that can accept a given); the notion of free cells is important as it allowed to eliminate 38 patterns as a priori impossible in a real puzzle.
- Code: Select all
+-------+-------+-------+
! . . . ! . . . ! . . X !
! . . X ! . . X ! . X . !
! . . X ! . X . ! X . . !
+-------+-------+-------+
! . . . ! . . X ! X . . !
! . . . ! . X . ! . X . !
! . . X ! . . . ! . . X !
+-------+-------+-------+
! o o . ! o . . ! . . . !
! o o . ! o . . ! . . . !
! o o . ! o . . ! . . . !
+-------+-------+-------+
3) The manually arranged form making it look closest to one of the 3 forms of tridagon:
- Code: Select all
+-------+-------+-------+
! . . . ! . . - ! . . X !
! . . Z ! . X . ! . X . !
! . . Z ! X . . ! X . . !
+-------+-------+-------+
! . . Z ! . . - ! . . X !
! . . . ! X . . ! . X . !
! . . . ! . X . ! X . . !
+-------+-------+-------+
! o o . ! . . o ! . . . !
! o o . ! . . o ! . . . !
! o o . ! . . o ! . . . !
+-------+-------+-------+
- - minus signs mark the missing cells (wrt to the closest tridagon form)
- Z signs mark the intruders (wrt to the same form).
The whole pattern description will be preceded by its name and its relation to tridagon:
EL13c290: 2 cells missing, 3 added
Note that (as a check), as tridagon has 12 cells, the following must always hold: for any pattern EL<xx>c<yy> with p cells missing and q cells added:
xx = 12 - p + q
Reminder: the 3 selected isomorphic forms of tridagon referred to above are:
- Code: Select all
+-------+-------+-------+
! . . . ! . . X ! . . X !
! . . . ! . X . ! . X . !
! . . . ! X . . ! X . . !
+-------+-------+-------+
! . . . ! X . . ! . . X !
! . . . ! . X . ! . X . !
! . . . ! . . X ! X . . !
+-------+-------+-------+
! o o o ! . . . ! . . . !
! o o o ! . . . ! . . . !
! o o o ! . . . ! . . . !
+-------+-------+-------+
+-------+-------+-------+
! . . . ! . . X ! . . X !
! . . . ! . X . ! . X . !
! . . . ! X . . ! X . . !
+-------+-------+-------+
! . . . ! . . X ! . . X !
! . . . ! X . . ! . X . !
! . . . ! . X . ! X . . !
+-------+-------+-------+
! o o o ! . . . ! . . . !
! o o o ! . . . ! . . . !
! o o o ! . . . ! . . . !
+-------+-------+-------+
+-------+-------+-------+
! . . . ! . . X ! . . X !
! . . . ! . X . ! . X . !
! . . . ! X . . ! X . . !
+-------+-------+-------+
! . . . ! . X . ! . . X !
! . . . ! . . X ! . X . !
! . . . ! X . . ! X . . !
+-------+-------+-------+
! o o o ! . . . ! . . . !
! o o o ! . . . ! . . . !
! o o o ! . . . ! . . . !
+-------+-------+-------+
- denis_berthier
- 2010 Supporter
- Posts: 4233
- Joined: 19 June 2007
- Location: Paris
Re: How to deal with large numbers of patterns
by denis_berthier » Tue Mar 14, 2023 5:17 am
.
I've finally analysed the first 20,000 puzzles in mith's collection of 158,276 T&E(3) min-expand puzzles with all the rules automatically generated by CSP-Rules from eleven's collection of (630-38) impossible 3-digit patterns.
Remember that:
The results led me to introduce 4 sets of pattern selections that can be independently chosen (as a whole group or individually). Some of them are close to tridagon, but some are not. The updated version of the Augmented User Manual (that will come with the next CSP-Rules update) contains complete descriptions of them, similar to the example in my previous post.
This is in addition to the possibility of selecting large groups of patterns: all the patterns or all those that have xx cells
The meaningfulness of these selections may be understood with the following table, giving the number of puzzles in which each of them appeared as useful in the resolution path.
The 4 selections may change in the future, in particular for patterns that appear to be close to tridagon. I'm thinking in particular of EL15c97, which is a natural follow-up of the simplest tridagon elimination and which might therefore be upgraded to Imp630-Select2 or even Imp630-Select1. Such patterns lead to self-contained eliminations, contrary to using indirect implications of Remote Triplets.
.
I've finally analysed the first 20,000 puzzles in mith's collection of 158,276 T&E(3) min-expand puzzles with all the rules automatically generated by CSP-Rules from eleven's collection of (630-38) impossible 3-digit patterns.
Remember that:
- - for reasons of computational complexity, these rules can only detect non-degenerate patterns (i.e. the 3 digits must be present in all the cells of the pattern);
- in order to give patterns a chance of being detected before degenerating, SudoRules detects them immediately after W2+S3;
- in order to allow them to remain available if they degenerate during resolution, ORk-relations are ultra-persistent;
- the non-degeneracy condition is not a restriction for tridagon in mith's collection: all the puzzles still have a tridagon pattern after W2+S3 (sometimes, it appears only later);
- I eliminated 38 of the patterns because they have less than 2 free cells and can therefore not be found in non-degenerate form in a real puzzle;
- a priori priorities between patterns are based on the number of cells;
- rules that would assert an ORk-relation with a set of guardians that is a superset of an already existing one are prevented from doing it (the new ORk-relations would be useless);
- the maximum number of guardians allowed was set to 8 (which is quite high)
- the maximum length of whips and ORk-whips was set to 8.
The results led me to introduce 4 sets of pattern selections that can be independently chosen (as a whole group or individually). Some of them are close to tridagon, but some are not. The updated version of the Augmented User Manual (that will come with the next CSP-Rules update) contains complete descriptions of them, similar to the example in my previous post.
- Code: Select all
Imp630-Select1 =
EL13c290
EL14c30
EL14c159
EL14c13
EL14c1
Imp630-Select2 = Imp630-Select1 +
EL13c176
EL10c28
EL13c30
EL13c179
EL13c234
EL13c171
Imp630-Select3 = Imp630-Select2 +
EL10c6
EL10c8
EL13c175
EL13c259
EL10c4
EL14c19
EL13c187
EL13c172
Imp630-Select4 = Imp630-Select3 +
EL15c97
EL13c168
EL14c93
EL13c19
EL14c154
This is in addition to the possibility of selecting large groups of patterns: all the patterns or all those that have xx cells
- Code: Select all
Imp630-all
Imp630-10c
Imp630-12c
Imp630-13c
Imp630-14c
Imp630-15c
Imp630-16c
The meaningfulness of these selections may be understood with the following table, giving the number of puzzles in which each of them appeared as useful in the resolution path.
- Code: Select all
Trid = 19594
Imp630-Select1:
EL13c290 = 4491
EL14c30 = 2756
EL14c159 = 1684
EL14c13 = 1352
EL14c1 = 1066
Imp630-Select2:
EL13c176 = 521
EL10c28 = 491
EL13c30 = 468
EL13c179 = 432
EL13c234 = 380
EL13c171 = 257
Imp630-Select3:
EL10c6 = 234
EL10c8 = 177
EL13c175 = 157
EL13c259 = 148
EL10c4 = 141
EL14c19 = 136
EL13c187 = 134
EL13c172 = 122
Imp630-Select4:
EL15c97 = 95
EL13c168 = 82
EL14c93 = 80
EL13c19 = 71
EL14c154 = 61
The 4 selections may change in the future, in particular for patterns that appear to be close to tridagon. I'm thinking in particular of EL15c97, which is a natural follow-up of the simplest tridagon elimination and which might therefore be upgraded to Imp630-Select2 or even Imp630-Select1. Such patterns lead to self-contained eliminations, contrary to using indirect implications of Remote Triplets.
.
- denis_berthier
- 2010 Supporter
- Posts: 4233
- Joined: 19 June 2007
- Location: Paris
Re: How to deal with large numbers of patterns
by RichardGoodrich » Tue Jan 23, 2024 2:28 am
Mathimagics wrote:Hi Denis and ryokousha
I have some modest experience of Sudoku puzzle solving using graphs. I used Brendan Mckay's nauty library.
This is the first time I have noticed anyone else using graph-theoretic methods, so I'm interested to know what tools you are using.
Cheers
MM
Hope I am NOT too late to get on this. I want to use pynauty.py in my Python Sudoku code. No anyone with experience using it. 2nd best is just to find a MinLex program I can actually run. So far I have tried only one and even though it was a jar file, I could not get it to run!
Big1952
- RichardGoodrich
- Posts: 70
- Joined: 12 December 2012
- Location: Josephine, TX
Re: How to deal with large numbers of patterns
by denis_berthier » Tue Jan 23, 2024 3:55 am
RichardGoodrich wrote:Mathimagics wrote:Hi Denis and ryokousha
I have some modest experience of Sudoku puzzle solving using graphs. I used Brendan Mckay's nauty library.
This is the first time I have noticed anyone else using graph-theoretic methods, so I'm interested to know what tools you are using.
Hope I am NOT too late to get on this. I want to use pynauty.py in my Python Sudoku code. No anyone with experience using it. 2nd best is just to find a MinLex program I can actually run. So far I have tried only one and even though it was a jar file, I could not get it to run!
Hi Richard,
Basically, CSP-Rules works on graphs: all my resolution rules other than Singles rely only on the graph of candidates (with links = direct binary contradictions). In particular, decided values (once decided) play no more role. However, there's one more ingredient than mere graphs: the CSP-Variables. So that in reality, the problem is (implicitly) turned into a graph colouring problem (and indeed, I have graph colouring as one of the applications of CSP-Rules).
Regarding your question, I'm not using standard graph methods for solving and no graph software. I have very little experience with Python, even as a simple user.
I haven't found a (solution) minlexer that works on my Mac - I don't really need one, but it'd be nice.
.
- denis_berthier
- 2010 Supporter
- Posts: 4233
- Joined: 19 June 2007
- Location: Paris
Re: How to deal with large numbers of patterns
by denis_berthier » Sun Nov 10, 2024 7:36 am
.
This thread hasn't been updated for some time.
For completeness, note that SudoRules now allows full freedom of selection of the impossible patterns.
The pre-selected sets (of the most frequently used ones) remain available, but I've added a new possibility of making a personal selection. This may be very useful in two cases:
1) for some reason of your own, you are interested in some particular pattern(s);
2) you have activated all (or many of) the impossible patterns and the resolution path happens to use effectively only a few of them. Select the latter in the config file, choose a max number of guardians adapted to what you've seen in the 1st resolution path and re-run SudoRules: you'll get a resolution path cleaned of all the useless ORk-relations found for unused impossible patterns. See an example here: http://forum.enjoysudoku.com/the-bxb-classification-of-t-e-2-puzzles-t41922-165.html.
.
This thread hasn't been updated for some time.
For completeness, note that SudoRules now allows full freedom of selection of the impossible patterns.
The pre-selected sets (of the most frequently used ones) remain available, but I've added a new possibility of making a personal selection. This may be very useful in two cases:
1) for some reason of your own, you are interested in some particular pattern(s);
2) you have activated all (or many of) the impossible patterns and the resolution path happens to use effectively only a few of them. Select the latter in the config file, choose a max number of guardians adapted to what you've seen in the 1st resolution path and re-run SudoRules: you'll get a resolution path cleaned of all the useless ORk-relations found for unused impossible patterns. See an example here: http://forum.enjoysudoku.com/the-bxb-classification-of-t-e-2-puzzles-t41922-165.html.
.
- denis_berthier
- 2010 Supporter
- Posts: 4233
- Joined: 19 June 2007
- Location: Paris
Re: How to deal with large numbers of patterns
by denis_berthier » Mon Nov 11, 2024 6:25 am
.
One more result about eleven's 630 impossible 3-digit (Imp630 for short) patterns is their (non-)effectiveness for pre-tridagon T&E(2) puzzles.
These are old results for me, but it seems I haven't published them anywhere yet.
For eleven's collection of 26,368 hard puzzles in T&E(2):
- 3,211 (12.18 %) have some Imp630 pattern;
- the ratio depends on BxB; % patterns for BxB (x= 1...6):
0
0
0.16
0.63
11.69
22.92
- the ratio also depends on the SER; % patterns for SER = 10.6 to 11.9 by steps of 0.1:
0.0
0.0
0.0
0.0
1.83
1.15
2.57
2.19
6.17
24.53
20.77
8.77
10.62
14.93
Perhaps the most noticeable result is, almost all the puzzles with an Imp630 pattern also have a degenerate cyclic tridagon. Only 13 (2.09 %) puzzles don't (I haven't checked if they have a still more degenerate form of tridagon).
For the ph2010 collection, I had recorded (and probably done) computations for only the first 20,000 puzzles (SER ≥ 11.2 ; not all the SER=11.2)
- there are 7084 (35.42 %) Imp630 puzzles with an Imp630 pattern; this is a much larger proportion than for eleven's collection (even restricted to the same range of SER); but the different characteristics of the two collections is not a new thing;
- a larger proportion of them doesn't have a degenerate cyclic tridagon: 621 (8.67 %)
One common result is, most of the Imp630 patterns have a very large numbers of guardians (I mean >14) and are therefore useless in practice.
.
One more result about eleven's 630 impossible 3-digit (Imp630 for short) patterns is their (non-)effectiveness for pre-tridagon T&E(2) puzzles.
These are old results for me, but it seems I haven't published them anywhere yet.
For eleven's collection of 26,368 hard puzzles in T&E(2):
- 3,211 (12.18 %) have some Imp630 pattern;
- the ratio depends on BxB; % patterns for BxB (x= 1...6):
0
0
0.16
0.63
11.69
22.92
- the ratio also depends on the SER; % patterns for SER = 10.6 to 11.9 by steps of 0.1:
0.0
0.0
0.0
0.0
1.83
1.15
2.57
2.19
6.17
24.53
20.77
8.77
10.62
14.93
Perhaps the most noticeable result is, almost all the puzzles with an Imp630 pattern also have a degenerate cyclic tridagon. Only 13 (2.09 %) puzzles don't (I haven't checked if they have a still more degenerate form of tridagon).
For the ph2010 collection, I had recorded (and probably done) computations for only the first 20,000 puzzles (SER ≥ 11.2 ; not all the SER=11.2)
- there are 7084 (35.42 %) Imp630 puzzles with an Imp630 pattern; this is a much larger proportion than for eleven's collection (even restricted to the same range of SER); but the different characteristics of the two collections is not a new thing;
- a larger proportion of them doesn't have a degenerate cyclic tridagon: 621 (8.67 %)
One common result is, most of the Imp630 patterns have a very large numbers of guardians (I mean >14) and are therefore useless in practice.
.
- denis_berthier
- 2010 Supporter
- Posts: 4233
- Joined: 19 June 2007
- Location: Paris
Re: How to deal with large numbers of patterns
by denis_berthier » Tue Nov 12, 2024 5:17 am
.
In the BxB thread (http://forum.enjoysudoku.com/the-bxb-classification-of-t-e-2-puzzles-t41922-150.html), coloin has re-drawn my attention to eleven's 630 impossible 3-digit patterns (Imp630 for short).
Long ago, I gave results for their usability in T&E(3) puzzles (see [UMNR], https://www.researchgate.net/publication/372364607_User_Manual_and_Research_Notebooks_for_CSP-Rules, for a redacted version).
In the previous post, I gave results for the old, i.e. pre-tridagon, T&E(2) collections.
Here are now new results for the post-tridagon T&E(2) puzzles. My reference collection consists of coloin's 3362 puzzles in BxB, x≥7: http://forum.enjoysudoku.com/the-bxb-classification-of-t-e-2-puzzles-t41922-105.html.
As mentioned in previous posts, all these puzzles, except the 3 old ones in B7B, have a non-degenerate tridagon.
My goal was to see if they also have useful Imp630 patterns and the answer is yes, much more frequently than other (pre-tridagon) T&E(2) puzzles. I used the same comparison method as for T&E(3) puzzles: I computed the ratings when only Tridagons, Subsets, whips and OR5-whips are activated and when Imp630 patterns are added. Any time the rating is decreased, I consider the pattern was useful.
I found 193 (5.7%) useful cases, including 58 not solvable without the Imp630.
Coloin has given a first example here: http://forum.enjoysudoku.com/mission-impossible-t45243.html.
You can find another easy example (I mean easy once you've found the impossible patterns) here: http://forum.enjoysudoku.com/some-b10b-t45254.html
.
In the BxB thread (http://forum.enjoysudoku.com/the-bxb-classification-of-t-e-2-puzzles-t41922-150.html), coloin has re-drawn my attention to eleven's 630 impossible 3-digit patterns (Imp630 for short).
Long ago, I gave results for their usability in T&E(3) puzzles (see [UMNR], https://www.researchgate.net/publication/372364607_User_Manual_and_Research_Notebooks_for_CSP-Rules, for a redacted version).
In the previous post, I gave results for the old, i.e. pre-tridagon, T&E(2) collections.
Here are now new results for the post-tridagon T&E(2) puzzles. My reference collection consists of coloin's 3362 puzzles in BxB, x≥7: http://forum.enjoysudoku.com/the-bxb-classification-of-t-e-2-puzzles-t41922-105.html.
As mentioned in previous posts, all these puzzles, except the 3 old ones in B7B, have a non-degenerate tridagon.
My goal was to see if they also have useful Imp630 patterns and the answer is yes, much more frequently than other (pre-tridagon) T&E(2) puzzles. I used the same comparison method as for T&E(3) puzzles: I computed the ratings when only Tridagons, Subsets, whips and OR5-whips are activated and when Imp630 patterns are added. Any time the rating is decreased, I consider the pattern was useful.
I found 193 (5.7%) useful cases, including 58 not solvable without the Imp630.
Coloin has given a first example here: http://forum.enjoysudoku.com/mission-impossible-t45243.html.
You can find another easy example (I mean easy once you've found the impossible patterns) here: http://forum.enjoysudoku.com/some-b10b-t45254.html
.
- denis_berthier
- 2010 Supporter
- Posts: 4233
- Joined: 19 June 2007
- Location: Paris
Re: How to deal with large numbers of patterns
by denis_berthier » Mon Nov 18, 2024 6:48 am
.
The properties of T&E(2) puzzles with BxB≥7 are very close to those of the T&E(3) puzzles:
- all of them (except 3 old ones) have a non-degenerate tridagon;
- they have many clues and many candidates;
- their solutions using tridagons combined with ORk-chain rules may be easy or very hard;
- their solutions using tridagons and impossible patterns (from eleven's list of 630) combined with ORk-chain rules may be easy or very hard;
- the same impossible patterns as for T&E(3) puzzles appear frequently in the solutions.
For examples, see 3 puzzles in the Puzzles section:
http://forum.enjoysudoku.com/some-b10b-t45254.html, solved with a few impossible patterns and only very short ORk-chains;
http://forum.enjoysudoku.com/some-b8b-t45256.html, solved with a few impossible patterns and very short ORk-chains;
http://forum.enjoysudoku.com/a-harder-b8b-t45259.html, requires longer ORk-chains (up to length 4 - which is still far from the maximum length required by some puzzles.
The properties of T&E(2) puzzles with BxB≥7 are very close to those of the T&E(3) puzzles:
- all of them (except 3 old ones) have a non-degenerate tridagon;
- they have many clues and many candidates;
- their solutions using tridagons combined with ORk-chain rules may be easy or very hard;
- their solutions using tridagons and impossible patterns (from eleven's list of 630) combined with ORk-chain rules may be easy or very hard;
- the same impossible patterns as for T&E(3) puzzles appear frequently in the solutions.
For examples, see 3 puzzles in the Puzzles section:
http://forum.enjoysudoku.com/some-b10b-t45254.html, solved with a few impossible patterns and only very short ORk-chains;
http://forum.enjoysudoku.com/some-b8b-t45256.html, solved with a few impossible patterns and very short ORk-chains;
http://forum.enjoysudoku.com/a-harder-b8b-t45259.html, requires longer ORk-chains (up to length 4 - which is still far from the maximum length required by some puzzles.
- denis_berthier
- 2010 Supporter
- Posts: 4233
- Joined: 19 June 2007
- Location: Paris
45 posts
• Page 3 of 3 • 1, 2, 3
