Extra feature

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

Postby Hammerite » Mon Jul 04, 2005 9:59 pm

I think aloud, and make a (fairly trivial) observation.

The total number of "diagonals", using our definition of the word is 34, that is, 17 in each direction. (There are 8 "shorter" diagonals either side of the "longest" diagonal in each direction; 2 x 8 + 1 = 17). But 12 of these diagonals are irrelevant. These 12 are the 4 groups of 3 nearest each corner: each 3x3 box at a corner of the puzle contains 3 of our diagonals. Now since these diagonals are within a box, the grid satisfying the "normal" su doku properties implies that it will satisfy the property we desire for these 12 diagonals too (because no digit is repeated within the box, so no digit will be repeated within a diagonal). So one way of looking at it is that we only need consider the 22 diagonals (11 in each direction) that aren't wholly within a box.
Hammerite
 
Posts: 44
Joined: 20 June 2005

Postby dukuso » Tue Jul 05, 2005 2:41 pm

here is a randomly generated 12*12 diagonal sudoku.
Fill in letters A,B,C,D,E,F,G,H,I,J,K,L, such that
no letter appears more than once in any of the 12 rows,
12 columns, 46 diagonals.
This could be very hard.
11 clues are sufficient for a unique solution but
more clues were added to make it easier.
Diagonal sudokus of size smaller than 12*12 are trivial.
Only 5*5,7*7,11*11 are possible.

Image
Last edited by dukuso on Sun Jul 10, 2005 11:56 am, edited 2 times in total.
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby lunababy_moonchild » Sat Jul 09, 2005 10:52 am

Deleted because I felt it wasn't relevant, or interesting.

Luna
Last edited by lunababy_moonchild on Sun Jul 10, 2005 3:22 am, edited 1 time in total.
lunababy_moonchild
 
Posts: 659
Joined: 23 March 2005

Postby udosuk » Sun Jul 17, 2005 5:48 pm

Condor, after I solved your initial puzzle (7 of 9 digits having no duplication on long/short diagonals), I discover that it is in fact not the "unique sudoku" as you claimed. Of course you picked 2 & 4 as the remaining 2 digits. So if you look at the completed grid, you can noticed that these 2 digits are subdivided into 2 different groups:

1. 4 diagonal pairs (8 in total) in the 4 corners;

2. 10 alternating ones forming a ring around the centre.

And these 2 groups are NOT dependent on each other. So in fact you can swap the 2 & 4 in one of the group while keeping the other group fixed. That way an essentially different grid is created.

To show this fact, I rearranged the grid as follows:

Code: Select all
+ 2 3 4 8 7 6 + 9
4 + 6 2 9 3 8 7 +
7 8 9 + + 6 4 3 2
9 3 + 8 7 + 2 6 4
6 4 + 3 2 9 + 8 7
8 7 2 + 6 4 + 9 3
2 9 8 7 + + 3 4 6
+ 6 4 9 3 2 7 + 8
3 + 7 6 4 8 9 2 +


Here you can fill the grid with 1 & 5 in 2 essentially distinct ways.

Sorry for not able to help you in the programming area to verify the main result. But it would be a truly remarkable discovery if these 2 turn out to be the only existing patterns of this feature!
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby udosuk » Sun Jul 17, 2005 6:29 pm

As for the "12x12 diagonal sudoku" posted by dukuso, for it to be called a "sudoku" there must be boxes aside with rows, columns and diagonals. So could you specify whether the 12 3x4 (or 2x6 or 4x3 or 6x2) boxes are each filled with the letters a to l? (Or if ALL of the 4 types are?)

Anyway this is too hard for human to solve with only 14 clues provided. I don't even know what the next step is. Could you shred some lights? Or is it supposed to be solved by programs only?
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby dukuso » Sun Jul 17, 2005 9:49 pm

udosuk wrote:As for the "12x12 diagonal sudoku" posted by dukuso, for it to be called a "sudoku" there must be boxes aside with rows,
columns and diagonals. So could you specify whether the 12 3x4 (or 2x6 or 4x3 or 6x2) boxes are each filled with the letters a to l? (Or if ALL of the 4 types are?)

Anyway this is too hard for human to solve with only 14 clues provided. I don't even know what the next step is. Could you shred some lights? Or is it supposed to be solved by programs only?




propose a better name !
There are already lots of constraints, more constraints will
further reduce the number of grids.
Next step = more clues, until someone solves it.
Programs should be able to solve it, although I just took
my list of all 454 possible grids.

I haven't tried to solve it myself, so how many clues do you suggest
to add ?
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby udosuk » Mon Jul 18, 2005 5:02 pm

propose a better name !
There are already lots of constraints, more constraints will
further reduce the number of grids.
Next step = more clues, until someone solves it.
Programs should be able to solve it, although I just took
my list of all 454 possible grids.

I haven't tried to solve it myself, so how many clues do you suggest
to add ?


