Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Disjoint groups in addition to rows, columns and boxes
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Exotic sudoku
View previous topic :: View next topic  
Author Message
chuckfresno

Joined: 16 Jun 2005
Posts: 39
:

Items
PostPosted: Thu Jun 16, 2005 5:44 pm    Post subject: Disjoint groups in addition to rows, columns and boxes Reply with quote

At first blush, the following puzzle seems to have insufficient information to give a unique solution, however, it actually does have one and only one solution and is of medium difficulty:

Code:

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


Each cell in this Sudoku is a member of FOUR groups rather than the normal THREE (rows, columns and 3x3 boxes). The fourth groups are:


Code:

a b c | a b c | a b c
d e f | d e f | d e f
g h i | g h i | g h i
------+-------+------
a b c | a b c | a b c
d e f | d e f | d e f
g h i | g h i | g h i
------+-------+------
a b c | a b c | a b c
d e f | d e f | d e f
g h i | g h i | g h i



(To be clear, no two cells with the same letter will contain the same digit in the solution.)

This variation is common in several Japanese Number Place magazines. They're printed in color, with each cell in the same disjoint group sharing the same color.

An interesting question is -- can the number of clues given for this variant be reduced from the 17 clue record for a standard Sudoku? (18 for a standard symmetric Sudoku). Each clue gives the solver more information, as it interacts with 24 other cells instead of only 20 in a normal Sudoku.
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Thu Jul 14, 2005 8:48 am    Post subject: Re: Disjoint groups in addition to rows, columns and boxes Reply with quote

chuckfresno wrote:
At first blush, the following puzzle seems to have insufficient information to give a unique solution, however, it actually does have one and only one solution and is of medium difficulty:

Code:

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


Each cell in this Sudoku is a member of FOUR groups rather than the normal THREE (rows, columns and 3x3 boxes). The fourth groups are:


Code:

a b c | a b c | a b c
d e f | d e f | d e f
g h i | g h i | g h i
------+-------+------
a b c | a b c | a b c
d e f | d e f | d e f
g h i | g h i | g h i
------+-------+------
a b c | a b c | a b c
d e f | d e f | d e f
g h i | g h i | g h i



(To be clear, no two cells with the same letter will contain the same digit in the solution.)

This variation is common in several Japanese Number Place magazines. They're printed in color, with each cell in the same disjoint group sharing the same color.

An interesting question is -- can the number of clues given for this variant be reduced from the 17 clue record for a standard Sudoku? (18 for a standard symmetric Sudoku). Each clue gives the solver more information, as it interacts with 24 other cells instead of only 20 in a normal Sudoku.




probably yes. I haven't tried it yet, maybe I'll try it tonight.
Instead of the 2 constraints with blocks, you can require that
no symbol occurs twice in any of the (n+n-1) diagonals.
In that case 11 clues are sufficient for a 12*12 puzzle.
For 5,7,11 there are only the trivial doubly cyclic solutions,
for n=2,3,6,8,9,10 there is no solution at all.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
chuckfresno

Joined: 16 Jun 2005
Posts: 39
:

Items
PostPosted: Fri Jul 15, 2005 11:28 pm    Post subject: Re: Disjoint groups in addition to rows, columns and boxes Reply with quote

dukuso wrote:

probably yes. I haven't tried it yet, maybe I'll try it tonight.
Instead of the 2 constraints with blocks, you can require that
no symbol occurs twice in any of the (n+n-1) diagonals.
In that case 11 clues are sufficient for a 12*12 puzzle.
For 5,7,11 there are only the trivial doubly cyclic solutions,
for n=2,3,6,8,9,10 there is no solution at all.


Are you saying that a 12 x 12 puzzle can be made with only 11 clues if all diagonals going one direction are used? (!)

By (n+n-1) diagonals, do you mean that the fourth groups would be:

Code:

a b c d e f g h i j k l
b c d e f g h i j k l a
c d e f g h i j k l a b
d e f g h i j k l a b c
e f g h i j k l a b c d
f g h i j k l a b c d e
g h i j k l a b c d e f
h i j k l a b c d e f g
i j k l a b c d e f g h
j k l a b c d e f g h i
k l a b c d e f g h i j
l a b c d e f g h i j k
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sat Jul 16, 2005 1:22 am    Post subject: Reply with quote

no, what you gave would be called "pandiagonals".
In that case you could probably also make puzzles with n-1
clues and a unique solution. But the smallest interesting size
would be 13*13 or 17*17.

