The New Sudoku Players' Forum

[Dr. Octagon]

Is it possible to create a standard 9x9 Sudoku puzzle such that given clues don't touch either horizontally, vertically, or diagonally?

[blue]

Here's are two:

Code: Select all

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

Code: Select all

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

Added: one with all of the symmetries ...

Code: Select all

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

[blue]

Here's one with full symmetry and 5 empty houses.

Code: Select all

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

[blue]

Last one: has 2 or 3 clues in each house

Code: Select all

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

[m_b_metcalf]

Here's a set, rated (same pattern as blue's first one). 21 is the maximum number of clues. I imagine that the 17-clue data-base contains examples.

Regards,

Mike Metcalf

Code: Select all

 . 1 . 2 . 3 . 4 .
 . . . . . . . . .
 5 . . . 6 . . . 7
 . . 7 . . . 5 . .
 8 . . . 1 . . . 6
 . . 4 . . . 9 . .
 6 . . . 9 . . . 8
 . . . . . . . . .
 . 3 . 4 . 7 . 2 .   ED=2.6/1.5/1.5

 . 1 . 2 . 3 . 4 .
 . . . . . . . . .
 5 . . . 6 . . . 7
 . . 7 . . . 2 . .
 3 . . . 4 . . . 8
 . . 6 . . . 9 . .
 4 . . . 8 . . . 6
 . . . . . . . . .
 . 2 . 5 . 7 . 1 .   ED=3.4/1.5/1.5

 . 1 . 2 . 3 . 4 .
 . . . . . . . . .
 5 . . . 6 . . . 7
 . . 4 . . . 3 . .
 8 . . . 5 . . . 9
 . . 7 . . . 6 . .
 9 . . . 7 . . . 8
 . . . . . . . . .
 . 2 . 4 . 1 . 5 .   ED=7.1/1.5/1.5

 . 1 . 2 . 3 . 4 .
 . . . . . . . . .
 5 . . . 6 . . . 7
 . . 4 . . . 3 . .
 8 . . . 5 . . . 9
 . . 2 . . . 6 . .
 9 . . . 8 . . . 1
 . . . . . . . . .
 . 3 . 7 . 4 . 5 .   ED=7.2/2.6/2.6

 . 1 . 2 . 3 . 4 .
 . . . . . . . . .
 5 . . . 6 . . . 7
 . . 3 . . . 6 . .
 8 . . . 5 . . . 2
 . . 9 . . . 1 . .
 6 . . . 9 . . . 8
 . . . . . . . . .
 . 4 . 7 . 1 . 3 .   ED=8.3/1.5/1.5

 . 1 . 2 . 3 . 4 .
 . . . . . . . . .
 5 . . . 6 . . . 7
 . . 2 . . . 1 . .
 8 . . . 7 . . . 5
 . . 3 . . . 9 . .
 6 . . . 4 . . . 2
 . . . . . . . . .
 . 7 . 5 . 1 . 3 .   ED=8.3/2.6/2.6


[m_b_metcalf]

I imagine that the 17-clue data-base contains examples.

... but it doesn't!

Here are some 19-clue puzzles:

Code: Select all

 . 5 . . . . . 8 .
 . . . 6 . 7 . . .
 . . . . . . . . 9
 . . 4 . 9 . 6 . .
 7 . . . . . . . 1
 . . 8 . 3 . 7 . .
 6 . . . . . . . 7
 . . . 2 . 5 . . .
 . 1 . . . . . 9 .   ED=6.6/1.2/1.2

 . 1 . 2 . 3 . 4 .
 . . . . . . . . .
 5 . . . . . . . 6
 . . 7 . . . 3 . .
 8 . . . 6 . . . .
 . . 5 . . . 1 . .
 2 . . . 8 . . . 5
 . . . . . . . . .
 . 6 . 4 . 1 . 3 .   ED=2.0/1.2/1.2

 . 1 . 2 . 3 . 4 .
 . . . . . . . . .
 5 . . . . . . . 6
 . . 7 . . . 2 . .
 6 . . . 7 . . . 5
 . . 5 . . . . . .
 8 . . . 6 . . . 9
 . . . . . . . . .
 . 2 . 4 . 7 . 3 .   ED=2.6/1.5/1.5

 . . . 1 . 2 . 3 .
 . . . . . . . . .
 4 . . . 5 . . . 6
 . . 3 . . . 5 . .
 5 . . . 1 . . . 4
 . . 2 . . . 7 . .
 7 . . . 4 . . . .
 . . . . . . . . .
 . 8 . 9 . 3 . 6 .   ED=6.7/1.2/1.2

Does 18 exist?

Regards,

Mike Metcalf

[blue]

22 clues is possible.

Code: Select all

. 2 . 3 . 1 . 4 .
. . . . . . . . .
3 . 6 . . . 5 . 9
. . . . 4 . . . .
8 . 1 . . . 6 . 7
. . . . 5 . . . .
5 . 7 . . . 9 . 4
. . . . . . . . .
. 3 . 8 . 6 . 2 .   ED=2.6/1.2/1.2

. . . 8 . 7 . . .
2 . . . . . . . 7
. . 1 . 4 . 5 . .
4 . . . . . . . 3
. . 3 . 8 . 1 . .
9 . . . . . . . 6
. . 4 . 3 . 2 . .
6 . . . . . . . 9
. . 8 . 1 . 4 . .   ED=2.8/1.5/1.5

. 3 . 1 . 2 . 5 .
. . . . . . . . .
. 2 . 5 . 9 . 3 .
. . . . . . . . .
8 . 4 . . . 9 . 1
. . . . 8 . . . .
3 . 9 . . . 6 . 8
. . . . 7 . . . .
1 . 2 . . . 3 . 4   ED=2.6/2.0/2.0

. . 3 . 4 . 2 . .
7 . . . . . . . 9
. . 2 . 5 . 8 . .
1 . . . . . . . 7
. . 4 . 8 . 6 . .
2 . . . . . . . 5
. . 8 . 7 . 5 . .
. . . . . . . . .
. 5 . 8 . 9 . 1 .   ED=2.8/1.5/1.5

I think 23+ is impossible -- not that the shapes don't exist, just that they don't have puzzles.

I imagine that the 17-clue data-base contains examples.

... but it doesn't!

Does 18 exist?

I wondered if the symmetric 18's thread might contain some examples, but I didn't check.

[m_b_metcalf]

22 clues is possible.
[snip]
I think 23+ is impossible -- not that the shapes don't exist, just that they don't have puzzles.

I imagine that the 17-clue data-base contains examples.

... but it doesn't!

Does 18 exist?

I wondered if the symmetric 18's thread might contain some examples, but I didn't check.

Yes, missed the 22 patterns.

I checked the symmetric 18s and there is none.

Regards,

Mike

[Serg]

Hi, Mike, blue!
Interesting results.

I think 23+ is impossible -- not that the shapes don't exist, just that they don't have puzzles.

blue, I could not find at least one possible 23-clue pattern! Do you know any?

Mike, did you check 17-clue and 18-clue puzzle by applying all possible isomorphic transformation? Did you check both vertically and double diagonal symmetric 18-clue puzzles?

Serg

[m_b_metcalf]

Hi, Mike, blue!
Interesting results.

I think 23+ is impossible -- not that the shapes don't exist, just that they don't have puzzles.

blue, I could not find at least one possible 23-clue pattern! Do you know any?

Mike, did you check 17-clue and 18-clue puzzle by applying all possible isomorphic transformation? Did you check both vertically and double diagonal symmetric 18-clue puzzles?

Serg

Serg,
The 23-clue patterns consist mainly of straight lines which fail to cover the UAs (sorry, I'm away from home, so don't have my examples).

For the 17-clue puzzles, I selected those, about 20, that had the fewest (3) direct neighbours and tried to reduce that number by hand -- and failed. Once again, I'm away from home so can't show you the data set.

Regards,

Mike

[blue]

Hi Serg,

Mike, did you check 17-clue and 18-clue puzzle by applying all possible isomorphic transformation? Did you check both vertically and double diagonal symmetric 18-clue puzzles?

I did do that, for all of those puzzles.

I think 23+ is impossible -- not that the shapes don't exist, just that they don't have puzzles.

blue, I could not find at least one possible 23-clue pattern! Do you know any?

I'm not sure what you mean by "possible", but there are examples like these two, that are impossible in the end, since they can be mapped to subsets of the 3rd pattern (which is known to not have puzzles):

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 | . 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 . | 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 |
| . . . | . . . | . . x |
+-------+-------+-------+
| x x x | . x . | x x x |
| x x x | . x . | x x x |
| x x x | x x x | x x x |
+-------+-------+-------+


I wrote a program to find that largest possible patterns that could not be transformed to a subset of a known shape that doesn't have puzzles, and 22 was the largest size that it found. My "known shapes" list, though, contains some shapes that haven't been double checked by anyone else [ double checked by you, in particular ! ]. That's why I phrased it like "I think [that] ...".

On the other hand, it's possible that the only "known shapes" that were used, were ones that you have double checked.
The program ran for several hours (> 12). I'll run it again, and come back with some more details.

--

I'll run it again, and come back with some more details.

For sizes >= 22, it turns out that these 4 patterns, were the only ones used.

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 x x |
+-------+-------+-------+
| . . . | . . . | . . . |
| x x x | x x x | x x x |    22's, 23's, all 24+
| . . . | . . . | . . . |
+-------+-------+-------+
| 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 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 x x | . x . | x x x |    22's, 23's
| . . . | . 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 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 . | x x x |    22's, remaining 23's
| . . . | . . . | . . 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 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 x x |    22's only
| . . . | . . x | . . . |
+-------+-------+-------+
| x x x | . x . | x x x |
| x x x | . x . | x x x |
| x x x | . x . | x x x |
+-------+-------+-------+

That left 1417 (ED) size 22 patterns.
Almost all of those, have puzzles -- 1409 for sure.

[Serg]

Hi, blue!
Very impressive work!(And done surprisingly fast .)

Serg

[Dr. Octagon]

These puzzles are very pretty! Thanks for posting.