It could be called a "12x12 diagonal Latin square" or something along that line... Latin squares have been studied for hundreds of years and I think Euler has a famous story with it (or is it Latin-Greco squares?)

Anyway what makes sudoku so popular is that the boxes makes it looks so elegant and players are able to visually spot so many different types of logical rules. With only rows, columns and diagonals it becomes more algebraic and combinatoric and more difficult to solve without a computer. Just my personal opinions so don't feel too serious about them...

As for the number of clues, I guess at least one clue per each row/column/diagonal is needed, then have a look whether it's too many or too few...

But frankly compared to sudoku I don't have much interest in these types of puzzles... Pardon me...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby dukuso » Tue Jul 19, 2005 6:11 am

>It could be called a "12x12 diagonal Latin square" or something
>along that line...

OK. Or maybe "(chess-)queen's square"

>Anyway what makes sudoku so popular is that the boxes makes it looks
>so elegant and players are able to visually spot so many different
>types of logical rules. With only rows, columns and diagonals it
>becomes more algebraic and combinatoric and more difficult to solve
>without a computer. Just my personal opinions so don't feel too
>serious about them...

that could be, because the human eye can follow the compact boxes
more easily than the long diagonals, even with checkered grids.
But logically/mathematically the boxes are not so satisfying
since a row and a box intersect in 3 cells and not one.
The best would probably be "pandiagonals", but then the human
eye won't like to join the two broken diagonal parts.
And also there are only few such pandiagonal latin squares,
so maybe you'd switch to a hexagonal grid ?!

>As for the number of clues, I guess at least one clue per each
>row/column/diagonal is needed, then have a look whether it's
>too many or too few...

that would be about 30 clues ? OK, so far I've added 3 per week
I'll redouble this.

>But frankly compared to sudoku I don't have much interest
>in these types of puzzles... Pardon me...

is it just because the diagonals are harder to follow
with the eye or is it also because it requires more "guessing"
than normal sudokus ? (does it ?)
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby udosuk » Tue Jul 19, 2005 8:27 am

I guess you need to formulate and demonstrate a few tricks/rules to solve this type of puzzles to get people interested...

Anyway have you tried to verify Condor's result in the first place? Would really like to know if his example (and the twisted alternative) are the unique ones for its class...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby dukuso » Tue Jul 19, 2005 9:41 am

udosuk wrote:I guess you need to formulate and demonstrate a few tricks/rules to solve this type of puzzles to get people interested...

Anyway have you tried to verify Condor's result in the first place? Would really like to know if his example (and the twisted alternative) are the unique ones for its class...


make the graph whose vertices are the solutions of the 9-queens-problem
and there is an edge between two solutions, iff they are disjoint sets.

This graph has

maximal cliques:0 0 0 0 4260 6480 3744

cliques:81 1896 16200 52992 64416 26928 3744

so, there are 3744 disjoint sets of 7 9-queen solutions.



I see, it is also required that there are no 2 queens with same
symbol in the same block. Then I get:

maximal cliques:0 0 0 0 4284 6264 2916
cliques:81 1872 15552 48744 56016 21996 2916


edited July 22 : this is all completely wrong, see below in the thread
Last edited by dukuso on Fri Jul 22, 2005 2:36 pm, edited 1 time in total.
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby udosuk » Tue Jul 19, 2005 4:28 pm

Does that mean there should be 2916 sets of 7 9-queen solutions?

How about 8 9-queen and perfect 9-queen?
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby dukuso » Tue Jul 19, 2005 7:47 pm

perfect = suduko-queen ?

no 8 disjoint sets for either queen
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby udosuk » Thu Jul 21, 2005 6:58 pm

Hi dukuso, of the 2916 sets of 7 9-queen solutions, could you show 1 grid which is essentially different to the examples by Condor? That will give a satisfying end to this thread... Thanks!
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Condor » Fri Jul 22, 2005 12:00 am

udosuk wrote:I discovered that it is in fact not the "unique sudoku" as you claimed.


udosuk you are right. I guess I was so busy looking at the 7 digits with the extra feature that I didn't check the other 2 digits properly, I inserted them by hand. So only the 7 digits is unique.

It is still a remarkable discovery, but my original aim was for all 9 digits. I found out that 7 was the max.

You have discovered something very interesting yourself. I have never seen a sudoku that you can take 2 digits and swap some while keeping the others where they were and still end up with a valid sudoku.
Condor
 
Posts: 62
Joined: 19 June 2005

Postby udosuk » Fri Jul 22, 2005 1:25 pm

You're right it would be a very remarkable discovery if those twin grids turned out to be unique. But I'm afraid dukuso is going to find some counterexamples that there are other grids with this feature... But you still did a great job in proving that 7 is the best you can do as long as keeping the digits not repeated in each diagonals...
udosuk
 
Posts: 2698
Joined: 17 July 2005

PreviousNext

Return to General

cron