Just to clarify
This is the the "SF"
+---+---+---+
|639|241|785|
|284|765|193|
|517|983|624|
+---+---+---+
|123|857|946|
|796|432|851|
|458|619|237|
+---+---+---+
|342|178|569|
|861|594|372|
|975|326|418|
+---+---+---+
It has 29 17s, some of the the unavoidable sets are {12,16,32,36} - the 3/1 and 1/3 in Box1 and Box2. Others are {51,52,91,92}{24,25,64,65,74,75} {81,85,89,91,95,99} etc
no 2 in the collection is
---24-7--
-8-----9-
-1-------
---8----6
7--------
4-----2--
3---7----
--------2
-----6-78
The 16er [with 2 solutions] - [manipulated from published form for comparison]
---6--4--
-7--8--4--
-1-------
----1---3
4--------
6-----2--
5-24-----
-----3-71
---------
the 8 in r2c5 can be in 9 other positions and there can also be 9 other positions for the 9.
one of the the full grids is
+---+---+---+
|358|627|419|
|974|185|326|
|216|349|785|
+---+---+---+
|725|914|863|
|483|562|197|
|691|738|254|
+---+---+---+
|562|471|938|
|849|253|671|
|137|896|542|
+---+---+---+ {12,16,22,26} {51,52,81,82} etc
There are a lot of similarities between the two grids
C
Minimum number of clues
by dukuso » Fri Oct 21, 2005 5:20 am
>Just to clarify
>
>This is the the "SF"
>
>+---+---+---+
>|639|241|785|
>|284|765|193|
>|517|983|624|
>+---+---+---+
>|123|857|946|
>|796|432|851|
>|458|619|237|
>+---+---+---+
>|342|178|569|
>|861|594|372|
>|975|326|418|
>+---+---+---+
>
>It has 29 17s, some of the the unavoidable sets are {12,16,32,36} -
> the 3/1 and 1/3 in Box1 and Box2. Others are
>{51,52,91,92}{24,25,64,65,74,75} {81,85,89,91,95,99} etc
>no 2 in the collection is
>
>---24-7--
>-8-----9-
>-1-------
>---8----6
>7--------
>4-----2--
>3---7----
>--------2
>-----6-78
>
>The 16er [with 2 solutions] - [transposed for comparison]
>
>---6--4--
>-7--8--4--
>-1-------
>----1---3
>4--------
>6-----2--
>5-24-----
>-----3-71
>---------
it's not just transposed (=reflected on the diagonal), I assume
you mean these two are isomorphic (wrt. the 9!*6^8*2 operations)
>the 8 in r2c5 can be in 9 other positions and there can also
>be 9 other positions for the 9.
>
>one of the the full grids is
>+---+---+---+
>|358|627|419|
>|974|185|326|
>|216|349|785|
>+---+---+---+
>|725|914|863|
>|483|562|197|
>|691|738|254|
>+---+---+---+
>|562|471|938|
>|849|253|671|
>|137|896|542|
>+---+---+---+ {12,16,32,36} {51,52,81,82} etc
I don't know what {12,16,32,36} {51,52,81,82} refers to.
Probably not unavoidables in above grid ?!
>There are a lot of similarities between the two grids
>
>C
yes, they are isomorphic. (says my computer)
All solutions in all the known 16-puzzles with 2 solutions
are isomorphic to sf.
I had missed some of the earlier discussion about sf,
so I don't know whether this were already mentioned.
-Guenter.
>
>This is the the "SF"
>
>+---+---+---+
>|639|241|785|
>|284|765|193|
>|517|983|624|
>+---+---+---+
>|123|857|946|
>|796|432|851|
>|458|619|237|
>+---+---+---+
>|342|178|569|
>|861|594|372|
>|975|326|418|
>+---+---+---+
>
>It has 29 17s, some of the the unavoidable sets are {12,16,32,36} -
> the 3/1 and 1/3 in Box1 and Box2. Others are
>{51,52,91,92}{24,25,64,65,74,75} {81,85,89,91,95,99} etc
>no 2 in the collection is
>
>---24-7--
>-8-----9-
>-1-------
>---8----6
>7--------
>4-----2--
>3---7----
>--------2
>-----6-78
>
>The 16er [with 2 solutions] - [transposed for comparison]
>
>---6--4--
>-7--8--4--
>-1-------
>----1---3
>4--------
>6-----2--
>5-24-----
>-----3-71
>---------
it's not just transposed (=reflected on the diagonal), I assume
you mean these two are isomorphic (wrt. the 9!*6^8*2 operations)
>the 8 in r2c5 can be in 9 other positions and there can also
>be 9 other positions for the 9.
>
>one of the the full grids is
>+---+---+---+
>|358|627|419|
>|974|185|326|
>|216|349|785|
>+---+---+---+
>|725|914|863|
>|483|562|197|
>|691|738|254|
>+---+---+---+
>|562|471|938|
>|849|253|671|
>|137|896|542|
>+---+---+---+ {12,16,32,36} {51,52,81,82} etc
I don't know what {12,16,32,36} {51,52,81,82} refers to.
Probably not unavoidables in above grid ?!
>There are a lot of similarities between the two grids
>
>C
yes, they are isomorphic. (says my computer)
All solutions in all the known 16-puzzles with 2 solutions
are isomorphic to sf.
I had missed some of the earlier discussion about sf,
so I don't know whether this were already mentioned.
-Guenter.
- dukuso
- Posts: 479
- Joined: 25 June 2005
by dukuso » Fri Oct 21, 2005 5:22 am
>When you all talk about unavoidable sets, are you restricting
>yourselves down to the minimal sets only?
I think yes. Nobody would call the whole grid unavoidable,
although it certainly can't be avoided ;-)
Let me also call a set k-unavoidable if it is minimal
and k different symbols occur in it. Do 4-unavoidables exist ?
Define a set S of cells to be unavoidable wrt. a grid G,
if any sudoku over G intersects S, or equivalently if the
sudoku G-S has 2 or more solutions.
>An unavoidable is minimal if it contains no proper unavoidable.
>
>Its easy to check if an unavoidable is minimal: It is minimal if
>and only if removing any element makes it avoidable
for any cell c in S : G-S+{c} has one solution.
>(avoidable is
>of course the same as "not unavoidable"...).
..triple negation. Can't we say positively "mustbehit" or whatever word
there is in English (there should be one !?) instead of unavoidable ?
>This process could also be used to finding at least one minimal subset.
given a grid G, start with S={}.
As long as there is a cell c such that S+{c} has multiple solutions
add c to S and continue. Then at last G-S is minimally unavoidable.
>It's (almost) only interresting looking at minimal sets when dealing
>with unavoidables. But maybe they are too many also? I haven't tried
>anything on computer yet, so I don't know.
here is the statistics for Gordon's 17s :
number of (proper,minimal)2-unavoidables minus 36, count
--------------------------------------------------------
0,3
2,2
3,6
4,13
5,42
6,86
7,168
8,364
9,554
10,801
11,1174
12,1640
13,2170
14,2623
15,2697
16,2961
17,2888
18,2339
19,1771
20,1131
21,661
22,326
23,141
24,45
25,12
26,1
27,1
complements are not counted, so when the 18-set of cells containing
digits d1,d2 partitions into 3 2-unavoidables(connected components)
then for {d1,d2} only 2 are counted. So, one 2-unavoidable is
missed for each of the 36 {d1,d2}-pairs.
I just thought, I had a 4-unavoidable here:
12.34....
34.21....
.........
...13.42.
...42.31.
.........
23....14.
41....23.
.........
but my solver says, this has no solution.
Even this one
12.34....
34.12....
.........
21.43....
43.21....
.........
.........
.........
.........
has no solution, it is not minimal anyway.
>yourselves down to the minimal sets only?
I think yes. Nobody would call the whole grid unavoidable,
although it certainly can't be avoided ;-)
Let me also call a set k-unavoidable if it is minimal
and k different symbols occur in it. Do 4-unavoidables exist ?
Define a set S of cells to be unavoidable wrt. a grid G,
if any sudoku over G intersects S, or equivalently if the
sudoku G-S has 2 or more solutions.
>An unavoidable is minimal if it contains no proper unavoidable.
>
>Its easy to check if an unavoidable is minimal: It is minimal if
>and only if removing any element makes it avoidable
for any cell c in S : G-S+{c} has one solution.
>(avoidable is
>of course the same as "not unavoidable"...).
..triple negation. Can't we say positively "mustbehit" or whatever word
there is in English (there should be one !?) instead of unavoidable ?
>This process could also be used to finding at least one minimal subset.
given a grid G, start with S={}.
As long as there is a cell c such that S+{c} has multiple solutions
add c to S and continue. Then at last G-S is minimally unavoidable.
>It's (almost) only interresting looking at minimal sets when dealing
>with unavoidables. But maybe they are too many also? I haven't tried
>anything on computer yet, so I don't know.
here is the statistics for Gordon's 17s :
number of (proper,minimal)2-unavoidables minus 36, count
--------------------------------------------------------
0,3
2,2
3,6
4,13
5,42
6,86
7,168
8,364
9,554
10,801
11,1174
12,1640
13,2170
14,2623
15,2697
16,2961
17,2888
18,2339
19,1771
20,1131
21,661
22,326
23,141
24,45
25,12
26,1
27,1
complements are not counted, so when the 18-set of cells containing
digits d1,d2 partitions into 3 2-unavoidables(connected components)
then for {d1,d2} only 2 are counted. So, one 2-unavoidable is
missed for each of the 36 {d1,d2}-pairs.
I just thought, I had a 4-unavoidable here:
12.34....
34.21....
.........
...13.42.
...42.31.
.........
23....14.
41....23.
.........
but my solver says, this has no solution.
Even this one
12.34....
34.12....
.........
21.43....
43.21....
.........
.........
.........
.........
has no solution, it is not minimal anyway.
- dukuso
- Posts: 479
- Joined: 25 June 2005
by kjellfp » Fri Oct 21, 2005 7:35 am
I continue daring to contribute, without having read the entire thread and so running a risk of repeating the well-known...
Someone proved in another thread that there are grids with no 16.
Well, the canonical x, x+3, x+6, x+1, x+4, x+7, x+2, x+5, x+8 can easily be proved not to contain even a 17.
The grid:
123456789
456789123
789123456
234567891
567891234
891234567
345678912
678912345
912345678
The first band has a non-minimal unavoidable:
(*)
1..4..7..
4..7..1..
7..1..4..
It is well-kown that it needs two hints to be completed uniquely. (Two hints complete the set if and only if they are two different symbols on two different rows and columns). As there are 9 disjoint similar such unavoidables in the grid, we need at least 18 hints.
Another canonical form, which is very similar (but not isomorphic) to the above:
123456789
789123456
456789123
312645978
978312645
645978312
231564897
897231564
564897231
This has for the same reason no 17 hints solution. But this grid is isomorphic to its transposed, so an 18 hints solution must also hit each of the 9 similar unavoidables on the stacks twice each.
I tried yesterday by hand to find such an 18-set, and eventually succeeded. But this wasn't enough to give a solution, as it turned out to miss a much more complex minimal unavoidable.
So maybe someone would like to do the programming (I have too many other projects running now...) to either find an 18-solution, or prove that they don't exist.
This also points out that my suggestion about minimizing the number of 4-element unavoidables in the search for a 16 was no good idea after all - the above grids have no such unavoidables.
Someone proved in another thread that there are grids with no 16.
Well, the canonical x, x+3, x+6, x+1, x+4, x+7, x+2, x+5, x+8 can easily be proved not to contain even a 17.
The grid:
123456789
456789123
789123456
234567891
567891234
891234567
345678912
678912345
912345678
The first band has a non-minimal unavoidable:
(*)
1..4..7..
4..7..1..
7..1..4..
It is well-kown that it needs two hints to be completed uniquely. (Two hints complete the set if and only if they are two different symbols on two different rows and columns). As there are 9 disjoint similar such unavoidables in the grid, we need at least 18 hints.
Another canonical form, which is very similar (but not isomorphic) to the above:
123456789
789123456
456789123
312645978
978312645
645978312
231564897
897231564
564897231
This has for the same reason no 17 hints solution. But this grid is isomorphic to its transposed, so an 18 hints solution must also hit each of the 9 similar unavoidables on the stacks twice each.
I tried yesterday by hand to find such an 18-set, and eventually succeeded. But this wasn't enough to give a solution, as it turned out to miss a much more complex minimal unavoidable.
So maybe someone would like to do the programming (I have too many other projects running now...) to either find an 18-solution, or prove that they don't exist.
This also points out that my suggestion about minimizing the number of 4-element unavoidables in the search for a 16 was no good idea after all - the above grids have no such unavoidables.
- kjellfp
- Posts: 140
- Joined: 04 October 2005
by Moschopulus » Fri Oct 21, 2005 8:56 am
kjellfp wrote:I continue daring to contribute, without having read the entire thread and so running a risk of repeating the well-known...
Yes, we did all that earlier in the thread.
AFAIR dukuso checked, and no 18.
- Moschopulus
- Posts: 256
- Joined: 16 July 2005
by dukuso » Fri Oct 21, 2005 9:33 am
while I was searching for the referrence, Moschopulos already
answered.
anyway, here it is:
http://forum.enjoysudoku.com/viewtopic.php?t=605&postdays=0&postorder=asc&start=100
and then browse some posts below.
However, there was a mistake in the 19-clues grig which I posted !
I hope I didn't make the same mistake in the whole analysis !
grr.
While browsing the old messages, I found another
error. My program nppcsu3 is incomplete and doesn't find
all unavoidables with 3 different digits.
I suspect Colin and Moschopulos already knew this but didn't
want to complain....
answered.
anyway, here it is:
http://forum.enjoysudoku.com/viewtopic.php?t=605&postdays=0&postorder=asc&start=100
and then browse some posts below.
However, there was a mistake in the 19-clues grig which I posted !
I hope I didn't make the same mistake in the whole analysis !
grr.
While browsing the old messages, I found another
error. My program nppcsu3 is incomplete and doesn't find
all unavoidables with 3 different digits.
I suspect Colin and Moschopulos already knew this but didn't
want to complain....
- dukuso
- Posts: 479
- Joined: 25 June 2005
by coloin » Fri Oct 21, 2005 10:43 am
dukuso wrote:>
>The 16er [with 2 solutions] - [transposed for comparison]
>
>---6--4--
>-7--8--4--
>-1-------
>----1---3
>4--------
>6-----2--
>5-24-----
>-----3-71
>---------
it's not just transposed (=reflected on the diagonal), I assume
you mean these two are isomorphic (wrt. the 9!*6^8*2 operations)
>the 8 in r2c5 can be in 9 other positions and there can also
>be 9 other positions for the 9.
>
>one of the the full grids is
>+---+---+---+
>|358|627|419|
>|974|185|326|
>|216|349|785|
>+---+---+---+
>|725|914|863|
>|483|562|197|
>|691|738|254|
>+---+---+---+
>|562|471|938|
>|849|253|671|
>|137|896|542|
>+---+---+---+ {12,16,32,36} {51,52,81,82} etc
I don't know what {12,16,32,36} {51,52,81,82} refers to.
Probably not unavoidables in above grid ?!
>There are a lot of similarities between the two grids
>
>C
yes, they are isomorphic. (says my computer)
All solutions in all the known 16-puzzles with 2 solutions
are isomorphic to sf.
I had missed some of the earlier discussion about sf,
so I don't know whether this were already mentioned.
-Guenter.
"transposed" should read "manipulated".....
{12,16,32,36} shoud read {12,16,22,26} are the coordinates of the 4 set in B1/B2 sorry - I will edit it.
I dont understand how all the puzzles in the 16 series are isomorphic to the SF puzzles..
Gfroyle said it was a "subgrid" of the SF but didnt eloborate.
That would mean that each of the 18 puzzles in the 16 with 2 solution series is equivalent to one of the SF puzzles. How strange indeed.
Ahhhhhhhhh.............
I get it now..............the SF puzzle that I used isnt one of the 18.
I dont believe this has been discussed openly.
The term unavoidable could be better described as "obligatory" or "mandatory".
Yes I have been spotting groups of 6 clue triple pair "unavoidable" sets without the nppcsu programs !
C
- coloin
- Posts: 2502
- Joined: 05 May 2005
- Location: Devon
by Moschopulus » Fri Oct 21, 2005 11:47 am
coloin wrote:The term unavoidable could be better described as "obligatory" or "mandatory".
Yes, or "essential". I don't mind changing as long as everybody uses the same word. We already changed from "exchangable" to "unavoidable". If everybody uses a different word then it gets confusing. Maybe it's too late to change now.
dukuso wrote:My program nppcsu3 is incomplete and doesn't find
all unavoidables with 3 different digits.
I suspect Colin and Moschopulos already knew this but didn't
want to complain....
Yes, I knew it didn't find all unavoidables but I think you said that ....
That's why I keep asking for a program to find *all* unavoidables of size <= k, where k could be 12 or 15 or 20.
One way is to find all possible configurations for each size.
gfroyle has a recursive procedure, posted earlier in the thread, which does very well although it didn't quite catch all the unavoidable sets for the SF grid.
- Moschopulus
- Posts: 256
- Joined: 16 July 2005
by Wolfgang » Fri Oct 21, 2005 11:54 am
coloin wrote:I dont understand how all the puzzles in the 16 series are isomorphic to the SF puzzles..
Those are the 18 (out of the 29) sudokus in gfroyles list isomorphic to the 16 clue with 2 solutions, the 9 and 5 are wandering around (but i have no program to calculate the transposition):
000040700080000000010000020000800006700000000400009200302070000000000000000006018
000040700080000000010000020000800906700000000400000200302070000000000000000006018
000040700080000000010000020000800006790000000400000200302070000000000000000006018
000040700080000000010000020000800006700000000400000200302070000000000000900006018
000040700080000000010000020000800006700000000400000200302070009000000000000006018
000040700080000000010000020000800006700000000400000200302070000000090000000006018
009040700080000000010000020000800006700000000400000200302070000000000000000006018
000040700080000000010900020000800006700000000400000200302070000000000000000006018
000040700080000090010000020000800006700000000400000200302070000000000000000006018
000040700080000000010000020000850006700000000400000200302070000000000000000006018
000040700080000000010000020000800006700000000450000200302070000000000000000006018
000040700080000000010000020000800006700000050400000200302070000000000000000006018
000040700080000000010000020000800006700000000400000200302070000000000000005006018
000040700080000000010000020000800006700000000400000200302070500000000000000006018
000040700080000000010000020000800006700000000400000200302070000000500000000006018
000040705080000000010000020000800006700000000400000200302070000000000000000006018
000040700080005000010000020000800006700000000400000200302070000000000000000006018
000040700080000000510000020000800006700000000400000200302070000000000000000006018
- Wolfgang
- Posts: 208
- Joined: 22 June 2005
by coloin » Fri Oct 21, 2005 12:59 pm
Thanks Wolfgang.....I have clocked it now
This is also unsolvable:
12.......
34.......
.........
21.......
43.......
.........
.........
.........
.........
C
dukuso wrote:Even this one
12.34....
34.12....
.........
21.43....
43.21....
.........
.........
.........
.........
has no solution
This is also unsolvable:
12.......
34.......
.........
21.......
43.......
.........
.........
.........
.........
C
Last edited by coloin on Fri Nov 18, 2005 7:28 pm, edited 1 time in total.
- coloin
- Posts: 2502
- Joined: 05 May 2005
- Location: Devon
by kjellfp » Fri Oct 21, 2005 2:16 pm
coloin wrote:This is also unsolvable:
12.......
34.......
.........
21.......
43.......
.........
.........
.........
.........
Can easily be seen: Box 3.1. (lower left) has only three positions for the numbers 1,2,3,4. Generally: If we can find two boxes and two columns in the same stack and four symbols such that each of the two columns contain all four symbols within the two boxes, then the grid is unsolvable.
Is this the simplest unsolvable sudoku that does not directly violate the laws of sudoku? (i.e. no multiples within the same column, row or box).
Edit: No, it isn't, if simple means as few cells filled as possible. This is simpler:
... ... ...
... ... ...
1.. ... ...
... ... ...
... ... ...
.1. ... ...
..2 ... ...
... 1.. ...
... ... 1..
- kjellfp
- Posts: 140
- Joined: 04 October 2005
by dukuso » Fri Oct 21, 2005 2:53 pm
Moschopulus wrote:coloin wrote:The term unavoidable could be better described as "obligatory" or "mandatory".
Yes, or "essential". I don't mind changing as long as everybody uses the same word. We already changed from "exchangable" to "unavoidable". If everybody uses a different word then it gets confusing. Maybe it's too late to change now.
I like mandatory. The word is rare enough here so not to cause
accidental confusion
dukuso wrote:My program nppcsu3 is incomplete and doesn't find
all unavoidables with 3 different digits.
I suspect Colin and Moschopulos already knew this but didn't
want to complain....
Yes, I knew it didn't find all unavoidables but I think you said that ....
you should have moaned louder !
I wouldn't have uploaded it if it were of sooo little use
That's why I keep asking for a program to find *all* unavoidables of size <= k, where k could be 12 or 15 or 20.
One way is to find all possible configurations for each size.
gfroyle has a recursive procedure, posted earlier in the thread, which does very well although it didn't quite catch all the unavoidable sets for the SF grid.
yes, now I also backtracked through all subsets to find all minimal
unavoidables. Worked quite well and I liked it, just only
that it was so slow.
How about finding mandatories for each of the 416 bands
and then using lookup for the 6 chutes in a grid ?
Plus maybe examining the 84 rookeries with 3 digits.
-Guenter
- dukuso
- Posts: 479
- Joined: 25 June 2005
by Moschopulus » Fri Oct 21, 2005 11:06 pm
dukuso wrote:you should have moaned louder !
I wouldn't have uploaded it if it were of sooo little use
No, no, it was very useful. And you told me it didn't find them all.
dukuso wrote:yes, now I also backtracked through all subsets to find all minimal
unavoidables. Worked quite well and I liked it, just only
that it was so slow.
How about finding mandatories for each of the 416 bands
and then using lookup for the 6 chutes in a grid ?
Plus maybe examining the 84 rookeries with 3 digits.
Yes, good. Still won't find them all, but it would be good.
I can find all of size 4 and 6, can post the code if you want.
It would be good to find all of size 8, 9, 10,11,12. (I think all size 7 ones are not minimal)
The small ones seem to have more effect when it comes to hitting sets.
It would be good to be able to take a 3-rookery and find all minimal unavoidables it contains.
- Moschopulus
- Posts: 256
- Joined: 16 July 2005
by Moschopulus » Fri Oct 21, 2005 11:12 pm
dukuso wrote:
Let me also call a set k-unavoidable if it is minimal
and k different symbols occur in it. Do 4-unavoidables exist ?
Maybe this is an example:
- Code: Select all
639|241|785
284|765|193
5..|983|624
---+---|---
123|857|946
796|432|851
458|619|237
---+---+---
3.2|.78|.69
86.|.94|372
9..|326|.18
...|...|... ...|...|...
...|...|... ...|...|...
.17|...|... .71|...|...
---+---+--- ---+---+---
...|...|... ...|...|...
...|...|... ...|...|...
...|...|... ...|...|...
---+---+--- ---+---+---
.4.|1..|5.. .1.|5..|4..
..1|5..|... ..5|1..|...
.75|...|4.. .47|...|5..
posted earlier by Red Ed
- Moschopulus
- Posts: 256
- Joined: 16 July 2005