My 12*12 puzzle, when solved, would look like a configuration
of 12 sets of 12 chess-queens , with no 2 queens
in any of the sets attacking each other.

See:
http://magictour.free.fr/sudo12.jpg
actually 14 clues, I started with 11 but will have to add further
clues, since it's probably too difficult else.

see also:
http://www.cs.concordia.ca/~chvatal/queengraphs.html


I forgot to examine how many clues are needed for your puzzle,
maybe later...
Back to top
View user's profile Send private message Send e-mail Visit poster's website
chuckfresno

Joined: 16 Jun 2005
Posts: 39
:

Items
PostPosted: Sat Jul 16, 2005 4:04 am    Post subject: Reply with quote

dukuso wrote:
no, what you gave would be called "pandiagonals".
In that case you could probably also make puzzles with n-1
clues and a unique solution. But the smallest interesting size
would be 13*13 or 17*17.


1) Why n-1 clues?
2) Why would the smallest interesting size be that large? What do you mean by "interesting"? Why not 8x8 or 9x9?
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sat Jul 16, 2005 12:25 pm    Post subject: Reply with quote

chuckfresno wrote:
dukuso wrote:
no, what you gave would be called "pandiagonals".
In that case you could probably also make puzzles with n-1
clues and a unique solution. But the smallest interesting size
would be 13*13 or 17*17.


1) Why n-1 clues?
2) Why would the smallest interesting size be that large? What do you mean by "interesting"? Why not 8x8 or 9x9?


1) n-1 is the minimum. n-2 is not possible since two symbols
were unused and you could always swap these for at least
two different solutions
2) there are pandiagonal latin squares of order n, iff neither
2 nor 3 divides n. So 8*8 or 9*9 are impossible.
All PLS of order <12 are "linear" : A(x,y)=(c*x+d*y+e) mod n
for constants c,d,e. They are easy to construct and to find
since they expand cyclically in both directions
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sat Jul 16, 2005 8:36 pm    Post subject: Reply with quote

generating random sudokus and then deleting as many clues as possible
such that there is still a unique solution,
I remain with 24 clues in average for the normal sudoku.
For your version with the additional constraint it's 18 clues,
minimum was 16 with 100 tries.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
chuckfresno

Joined: 16 Jun 2005
Posts: 39
:

Items
PostPosted: Sat Jul 16, 2005 11:00 pm    Post subject: Reply with quote

I’m confused. Tell me where I misunderstand.

A standard Sudoku solution has 3 groups: rows, columns and boxes.

A common variant published in Japanese’s Number Place magazines includes a fourth group. Call it “disjoint box”:

This type of puzzle has four simultaneous groups:
Code:

Row       Column    Box       Disjoint box
a a a a   a b c d   a a b b   a b a b
b b b b   a b c d   a a b b   d e d e
c c c c   a b c d   c c d d   a b a b
d d d d   a b c d   c c d d   d e d e


The cells of the disjoint box groups are color coded for easier solving.

This order 4 square has all four groups:
Code:

1 2 3 4
3 4 1 2
2 1 4 3
4 3 2 1


Here’s an order 9 example:
Code:

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





If I understand the way you are using “pan-diagonal”, then a pan-diagonal square of order five would have these four groups:

Code:

Rows --         Columns --      Right and left broken diagonals --
a a a a a       a b c d e       a b c d e      e a b c d
b b b b b       a b c d e       b c d e a      d e a b c
c c c c c       a b c d e       c d e a b      c d e a b
d d d d d       a b c d e       d e a b c      b c d e c
e e e e e       a b c d e       e a b c d      a b c d e



This order 5 square has all four groups:
Code:

2 3 4 5 1
4 5 1 2 3
1 2 3 4 5
3 4 5 1 2
5 1 2 3 4



Is this different from the 5 sets of 5 non-attacking queens?

Order 9 pan-diagonal squares are impossible, right?

Order 11 IS possible:

Order 11 4 group pan-diagonal solution:
Code:

1 2 3 4 5 6 7 8 9 t e
3 4 5 6 7 8 9 t e 1 2
5 6 7 8 9 t e 1 2 3 4
7 8 9 t e 1 2 3 4 5 6
9 t e 1 2 3 4 5 6 7 8
e 1 2 3 4 5 6 7 8 9 t
2 3 4 5 6 7 8 9 t e 1
4 5 6 7 8 9 t e 1 2 3
6 7 8 9 t e 1 2 3 4 5
8 9 t e 1 2 3 4 5 6 7
t e 1 2 3 4 5 6 7 8 9


