| View previous topic :: View next topic |
| Author |
Message |
gsf
Joined: 21 Sep 2005
Posts: 4032
Location: NJ USA
|
 Posted: Thu Mar 02, 2006 1:04 am Post subject: |
 |
|
| Moschopulus wrote: |
Maybe that time is comparable to finding a 12 for sudoku-DG. |
2 12's popped out
| Code: |
.46.....3....71.....3....8.2.........9..4.............1.................5........
746982513825371964913465287271638495698547132354129678167854329489213756532796841
.59....6.......5......1.....4...............4....21...2.....7..............3.....
159873462372649518864215973647598321921736854538421697215984736493167285786352149
|
|
|
| Back to top |
|
 |
coloin
Joined: 05 May 2005
Posts: 1103
Location: Devon UK
|
| Posted: Thu Mar 02, 2006 8:20 am Post subject: |
|
|
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 ? |
|
| Back to top |
|
|
gsf
Joined: 21 Sep 2005
Posts: 4032
Location: NJ USA
|
| Posted: Thu Mar 02, 2006 8:57 am Post subject: |
|
|
| 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 |
|
| Back to top |
|
|
coloin
Joined: 05 May 2005
Posts: 1103
Location: Devon UK
|
| Posted: Thu Mar 02, 2006 1:38 pm Post subject: |
|
|
| 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 ? |
|
| Back to top |
|
|
Moschopulus
Joined: 16 Jul 2005
Posts: 257
|
| Posted: Thu Mar 02, 2006 1:55 pm Post subject: |
|
|
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://www.sudoku.com/boards/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. |
|
| Back to top |
|
|
coloin
Joined: 05 May 2005
Posts: 1103
Location: Devon UK
|
| Posted: Thu Mar 02, 2006 2:24 pm Post subject: |
|
|
Ah...I knew that had to be.
But...... | Code: | +---+---+---+
|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: | +---+---+---+
|...|..2|5..|
|...|...|...|
|...|..5|2..|
+---+---+---+
|2..|...|..5|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|5.2|...|...|
+---+---+---+ |
sorry I am slow ! Implicit unavoidable logic ! |
|
| Back to top |
|
|
Ocean
Joined: 29 Aug 2005
Posts: 442
|
| Posted: Thu Aug 30, 2007 6:29 pm Post subject: Sudoku DG with 11 clues. |
|
|
Here is a recent finding:
| Code: |
#
# 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: |
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 7:35 pm; edited 1 time in total |
|
| Back to top |
|
|
gsf
Joined: 21 Sep 2005
Posts: 4032
Location: NJ USA
|
| Posted: Thu Aug 30, 2007 6:57 pm Post subject: Re: Sudoku DG with 11 clues. |
|
|
| Code: |
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) |
|
| Back to top |
|
|
Ocean
Joined: 29 Aug 2005
Posts: 442
|
| Posted: Thu Aug 30, 2007 7:29 pm Post subject: Re: Sudoku DG with 11 clues. |
|
|
| gsf wrote: | | Code: |
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) |
Thanks!!
This was fast response!
The last puzzle was transferred wrongly to the post (sorry), it should read:
| Code: | | 102300000000400000000000500060070000070000000000000020080000000000000000000000800 |
|
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
