The New Sudoku Players' Forum

[JPF]

Edited after marek stefanik's and Serg's comments.

This thread is related to a question raised here.
Definitions:

• Two cells are connected if their boundaries have at least one point in common.
  Here are some examples in a box:
  

  Code: Select all

  +---+   +---+   +---+
|...|   |...|   |...|
|.xx|   |.x.|   |.x.|
|...|   |.x.|   |..x|
+---+   +---+   +---+


• Here are non-connected cells:
  

  Code: Select all

  +---+   +---+   +---+
|...|   |x..|   |..x|
|x.x|   |...|   |. .|
|...|   |.x.|   |..x|
+---+   +---+   +---+


• A puzzle is said to be a k-regular if every non-empty cell is connected to exactly k non-empty cells.
• A group G of givens is k-regular if all of its cells are connected to k cells of the same group.

This property is not invariant under all 3,359,232 VPT of a Sudoku grid. However, this is not the main point of this thread.

Examples (n is the number of givens):
k=3

Code: Select all

+-------------------+
| . . . . . . . . . |
| . 1 2 . 3 4 . 5 6 |
| . 4 6 . 7 8 . 9 1 |
| . . . . . . . . . |
| . 7 4 . 1 3 . 2 8 |
| . 6 3 . 8 9 . 1 7 |
| . . . . . . . . . |
| . 8 5 . 2 6 . 3 9 |
| . 2 1 . 9 7 . 4 5 |
+-------------------+   n=36; 9 groups; SE=7.3


k=2

Code: Select all

+-------------------+
| . . . 1 . 2 . . . |
| . . 3 . 4 . 1 . . |
| . 5 . . . . . 6 . |
| 7 . . . . . . . 3 |
| . 6 . . . . . 5 . |
| 5 . . . . . . . 8 |
| . 8 . . . . . 9 . |
| . . 4 . 8 . 2 . . |
| . . . 5 . 7 . . . |
+-------------------+   n=20; 1 group; SE=8.9


k=1

Code: Select all

+-------------------+
| 1 2 . 3 . . . . 4 |
| . . . 5 . 2 6 . 7 |
| 5 . . . . . . . . |
| . 8 . . . 5 3 . 1 |
| . . . 1 . . . . 9 |
| 6 1 . . 9 . 7 . . |
| . . . . . . . 9 . |
| 8 . 4 . 5 . . . . |
| 2 . 1 . 6 . 4 7 . |
+-------------------+   n=28; 14 groups; SE=9.2 ;


k=0 (isolated cells)

Code: Select all

+-------------------+
| 1 . . . 2 . . . 3 |
| . . 4 . . . 5 . . |
| 6 . . . 7 . . . 1 |
| . . 6 . . . 8 . . |
| 3 . . . 9 . . . 2 |
| . . 2 . . . 7 . . |
| 2 . . . 3 . . . 9 |
| . . 1 . . . . . . |
| 9 . . . . 8 . 6 . |
+-------------------+  n=22; 22 groups;  SE=9.2


Special case n=17 clues

Here are some results :

• For k=0 there are only 83 ed 0-regular 17-clues puzzles
  Here is one:
  

  Code: Select all

  +-------------------+
| . . 1 . 2 . . 3 . |
| . . . . . . . . . |
| . . . . 4 . 5 . . |
| 4 . 6 . . . . . 7 |
| . . . . 1 . . . . |
| . 7 . . . . 8 . . |
| . . . 6 . . . . 1 |
| . 5 . . . 7 . . . |
| . . . 9 . . . . 2 |
+-------------------+ k=0; n=17; SE=8.3


  
  here is the list:
  
  Hidden Text: Show

  Code: Select all

  .1.2.3.4.............5.6....7......4....8......2...5.66............7..8.3.5......
