Sparse Sudoku's

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

Sparse Sudoku's

Postby Dr. Octagon » Wed Oct 01, 2014 7:01 pm

Is it possible to create a standard 9x9 Sudoku puzzle such that given clues don't touch either horizontally, vertically, or diagonally?
Dr. Octagon
 
Posts: 8
Joined: 30 March 2014

Re: Sparse Sudoku's

Postby blue » Wed Oct 01, 2014 8:36 pm

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
 
Posts: 573
Joined: 11 March 2013

Re: Sparse Sudoku's

Postby blue » Thu Oct 02, 2014 4:39 am

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
 
Posts: 573
Joined: 11 March 2013

Re: Sparse Sudoku's

Postby blue » Thu Oct 02, 2014 7:09 am

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 .
blue
 
Posts: 573
Joined: 11 March 2013

Re: Sparse Sudoku's

Postby m_b_metcalf » Thu Oct 02, 2014 8:03 am

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Re: Sparse Sudoku's

Postby m_b_metcalf » Thu Oct 02, 2014 9:09 am

m_b_metcalf wrote: 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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Re: Sparse Sudoku's

Postby blue » Thu Oct 02, 2014 5:13 pm

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.

m_b_metcalf wrote:
m_b_metcalf wrote: 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.
blue
 
Posts: 573
Joined: 11 March 2013

Re: Sparse Sudoku's

Postby m_b_metcalf » Thu Oct 02, 2014 6:22 pm

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

m_b_metcalf wrote:
m_b_metcalf wrote: 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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Re: Sparse Sudoku's

Postby Serg » Sat Oct 04, 2014 6:00 pm

Hi, Mike, blue!
Interesting results.
blue wrote: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
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: Sparse Sudoku's

Postby m_b_metcalf » Sat Oct 04, 2014 6:51 pm

Serg wrote:Hi, Mike, blue!
Interesting results.
blue wrote: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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Re: Sparse Sudoku's

Postby blue » Sat Oct 04, 2014 9:23 pm

Hi Serg,

Serg wrote: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.

Serg wrote:
blue wrote: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.

--

blue wrote: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.
Last edited by blue on Tue Oct 07, 2014 4:39 am, edited 1 time in total.
blue
 
Posts: 573
Joined: 11 March 2013

Re: Sparse Sudoku's

Postby Serg » Sun Oct 05, 2014 1:34 pm

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

Serg
Last edited by Serg on Mon Oct 06, 2014 5:20 am, edited 2 times in total.
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: Sparse Sudoku's

Postby Dr. Octagon » Sun Oct 05, 2014 7:10 pm

These puzzles are very pretty! Thanks for posting.
Dr. Octagon
 
Posts: 8
Joined: 30 March 2014


Return to General