Disjoint groups in addition to rows, columns and boxes

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:

dukuso

chuckfresno

dukuso · Posted: Sat Jul 16, 2005 1:22 am Post subject:

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

chuckfresno · Posted: Sat Jul 16, 2005 4:04 am Post subject:

dukuso · Posted: Sat Jul 16, 2005 12:25 pm Post subject:

dukuso · Posted: Sat Jul 16, 2005 8:36 pm Post subject:

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.

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

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:

chuckfresno · Posted: Sun Jul 17, 2005 12:48 am Post subject:

dukuso · Posted: Sun Jul 17, 2005 10:22 am Post subject:

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

Michael Kennett

[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:

jaap

Michael Kennett · Posted: Thu Jul 21, 2005 10:19 am Post subject:

Thanks for the clarification - I misunderstood the original posting.

chuckfresno · Posted: Sat Jul 23, 2005 5:49 am Post subject:

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:

dukuso · Posted: Sat Jul 23, 2005 7:41 am Post subject:

>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