.1..2.3.............4.....55...3.6....7......8.....2.....8....42...........4.5..7
..1..........2.3.45.6..........4.2....7.....38....9......1...6..4..........6...7.
.....1.2..3.4............5.6.2.5..........7..1.......4..5.7....2...........8.4..3
...1.2....3......4.....5...5.2..........4.6.3..........6..7...8.........1..5.8.2.
..1.....23...4......5...6.7....3.....2......8.....1....7.8..........2...6.4....3.
...1.2....3......4.....5...5.2..........4.6.3..........6..7...8.........1..5.9.2.
.1..2.3...............4.5....6..........5.2.78.9...........3.9..2..........6.9..8
.1..2.3...............4.5....6..........3.2.78.9...........5.9..2..........9.6..8
.1.....2....3.4....5.............6.3.7..5............83..8.6..........7.8.9..2...
.1.....2....3.4....5.............3.6.7..5............84..8.2..........7.8.3..6...
.1....2.3...4......3...5..6.........4.7..........3.6.25...........8.7.4..2.......
.1.....2....3.4....5.............3.6.7..5............84..8.9..........7.3.8..6...
.1.....2....3.4....5.............3.6.7..5............83..8.6..........7.4.8..9...
.1..2.3................4.5.6.5..........1.4.78...........6.3....3......2...5..8..
1.2....3...........4..5.6..........47.3.1..........2.89..3..........2....1......5
1.2.3..........4.56...........5......4....7.8....1....3......1......7....9.4...2.
........12.3.4..........5.6...1.....4......2....7.5....1......5....3......6...8.7
..1..........2.3.45.6..........3.4....7.....28....9......1...6..3..........6...7.
1...........2.3.4..5...........6.5..4.2.....3..........6...1..7...4......8....6.5
1.2.....3............4.5.6..4...........1.7.28.3...........9...........1.5.8.4...
..1..........2.3.45.6...........3..2..7......1......6....1.7....4......3...6.8...
1.2.3...4............5.6.7.8............1.3.2.5............8...........1.6.7.5...
1..2.3...........4.....1...5.3....2...........6..4...5......7..2.1..........8.4.6
....1...23.4...5.................4.67...8......8...9..1.......7...4.9....2......3
..1....2.3...4..........5.6..7..........5.4.3.2..........1.2...5.......8..9..7...
1...2..3...........4...3..5...6.....2......7....4.5...........87.2.1..........4.6
1...2..3...........4...5..6...7.....2......8....4.6...........38.2.1..........4.7
1...2..3...........4...5..6...4.....2......7....8.6...........37.2.1..........4.8
.1..2..3..........4.5.....6....5.2..6.7.............8..2...8......6....7.5....4..
.1..2..3..........4.5.....6....4.2..6.7.............8..2...8......6....7.4....5..
.1.2.3.4..........5...6.7....4..........8.5.9.2............2...7.......8...1.4...
1..2.3.4...........5.....6....7.1..........2..8..5............92.7..........6.8.5
1..2.3.4...........5.....6....1.7..........2..8..5............92.7..........6.8.5
..1..........2.3.45.6..........3..7.6..........8..7..52...........1....6.3...4...
...1.2.3..........4.5.....6.....7...........4.2.8.1..........1.8.6.4..........9.5
...1.2.3...........4..5.6..........72..3..........8..43............7.4.81.9......
....1..2..3..........4...5......3...2......1....6.7....7......8....5....8.4...7.3
.1.2.3..................4.55.2..........4.6.7.8..........8...1.4..........6..1.2.
..1..........2.3.45.6...........2.6..3.7...........5.....3....74....5.....2....8.
...1..2.3.........4.5.6...........5..7.2.3...........7.3.7..8.............6.5..4.
.1..2...3......4...5..........4......6....5.1....7....8.7.....2.....6...9..5...7.
.1..2.3..............4...5.5............1.2.64.7............8.27..5..........3..1
.....1.2..3............4.5.5.6..........7.3.8..........8....7.1.........9..2.5.6.
1.2.3...4.............4.5.6.5...........7..8..6..........5..8..7..........3..9.1.
1.2....3..............4...56.3..........7.5.48...........1.3.6...........5....3.9
....1..2.3...........4...5......3....2.....1....6.7...7.......8....5....4.8...7.3
1.2.3...4............5..6.7.7...........2..8.4.6...........8...9......1....6.7...
.1..2..........3.4.5............6....7.....5....3.8...6.......2....7....4.3...6.8
......1.23.4.5............6...1.7...5......4....6......6....8.1....3......2.....7
1.2..........3.4.5.........6..7.2.1...........4....3.8...1......5......4...2.6...
.1.2..3.4.............5.6...4...........7..5.6...........1.4..85..........7..8.9.
.1..2...3......4...5............6....7.....5....4.8...6.......9....7....4.3...6.8
.1...2..3.........4.5....6......1...7......4....3.8...9..............8.16.4.7....
.1....2.3...4......5...6..........6..2..3............7..4...3......1...87.6...5..
1.2...3..............4.5.6..4...........1.7.23.6...........8...........1.5.6.4...
...1.2....3......4.....5...5.2..........4.6.7..........6..8.3...........1..5.9.2.
...1..2.3.........4..5.6..........6.1.2.7...........5..6.4.............1.8..2.7..
.1..2..3.............4.5.6.5............7.1.26.3...........8..14..6.............7
1.2..3.4...............5..63.4..........7.6.58................4.6..........8.1.3.
1...2.3..............4.5..6.4...........1.7....5.....82...3............43..8..1..
.1..2.3...........4.5.....6....7.2....8......6.....7.....5....8.7..........8.6..9
1.2...3.4............5.6...3.............4..52.7..........1.2..........8.6.3.9...
1..2.3................4...52.6..........5.7.48...........8.1.2...........4..7...6
..1.2..3...............4.5..6.7............2.7.8..5...........95.4..........9.7.6
.1...2..3..............4.5.4.5..........6.3.17...........1....62..........4.7..8.
1.2..3..4..............5..3..5..........6.7....3......6...7.2..........57..1..8..
1.2..3.4..............5...67.1..........6.2.84...........4......8......5...1..7..
1.2.3..4.............5..6.7.7............1.8..5.9...........5.....7....93....4...
.1...2..3.........4...1..5...6......5......4....7.3....8......7....4......7...3.9
..1..2..34..........5....6.....6......7...2.1....4....6......5......7....8.9....2
........1.2.3.4...........5..4..........1.5.6.7..........2.7.3.1..........6..8.7.
......1.23.4.5...........6...1......2...7.5.8..6...........6.4....1......5......7
.....1....2.....3....2.4...........5..6.3..........4.1..7.8..........1.26.3.9....
.1....2.....3....4.5..........6.2....7.....1......4...6.8.....9....7......4...3.6
.1.2..........3..4.5.............2.6.7..1............38..4.6..........7.3.6..9...
.1.2.3.4...............5.6.2.7.............8...6.7....3.....5.2....8......5.....7
.....1.2..3.4...........5..6.1.....7....5......7....8.8....7......8....4.5....3..
1.2..........3.4.5.6..........2...7..8...........4.1..3.1...........7..84..1.....
..1.2..3..............4.5..4.6.....7....1.....7....8.....6....1.5...7......9....2
1..2.3.............4......5....1.2...6...........5.7.43.2..........4...8..7...3..
1.2..3.4..............5.6.7.5..........8.1..3.6..........6..8..3..........9.4....
....1.2..3.4............5.6...7......8......5...9.3....2.....9.....8....7.9....3.


