The New Sudoku Players' Forum

by **Red Ed** » Thu May 23, 2013 10:17 pm

One way to look at non-uniqueness solving techniques is that holes beget holes. When you eliminate a candidate (create a hole), you find you can eliminate further candidates (creating more holes). The eliminations are done by spotting the existence of some pattern, H, of holes, and applying a rule of the form H => J, meaning "if I've got holes H then I must also have holes J".

For example, with notation thus

pattern: /xy ... candidates x and y are holes; *xy ... all except candidates x and y are holes
implies: -xy ... candidates x and y are eliminated; =xy ... all except candidates x and y are eliminated

the box/line reduction rule can (unsurprisingly) be displayed like this:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- -1 -1 -1 | . . . | . . . -1 -1 -1 | . . . | . . . . . . | /1 /1 /1 | /1 /1 /1

I'd like to know: what are the "fundamental" patterns of holes and what do they eliminate?
There is no good definition of "fundamental", so that's where I was hoping I might get your thoughts. There might not be any sensible definition of "fundamental", but let's not give up immediately.

Axiom 1: I think there's one uncontroversial rule that all "fundamental" patterns should obey: there must be at least one elimination that requires all the holes. In the box/line reduction example, the elimination at r7c1 (or indeed any other) cannot be made if any of the holes in r9 is missing. (As an aside, I admit it's a bit of a double negative to talk about missing holes ...) You need this axiom to stop me adding 1r5c5 (say) as a hole and claiming that the pattern is still fundamental.

Because of axiom 1, I will only ever show the eliminations that require all of the holes ("critical" eliminations, if you like). This takes a bit of getting used to, for example in the hidden-single-in-a-box pattern ...

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- . . . | . . . | =1 /1 /1 . . . | . . . | /1 /1 /1 . . . | . . . | /1 /1 /1

... where the eliminations 23456789r7c7 are critical (shown concisely as "=1"), but the eliminated 1s in r7 and c7 are not (so are not shown).

It takes a fair amount of work just to enumerate small patterns that satisfy axiom 1. So far, I've limited myself to patterns where the holes are contained within at most two rows, columns, boxes or cells. I ended up with 55 distinct patterns, all of which are listed in the next post (EDIT: to which I'll add comments as the discussion progresses). I think that pretty much any (non-uniqueness) technique you can think of on at most two rows/cols/boxes/cells is covered by that list, which is great -- it's a demonstration of automatic pattern discovery.

On the other hand, many of the listed patterns look like they're the aggregate of other, simpler, components, and so are not intuitively fundamental. That means (if this exercise has any hope of success) that we need more axioms to prune the rubbish from the list. What additional axioms would you suggest?

by **Red Ed** » Thu May 23, 2013 10:18 pm

Note:

Axiom 2a = Axiom 2 with "P < Q" = "P has fewer holes than Q".
Axiom 2b = Axiom 2 with "P < Q" = "P's x-sees-y graph is a subgraph of Q's" ((( to do ... will be tedious )))

Pattern #1
Name: hidden single in row
Axiom 2a: OK for elims in r9c1 only
Comment:

Code: Select all: -1 . . | . . . | . . . -1 . . | . . . | . . . -1 . . | . . . | . . . ---------+----------+--------- -1 . . | . . . | . . . -1 . . | . . . | . . . -1 . . | . . . | . . . ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . =1 /1 /1 | /1 /1 /1 | /1 /1 /1

Pattern #2
Name: box/line reduction
Axiom 2a: OK
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- -1 -1 -1 | . . . | . . . -1 -1 -1 | . . . | . . . . . . | /1 /1 /1 | /1 /1 /1

Pattern #3
Name: hidden single in box
Axiom 2a: OK
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- . . . | . . . | =1 /1 /1 . . . | . . . | /1 /1 /1 . . . | . . . | /1 /1 /1

Pattern #4
Name: pointing triple
Axiom 2a: OK
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- -1 -1 -1 | -1 -1 -1 | . . . . . . | . . . | /1 /1 /1 . . . | . . . | /1 /1 /1

Pattern #5
Name: naked single
Axiom 2a: OK
Comment:

Code: Select all: . . . | . . . | . . -1 . . . | . . . | . . -1 . . . | . . . | . . -1 ---------+----------+--------- . . . | . . . | . . -1 . . . | . . . | . . -1 . . . | . . . | . . -1 ---------+----------+--------- . . . | . . . | -1 -1 -1 . . . | . . . | -1 -1 -1 -1 -1 -1 | -1 -1 -1 | -1 -1 *1

Pattern #6
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

Pattern #7
Name: 2-string kite
Axiom 2a: OK
Comment:

Code: Select all: -1 . . | . . . | . . . . . . | . . . | . . /1 . . . | . . . | . . /1 ---------+----------+--------- . . . | . . . | . . /1 . . . | . . . | . . /1 . . . | . . . | . . /1 ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . /1 /1 | /1 /1 /1 | . . /1

Pattern #8
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

Pattern #9
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

Pattern #10
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

Pattern #11
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

Pattern #12
Name: finned x-wing
Axiom 2a: OK
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- -1 . . | . . . | . . . -1 . . | . . . | . . . . . . | . /1 /1 | /1 /1 /1 ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . /1 /1 | . /1 /1 | /1 /1 /1

Pattern #13
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

Pattern #14
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

Pattern #15
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

Pattern #16
Name: x-wing
Axiom 2a: OK
Comment:

Code: Select all: -1 . . | -1 . . | . . . -1 . . | -1 . . | . . . -1 . . | -1 . . | . . . ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . /1 /1 | . /1 /1 | /1 /1 /1 ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . /1 /1 | . /1 /1 | /1 /1 /1

Pattern #17
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

Pattern #18
Name: empty rectangle / finned franken x-wing
Axiom 2a: OK
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . /1 /1 | /1 /1 /1 | . /1 /1 ---------+----------+--------- -1 . . | . . . | . . . . . . | . . . | . /1 /1 . . . | . . . | . /1 /1

Pattern #19
Name:
Axiom 2a: FAILED
Comment: *** need to double-check my code ***

Hidden Text: Show

Pattern #20
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

Pattern #21
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

Pattern #22
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

Pattern #23
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

Pattern #24
Name: hidden pair in row (sitting in same box)
Axiom 2a: OK
Comment: looks like this should be redundant, as it's a special case of HP-in-a-row

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . =12 =12 /12 | /12 /12 /12 | /12 /12 /12

Pattern #25
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

Pattern #26
Name: hidden pair in row
Axiom 2a: OK
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . =12 /12 /12 | =12 /12 /12 | /12 /12 /12

Pattern #27
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

Pattern #28
Name:
Axiom 2a: FAILED
Comment:

Hidden Text: Show

((( stopped checking Axiom 2a at this point )))

Pattern #29
Name:
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ -1 -1 -1 | -1 -1 -1 | . . . . . . | . . . | /1 /1 /1 /2 /2 /2 | /2 /2 /2 | . /12 /12

Pattern #30
Name:
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | =12 /1 /1 . . . | . . . | /1 /1 /1 /2 /2 /2 | /2 /2 /2 | . /12 /12

Pattern #31
Name:
Comment:

Code: Select all: . . . | . . . | -1 . . . . . | . . . | -1 . . . . . | . . . | -1 . . ------------+-------------+------------ . . . | . . . | -1 . . . . . | . . . | -1 . . . . . | . . . | -1 . . ------------+-------------+------------ . . . | . . . | . /1 /1 . . . | . . . | . /1 /1 /2 /2 /2 | /2 /2 /2 | /2 . /12

Pattern #32
Name:
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | =12 /1 /1 . . . | . . . | /1 /1 /1 /2 /2 /2 | /2 /2 /2 | /12 . /12

Pattern #33
Name:
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ -2 -2 -2 | . . . | /1 /1 /1 -2 -2 -2 | . . . | /1 /1 /1 . . . | /2 /2 /2 | . /12 /12

Pattern #34
Name:
Comment:

Code: Select all: -2 . . | . . . | . . . -2 . . | . . . | . . . -2 . . | . . . | . . . ------------+-------------+------------ -2 . . | . . . | . . . -2 . . | . . . | . . . -2 . . | . . . | . . . ------------+-------------+------------ . . . | . . . | /1 /1 /1 . . . | . . . | /1 /1 /1 =12 /2 /2 | /2 /2 /2 | . /12 /12

