Minimum number of clues in Sudoku DG

For fans of Killer Sudoku, Samurai Sudoku and other variants

Minimum number of clues in Sudoku DG

Postby Moschopulus » Thu Feb 23, 2006 10:49 pm

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

Postby coloin » Fri Feb 24, 2006 8:22 pm

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: 1637
Joined: 05 May 2005

Postby Moschopulus » Sat Feb 25, 2006 3:17 pm

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}
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby coloin » Tue Feb 28, 2006 12:39 am

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: 1637
Joined: 05 May 2005

Postby Moschopulus » Tue Feb 28, 2006 2:13 am

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

Postby gsf » Tue Feb 28, 2006 6:48 pm

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

Postby Moschopulus » Wed Mar 01, 2006 10:28 am

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

Postby gsf » Thu Mar 02, 2006 10:04 am

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

Postby coloin » Thu Mar 02, 2006 5:20 pm

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: 1637
Joined: 05 May 2005

Postby gsf » Thu Mar 02, 2006 5:57 pm

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

Postby coloin » Thu Mar 02, 2006 10:38 pm

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: 1637
Joined: 05 May 2005

Postby Moschopulus » Thu Mar 02, 2006 10:55 pm

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

Postby coloin » Thu Mar 02, 2006 11:24 pm

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: 1637
Joined: 05 May 2005

Sudoku DG with 11 clues.

Postby Ocean » Fri Aug 31, 2007 2:29 am

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

Postby gsf » Fri Aug 31, 2007 2:57 am

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

Return to Sudoku variants