## Minimum number of clues in Sudoku DG

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Minimum number of clues in Sudoku DG

There's a sudoku variant called Sudoku DG (DG stands for Disjoint Groups).

Sudoku DG has 9 additional groups.

(Group = set of cells that has to contain 1-9. In ordinary sudoku a group means a row or column or box. Sudoku X has 2 additional groups, the 2 diagonals.)

The 9 additional groups are the cells in the same position within each 3x3 box. For example, these cells

Code: Select all
`. x . | . x . | . x . . . . | . . . | . . . . . . | . . . | . . . --------------------- . x . | . x . | . x . . . . | . . . | . . . . . . | . . . | . . . --------------------- . x . | . x . | . x . . . . | . . . | . . . . . . | . . . | . . . `

are one additional group. There is one additional group for each position. In Sudoku DG, each of these 9 additional groups has to contain 1-9.

Question: What is the minimum number of clues for a sudoku DG puzzle?

Here is a puzzle with 13 clues.

000000000000006003000900002000000000020000800000000070000000006900180500000050000

Code: Select all
`. . . | . . . | . . . . . . | . . 6 | . . 3 . . . | 9 . . | . . 2 --------------------- . . . | . . . | . . . . 2 . | . . . | 8 . . . . . | . . . | . 7 . --------------------- . . . | . . . | . . 6 9 . . | 1 8 . | 5 . . . . . | . 5 . | . . . `

This was found using checker. Presumably the people with random search programs can do better....is there a 12?

Can anyone tell me if this is a hard puzzle?
Last edited by Moschopulus on Sat Feb 25, 2006 11:17 am, edited 1 time in total.
Moschopulus

Posts: 256
Joined: 16 July 2005

How is checker coming on ?

How do the unavoidables work in this ?

I suppose any ordinary sudoku unavoidable that has a clue in the extra group is no longer unavoidable ?
Could you construct a grid with 4 clue unavoidables occuring over the additional group of clues ?

C
coloin

Posts: 1738
Joined: 05 May 2005

Checker coming along slowly! When it comes it will be able for variants sudoku X and sudoku DG. Don't know when, sorry.

Here's a DG puzzle

902000800000020900100004000000000300040000090003000000000500007001060000008000649

Code: Select all
`902|000|800000|020|900100|004|000-----------000|000|300040|000|090003|000|000-----------000|500|007001|060|000008|000|649`

(is this a hard puzzle?)

with solution

932615874584327916167984532729458361645132798813796425296543187471869253358271649

Code: Select all
`932|615|874584|327|916167|984|532-----------729|458|361645|132|798813|796|425-----------296|543|187471|869|253358|271|649`

Unavoidables have the same definition (permuting the set gives another valid DG grid).
Some unavoidables from ordinary sudoku survive, but most don't.
Here there are 3 unavoidables of size 4 and 3 of size 6:

{23,26,33,36}
{44,45,74,75}
{61,63,91,93}
{11,13,42,43,71,72}
{16,19,36,37,67,69}
{18,19,75,79,95,98}
Moschopulus

Posts: 256
Joined: 16 July 2005

Thanks
I get it now..I took your digram too literally - every clue in the box is envolved [9 additional groups].

This changes our unavoidables somewhat !

{23,26,33,36} is still one as you say.

Dukuso
Code: Select all
`  If I made no mistake then the classes for 3x3x3x3 latin tesseracts are :  `

http://forum.enjoysudoku.com/viewtopic.php?t=44&postdays=0&postorder=asc&start=405

Suffice to say the value of this maybe in that it is an easier example to get a program to work out minimals/maximals in a grid.
coloin

Posts: 1738
Joined: 05 May 2005

Last edited by Moschopulus on Mon Mar 06, 2006 9:20 pm, edited 1 time in total.
Moschopulus

Posts: 256
Joined: 16 July 2005

### Re: Minimum number of clues in Sudoku DG

Moschopulus wrote:
This was found using checker. Presumably the people with random search programs can do better....is there a 12?

Can anyone tell me if this is a hard puzzle?

easy
for my one solver that propagates singles as the initial puzzle is constructed
the puzzle was solved as the last clue was added

anecdotal evidence for a 12
the best for my random generator for sudoku, over a day, is
19 clue minimal minimals and 31 clue maximal minimals
for dg the smallest minimal it hit is 13 over 6 hours
for a rate of ~200 13's per day
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Interesting. Wonder how long it will take your random generator to find an 18 (and a 17) for ordinary sudoku.

Maybe that time is comparable to finding a 12 for sudoku-DG.
Moschopulus

Posts: 256
Joined: 16 July 2005

Moschopulus wrote:Maybe that time is comparable to finding a 12 for sudoku-DG.

2 12's popped out
Code: Select all
`.46.....3....71.....3....8.2.........9..4.............1.................5........746982513825371964913465287271638495698547132354129678167854329489213756532796841.59....6.......5......1.....4...............4....21...2.....7..............3.....159873462372649518864215973647598321921736854538421697215984736493167285786352149`
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Well done.

I am still getting to grips with the unavoidables in these grids.

What I was going to say was that you wont find a 12 if the grid has a MCN of 13 ! [Obviously]

The DG MCN may well be different from the normal MCN. Perhaps we need to look in the DG grid with the lowest MCN

So if these grids are completed in less clues - do you have any idea which classes of unavoidable dont survive ?
coloin

Posts: 1738
Joined: 05 May 2005

coloin wrote:So if these grids are completed in less clues - do you have any idea which classes of unavoidable dont survive ?

