The New Sudoku Players' Forum

[denis_berthier]

I broadly agree with all you say. There is an important misunderstanding we need to clear up, so we're talking about the same thing:

.

Concerning the classification of those patterns, there are some easy things to be said if we view them as graphs (subgraphs of the sudoku graph, induced by the restricted cells, to be precise):

To be still more precise, you're talking of the full subgraph of the sudoku graph for the candidates in the pattern (i.e. it inherits all the sudoku links between candidates in the pattern). Which of course keeps all this very sudoku-specific. This will be useful to remember when we come to your last point.

No. I'm talking about (subgraphs of) the graph where the cells are the nodes and an edge exists when two cells see each other: https://en.wikipedia.org/wiki/Sudoku_graph
The full graph between candidates is of course also interesting, in particular isomorphic subgraphs. I'm not entirely sure in what context coloring/chromaticity on that full graph would be useful (maybe for broken wings / patterns which mix restricted candidate choices in cells and restricted locations for candidates in houses?). What does coloring of single candidates even mean?
Anyway, I'm not concerned with the full graph at the moment.

Actually, considering that all the cells must have the k digits, there's a trivial bijection between the subgraphs in your sense and those in mine.
What corresponds to colouring in your subgraph corresponds to T&E-depth of contradiction in mine.

[Mathimagics]

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

[denis_berthier]

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.

I'll let Ryokusha speak for himself. As for me, I'm not really using graph theory to solve Sudokus.
My general approach of solving is based on Constraint Satisfaction. Sudoku indeed appears as a graph with candidates as vertices and direct contradictions between them as edges. Candidates and such links are the only thing that play a role in writing my generic resolution rules. But graph-theoretic concepts don't really play any other role in them.

In the recent part of my work, I've been using eleven's impossible 3-digit patterns as a base for defining OR-relations (useable by some of my generic chain rules). Here again, even if graph theory may have played a role in finding the patterns (I don't know how eleven did), the way I use them doesn't rely on graph theory.

[ryokousha]

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

Interesting, I will have a look at that library.
I've mostly been using networkx (and also its grinpy extension to find and verify chromatic numbers directly).
For a specific other problem which is only partially related (finding maximal cliques in the compatibility graph of the 46656 1-digit templates) I had to switch to networkit.

[denis_berthier]

A far goal would be to have a computer solver that not only can recognize such patterns in a puzzle by pulling them from a "library" and just stating that they are impossible, but is able to check any set of restricted cells in a puzzle for chromaticity and give a proof of the fact when appropriate.

Not sure we're talking of the same thing.
Currently, given any set of supposedly impossible k-digit patterns, SudoRules can:

1) classify them according to the T&E-depth or to the restricted T&E-depth necessary to prove their contradiction. Those are two related but different measures of their complexity.
I understand you're looking for different, graph-based measures of complexity. It's very interesting also, but in the end they will all fall under this broad universal classification.

2) automatically generate the corresponding rules that conclude the only thing an impossible pattern can conclude: there is some ORk-relation between their "guardians".
This is what I have reported in a previous post: based on eleven's 630 - 38 patterns, SudoRules can automatically generate (630 - 38) * 3 resolution rules.
You can see these rules at work in the puzzles I've recently proposed in the Puzzles section. They appear as EL<xxx>c<yyy>-OR<k>-relation: EL is for eleven, <xxx> is the number of cells, <yyy> the place in the corresponding list, <k> the number of guardians.
Of course, rule generation is done once and for all. Note that generating all these rules takes only a few seconds. Instead of a "library" of patterns, SudoRules has a collection of resolution rules.
In order to solve a given puzzle, one can decide to activate them or not. If activated, SudoRules will automatically try to match the patterns they represent.
Note that these rules have already been thoroughly tested (currently on about 20,000 puzzles).
If you want to generate rules for a different set of k-digit patterns, you can post the patterns; it's not a big deal for me to generate more rules, with a RY prefix (or any 2-character prefix you'd prefer).
I plan to do the same with a few patterns used by Totuan; but I need time to collect them from the Puzzles section.

3) use these Sudoku-specific rules together with generic ORk-chain rules in any puzzle, by activating them in the configuration file.
Note that, in spite of the very large number of rules thus added to SudoRules, this doesn't crush or crash it.
.

[ryokousha]

Understood. As great as that is, there is still a need for a solver that can identify (and prove) chromatic patterns without being fed a pre-generated list first.
We don't yet have an exhaustive list for 3-band patterns for example and it is at least hard to produce. More importantly (for many people) in variant sudoku such patterns can take entirely different forms where links between cells can come from killer-cages, renban-lines, anti-elephant and whatnot.

[denis_berthier]

Understood. As great as that is, there is still a need for a solver that can identify (and prove) chromatic patterns without being fed a pre-generated list first.
We don't yet have an exhaustive list for 3-band patterns for example and it is at least hard to produce. More importantly (for many people) in variant sudoku such patterns can take entirely different forms where links between cells can come from killer-cages, renban-lines, anti-elephant and whatnot.

I agree that'd be great. However, I have no idea how to do this with acceptable computation times - or even just how to do this. I'm therefore very interested in any results you can get along these lines.

My approach of impossible patterns is much more modest. It relies on what I feel able to express in reasonable time, in the conceptual framework defined in [PBCS] and implemented in CSP-Rules, where Sudoku and other logic games are treated as constraint satisfaction problems. You may think this is not ambitious enough, but this allows me to study such things as: among such large families of potentially useful patterns, are there many that are really useful in concrete examples? My still very preliminary results tend to show that there are not so many.
.

