Sudoku Programmers :: View topic

FAQ

Memberlist

Usergroups

Profile

Hidden Patterns

Sudoku Programmers Forum Index -> Solving sudoku

View previous topic :: View next topic

Author

Message

Ocean

Joined: 29 Aug 2005

Posts: 15

Items

Posted: Fri Sep 16, 2005 8:29 pm Post subject: Hidden Patterns

I don't know if these patterns (of candidates) have been described earlier.
First an example:

Code:

Example: Reduces to:
*-----------------* *-----------------*
|. . 1|1 . .|1 1 1| |. . 1|1 . .|1 1 1|
|. . 1|1 . .|1 1 1| |. . 1|1 . .|1 1 1|
|1 1 1|1 1 1|1 1 1| |1 1 .|. 1 1|. . .|
|-----+-----+-----| |-----+-----+-----|
!1 1 1|1 1 1|1 1 1| |1 1 .|. 1 1|. . .|
|. . 1|1 . .|1 1 1| |. . 1|1 . .|1 1 1|
|. . 1|1 . .|1 1 1| |. . 1|1 . .|1 1 1|
|-----+-----+-----| |-----+-----+-----|
|1 1 1|1 1 1|1 1 1| |1 1 .|. 1 1|1 1 1|
|1 1 1|1 1 1|1 1 1| |1 1 .|. 1 1|1 1 1|
|1 1 1|1 1 1|1 1 1| |1 1 .|. 1 1|1 1 1|
*-----------------* *-----------------*

Proof (by implication chain):
r3c3=1 => r3c5<>1 & r3c6<>1 & r5c3<>1 & r6c3<>1 => (r1c4=1 or r2c4=1) & (r4c1=1 or r4c2=1) => r5c4<>1 & r6c4<>1 & r4c5<>1 & r4c6<>1 => No cells in box 5 can be 1.
The proofs for r3c4<>1, r4c3<>1, r4c4<>1 are similar (symmetric).

r7c3=1 => r1c3<>1 & r2c3<>1 & r5c3<>1 & r6c3<>1 => (r3c1=1 or r3c2=1) & (r4c1=1 or r4c2=1)
=> r3c5<>1 & r3c6<>1 & r4c5<>1 & r4c6<>1 => (r1c4=1 or r2c4=1) => r5c4<>1 & r6c4<>1 => No cells in box 5 can be 1.
The proofs for r8c3<>1, r9c3<>1, r7c4<>1, r8c4<>1, r9c4<>1, r3c7<>1, r3c8<>1, r3c9<>1, r4c7<>1, r4c8<>1, r4c9<>1 are similar (symmetric).

Personally I find it easier to describe (and discover) these kinds of patterns if we choose a different notation - namely looking at the Hidden Pattern, the pattern of cells that are 'empty' (not having candidate x).

Code:

Hidden Pattern:
*-----------------*
|0 0 .|. 0 0|. . .|
|0 0 .|. 0 0|. . .|
|. . E|E . .|E E E|
|-----+-----+-----|
!. . E|E . .|E E E|
|0 0 .|. 0 0|. . .|
|0 0 .|. 0 0|. . .|
|-----+-----+-----|
|. . E|E . .|. . .|
|. . E|E . .|. . .|
|. . E|E . .|. . .|
*-----------------*

Where '0' means there is no candidate x in this cell, '.' means the cell may or may not have a candidate x, and 'E' means that a candidate x in this cell can be removed (excluded).

Standard permutations give rise to a total of 729 'new' patterns (see the example below). We can also find other kind of variations different from the basic form above.

Code:

Permutation (1 of total 729):
*-----------------*
|. 0 0|. . .|0 . 0|
|. 0 0|. . .|0 . 0|
|E . .|E E E|. E .|
|-----+-----+-----|
!. 0 0|. . .|0 . 0|
|E . .|E E E|. E .|
|. 0 0|. . .|0 . 0|
|-----+-----+-----|
|E . .|. . .|. E .|
|E . .|. . .|. E .|
|E . .|. . .|. E .|
*-----------------*

Variant - has 5832 permutations included transposition:
*-----------------*
|0 0 .|. 0 .|. . .|
|0 0 .|. 0 .|. . .|
|. . E|E . .|E E E|
|-----+-----+-----|
!. . E|E . .|E E E|
|0 0 .|. 0 .|. . .|
|0 0 .|. 0 .|. . .|
|-----+-----+-----|
|. . E|. 0 .|. . .|
|. . E|. 0 .|. . .|
|. . E|. 0 .|. . .|
*-----------------*