I used sudocoup that loops on initial grids with 7 random clues (7 determined by manual observation) and then
solves to find any solution and then
minimizes the puzzle just before the last batch of singles that solved the puzzle
no explicit unavoidable logic

the two hits came from non-minimal 18 and 17 clue puzzles
looks like the hit rate is ~150 13's per day, ~0.8 12's per day
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Red Ed wrote:The number of restricted sudokus, such that no digit appears at the same offset in any two 3x3 boxes, appears to be 201105135151764480. Here's how ...

1. without loss of generality, we can assume the top left box is 1...9 in order. We can also assume that the 1s in boxes 2,3 (top middle/right) are in rows 2,3 respectively and the 1s in boxes 4,7 are in columns 2,3. So we solve the problem with those constraints and multiply the answer by 9! x 4.

2. naively, we can just exhaust over the 244 subproblems corresponding to each of the possible arrangements of 1s. Someone said earlier that there are 8784 arrangements without the constraints above, so that's 8784/9 = 976 with 1 in the top left cell and 976/4 = 244 with the additional row/col constraints. But we can do better.

3. following AFJ's and Bertram's lead, we can look for equivalence classes. The following operations leave the number of solutions intact: (a) rotate the whole grid; (b) transpose it; (c) switch the order of the row bands [by band, I mean rows 1,2,3 or 4,5,6 or 7,8,9]; (d) switch the order of the rows within each band according to the *same* permutation for each band. Applying these ops, we find that the 244 layouts of the 1s breaks down into 11 equivalence classes of sizes 1, 2, 4, 9, 12, 18, 18, 36, 36, 36, 72. The number of solutions for each of the 11 representative subproblems is different, suggesting this is the best we can do.

I could easily have messed up my sums here -- I've done it before. Anyone want to check it?

The mcn of your grids are 10 and 11.

Red Ed might have an example of each of the 11 or 244 rep grids -if this helps.

What does Checker think of the first grid ?
coloin

Posts: 1738
Joined: 05 May 2005

There are a lot fewer unavoidables in sudoku-DG, so the MCNs are smaller.
You posted the MCN using the unavoidables from ordinary sudoku.
I posted on this topic for sudoku-X here:

http://forum.enjoysudoku.com/viewtopic.php?t=2715

gsf's first grid has MCN=5 (as a sudoku-DG grid), the second has MCN=7.

Nice to see a 12 .... checker can search the MCN = 7 grid for an 11.
Moschopulus

Posts: 256
Joined: 16 July 2005

Ah...I knew that had to be.

But......
Code: Select all
`+---+---+---+|746|982|513||825|371|964||913|465|287|+---+---+---+|271|638|495||698|547|132||354|129|678|+---+---+---+|167|854|329||489|213|756||532|796|841|+---+---+---+  the full grid+---+---+---+|...|..2|5..||...|...|...||...|..5|2..|+---+---+---+|...|...|...||...|...|...||...|...|...|+---+---+---+|...|...|...||...|...|...||...|...|...|+---+---+---+    an apparently avoidable unavoidable+---+---+---+|.46|...|..3||...|.71|...||..3|...|.8.|+---+---+---+|2..|...|...||.9.|.4.|...||...|...|...|+---+---+---+|1..|...|...||...|...|...||5..|...|...|+---+---+---+ not covered in this solution !`

Ahhh I see now !

Code: Select all
`+---+---+---+|...|..2|5..||...|...|...||...|..5|2..|+---+---+---+|2..|...|..5||...|...|...||...|...|...|+---+---+---+|...|...|...||...|...|...||5.2|...|...|+---+---+---+`
sorry I am slow ! Implicit unavoidable logic !
coloin

Posts: 1738
Joined: 05 May 2005

### Sudoku DG with 11 clues.

Here is a recent finding:

Code: Select all
`## SudokuDG with 11 clues.# *-----------* |1.2|...|...| |..3|...|...| |...|...|..4| |---+---+---| |.4.|.5.|...| |.6.|.7.|...| |...|...|.2.| |---+---+---| |.8.|...|...| |...|...|...| |...|...|8..| *-----------*`

This is one from a group of ten related Sudoku-DG-puzzles, all with eleven clues (not extensively checked for isomorphism):
Code: Select all
`102000000003000000000000004040050000060000000000000010070000000000080000000000700102000000003000000000000004040050000060070000000000020080000000000000000000000800102000000003004000000000005050060000070000000000000010080000000000000000000000800102000000003004000000000005050060000070000000000000020080000000000000000000000800102000000300400000000000500060070000070000000000000020080000000000000000000000800102003000000000000000000004040050000060000000000000010070000000000080000000000700102003000000000000000000004040050000060070000000000020080000000000000000000000800102003000000004000000000005050060000070000000000000010080000000000000000000000800102003000000004000000000005050060000070000000000000020080000000000000000000000800102300000000400000000000500060070000070000000000000020080000000000000000000000800`

The puzzle in the diagram is solved manually, as a way of proofreading a newly written solver. But independent verifications would be welcomed.

Also other sets of Sudoku-DGs with 11 clues were found. (Work in progress for compilation of a longer list, but don't know if anybody is interested...).

[Edit: Corrected typo in last puzzle. Thanks to gsf for finding this, and for verifying the nine others!]
Last edited by Ocean on Thu Aug 30, 2007 11:35 pm, edited 1 time in total.
Ocean

Posts: 442
Joined: 29 August 2005

### Re: Sudoku DG with 11 clues.

Code: Select all
`102003000000400000000000500060070000070000000000000020080000000000000000000000800`

all but the last look valid
the last has 102 solutions (but I'd like corroboration on that count -- my dg code is not well-exercized)
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Next