[denis_berthier]

.
One more useful pattern (less frequent than the previous ones), EL13c175:

Code: Select all

...........X..X..X..X.X..X......X.X.....X.X....XX...X............................
+-------+-------+-------+
! . . . ! . . . ! . . . !
! . . X ! . . X ! . . X !
! . . X ! . X . ! . X . !
+-------+-------+-------+
! . . . ! . . X ! . X . !
! . . . ! . X . ! X . . !
! . . X ! X . . ! . X . !
+-------+-------+-------+
! o o . ! . . . ! . . . !
! o o . ! . . . ! . . . !
! o o . ! . . . ! . . . !
+-------+-------+-------+

isomorphic to:

Code: Select all

+-------+-------+-------+
! . . . ! . . X ! . . X !
! . . . ! . X . ! . X . !
! . . X ! . . X ! X . . !
+-------+-------+-------+
! . . X ! X . . ! . . X !
! . . X ! . . X ! . X . !
! . . . ! . . . ! . . . !
+-------+-------+-------+
! o o . ! . . . ! . . . !
! o o . ! . . . ! . . . !
! o o . ! . . . ! . . . !
+-------+-------+-------+

used in this puzzle: http://forum.enjoysudoku.com/1378-in-mith-s-list-of-t-e-3-min-expands-t40969.html
.

[ryokousha]

This falls in the easy category (simple coloring):

Code: Select all

000000000001001001001010010000001010000010100001100010000000000000000000000000000 EL13c175 6
r3c8 is in r5c7 of triple (r5c7, r4c8, r6c8)
r3c3 is in r5c5 of triple (r5c5, (r3c8=r5c7), r3c5)
r2c3 is in r6c4 of triple (r6c4, (r3c3=r5c5), r6c3)
r4c6 is in r2c9 of triple (r2c9, (r2c3=r6c4), r2c6)
r4c8 is in (r3c3=r5c5) of triple ((r3c3=r5c5), (r3c8=r5c7), (r4c6=r2c9))
(r4c8=(r3c3=r5c5)), (r2c3=r6c4), r6c8, r6c3 need 4 different digits.

The similar EL13c176 for example should be harder:

Code: Select all

000000000001001001001010010000001010000100100001001001000000000000000000000000000 EL13c176 7
r2c6 is in r5c4 of triple (r5c4, r4c6, r6c6)
Circular ladder with 2 satellites: The pairs (r2c3,r6c3), ((r2c6=r5c4),r6c6), (r2c9,r6c9) are each missing a different digit, so r3c3 and r4c6 are different.
Circular ladder with 1 satellite: The pairs (r2c3,(r2c6=r5c4)), (r6c3,r6c6), (r3c3,r4c6) are each missing a different digit, so r2c9 must repeat in r6c3+r4c6 or r3c3+r6c6:
if r2c9=r6c3=r4c6 then
  bi-value oddagon r4c8, r3c8, r3c3, r2c3, (r2c6=r5c4), r6c6, r6c9.
if r2c9=r3c3=r6c6 then
  r4c6 is in r3c5 of triple (r3c5, (r2c6=r5c4), (r2c9=r3c3=r6c6))
  r4c8 is in (r2c9=r3c3=r6c6) of triple ((r2c9=r3c3=r6c6), (r4c6=r3c5), r3c8)
  bi-value oddagon r5c7, (r2c6=r5c4), r2c3, r6c3, r6c9.

[denis_berthier]

This falls in the easy category (simple coloring):

Code: Select all

000000000001001001001010010000001010000010100001100010000000000000000000000000000 EL13c175 6
r3c8 is in r5c7 of triple (r5c7, r4c8, r6c8)
r3c3 is in r5c5 of triple (r5c5, (r3c8=r5c7), r3c5).

I'm sure you know what you mean. I don't. What does "r3c8 is in r5c7" mean ?

[ryokousha]

Formulations, among other things, are still work in progress
It just means both cells have the same color/value (all under the presumption of a 3-coloring of all cells, of course).

[denis_berthier]

Formulations, among other things, are still work in progress
It just means both cells have the same color/value (all under the presumption of a 3-coloring of all cells, of course).

OK, but it shouldn't be that difficult to make them understandable. Is there any reason for not writing "r3c8 = r5c7" ?

[ryokousha]

Can do that. I'll also probably introduce actual colors at some point, so something like

Code: Select all

r2c6 = r5c4 = blue by triple (r5c4, r4c6, r6c6)

and then later

Code: Select all

bi-value oddagon r4c8, r3c8, r3c3, r2c3, blue, r6c6, r6c9.

etc.
The difficulty being that a color should only be introduced when we know it represents a value different from all previously introduced colors. So I want to avoid things like blue=green for clarity.

Also I'm aware that things like "circular ladders with satellites" (or whatever a final terminology will be) need some outside explanation.

[denis_berthier]

Can do that. I'll also probably introduce actual colors at some point, so something like

Code: Select all

r2c6 = r5c4 = blue by triple (r5c4, r4c6, r6c6)

Actually, even this would require an explanation: in and of itself, a triplet never implies any condition on any of its cells. So, in order to avoid ad hoc reasoning in each potential instance of your pattern, more info about other cells would be required - in the present case, some particular relation between r2c6 and r5c4.

[ryokousha]

So you're liking

Code: Select all

r2c6=r5c4 as both see r4c6 and r6c6

better?