how many components?

Everything about Sudoku that doesn't fit in one of the other sections

how many components?

Postby P.O. » Fri May 19, 2023 6:21 pm

i couldn't find any posts on this topic but i guess it has already been discussed:
since a puzzle can be represented as a graph whose vertices are the clues and whose edges are pairs of clues that share a unit, i was wondering how many components a puzzle with a unique solution can have? and also what can be the maximum size of the components.
here is a puzzle with 4 components, 3 of size 1 and 1 of size 20:
Code: Select all
1 . .  . . .  . . .
. . .  . 3 5  2 1 .
. . .  . 8 2  7 . .
. . 7  . 4 .  1 3 .
. . 6  . . .  9 5 .
. . 8  . 5 3  . . .
. . .  6 1 4  . . .
. 3 .  . . .  . . .
. . .  . . .  . . 2

1............3521.....827....7.4.13...6...95...8.53......614....3...............2
P.O.
 
Posts: 1731
Joined: 07 June 2021

Re: how many components?

Postby P.O. » Sat May 20, 2023 7:06 am

4 components, 2 of size 1, 1 of size 4, 1 of size 16
Code: Select all
2 1 .  . . .  . . .
. . .  . . .  . 6 .
. . .  3 7 4  . . .
. . 5  2 9 .  4 . .
. . 1  . . .  3 . .
. . 7  5 . 6  1 . .
. . .  1 4 5  . . .
3 8 .  . . .  . . .
. . .  . . .  . . 2

21..............6....374.....529.4....1...3....75.61.....145...38...............2
P.O.
 
Posts: 1731
Joined: 07 June 2021

Re: how many components?

Postby JPF » Sun May 21, 2023 4:12 pm

I assume that only minimal puzzles are being considered.
Just for information, there are five 17-clue puzzles that have 4 components.
Here they are:
Code: Select all
........1.......23..2..4.......5.......31.....6....4.....12.....7....8..64....9..
........1.......23..4.56...........7..5.8.....96.1..........5..2..3.....3..7.....
........1.......23..4.56...........7..5.8.....96.3..........5..1..7.....2..1.....
........1.......23..4.56..........17..5.......86..4.........6..1..3.....2..7.....
........1.......23..4.56..........17..5.......86..4.........6..1..7.....2..3.....

The first one:
Code: Select all
+-------+-------+-------+
| . . . | . . . | . . 1 |
| . . . | . . . | . 2 3 |
| . . 2 | . . 4 | . . . |
+-------+-------+-------+
| . . . | . 5 . | . . . |
| . . . | 3 1 . | . . . |
| . 6 . | . . . | 4 . . |
+-------+-------+-------+
| . . . | 1 2 . | . . . |
| . 7 . | . . . | 8 . . |
| 6 4 . | . . . | 9 . . |
+-------+-------+-------+  2-3-5-7

Most 17-clue puzzles are 'single-piece' puzzles (i.e. size 17)

JPF
JPF
2017 Supporter
 
Posts: 6139
Joined: 06 December 2005
Location: Paris, France

Re: how many components?

Postby P.O. » Sun May 21, 2023 6:15 pm

thank you for the info, their shape is interesting well distributed on the grid, i was planning to check some puzzle collections but my system is very slow, i try to build some but for the moment i can't pass the 4 components, so far i have not found that redundant clues add components but why not.
P.O.
 
Posts: 1731
Joined: 07 June 2021

Re: how many components?

Postby JPF » Sun May 21, 2023 8:32 pm

For 5 components, this pattern could be a good candidate:
Code: Select all
+-------+-------+-------+
| x . . | . . . | . . . |
| . . . | . . . | . . x |
| . . . | x x x | . . . |
+-------+-------+-------+
| . . x | x x x | x . . |
| . . x | x x x | x . . |
| . . x | x x x | x . . |
+-------+-------+-------+
| . . . | x x x | . . . |
| . x . | . . . | . . . |
| . . . | . . . | . x . |
+-------+-------+-------+

Unfortunately, I strongly believe that this pattern is (maximum) invalid.

JPF
JPF
2017 Supporter
 
Posts: 6139
Joined: 06 December 2005
Location: Paris, France

Re: how many components?

Postby JPF » Mon May 22, 2023 10:29 am

Here is a 5 components:
Code: Select all
+-------+-------+-------+
| 4 . . | . . . | . . . |
| . . . | 3 . . | . . . |
| . . . | . . . | 2 . . |
+-------+-------+-------+
| . . . | . . . | . . 8 |
| . 2 3 | . . 9 | . . . |
| . 7 8 | . 6 1 | . . . |
+-------+-------+-------+
| . 8 1 | . . 3 | . 7 . |
| . 9 . | . 2 7 | . 6 . |
| . 3 . | . 4 8 | . 9 . |
+-------+-------+-------+  1-1-1-1-19

JPF
JPF
2017 Supporter
 
Posts: 6139
Joined: 06 December 2005
Location: Paris, France

Re: how many components?

Postby P.O. » Mon May 22, 2023 10:41 am

really great, the best i could do has 2 solutions with (4 1) (1 18) components
Code: Select all
3 . .  . . .  . . .
. . .  . 2 .  . . .
. . .  . . .  . 5 .
. 1 .  . . .  . . .
. . .  9 . 8  2 . 3
. . .  4 . 6  . . 1
. . 6  . . 3  8 . 2
. . 9  6 . 4  . . 7
. . 4  . . 5  1 . .

3............2...........5..1..........9.82.3...4.6..1..6..38.2..96.4..7..4..51..
P.O.
 
Posts: 1731
Joined: 07 June 2021

Re: how many components?

Postby sudokuvalleyvenusrye » Fri Jun 23, 2023 9:28 pm

It depends on the complexity of the puzzle. Generally, puzzles with unique solutions have components of two - the clues and the units that connect them - but some more complex puzzles can have more components than that.
sudokuvalleyvenusrye
 
Posts: 6
Joined: 12 June 2023


Return to General