• k=1 : no puzzle, 17 beeing odd.
• k=2 : only one puzzle:
  

  Code: Select all

  +-------------------+
| . . . . . . . . . |
| . . 1 . . . . . . |
| . 4 . 2 . . . 3 . |
| . . 8 . . . 6 . 4 |
| . . . . 2 . . 5 . |
| . . . . 3 7 . . . |
| 2 5 . . . . . . . |
| 3 . . . . 6 7 . . |
| . . . . . . 1 . . |
+-------------------+ k=2; n=17; 5 Groups; SE=2.0


• k=3 : no puzzle
• k=4 : no puzzle

18 clues
Here are some examples:
k=0

Code: Select all

+-------------------+
| . 1 . . 2 . 3 . . |
| . . . . . . . . 4 |
| . . 2 . 5 . 6 . . |
| . . . . . . . . . |
| . . . . 4 . 5 . 1 |
| 7 . 8 . . . . . . |
| . . . . . 1 . 8 . |
| . 4 . . . . . . . |
| . . . 8 . 2 . 7 . |
+-------------------+   n=18; 18 Groups; SE=8.3


k=1

Code: Select all

+-------------------+
| . . . . . . . . 1 |
| . . 2 3 . . . 4 . |
| 5 . . . . . . . . |
| 6 . . . 7 . . . . |
| . . . . 1 . . . 2 |
| . 4 . . . . . 3 . |
| . . 4 . . . . . . |
| . . . . 5 2 . . 7 |
| . 8 3 . . . . 9 . |
+-------------------+  n=18; 9 Groups; SE=9.0