Ignoring the difficulty that the solver might have keeping track of the broken diagonals, is there another reason that this size could not be used? Is it that there are too few pan-diagonal order 11 squares? If it *can* work, it seems like the best size as it's only about 50% larger than the standard size.

dukuso wrote:


...Instead of the 2 constraints with blocks, you can require that
no symbol occurs twice in any of the (n+n-1) diagonals.


What do you mean by “(n+n-1) diagonals”.

How is this different from what you call "pan-diagonal"?

Are you suggesting that the fourth group be something like:

Code:

b c d e a
d e a b c
a b c d e
c d e a b
e a b c d


This would seem very difficult for the solver to keep track of, even if the grid was color coded. And if it weren't color coded, is it up to the solver to discover which cell belongs to which disjoint-non-attacking-queen group?

Digressing, a fifth group can be added to the above order 5 square:
Code:

+---+---------------+
| 2   3 | 4   5   1 |
|       +---+       +
| 4   5 | 1 | 2   3 |
|   +---+   +---+---|
| 1 | 2   3   4 | 5 |
|---+---+   +---+   |
| 3   4 | 5 | 1   2 |
+       +---+       |
| 5   1   2 | 3   4 |
+---------------+---+


An order 7 or 11 puzzle could have polyomino or disjoint groups as well. Polyomino groups are also popular in the Japanese magazines, either instead of the standard box group, or an incomplete set of polyomino and/or disjoint groups in addition to all the normal groups.

For example, this puzzle:

Code:

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


... has the standard row, column and box groups, but cannot be solved without using these four additional groups, each of which must have the digits 1-9 in the solution:

Code:

. . a a . . . . .
. a a . . b b b .
a . . . . b b b .
. a a . . b b b .
. . a a . c c . .
. d d d . . c c .
. d d d . . . . c
. d d d . . c c .
. . . . . c c . .
Back to top
View user's profile Send private message
chuckfresno

Joined: 16 Jun 2005
Posts: 39
:

Items
PostPosted: Sun Jul 17, 2005 12:48 am    Post subject: Reply with quote

dukuso wrote:
generating random sudokus and then deleting as many clues as possible
such that there is still a unique solution,
I remain with 24 clues in average for the normal sudoku.
For your version with the additional constraint it's 18 clues,
minimum was 16 with 100 tries.


On average, how often do you get a 17 while generating normal sudoku?


Last edited by chuckfresno on Mon Jul 18, 2005 4:49 am; edited 1 time in total
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sun Jul 17, 2005 10:22 am    Post subject: Reply with quote

with that program, which is not very fast, I got:

9,19,29,31,9,2,0,0,1 special sudokus with 16,..,24 clues
and 3,30,37,19,9,2 normal sudokus with 22,..,27 clues
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Michael Kennett

Joined: 21 Jul 2005
Posts: 11
:
Location: Adelaide, South Australia

Items
PostPosted: Thu Jul 21, 2005 7:51 am    Post subject: Re: Disjoint groups in addition to rows, columns and boxes Reply with quote

[quote="chuckfresno"]At first blush, the following puzzle seems to have insufficient information to give a unique solution, however, it actually does have one and only one solution and is of medium difficulty:

Code:

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

[/quote="chuckfresno"]

I've just run your board through my solver, and found more than one solution (indeed, got 488!). The first 6 solutions that were generated (with fixed digits in parenthesis) are reproduced below.

Is the original board missing a digit?

Code:
 3 8 5 | 6 2(1)| 7 9 4
 6(2)9 | 8(7)4 | 5(3)1
 7 1(4)| 3 9 5 |(2)8 6
-------+-------+-------
(8)9 7 |(5)3(6)| 4 1(2)
 4 5 6 | 2(1)9 | 8 7 3
(1)3 2 |(4)8(7)| 6 5(9)
-------+-------+-------
 9 6(3)| 7 4 8 |(1)2 5
 2(4)8 | 1(5)3 | 9(6)7
 5 7 1 |(9)6 2 | 3 4 8

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

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

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

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

 3 8 9 | 6 2(1)| 5 4 7
 6(2)5 | 8(7)4 | 9(3)1
 7 1(4)| 3 9 5 |(2)8 6
-------+-------+-------
(8)9 7 |(5)3(6)| 4 1(2)
 4 5 6 | 2(1)9 | 3 7 8