Pattern #35
Name:
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | /1 /1 /1 . . . | . . . | /1 /1 /1 /2 /2 /2 | /2 /2 /2 | =12 =12 /12

Pattern #36
Name:
Comment:

Code: Select all: . . . | . . . | . -2 . . . . | . . . | . -2 . . . . | . . . | . -2 . ------------+-------------+------------ . . . | . . . | . -2 . . . . | . . . | . -2 . . . . | . . . | . -2 . ------------+-------------+------------ . . . | . . . | /1 /1 /1 . . . | . . . | /1 /1 /1 /2 /2 /2 | /2 /2 /2 | . /1 /12

Pattern #37
Name:
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- -1 -1 -1 | . . . | . . . . . . | . . . | . . *1 . . . | /1 /1 /1 | . . .

Pattern #38
Name:
Comment:

Code: Select all: -1 . . | . . . | . . . -1 . . | . . . | . . . -1 . . | . . . | . . . ---------+----------+--------- -1 . . | . . . | . . . -1 . . | . . . | . . . -1 . . | . . . | . . . ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . *1 =1 /1 /1 | /1 /1 /1 | . . .

Pattern #39
Name:
Comment:

Code: Select all: . . . | . . . | . . -2 . . . | . . . | . . -2 . . . | . . . | . . -2 ------------+-------------+------------ . . . | . . . | . . -2 . . . | . . . | . . -2 . . . | . . . | . . -2 ------------+-------------+------------ . . . | . . . | -2 -2 -2 -2 -2 -2 | -2 -2 -2 | -2 -2 *12 /1 /1 /1 | /1 /1 /1 | -2 -2 -2

Pattern #40
Name:
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . *1 ---------+----------+--------- -1 -1 -1 | . . . | . . . -1 -1 -1 | . . . | . . . . . . | /1 /1 /1 | /1 /1 .

Pattern #41
Name:
Comment:

Code: Select all: -1 . . | . . . | . . . -1 . . | . . . | . . . -1 . . | . . . | . . . ---------+----------+--------- -1 . . | . . . | . . . -1 . . | . . . | . . . . . . | . . . | . . *1 ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . =1 /1 /1 | /1 /1 /1 | /1 /1 .

Pattern #42
Name:
Comment:

Code: Select all: . . . | . . . | -1 . . . . . | . . . | -1 . . . . . | . . . | -1 . . ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . *1 ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . /1 /1 /1 | /1 /1 /1 | =1 /1 .

Pattern #43
Name:
Comment:

Code: Select all: . . . | . . . | . . -2 . . . | . . . | . . -2 . . . | . . . | . . -2 ------------+-------------+------------ . . . | . . . | -2 -2 -2 . . . | . . . | -2 -2 -2 -2 -2 -2 | -2 -2 -2 | -2 -2 *12 ------------+-------------+------------ . . . | . . . | . . -2 . . . | . . . | . . -2 /1 /1 /1 | /1 /1 /1 | /1 /1 .

Pattern #44
Name:
Comment:

Code: Select all: . . . | . . . | -1 . . . . . | . . . | -1 . . . . . | . . . | -1 . . ---------+----------+--------- . . . | . . . | -1 . . . . . | . . . | -1 . . . . . | . . . | -1 . . ---------+----------+--------- . . . | . . . | . /1 /1 . . . | . . . | . /1 /1 . . . | . . *1 | . . .

Pattern #45
Name:
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- . . . | . . . | =1 /1 /1 . . . | . . . | /1 /1 /1 . . . | . . *1 | . . .

Pattern #46
Name:
Comment:

Code: Select all: . . . | . . -2 | . . . . . . | . . -2 | . . . . . . | . . -2 | . . . ------------+-------------+------------ . . . | . . -2 | . . . . . . | . . -2 | . . . . . . | . . -2 | . . . ------------+-------------+------------ . . . | -2 -2 -2 | /1 /1 /1 . . . | -2 -2 -2 | /1 /1 /1 -2 -2 -2 | -2 -2 *12 | -2 -2 -2

Pattern #47
Name:
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ -1 -1 -1 | -1 -1 -1 | /2 /2 /2 . . . | . . . | . /12 /12 . . . | . . . | /12 /12 /12

Pattern #48
Name: hidden pair in box (sitting in same row)
Comment: redundant, given HP in box pattern?

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | =12 =12 /12 . . . | . . . | /12 /12 /12 . . . | . . . | /12 /12 /12

Pattern #49
Name: hidden pair in box
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | =12 /12 /12 . . . | . . . | /12 =12 /12 . . . | . . . | /12 /12 /12

Pattern #50
Name:
Comment:

Code: Select all: . . . | . . . | . -2 . . . . | . . . | . -2 . . . . | . . . | . -2 . ------------+-------------+------------ . . . | . . . | . -2 . . . . | . . . | . -2 . . . . | . . . | . -2 . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . *12 *1

Pattern #51
Name: naked pair in row and in box
Comment: redundant, given NP in row and NP in box patterns?

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | -12 -12 -12 . . . | . . . | -12 -12 -12 -12 -12 -12 | -12 -12 -12 | -12 *12 *12

Pattern #52
Name:
Comment:

Code: Select all: . . . | . . -2 | . . . . . . | . . -2 | . . . . . . | . . -2 | . . . ------------+-------------+------------ . . . | . . -2 | . . . . . . | . . -2 | . . . . . . | . . -2 | . . . ------------+-------------+------------ . . . | -2 -2 -2 | . . . . . . | -2 -2 -2 | . . . . . . | . . *12 | . . *1

Pattern #53
Name: naked pair in row
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . -12 -12 -12 | -12 -12 *12 | -12 -12 *12

Pattern #54
Name:
Comment:

Code: Select all: . . . | . . . | . . -2 . . . | . . . | . . -2 . . . | . . . | . . -2 ------------+-------------+------------ . . . | . . . | . . -2 . . . | . . . | . . -2 . . . | . . . | . . -2 ------------+-------------+------------ . . . | . . . | . . . -2 -2 -2 | -2 -2 -2 | . . *12 . . . | . . . | . *1 .

Pattern #55
Name: naked pair in box
Comment:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------------+-------------+------------ . . . | . . . | -12 -12 -12 . . . | . . . | -12 -12 *12 . . . | . . . | -12 *12 -12

Website · by **denis_berthier** » Fri May 24, 2013 5:10 am

Hi Red Ed,

Red Ed wrote:One way to look at non-uniqueness solving techniques is that holes beget holes. When you eliminate a candidate (create a hole), you find you can eliminate further candidates (creating more holes).

I think you're going to have very hard time reconciling this "elimination-only" view of solving with your other requirement of "fundamentality" (for the patterns). I haven't analysed your 55 examples but the first is enough to illustrate this comment.

Red Ed wrote:Pattern #1
Name: hidden single in a row
Code: Select all
-1 . . | . . . | . . . -1 . . | . . . | . . . -1 . . | . . . | . . . ---------+----------+--------- -1 . . | . . . | . . . -1 . . | . . . | . . . -1 . . | . . . | . . . ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . =1 /1 /1 | /1 /1 /1 | /1 /1 /1

The -1 are not part of the usual "hidden single" rule. Of course, it isn't logically false to write them here, but my only point is: your "hidden single" rule can be decomposed into simpler rules (one of which, the usual "hidden single" asserting a value, is not of the elimination type).

Also, given a pattern of holes, which kind of proof do you accept for the creation of a new hole, i.e. the elimination of some candidate C? Are you checking that there is no possible truth value assignment compatible with C=True and the holes?

Red Ed wrote:(As an aside, I admit it's a bit of a double negative to talk about missing holes ...)

Actually, no:
- a candidate is a value that has not yet been proven to be impossible;
- a hole is a value that has been proven impossible.

Finally, given two cells in the same row and same block, with only candidates 1 and 2, your definition would lead to introduce a Naked-Pairs-in-a-row-and-a-block pattern, which is obviously useless if you already have Naked-Pairs-in-a-row and Naked-Pairs-in-a-block. So, if you want to eliminate redundant patterns, you somehow need a means of comparing "patterns of holes" and their sets of eliminations.

by **Red Ed** » Fri May 24, 2013 7:11 am

Hello again, Denis.

Regarding the existence of -1s in column 1: they're present because the holes-centric way of asserting a candidate (where every other in a row/col/box/cell is ruled out) is to create new holes everywhere that sees the candidate. Perhaps it doesn't look very natural. As for not writing down the -1s at r78c9: they are implied by box/line reduction (pattern 2), which is a subset of pattern 1, so are not "critical" eliminations. [edit: oh, I see you've spotted this while I was typing and updated your post; okay]

The program that works out the implied holes (the eliminations) does so by checking that there is no possible truth value assignment compatible with that eliminated candidate. The holes, plus that candidate asserted, cannot be completed to a full grid.

On your last point, concerning patterns 51 (NP in row-and-block), 53 (NP in row) and 55 (NP in block), I have to keep all three patterns because no two of them imply the other. For example, if you're in the situation of pattern 51 then, up to isomorphism in the usual way, you do not match patterns 53 or 55. This is definitely a weakness of the approach and is something I'll need to think about a bit more.

Website · by **denis_berthier** » Fri May 24, 2013 1:05 pm

Red Ed wrote:The program that works out the implied holes (the eliminations) does so by checking that there is no possible truth value assignment compatible with that eliminated candidate. The holes, plus that candidate asserted, cannot be completed to a full grid.

As I understand it, you consider all the cells in the grid, not only those included in the pattern or directly related to it. If this is the case, you can have very indirect implications that could be very hard to explain. Is this right?

Red Ed wrote:On your last point, concerning patterns 51 (NP in row-and-block), 53 (NP in row) and 55 (NP in block), I have to keep all three patterns because no two of them imply the other. For example, if you're in the situation of pattern 51 then, up to isomorphism in the usual way, you do not match patterns 53 or 55.

I hadn't checked your list for these patterns, but this is exactly what I meant.
But why don't they match?
[Sequel edited]
There are two reasons:
- because the conclusions don't, i.e. because you consider the whole set of (critical) eliminations (the -1's) as part of the pattern; considering that P => (not C1 and not C2 ...) is equivalent to (P => not C1) and (P => not C2) ..., this may finally be only a superficial problem, but all depends on the reasons why you want to state all the critical eliminations;
- because the condition parts don't match; the main reason in the present case is the "up to isomorphism" condition; this obliges you to introduce irrelevant differences among patterns, e.g. (in the same row and in the same block) vs (in the same row and not in the same block); and the more complex the patterns will get, the more such differences you'll have to consider; another way of seeing this is, your "language" for describing patterns is too weak.

by **Red Ed** » Fri May 24, 2013 7:13 pm

denis_berthier wrote:you can have very indirect implications that could be very hard to explain. Is this right?

For bigger patterns, yes, that's probably true. I'm not really worried about that. I just want a way of "reinventing" the well known simple techniques automatically. So far, so good, but I'm producing a lot of unnecessary patterns besides the good stuff at the moment.

... and the more complex the patterns will get, the more such differences you'll have to consider; another way of seeing this is, your "language" for describing patterns is too weak.

The addition of more axioms, i.e. more rules to reduce the set of 55 down to something more manageable, will go some way to fixing that.

Another tack would be to continue to present the patterns pictorially, but to think of them in terms of nodes-and-edges graphs, with axioms concerning the use of sub-patterns translating to statements about subgraphs. I will put that idea aside for a bit, because I think there's still value to be had from considering what other axioms would help with the current framework.

For example, axiom 2: an elimination is not critical if it can be accomplished by a sequence of applications of sub-patterns of the original. (In a graph-theoretic setting, I think this would address your criticism of patterns 51/53/55.)

by **eleven** » Sat May 25, 2013 9:58 am

Red Ed wrote:For example, axiom 2: an elimination is not critical if it can be accomplished by a sequence of applications of sub-patterns of the original. (In a graph-theoretic setting, I think this would address your criticism of patterns 51/53/55.)

Yes, this was my first thought, when i looked through them. I guess, it would leave these patterns:
1,3 hidden single row/box
2,4 boxline/pointing
5 naked single
7,12,18 (grouped) kite/skyscraper
14,16 x-wing
24,26,35,48,49 hidden pair
51,53,55 naked pair
[edited some numbers]

by **Red Ed** » Sat May 25, 2013 12:33 pm

More generally, I should probably say an elimination isn't critical if it can be accomplished by a sequence of "smaller" patterns. "Smaller" could be defined in a number of different ways; it will take me a while to try them out and identify cases where the choice of definition makes a difference.

Update: I've been pm'd a nice example of where the definition of "smaller" matters.

Red Ed wrote:
paraphrasing, pm sender wrote:What about ALS-XZ?
Code: Select all
-ABC *ABC *ABC | -ABC *AB -ABC | -ABC -ABC -ABC -C -C -C | . . . | . . . -C -C -C | . . . | . . .

Very nice example. The HBH view of this would be that the pattern is minimal for elimination r23 candidates but not for the r1 candidates. The r1 candidates are eliminated by the "plain naked triple" pattern ( . *ABC *ABC | . *ABC . | . . . ), which is a subset of your ALS-XZ one ( . *ABC *ABC | . *AB . | . . . ). After application of the plain naked triple pattern, you can use box/line reduction to wipe out the remaining r23 candidates. PS: recall in HBH notation that *X means those are the only candidates in that cell.

If you view box/line reduction as a "smaller" pattern than ALS-XZ (which is debatable) then my Axiom 2 would reject ALS-XZ as invalid (or at least not "fundamental"), telling you to use plain naked triple + box/line reduction to obtain the same result. If you view box/line reduction as not "smaller" then you are allowed to use ALS-XZ directly. I don't yet have a strong reason to prefer one way to the other, i.e. to regard this specific case of ALS-XZ as a fundamental pattern or not.

by **Red Ed** » Wed May 29, 2013 11:48 am

I've got the computer slowly grinding through a version of axiom 2. It's got up to and including pattern 12 so far (it's not the best algorithm ...) and it appears to be doing an intuitively pleasing job of eliminating "redundant" patterns.

What's the usual name for pattern 12? To save you scrolling, here it is again:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- -1 . . | . . . | . . . -1 . . | . . . | . . . . . . | . /1 /1 | /1 /1 /1 ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . /1 /1 | . /1 /1 | /1 /1 /1

Thanks.

by **eleven** » Wed May 29, 2013 12:43 pm

Most common is "finned x-wing" (with the candidates in r6c23 being fins).
It is also call grouped skyscraper (with the strong link 1r6c123=1r6c4 including the grouped cells r6c123) or more general grouped turbot fish (including kites too).

by **Pat** » Wed May 29, 2013 12:46 pm

Red Ed wrote:What's the usual name for pattern 12?
Code: Select all
. . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- -1 . . | . . . | . . . -1 . . | . . . | . . . . . . | . /1 /1 | /1 /1 /1 ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . /1 /1 | . /1 /1 | /1 /1 /1

by **Red Ed** » Wed May 29, 2013 2:12 pm

Thanks, both. How about pattern 18?

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . ---------+----------+--------- . . . | . . . | . . . . . . | . . . | . . . . /1 /1 | /1 /1 /1 | . /1 /1 ---------+----------+--------- -1 . . | . . . | . . . . . . | . . . | . /1 /1 . . . | . . . | . /1 /1

by **StrmCkr** » Wed May 29, 2013 4:18 pm

Empty rectangle is patter n 18
Or franken x wing

by **Red Ed** » Wed May 29, 2013 9:22 pm

Thanks, StrmCkr. I've updated the second post accordingly.

A quick progress update. Axiom 2a was doing a good job of boiling-down the list of 55 to patterns that I think most of us could agree were "fundamental" in some vague sense. The stand-out cases that need fixing are the pairs-in-a-box-and-row examples that Denis pointed out, for which I propose to use some sort of x-sees-y subgraph check; here's hoping it doesn't wreck the good work of Axiom 2a. Subgraph isomorphism is a hard problem, though, so this will take some time. I also need to re-run the original program that implemented Axiom 1, as it turns out that the way I'm using attractivechaos's kudoku solver causes it to break in certain circumstances -- which I have now fixed.

by **eleven** » Wed May 29, 2013 9:39 pm

Red Ed wrote:Thanks, both. How about pattern 18?

Alternatively grouped kite (or turbot fish).
You didn't ask for pattern 7: empty rectangle or grouped kite again.

The New Sudoku Players' Forum

Holes beget holes

Holes beget holes

Re: Holes beget holes

Re: Holes beget holes

Re: Holes beget holes

Re: Holes beget holes

Re: Holes beget holes

Re: Holes beget holes

Re: Holes beget holes

Re: Holes beget holes

Re: Holes beget holes

Re: Holes beget holes

Re: Holes beget holes

Re: Holes beget holes

Re: Holes beget holes