k=2

Code: Select all

+-------------------+
| . . 1 . . . . 2 . |
| . . 2 3 . . . 4 5 |
| . . . . . 6 . . . |
| . . . . . 7 6 . . |
| . . . . . . . . . |
| 8 . . . . . 7 1 . |
| 6 3 . . . . 8 . . |
| . . . . 3 . . . . |
| . . . 2 4 . . . . |
+-------------------+  n=18; 6 Groups; SE=6.6


k=3 : no puzzle

Open questions:
what is the maximum value of k?
what is the maximum number of givens (n)?
for a number of clues = n, what are the different k-regular groups (k>1)?
any other ideas?

Here are some more examples:

Code: Select all

+-------------------+
| . . . . . . . . . |
| . . . . . . 1 . . |
| . . 2 . . 3 . 4 . |
| . 5 . 6 . 1 . 2 . |
| . 1 . 3 . 4 . 7 . |
| . 8 . 7 . 9 . 6 . |
| . 9 . 4 . 6 . 3 . |
| . 2 . 5 . . 6 . . |
| . . 4 . . . . . . |
+-------------------+   n=24; k=2; 2 groups


based on eleven's exemple here:

Code: Select all

+-------------------+
| . . . 1 . 2 . . . |
| . . 1 . 3 . 4 . . |
| . 5 . . . . . 6 . |
| 1 . . . 2 . . . 7 |
| . 8 . 7 . 9 . 1 . |
| 3 . . . 1 . . . 9 |
| . 4 . . . . . 7 . |
| . . 6 . 8 . 5 . . |
| . . . 2 . 5 . . . |
+-------------------+   n=24; k=2; 2 groups


Code: Select all

+-------------------+
| . . . . . . . . . |
| . . . . . . 1 . . |
| . . 2 . . 3 . 4 . |
| . 5 . 1 . 6 . 7 . |
| . . 8 . . 4 . 2 . |
| . . . . . 9 . 3 . |
| . . 4 . . 2 . 6 . |
| . 8 . 5 . . 9 . . |
| . . 3 . . . . . . |
+-------------------+   n=20; k= 2; 3 groups


Code: Select all

+-------------------+
| . . . . . 1 2 . . |
| . 3 4 . . 5 1 . . |
| . 6 2 . . . . . . |
| . . . . . . . . . |
| . . 7 8 . . . . . |
| . . 3 2 . . 4 6 . |
| . . . . . . 7 8 . |
| . . . 3 1 . . . . |
| . . . 6 9 . . . . |
+-------------------+   n=20; k=3; 5 groups


JPF

[Serg]

Hi, JPF!
Interesting. Some isomorphic transformations are still applicable to k-connected puzzles (reflections, quarter-turns, etc.)
It looks like 4-connected puzzles are impossible.

Serg

[denis_berthier]

.
I wonder why you allow diagonal connections in your definition. This obviously implies non invariance under isomorphisms.
Is the problem already solved without these diagonal connections?
.

[marek stefanik]

May I suggest the term k-regular instead?
k-connected graphs remain connected when you delete up to k-1 vertices in any possible way, which is not the case here.
In k-regular graphs each vertex has k neighbours.

4-regular groups are indeed impossible, here is a quick proof:

WLOG suppose there is only one group in the grid (we can always pick a group and make a grid with that group only).
We will refer to the top-most cell with the highest difference of its column and row as rxcy (marked with 0).
r(x-1)c(y-1) and cells with a higher difference cannot be part of the group (marked with –).

Code: Select all

           y
rx-1 ... – – – – – –––
rx   ... 1 0 – – – –––
rx+1 ... 1 1 1 – – –––
rx+2 ... – – – . – –––

rxcy must have 4 neighbours, there is only one possibility (marked with 1s).
Now r(x+1)c(y) already has 4 neighbours, remaining adjacent cells cannot be part of the group (marked with –).
Now r(x+1)c(y+1) cannot get enough neighbours, ie. contra.

It could still be interesting on toroidal grids, where for example r124578 is a 5-regular pattern.

I wonder why you [JPF] allow diagonal connections in your definition. This obviously implies non invariance under isomorphisms.
Is the problem already solved without these diagonal connections?

What happens to the connected cells r1c12 when I swap c23?

Marek

[denis_berthier]

I wonder why you [JPF] allow diagonal connections in your definition. This obviously implies non invariance under isomorphisms.
Is the problem already solved without these diagonal connections?

What happens to the connected cells r1c12 when I swap c23?

The question is not about what happens without diagonal connections. It's why should one consider connections that are not Sudoku connections?

[JPF]

May I suggest the term k-regular instead?

I knew that k-connected was a very specific property of graphs, but I couldn't find anything better.
k-regular seems perfect to me.Thread name modified.

JPF

[marek stefanik]

My shot at the highest n:

Code: Select all

+–––––––––––––––––––+
| . 2 3 4 5 6 7 8 . |
| 4 . . . . . . . 6 |
| 5 . . 8 9 1 . . 4 |
| 3 . 2 . . . 8 . 1 |
| 6 . 4 . . . 9 . 2 |
| 9 . 5 . . . 4 . 3 |
| 7 . . 1 2 5 . . 8 |
| 8 . . . . . . . 7 |
| . 4 6 7 8 9 1 3 . |
+–––––––––––––––––––+ n=40; k=2; 2 groups

And at the lowest n not divisible by 4 for k=3:

Code: Select all

+–––––––––––––––––––+
| . . . 1 . . . . . |
| . . 2 3 4 . . . . |
| . 8 . . . 6 7 . . |
| 4 9 . . . 1 . 2 . |
| . 3 . . . 8 . 6 4 |
| . . 7 5 2 4 . 3 . |
| . . 8 . . . 9 . . |
| . . . 2 6 9 . . . |
| . . . . 7 . . . . |
+–––––––––––––––––––+ n=26; k=3; 1 group

Marek

[JPF]

Excellent! The shape of the group with n=26 and k=3 is just surprising!

For purists, I need to clarify the definition of a group. Indeed, if we look at your first diagram (n=40; k=2), it shows two groups: G1 from the outer loop and G2 from the inner loop. As my definition is formulated, G1+G2 is also a group. To avoid this ambiguity, we should consider only the minimal groups: groups that do not contain any other groups than themselves.
In your example, G1 and G2 are minimal groups and they are the only ones.

JPF

[marek stefanik]

Got a 22, so unless there is an 18...

Code: Select all

+–––––––––––––––––––+
| . . . . . . . . . |
| . . . . . 1 2 . . |
| . . . . 3 4 . 1 . |
| . . . 1 . . . 4 3 |
| . . 5 . 4 6 . 7 . |
| . 3 2 . 7 . 9 . . |
| . 1 . . . 3 . . . |
| . . 9 5 8 . . . . |
| . . . 2 . . . . . |
+–––––––––––––––––––+ n=22; k=3; 1 group

Marek