(1)3 2 |(4)8(7)| 6 5(9)
-------+-------+-------
 2 6(3)| 7 4 8 |(1)9 5
 9(4)8 | 1(5)2 | 7(6)3
 5 7 1 |(9)6 3 | 8 2 4
Back to top
View user's profile Send private message Visit poster's website
jaap

Joined: 13 Jun 2005
Posts: 24
:
Location: NL

Items
PostPosted: Thu Jul 21, 2005 9:04 am    Post subject: Re: Disjoint groups in addition to rows, columns and boxes Reply with quote

Michael Kennett wrote:
chuckfresno wrote:
At first blush, the following puzzle seems to have insufficient information to give a unique solution, however, it actually does have one and only one solution and is of medium difficulty:


I've just run your board through my solver, and found more than one solution (indeed, got 488!). The first 6 solutions that were generated (with fixed digits in parenthesis) are reproduced below.

Is the original board missing a digit?


Did you read the part in that post about the extra groups? In the first solution you give, there are 2s at (6,3) and (9,6), violating those extra constraints. In the second, (1,7) and (7,4) are both 7s. The other solutions you quote similarly do not satisfy the extra group constraints.
_________________
Jaap
--
Jaap's Puzzle Page:
http://www.geocities.com/jaapsch/puzzles
Back to top
View user's profile Send private message Visit poster's website
Michael Kennett

Joined: 21 Jul 2005
Posts: 11
:
Location: Adelaide, South Australia

Items
PostPosted: Thu Jul 21, 2005 10:19 am    Post subject: Reply with quote

Thanks for the clarification - I misunderstood the original posting.
Back to top
View user's profile Send private message Visit poster's website
chuckfresno

Joined: 16 Jun 2005
Posts: 39
:

Items
PostPosted: Sat Jul 23, 2005 5:49 am    Post subject: Reply with quote

Why not modify your solver/gererator to handle this type of Sudoku variant? I think you'd be the first.

I really like your idea of using templates to design the look of the puzzles exactly, rather than just symmetrical, but randomly placed, clues that most everyone else uses. This makes it simple to create non-symmetrical patterns in bulk like:
Code:

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


... or one with someone's initials:

Code:

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




Templates might also be used to used to create an entirerly different Sudoku variant:


Code:

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


Instead of 3x3 boxes, 9 irregularly shaped areas are used. These are a very common variant in some of the Japanese puzzle mgazines.

Both these variations are currently hard to find outside of Japanese publications.
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sat Jul 23, 2005 7:41 am    Post subject: Reply with quote

>Posted: Sat Jul 16, 2005 11:00 pm Post subject:
>

sorry, I had missed this post.


>
>
>I'm confused. Tell me where I misunderstand.
>
>A standard Sudoku solution has 3 groups: rows, columns and boxes.
>
>A common variant published in Japanese’s Number Place magazines
>includes a fourth group. Call it “disjoint box”:
>
>This type of puzzle has four simultaneous groups:
>Code:
>
>Row Column Box Disjoint box
>a a a a a b c d a a b b a b a b
>b b b b a b c d a a b b d e d e
>c c c c a b c d c c d d a b a b
>d d d d a b c d c c d d d e d e
>
>
>
>The cells of the disjoint box groups are color coded for easier solving.
>
>This order 4 square has all four groups:
>Code:
>
>1 2 3 4
>3 4 1 2
>2 1 4 3
>4 3 2 1
>
>
>
>Here’s an order 9 example:
>Code:
>
>1 2 3 4 5 6 7 8 9
>4 5 6 7 8 9 1 2 3
>7 8 9 1 2 3 4 5 6
>2 3 4 5 6 7 8 9 1
>5 6 7 8 9 1 2 3 4
>8 9 1 2 3 4 5 6 7
>3 4 5 6 7 8 9 1 2
>6 7 8 9 1 2 3 4 5
>9 1 2 3 4 5 6 7 8
>
>
>


yes.


>
>
>
>If I understand the way you are using “pan-diagonal”,
>then a pan-diagonal square of order five would have these four groups:
>
>Code:
>
>Rows -- Columns -- Right and left broken diagonals --
>a a a a a a b c d e a b c d e e a b c d
>b b b b b a b c d e b c d e a d e a b c
>c c c c c a b c d e c d e a b c d e a b
>d d d d d a b c d e d e a b c b c d e c
>e e e e e a b c d e e a b c d a b c d e
>
>
>
>
>This order 5 square has all four groups:
>Code:
>
>2 3 4 5 1
>4 5 1 2 3
>1 2 3 4 5
>3 4 5 1 2
>5 1 2 3 4
>
>
>
>
>Is this different from the 5 sets of 5 non-attacking queens?


