The New Sudoku Players' Forum

[Moschopulus]

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?

[coloin]

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

[Moschopulus]

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|800
000|020|900
100|004|000
-----------
000|000|300
040|000|090
003|000|000
-----------
000|500|007
001|060|000
008|000|649


(is this a hard puzzle?)


with solution

932615874584327916167984532729458361645132798813796425296543187471869253358271649

Code: Select all

932|615|874
584|327|916
167|984|532
-----------
729|458|361
645|132|798
813|796|425
-----------
296|543|187
471|869|253
358|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}

[coloin]

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.

[Moschopulus]

There are a lot fewer unavoidables, so I think it's just as hard to write a program.

Some places where sudoku DG has been mentioned before:

http://forum.enjoysudoku.com/viewtopic.php?t=44&start=187

http://forum.enjoysudoku.com/viewtopic.php?t=44&start=402

http://forum.enjoysudoku.com/viewtopic.php?t=44&start=409

http://www.menneske.no/sudoku/dg/3/eng/

http://www.setbb.com/phpbb/viewtopic.php?t=57&mforum=sudoku

[gsf]

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

[Moschopulus]

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.

[gsf]

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


[coloin]

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 ?

[gsf]

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

[coloin]

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 ?

[Moschopulus]

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.

[coloin]

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 !

[Ocean]

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

102000000003000000000000004040050000060000000000000010070000000000080000000000700
102000000003000000000000004040050000060070000000000020080000000000000000000000800
102000000003004000000000005050060000070000000000000010080000000000000000000000800
102000000003004000000000005050060000070000000000000020080000000000000000000000800
102000000300400000000000500060070000070000000000000020080000000000000000000000800
102003000000000000000000004040050000060000000000000010070000000000080000000000700
102003000000000000000000004040050000060070000000000020080000000000000000000000800
102003000000004000000000005050060000070000000000000010080000000000000000000000800
102003000000004000000000005050060000070000000000000020080000000000000000000000800
102300000000400000000000500060070000070000000000000020080000000000000000000000800


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!]

[gsf]

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)