Variant (or even more basic form) - 2 from 2916 different permutations:
*-----------------* *-----------------*
|0 0 .|. 0 0|. . .| |. . .|. . .|0 . 0|
|0 0 .|. 0 0|. . .| |. . .|. . .|0 . 0|
|. . .|. . .|. . .| |E . .|. . .|. . .|
|-----+-----+-----| |-----+-----+-----|
!. . .|E . .|. . .| |. . .|. . .|. . .|
|0 0 .|. . .|. . .| |. . .|. . .|. . .|
|0 0 .|. . .|. . .| |. . .|. . .|. . .|
|-----+-----+-----| |-----+-----+-----|
|. . .|. . .|. . .| |. 0 0|. . .|0 . 0|
|. . .|. . .|. . .| |. . .|. . .|. . .|
|. . .|. . .|. . .| |. 0 0|. . .|0 . 0|
*-----------------* *-----------------*

Proof (of 'more basic form'):
r4c4=1 => r1c4<>1 & r2c4<>1 & r3c4<>1 & r4c1<>1 & r4c2<>1 & r4c3<>1 => (r3c5=1 or r3c6=1) & (r5c3=1 or r6c3=1) => r1c3<>1 & r2c3<>1 & r3c1<>1 & r3c2<>1 => No cells in box 1 can be 1.

Direct proof of the permuted variant is similar.
General proof of all permutations should be obvious.

Some classical patterns can also be expressed in 'Hidden' notation:

Code:

Locked Candidates: Swordfish:
*-----------------* *-----------------*
|0 0 0|. . .|. . .| |. 0 0|. 0 0|. 0 0|
|0 0 0|. . .|. . .| |E . .|E . .|E . .|
|. . .|E E E|E E E| |E . .|E . .|E . .|
|-----+-----+-----| |-----+-----+-----|
!. . .|. . .|. . .| |. 0 0|. 0 0|. 0 0|
|. . .|. . .|. . .| |E . .|E . .|E . .|
|. . .|. . .|. . .| |E . .|E . .|E . .|
|-----+-----+-----| |-----+-----+-----|
|. . .|. . .|. . .| |. 0 0|. 0 0|. 0 0|
|. . .|. . .|. . .| |E . .|E . .|E . .|
|. . .|. . .|. . .| |E . .|E . .|E . .|
*-----------------* *-----------------*

Lummox JR

Joined: 07 Sep 2005

Posts: 202

Items

Posted: Sat Sep 17, 2005 4:40 pm Post subject:

I had trouble following your implication chain notation until I simply tried out the example myself. Here I present the same proof in slightly more basic language:

(3,3)=1 would clear r3 and c3 of other candidates, creating pointing pairs in c4/b2 and r4/b4, which completely clears b5 of candidates, hence a contradiction. Symmetricality is easy to prove because the same layout exists relative to (4,3), (3,4), and (4,4); in each case you'd get pointing pairs in two boxes eliminating all the candidates in the fourth box.

Code:

*-----------------*
|. . .|1 . .|1 1 1|
|. . .|1 . .|1 1 1|
|. . *|. . .|. . .|
|-----+-----+-----|
!1 1 .|. . .|. . .|
|. . .|. . .|1 1 1|
|. . .|. . .|1 1 1|
|-----+-----+-----|
|1 1 .|1 1 1|1 1 1|
|1 1 .|1 1 1|1 1 1|
|1 1 .|1 1 1|1 1 1|
*-----------------*

(3,7)=1 would clear c3, r7, and b7 of other candidates, creating pointing pairs in r3/b1 and r4/b4. This in turn creates pointing pairs in c4/b2 and c4/b5. Since both b2 and b5 must have a candidate in c4, this is a contradiction. The same proof applies to all (3,7-9), and with the symmetry described above also to (4,7-9), (7-9,3), and (7-9,4). Ingenious.

Code:

*-----------------*
|. . .|1 . .|1 1 1|
|. . .|1 . .|1 1 1|
|1 1 .|. . .|1 1 1|
|-----+-----+-----|
!1 1 .|. . .|1 1 1|
|. . .|1 . .|1 1 1|
|. . .|1 . .|1 1 1|
|-----+-----+-----|
|. . *|. . .|. . .|
|. . .|1 1 1|1 1 1|
|. . .|1 1 1|1 1 1|
*-----------------*

One question I have regarding permutations of this 4x4 empty pattern: Is it only applicable where each of 4 boxes has 2 of the columns and 2 of the rows? That would certainly explain how you came up with 729 permutations but no more.

Interestingly once the eliminations are done, You should find that in each of the 2x2 sections of candidates that are left, the digit can appear only once in any of them. For example, if (1,3)=1, then r3 is cleared leaving a pointing pair in c4/b2, which leaves a pointing pair in r4/b5, which eliminates (2,4).

This is a pretty fascinating technique. I vote we call this pattern "hidden corners", since it's based on the inner corners of a 6x6 cross in 4 boxes. This approach does raise the question, though, of what other hidden patterns may be revealed. I did try seeing if hidden corners could occur more than once for the same digit, but it's pretty easy to prove that's impossible.

Ruud
Site Admin

Joined: 17 Sep 2005

Posts: 708

Location: Netherlands

Items

Posted: Sat Sep 17, 2005 11:59 pm Post subject:

Please have a look at my topic on templates. Your examples were immediately recognized when I entered them in my program. However, do not expect to encounter these patterns in your average Sudoku puzzle. They seem pretty rare to me, unless one puts them into the puzzle deliberately.

Ocean

Joined: 29 Aug 2005

Posts: 15

Items

Posted: Sun Sep 18, 2005 6:47 pm Post subject:

Lummox JR wrote:

Thank you for giving the proofs a much more readable form!

The total number of permissable permutations for any pattern is of course 6x6x6x6x6x6x6x6=1669373, and an additional factor 2 for transposition. Because of the high degree of symmetry (in the first example), only 729 of these permuted patterns are distinct (3x3x3x3x3x3=729). The other examples have less symmetry and therefore more distinct permutations.

The actual number of permutations is not so important in itself, except telling that the same basic 'essential' pattern can show up in several differnt forms, and therefore may be hard to recognize.

Here is one permutation, where the pattern is a bit distorted, and therefore harder to spot.

Code:

Example(permutation): Reduces to: Pattern:
*-----------------* *-----------------* *-----------------*
|1 1 1|1 1 1|1 1 1| |. 1 1|1 1 1|1 . 1| |E . .|. . .|. E .|
|1 1 1|1 1 1|1 1 1| |. 1 1|1 1 1|1 . 1| |E . .|. . .|. E .|
|1 1 1|1 1 1|1 1 1| |. 1 1|1 1 1|1 . 1| |E . .|. . .|. E .|
|-----+-----+-----| |-----+-----+-----| |-----+-----+-----|
!1 1 1|1 1 1|1 1 1| |. 1 1|. . .|1 . 1| |E . .|E E E|. E .|
|1 . .|1 1 1|. 1 .| |1 . .|1 1 1|. 1 .| |. 0 0|. . .|0 . 0|
|1 . .|1 1 1|. 1 .| |1 . .|1 1 1|. 1 .| |. 0 0|. . .|0 . 0|
|-----+-----+-----| |-----+-----+-----| |-----+-----+-----|
|1 . .|1 1 1|. 1 .| |1 . .|1 1 1|. 1 .| |. 0 0|. . .|0 . 0|
|1 . .|1 1 1|. 1 .| |1 . .|1 1 1|. 1 .| |. 0 0|. . .|0 . 0|
|1 1 1|1 1 1|1 1 1| |. 1 1|. . .|1 . 1| |E . .|E E E|. E .|
*-----------------* *-----------------* *-----------------*

Ocean

Joined: 29 Aug 2005

Posts: 15

Items

Posted: Sun Sep 18, 2005 7:13 pm Post subject:

Ruud wrote:

Please have a look at my topic on templates.

Your examples were immediately recognized when I entered them in my program. However, do not expect to encounter these patterns in your average Sudoku puzzle. They seem pretty rare to me, unless one puts them into the puzzle deliberately.

Your technique is exactly the same that I used to explore patterns. Here is my algorithm:

Code:

Algorithm:

1. Initializing. There are 46656 possible ways to place a candidate x in a sudoku grid. These can be represented as an int iarr[46656] of 9-digit numbers (147258369, 147258396...), which is initialized once and saved for later use.

2. Filter a candidate:
for (i=0;i<46656;i++) { f=1; k=iarr[i];
for (j=9;j>0;j--) {if (current.cand[k-(10*(k/10))][j]!=1) f=0; k=k/10;}
if (f){k=iarr[i]; for (j=9;j>0;j--) {next.cand[k-(10*(k/10))][j]=1; k=k/10;}}
}

For effective use in solvers, it's probably faster to operate on a linked list of pointers to the remaining possible configurations, but I have not implemented this in my analyzer.

This fairly simple algorithm covers all possible two-dimensional 'hidden patterns' (also including 'swordfish', 'turbot fish', 'coloring' and others). When such an algorithm is included in solvers, it can show logical solution paths that are 'easier' to understand (and find) than the general forcing chains. The forcing chains are of course more general, and will solve more puzzles.

As for the 'rare' patterns, I have no idea yet of how rare they are. I agree that each one will occur very seldom, but if you count all variants with permutations, there might be some 'relevant' cases. That is, cases where 'basic' methods fail, and recognizing the 'unknown hidden patterns' leads to quicker solutions than more advanced methods.

Nick70

Joined: 08 Jun 2005

Posts: 160

Items

Posted: Thu Nov 24, 2005 12:27 pm Post subject: Re: Hidden Patterns

Ocean wrote:

Code:

Variant (or even more basic form) - 2 from 2916 different permutations:
*-----------------* *-----------------*
|0 0 .|. 0 0|. . .| |. . .|. . .|0 . 0|
|0 0 .|. 0 0|. . .| |. . .|. . .|0 . 0|
|. . .|. . .|. . .| |E . .|. . .|. . .|
|-----+-----+-----| |-----+-----+-----|
!. . .|E . .|. . .| |. . .|. . .|. . .|
|0 0 .|. . .|. . .| |. . .|. . .|. . .|
|0 0 .|. . .|. . .| |. . .|. . .|. . .|
|-----+-----+-----| |-----+-----+-----|
|. . .|. . .|. . .| |. 0 0|. . .|0 . 0|
|. . .|. . .|. . .| |. . .|. . .|. . .|
|. . .|. . .|. . .| |. 0 0|. . .|0 . 0|
*-----------------* *-----------------*

I had missed this thread previously.
Interestingly, I had examined the same pattern while experimenting with the BxRx notation.

I had done some research on my database of problems, and while the pattern involving 4 boxes is extremely rare, this basic form only involving 3 boxes (with a single exclusion in the 4th) can be found more often. The pattern is also quite easy to see.

The following example requires application of this technique a couple of times, and nothing else more advanced than locked candidates:

Code:

...1....2
.1..5....
..7...6..
5....2...
.4..6..7.
...5....1
..2...3..
....9..8.
3....1...

rkral

Joined: 21 Oct 2005

Posts: 233

Items

Posted: Sun Nov 27, 2005 11:01 am Post subject:

Ocean wrote:

The total number of permissable permutations for any pattern is of course 6x6x6x6x6x6x6x6=1669373, and an additional factor 2 for transposition.

But 6^8=1679616 and the difference doesn't look like a typical typo.

There are six permutations of the towers, six permutations of the floors, and six permutations of the rows within each tower and six permutations of the columns within each tower ... and I don't see where distinctness would yield any exclusions. So what am I missing?

rkral

Joined: 21 Oct 2005

Posts: 233

Items

Posted: Fri Oct 27, 2006 7:49 pm Post subject:

Ocean wrote:

Your technique is exactly the same that I used to explore patterns. Here is my algorithm:

Code:

Algorithm:

1. Initializing. There are 46656 possible ways to place a candidate x in a sudoku grid. These can be represented as an int iarr[46656] of 9-digit numbers (147258369, 147258396...), which is initialized once and saved for later use.

2. Filter a candidate:
for (i=0;i<46656>0;j--) {if (current.cand[k-(10*(k/10))][j]!=1) f=0; k=k/10;}
if (f){k=iarr[i]; for (j=9;j>0;j--) {next.cand[k-(10*(k/10))][j]=1; k=k/10;}}
}

I know this is ancient but ... a few words to help understand the use of structures "current" and "next" would be appreciated.

TIA, Ron

daj95376

Joined: 05 Feb 2006

Posts: 349

Items

Posted: Sat Oct 28, 2006 6:35 pm Post subject:

Ron, FYI: Your copy of Part (2) of the original algorithm is incorrect. It appears that a chunk of code is missing between the first for loop and the second for loop -- inclusive.

Ocean

Joined: 29 Aug 2005

Posts: 15

Items

Posted: Sun Oct 29, 2006 5:09 am Post subject: Hidden Patterns

rkral wrote:

I know this is ancient but ... a few words to help understand the use of structures "current" and "next" would be appreciated.

TIA, Ron

The algorithm is from a pattern analyzer, taking as input a current candidate set, and generating a next candidate set for output. As this example (slightly modified from a previous, one-year-old post):

Code:

"current" set: "next" (reduced) set: Pattern (bbbb\rrcc):
*-----------------* *-----------------* *-----------------*
|1 1 1|1 1 1|1 1 1| |. 1 1|1 1 1|1 . 1| |* . .|. . .|. * .|
|1 1 1|1 1 1|1 1 1| |. 1 1|1 1 1|1 . 1| |* . .|. . .|. * .|
|1 1 1|1 1 1|1 1 1| |. 1 1|1 1 1|1 . 1| |* . .|. . .|. * .|
|-----+-----+-----| |-----+-----+-----| |-----+-----+-----|
!1 1 1|1 1 1|1 1 1| |. 1 1|. . .|1 . 1| |* X X|* * *|X * X|
|1 . .|1 1 1|. 1 .| |1 . .|1 1 1|. 1 .| |X / /|. . .|/ X /|
|1 . .|1 1 1|. 1 .| |1 . .|1 1 1|. 1 .| |X / /|. . .|/ X /|
|-----+-----+-----| |-----+-----+-----| |-----+-----+-----|
|1 . .|1 1 1|. 1 .| |1 . .|1 1 1|. 1 .| |X / /|. . .|/ X /|
|1 . .|1 1 1|. 1 .| |1 . .|1 1 1|. 1 .| |X / /|. . .|/ X /|
|1 1 1|1 1 1|1 1 1| |. 1 1|. . .|1 . 1| |* X X|* * *|X * X|
*-----------------* *-----------------* *-----------------*

Key: X = candidate (may be missing)
/ = no candidate
* = potential exclusion

The data structure is a simple int cand[10][10] array. A solver must obviously loop over all digits (there are several ways to to this). It should also optimize the loop drastically, making it a lot faster but more complicated. The Filter algorithm above simply checks, for all "templates", whether the template is fully contained in the "current" set (input), and for those that are, assures that all candidate positions in those templates also are included in the "next" set (output). Primitive but 'foolproof'.

rkral wrote:

But 6^8=1679616 and the difference doesn't look like a typical typo.

Thanks. Can not remember the origin of this "typo". Probably misread or picked a wrong number from some handwritten notes.

Nick70 wrote:

The following example requires application of this technique a couple of times, and nothing else more advanced than locked candidates:

Code:

...1....2
.1..5....
..7...6..
5....2...
.4..6..7.
...5....1
..2...3..
....9..8.
3....1...

Great example! (It's been more than a year since I checked this thread. Sorry for the late response!)

Code:

*-----------------------------------------------------------*
| 4689 689 489 | 1 3 7 |-489 5 2 |
| 2 #1 #3 | 489 5 6 | 7 49 489 |
| 489 #5 #7 | 489 2 48 | 6 1 3 |
|-------------------+-------------------+-------------------|
| 5 3 89 | 7 1 2 | 489 469 689 |
| 89 #4 #1 | 3 6 89 | 2 #7 #5 |
| 7 #2 #6 | 5 48 489 | 89 #3 #1 |
|-------------------+-------------------+-------------------|
| 1 6789 2 | 468 478 5 | 3 469 4679 |
| 46 67 5 | 2 9 3 | 1 8 467 |
| 3 6789 489 | 468 478 1 | 5 2 4679 |
*-----------------------------------------------------------*

*-----------------------------------------------------------*
| 4689 689 489 | 1 3 7 | 489 5 2 |
| 2 #1 #3 | 489 5 6 |#7 #49 489 |
| 489 #5 #7 | 489 2 48 |#6 #1 3 |
|-------------------+-------------------+-------------------|
| 5 3 89 | 7 1 2 | 489 469 -689 |
| 89 #4 #1 | 3 6 89 | 2 7 5 |
| 7 #2 #6 | 5 48 489 | 89 3 1 |
|-------------------+-------------------+-------------------|
| 1 6789 2 | 468 478 5 | 3 469 4679 |
| 46 67 5 | 2 9 3 | 1 8 467 |
| 3 6789 489 | 468 478 1 | 5 2 4679 |
*-----------------------------------------------------------*

Cell pattern of holes (missing '8') is marked '#'. Elimination of '8' is marked '-'. Choose any of the two eliminations, and the puzzle is solved.

Display posts from previous:

	Sudoku Programmers Forum Index -> Solving sudoku	All times are GMT
Page 1 of 1

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum