The New Sudoku Players' Forum

[Ruud]

I would like to introduce a related concept: Twins.

Recently, I have been working on a method to fingerprint Sudoku puzzles. Although canonicalization can find puzzles that are mathematically equivalent, it is a slow process, not suited for scanning large collections of puzzles. Instead, I am taking a fingerprint of a puzzle, which does not identify puzzles with 100% certainty, but it can be used as a triage before using the time-consuming canonicalization routines.

Fingerprinting only examines the candidate space in the initial grid:

For each digit:
- Count the number of eliminated candidates
- Count the number of surplus eliminations for all candidates (when a cell can see multiple peers with the same digit and/or another digit is placed in the cell as a given)
Sort these counts in descending order
Also count the number of cells with 1 candidate, 2 candidates, ..., 9 candidates left.

I've used Gordon's collection of minimum Sudokus and it contains 474 twins and 4 triplets. (2 or 3 puzzles with the same fingerprint)

Here are 2 puzzles with the fingerprint 57:17,49:6,48:7,48:7,48:7,45:10,43:12,33:3,30:6,1:1:7:13:22:15:5:0:0.

Code: Select all

5 . .|. 3 .|. 1 .    6 . .|. 3 .|. 1 .
. . 9|8 . .|. . .    . . 5|9 . .|. . .
. . .|. . .|. . .    . . .|. . .|. . .
-----+-----+-----    -----+-----+-----
1 . .|. . .|. 3 .    1 . .|. . .|. 3 .
. . .|2 . 8|. . .    . . .|2 . 9|. . .
. . .|6 . .|. . .    . . .|7 . .|. . .
-----+-----+-----    -----+-----+-----
6 4 .|. 7 .|. . .    7 4 .|. 8 .|. . .
. . .|. . .|9 . 2    . . .|. . .|2 . 5
7 . .|. . .|8 . .    8 . .|. . .|9 . .

The distribution of the candidates is the same, but after relabeling the second puzzle, the true similarities are revealed:

Code: Select all

5 . .|. 3 .|. 1 .    5 . .|. 3 .|. 1 .
. . 9|8 . .|. . .    . . 9|8 . .|. . .
. . .|. . .|. . .    . . .|. . .|. . .
-----+-----+-----    -----+-----+-----
1 . .|. . .|. 3 .    1 . .|. . .|. 3 .
. . .|2 . 8|. . .    . . .|2 . 8|. . .
. . .|6 . .|. . .    . . .|6 . .|. . .
-----+-----+-----    -----+-----+-----
6 4 .|. 7 .|. . .    6 4 .|. 7 .|. . .
. . .|. . .|9 . 2    . . .|. . .|2 . 9
7 . .|. . .|8 . .    7 . .|. . .|8 . .

The only difference is that 2 and 9 are swapped in row 7.

The solutions are also strikingly similar:

Code: Select all

5 2 6|7 3 9|4 1 8    5 2 6|7 3 9|4 1 8
4 1 9|8 6 5|7 2 3    4 1 9|8 6 5|3 2 7
8 3 7|1 2 4|6 9 5    8 3 7|1 2 4|5 9 6
-----+-----+-----    -----+-----+-----
1 8 4|5 9 7|2 3 6    1 8 4|5 9 7|6 3 2
9 6 3|2 1 8|5 4 7    9 6 3|2 1 8|7 4 5
2 7 5|6 4 3|1 8 9    2 7 5|6 4 3|9 8 1
-----+-----+-----    -----+-----+-----
6 4 8|9 7 2|3 5 1    6 4 8|9 7 2|1 5 3
3 5 1|4 8 6|9 7 2    3 5 1|4 8 6|2 7 9
7 9 2|3 5 1|8 6 4    7 9 2|3 5 1|8 6 4

Only r2345678c7 and r2345678c9 have been swapped.

The solving paths are different because the second puzzle has an extra hidden pair (2,8) in row 1.

It would be interesting to study twins a little further. What would be the upper and lower boundaries of changed digits in the solution when we swap 2 givens? Would it be possible to find a twin that not only has the same fingerprint, but also has exactly the same solving path?
What is the maximum difference between 2 puzzles with the same fingerprint, in terms of swapped digits and/or different placements?

I will try to find some answers from the remaining twins in Gordon's collection.

Ruud

[tarek]

Recently, I have been working on a method to fingerprint Sudoku puzzles.

Interesting Ruud, I think this has more yield in easier puzzles....The Ultra hard puzzles would have more chance to end up with the same print.

I guess that you've already tried to add hidden singles &/or box-line eliminations to see how more effective would it be in narrowing down the SUSPECTS (I'm not sure how much slower the search would be though )

tarek

[Ocean]

I The solutions are also strikingly similar:

Code: Select all

5 2 6|7 3 9|4 1 8    5 2 6|7 3 9|4 1 8
4 1 9|8 6 5|7 2 3    4 1 9|8 6 5|3 2 7
8 3 7|1 2 4|6 9 5    8 3 7|1 2 4|5 9 6
-----+-----+-----    -----+-----+-----
1 8 4|5 9 7|2 3 6    1 8 4|5 9 7|6 3 2
9 6 3|2 1 8|5 4 7    9 6 3|2 1 8|7 4 5
2 7 5|6 4 3|1 8 9    2 7 5|6 4 3|9 8 1
-----+-----+-----    -----+-----+-----
6 4 8|9 7 2|3 5 1    6 4 8|9 7 2|1 5 3
3 5 1|4 8 6|9 7 2    3 5 1|4 8 6|2 7 9
7 9 2|3 5 1|8 6 4    7 9 2|3 5 1|8 6 4

Only r2345678c7 and r2345678c9 have been swapped.

Maybe we could call these solution grids for sister grids: They only differ by a permuted unavoidable set.

Better seen if we write the two grids as:

Code: Select all

5 2 6|7 3 9|4 1 8    5 2 6|7 3 9|8 1 4
4 1 9|8 6 5|7 2 3    4 1 9|8 6 5|7 2 3
8 3 7|1 2 4|6 9 5    8 3 7|1 2 4|6 9 5
-----+-----+-----    -----+-----+-----
1 8 4|5 9 7|2 3 6    1 8 4|5 9 7|2 3 6
9 6 3|2 1 8|5 4 7    9 6 3|2 1 8|5 4 7
2 7 5|6 4 3|1 8 9    2 7 5|6 4 3|1 8 9
-----+-----+-----    -----+-----+-----
6 4 8|9 7 2|3 5 1    6 4 8|9 7 2|3 5 1
3 5 1|4 8 6|9 7 2    3 5 1|4 8 6|9 7 2
7 9 2|3 5 1|8 6 4    7 9 2|3 5 1|4 6 8

where r19c79 is the unavoidable set.

The corresponding puzzles:

5 . .|. 3 .|. 1 .    5 . .|. 3 .|. 1 .
. . 9|8 . .|. . .    . . 9|8 . .|. . .
. . .|. . .|. . .    . . .|. . .|. . .
-----+-----+-----    -----+-----+-----
1 . .|. . .|. 3 .    1 . .|. . .|. 3 .
. . .|2 . 8|. . .    . . .|2 . 8|. . .
. . .|6 . .|. . .    . . .|6 . .|. . .
-----+-----+-----    -----+-----+-----
6 4 .|. 7 .|. . .    6 4 .|. 7 .|. . .
. . .|. . .|9 . 2    . . .|. . .|9 . 2
7 . .|. . .|8 . .    7 . .|. . .|. . 8


Every grid has of course lots of sisters, and they could be classified according to the size and nature of their corresponding unavoidable sets.

[gsf]

I would like to introduce a related concept: Twins.

Recently, I have been working on a method to fingerprint Sudoku puzzles.

look at papy's posts -- he posted some sudoku17 properties along these lines

Although canonicalization can find puzzles that are mathematically equivalent, it is a slow process, not suited for scanning large collections of puzzles.

not true
gordon's 36628 sudoku17 solve in 6.35s, solve+canonicalize in 9.95s @ 3.2Ghz
so, depending on your algorithms and/or implementation, canonicalization can take ~1/2 the time of solving
and it does not seem to be sensitive to puzzle difficulty
ravel's 289 hardest solve in 0.63s, solve+canonicalize in 0.66s @ 992Mhz
(this shows that solving is sensitive to puzzle difficulty)

however, like you note, properties may provide a way to compare similar (but not equivalent) puzzles

[gsf]

In the Gordon's list for instance, this % is around 60 %. (I made a calculation on 1000 randomly picked puzzles).

there are 22396 puzzles out of the 36628 gordon's 17's with mutable clues -- 61%
it took 33min @ 3.2Ghz to count all of the mutable clues/solutions
these characterizations are getting harder to compute

here are the two with 7 mutable clues
all the rest had less
the pm grid shows the mutable clues and values

Code: Select all

#  4120 7 14 2-2-2-2-2-2-2
....4.61.2.53...........8..4......72.6..1.............3..5.2......7..1...........

 .  .  . | . 49  . | .  .  .
 .  . 59 |39  .  . | .  .  .
 .  .  . | .  .  . |89  .  .
---------+---------+---------
49  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
---------+---------+---------
39  .  . |59  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .

# 16875 7 14 2-2-2-2-2-2-2
.3.7.1...2.....3.....6.......78......4....2......4.5..5...2......6....7........1.

 . 39  . | .  . 19 | .  .  .
 .  .  . | .  .  . |39  .  .
 .  .  . | .  .  . | .  .  .
---------+---------+---------
 .  .  . |89  .  . | .  .  .
 . 49  . | .  .  . | .  .  .
 .  .  . | . 49  . | .  .  .
---------+---------+---------
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | . 19  .


[JPF]

Thanks gsf for the exhaustive check.

there are 22396 puzzles out of the 36628 gordon's 17's with mutable clues -- 61%

Glad that my estimation (60%) was not too far

About the two puzzles with 7 mutable clues :

-They only have 8 digits (9 is missing).
-Each puzzle P, say P0, gives by mutations, 7 puzzles (P1,P2,P3,P4,P5,P6,P7)
For instance case 1 :

Code: Select all

0# ....4.61.2.53...........8..4......72.6..1.............3..5.2......7..1...........
1# ....9.61.2.53...........8..4......72.6..1.............3..5.2......7..1...........
2# ....4.61.2.93...........8..4......72.6..1.............3..5.2......7..1...........
3# ....4.61.2.59...........8..4......72.6..1.............3..5.2......7..1...........
4# ....4.61.2.53...........9..4......72.6..1.............3..5.2......7..1...........
5# ....4.61.2.53...........8..9......72.6..1.............3..5.2......7..1...........
6# ....4.61.2.53...........8..4......72.6..1.............9..5.2......7..1...........
7# ....4.61.2.53...........8..4......72.6..1.............3..9.2......7..1...........


The 8 puzzles are equivalent 2 by 2 :
2~7
0~4
1~5
3~6

In case 2 :
1~3
2~7
5~6
0~4

JPF

[Papy]

Twin is an essential concept for sudoku.
Why?
I'm preparing a communication
but I can tell opu the general idea.

If you take the gordon file and you compute for all the grids (36628)
the repartition in row, colonnes and box '(Without the digit) you obtain only 1653 differentes dispositions
At this time but it's not ended for each disposition you may have 22,5 digit dispositions:
that means thant is you take the disposition of 17 clues you can find 22or more sudoku grids that give you 22 valis sudokhu

To add grids to the Gordon file so you can
1 Find new dispositions of the clue
2- find new digit repartition on tne given clue.
More to come ( if I arrive to use the gsk c14n!!!)
Papy

[JPF]

Twin is an essential concept for sudoku.
Why?
I'm preparing a communication

As I’m not sure to fully understand what you are doing, I’m looking forward to your next coming communication with a great deal of interest.

JPF

[Papy]

In the Gordo file we have a clues disposition wiith more than 2000 digits repartirtions

Quickly just with one box

1.3
2..
...


If you compute the clues

R1 =2
R2 = 1
R3 = 0

C1= 2
C2= 0
C3= 1


Sport the numbers 210=>012 201 =>012

If you do the same with a 9*9 you obtain 2 numbers with 9 digits
If you do it oin all the gordon file you get only 35 numbers for the 'sort row' and the 'sort columns'

This copmputation eliminate isomorphs and you have only clues dispositions (you need to do the same,with the nine box)

So in fact in the gordon fle you will have really 36628 GOOD grids

but you only have 1260 differents dispositions.35000 are varitions of the them

Papy

[RW]

I'm interested in different kinds of chameleon cells. These are the cells that can give a new unique puzzle by changing the given digit. What is the maximum amount of puzzles that can be found by changing the value in the same cell? I've seen lots with three and just found one with four:

Code: Select all

 *-----------*
 |..9|..5|7..|
 |.4.|.2.|.1.|
 |6..|3..|..2|
 |---+---+---|
 |..6|...|..3|
 |.1.|...|.5.|
 |*..|...|9..|
 |---+---+---|
 |..5|..9|..6|
 |.2.|.7.|.8.|
 |...|2..|4..|
 *-----------*

This puzzle has 8 solutions. The values {4,5,7,8} in r6c1 all give unique puzzles (SE rating 9,0 ; 6,7 ; 8,4 ; 9,1). The remaining four solutions all have r6c1=3. I think four unique puzzles from the same cell is already stretching the limits, but can anyone find one with 5..?

Another thing that fascinates me is cells where all valid candidates give different unique solutions. These are quite common with 2 solutions and I've seen some with three, but none with four. As you saw above, there was one valid candidate in r6c1 ('3') that didn't give a unique solution. Here's an example with 3 solutions:

Code: Select all

 *-----------*
 |..9|..5|7..|
 |.4.|.2.|.1.|
 |6..|3..|..2|
 |---+---+---|
 |..6|...|..3|
 |.7.|...|.5.|
 |5..|...|8..|
 |---+---+---|
 |..5|..9|..6|
 |.*.|.7.|.8.|
 |...|2..|9..|
 *-----------*

The puzzle has 3 solutions, all can be reached by setting values {1,2,9} in r8c2 (SE rating 2,0 ; 7,1 ; 8,4). All other values in r8c2 would give 0 solutions.

RW

[JPF]

I'm interested in different kinds of chameleon cells. These are the cells that can give a new unique puzzle by changing the given digit. What is the maximum amount of puzzles that can be found by changing the value in the same cell? I've seen lots with three and just found one with four:

Code: Select all

 *-----------*
 |..9|..5|7..|
 |.4.|.2.|.1.|
 |6..|3..|..2|
 |---+---+---|
 |..6|...|..3|
 |.1.|...|.5.|
 |*..|...|9..|
 |---+---+---|
 |..5|..9|..6|
 |.2.|.7.|.8.|
 |...|2..|4..|
 *-----------*

This puzzle has 8 solutions. The values {4,5,7,8} in r6c1 all give unique puzzles (SE rating 9,0 ; 6,7 ; 8,4 ; 9,1). The remaining four solutions all have r6c1=3. I think four unique puzzles from the same cell is already stretching the limits, but can anyone find one with 5..?

yes, I posted two puzzles with 5 mutable cells

Code: Select all

[3,4,5,8,9 are valid digits in A = r4c9]

 . . . | 2 . 8 | 1 . .
 . 4 3 | . . . | . 8 .
 . 9 . | . . . | . 5 .
-------+-------+-------
 1 . . | . . 6 | 7 . 9
 . . . | 5 . . | 2 6 .
 6 . . | . 2 . | . . .
-------+-------+-------
 . 7 . | . . . | . . .
 . . . | . 6 . | 9 . .
 . . 8 | 9 . 5 | . . 1



one other example :

Code: Select all

r3c9 = [1,2,5,6,9]

 9 . . | 1 . . | . 7 .
 . . 6 | . 4 . | . 8 3
 . . . | . . . | . . 5
-------+-------+-------
 . 7 . | 5 . . | . . .
 . . . | . . 3 | . . .
 . . . | 9 . . | . 5 4
-------+-------+-------
 . 1 5 | . . 2 | 3 4 .
 . . 3 | 7 5 . | 2 . .
 . 8 . | 6 . . | . . .



These cells are mutable cells .

See the definitions here :

Let P =(C) be a puzzle.
Ck is a cell of P and [Ck] is the given digit for the cell Ck.

A cell Ck is mutable if by replacing [Ck] by [C'k # Ck], all the other cells of the puzzle remaining equal, the new puzzle P' is valid.

A puzzle containing at least one mutable cell is volatile.
A puzzle without mutable cell is untouchable.

A puzzle in which all the cells are mutable is called a Chameleon.

JPF

[RW]

Thanks JPF! Once again it turned out that the subject is already covered in this forum, but it's not easy to keep track of all subjects that have been discussed...

RW

[Ocean]

..., but can anyone find one with 5..?

Here is a case with a 6-mutable cell:

Code: Select all

 *-----------*
 |..1|..2|...|
 |.3.|.4.|...|
 |5..|6..|7..|
 |---+---+---|
 |..7|...|..1|
 |.8.|...|.0.|
 |2..|...|6..|
 |---+---+---|
 |..9|..3|..5|
 |.4.|.2.|.8.|
 |6..|7..|2..|
 *-----------* # 6 solutions.
#
# Six puzzles (only one cell differs):
#
..1..2....3..4....5..6..7....7.....1.8.....2.2.....6....9..3..5.4..2..8.6..7..2..
..1..2....3..4....5..6..7....7.....1.8.....3.2.....6....9..3..5.4..2..8.6..7..2..
..1..2....3..4....5..6..7....7.....1.8.....4.2.....6....9..3..5.4..2..8.6..7..2..
..1..2....3..4....5..6..7....7.....1.8.....5.2.....6....9..3..5.4..2..8.6..7..2..
..1..2....3..4....5..6..7....7.....1.8.....7.2.....6....9..3..5.4..2..8.6..7..2..
..1..2....3..4....5..6..7....7.....1.8.....9.2.....6....9..3..5.4..2..8.6..7..2..
#

[JPF]

Here is a case with a 6-mutable cell:

Nice Ocean !
These diagonal patterns [with an empty box] are really magic.

JPF

[Ocean]

Here is a case with a 6-mutable cell:

Nice Ocean !
These diagonal patterns [with an empty box] are really magic.

JPF

Thanks. Only two of those puzzles are minimal (but we can't get everyting ...). Lots of interesting things in the diagonal puzzles. But of course, one reason it was found there was that a large such puzzle set was already available...