it's a collection of 5 disjoint sets of nonattacking (pan-) queens


>Order 9 pan-diagonal squares are impossible, right?

yes.

>Order 11 IS possible:

yes

>Order 11 4 group pan-diagonal solution:
>Code:
>
>1 2 3 4 5 6 7 8 9 t e
>3 4 5 6 7 8 9 t e 1 2
>5 6 7 8 9 t e 1 2 3 4
>7 8 9 t e 1 2 3 4 5 6
>9 t e 1 2 3 4 5 6 7 8
>e 1 2 3 4 5 6 7 8 9 t
>2 3 4 5 6 7 8 9 t e 1
>4 5 6 7 8 9 t e 1 2 3
>6 7 8 9 t e 1 2 3 4 5
>8 9 t e 1 2 3 4 5 6 7
>t e 1 2 3 4 5 6 7 8 9
>

yes


>
>Ignoring the difficulty that the solver might have keeping track
>of the broken diagonals,

no problem for the computer

>is there another reason that this size
>could not be used? Is it that there are too few pan-diagonal
>order 11 squares? If it *can* work, it seems like the best
>size as it's only about 50% larger than the standard size.

the reason is, that all rows or columns are just a shifted
version of the 1st row or column. And always bey the same amount.
So this is pretty easy to find.
Every solution of size 11 is of this type.

>dukuso wrote:
>
>
>...Instead of the 2 constraints with blocks, you can require that
>no symbol occurs twice in any of the (n+n-1) diagonals.
>
>
>
>What do you mean by “(n+n-1) diagonals”.
>
>How is this different from what you call "pan-diagonal"?

the diagonals don't wrap around.


e f g h i
d e f g h
c d e f g
b c d e f
a b c d e


no two cells with same letter may contain the same digit.
For same diagonals it's only a small constraint, since
it only contains few cells. Only the two main diagonals
contain n cells.


>Are you suggesting that the fourth group be something like:
>
>Code:
>
>b c d e a
>d e a b c
>a b c d e
>c d e a b
>e a b c d
>

no, but that's also interesting ! See Henry D. Shapiro: Generalized
Latin Squares on the Torus. Discrete Math.24 (1978)no.1,63-77

>
>This would seem very difficult for the solver to keep track of,
>even if the grid was color coded. And if it weren't color coded,
>is it up to the solver to discover which cell belongs to which
>disjoint-non-attacking-queen group?
>
>Digressing, a fifth group can be added to the above order 5 square:
>Code:
>
>+---+---------------+
>| 2 3 | 4 5 1 |
>| +---+ +
>| 4 5 | 1 | 2 3 |
>| +---+ +---+---|
>| 1 | 2 3 4 | 5 |
>|---+---+ +---+ |
>| 3 4 | 5 | 1 2 |
>+ +---+ |
>| 5 1 2 | 3 4 |
>+---------------+---+
>

yes, but it's not necessary that each set has n elements and that
there are n sets in the group as long as you just only require
that any two digits in a set from a group are different


>
>An order 7 or 11 puzzle could have polyomino or disjoint groups as well.
>Polyomino groups are also popular in the Japanese magazines, either
>instead of the standard box group, or an incomplete set of polyomino
>and/or disjoint groups in addition to all the normal groups.
>
>For example, this puzzle:
>
>Code:
>
>. . . . . . 6 . .
>. . . . 9 . . . .
>. . . 1 4 . . . 7
>9 5 . . . . . 4 3
>. 6 . . . . . 5 .
>4 3 . . . . . 6 8
>2 . . . 8 9 . . .
>. . . . 2 . . . .
>. . 7 . . . . . .
>
>
>
>... has the standard row, column and box groups, but cannot be solved
>without using these four additional groups, each of which must have
>the digits 1-9 in the solution:
>
>Code:
>
>. . a a . . . . .
>. a a . . b b b .
>a . . . . b b b .
>. a a . . b b b .
>. . a a . c c . .
>. d d d . . c c .
>. d d d . . . . c
>. d d d . . c c .
>. . . . . c c . . o



-Guenter. sterten@aol.com
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Exotic sudoku All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron