Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

NEWS:
New canonization
Goto page Previous  1, 2, 3
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku
View previous topic :: View next topic  
Author Message
coloin

Joined: 05 May 2005
Posts: 187
:

Items
PostPosted: Wed Mar 09, 2011 8:30 pm    Post subject: Reply with quote

Well - i think the thread might well be about fixing a few common clues - and maybe finding a 17 - if there is one to be found.

Thanks to blue for indulging me.

I dont think I will be embarking on possible searches untill aspects are a bit clearer.

However any mammoth search could maybe be reduced a little by splitting.
start with a ml8 - only search for puzzles {+9 clues} with 8 clue values
start with a ml9 - only search for puzzles {+8 clues} with 9 clue values

except ml9s are a bit unexpected - 18647 in total
Code:
1       000000000000000001000000002000000000000000003000000040000000000000005000067080009
2       000000000000000001000000002000000000000000003000000040000000000000005000067080090
*****                                                                                   
18641   000000000000000001002003000000000040000050000060000000000000070000800000900000000
18642   000000000000000001002003000000000040000050000060000000000000700000800000900000000
                                                                                         
18643   000000001000000020000000300000004000000050000000600000007000000080000000900000000
18644   000000001000000020000000300000004000000050000006000000000700000080000000900000000
18645   000000001000000020000003000000000400000050000006000000000700000080000000900000000
18646   000000001000000020000003000000000400005000000060000000000070000000800000900000000
18647   000000001000002000003000000000000040000050000060000000000000700000800000900000000


only 5 of the 18647 have a clue in every row and column.... correct ?


Meanwhile...........
Maybe a little exercise could be to start with a few thousand random 18s
from those - identify all the 18-puzzles witch have pattern 584 ml8
generate more 18s with the fixed ml8 [-2+2}
how long would it take to get all the 74 [or 304] 17-puzzles ?

C

18647 total corrected


Last edited by coloin on Fri Mar 11, 2011 12:05 pm; edited 1 time in total
Back to top
View user's profile Send private message
blue

Joined: 12 May 2010
Posts: 319
:

Items
PostPosted: Thu Mar 10, 2011 3:19 am    Post subject: Reply with quote

coloin wrote:
except ml9s are a bit unexpected - 18647 in total

coloin wrote:
only 5 of the 18457 have a clue in every row and column.... correct ?

Or was it 18547 ? Smile (18547, I assume).

Was that by searching in random puzzles, or with a "generate them all" process ?

I got 18663 (generated), with only 5 that use all 9 rows & columns (and 1131 ML8s, as you said).
My last 7 match yours, but I have 12 others listed before your #1.

Code:
.................1........2.................3........4................5..67.89...
.................1........2.................3........4..............5....67.8..9.
.................1........2.................3........4..............5.6..78.9....
.................1........2.................3........4.............56....78....9.
.................1........2.................3........4...........5..6....7..8..9.
.................1........2.................3........4.......5......6....78.9....
.................1........2.................3........4.......5.....67....89......
.................1........2.................3........4.......5...6..7....8..9....
.................1........2.................3........4.....5.......6.....78....9.
.................1........2.................3........4.....5.......6..7..89......
.................1........2.................3........4.....5.....6.......7..8..9.
.................1........2.................3........4.....5.....6....7..8..9....


coloin wrote:
Meanwhile...........
Maybe a little exercise could be to start with a few thousand random 18s
from those - identify all the 18-puzzles witch have pattern 584 ml8
generate more 18s with the fixed ml8 [-2+2} [dont bother removing any isomorphs]
how long would it take to get all the 74 [or 304] 17-puzzles ?

You're on your own here.
Maybe gsf's app allows you to do that, with some auxiliary scripts ?
(Or not, since then you would already have tried it ?)

I would point out three things: [ 1 & 3 are trivia ... 2 is "not good" ]

1) you would only need to find one from each set of 4 (or 8), for the 74 puzzles.
2) the restricted {-2,+2} test, will (likely) only be faster than the full test, by a factor of (18*17)/(10*9) = 3.4
3) if you start getting isomorphs of the 18's, you'll be repeating tests (in essence), and producing isomorphs of the 18's that were produced from the "originals" ... and the "3.4" will begin to shrink.

P.S. Is there a published list of "random" 18s ?
Back to top
View user's profile Send private message
ronk

Joined: 15 Apr 2010
Posts: 143
:
Location: Southeastern USA

Items
PostPosted: Thu Mar 10, 2011 11:20 pm    Post subject: Reply with quote

blue wrote:
ronk wrote:
blue wrote:
pattern 584 has 4 automorphisms, occurs 304 times in 74 puzzles

In the context of this thread, how is knowing that a pattern occurs more than once in any given puzzle useful?

I don't know if coloin has given an official definition of "the" ML8 canonical form for a puzzle (containing at least one ML8 pattern), but an algorithm to produce it, might be:

1) determine which ML8 patterns occur in the puzzle
2) select the one that is lexographically minimal
3) consider all transformations of the puzzle, that allow it to be overlaid on the given ML8 pattern, and select the one that is lexographically minimal.

In step (3) then, you need to deal with the (annoying) fact, that the pattern can "occur more than once" in the puzzle.

blue, thanks for the explanation. Although I've known for some time what an auto-morph is, I still don't have a feel for the practical consequences. This will help ... eventually. Smile
Back to top
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 187
:

Items
PostPosted: Fri Mar 11, 2011 12:00 pm    Post subject: Reply with quote

Thanks too, i now see the 4 automorphs in the particular ml8.

I have edited my error - adding a clue to the 1131 ml8s and counting the instances of a 9th clue wasnt quite the complete search !

This random 18
Code:
.5.9.............7......321...5...8.7....2.....4.................6.17....8....945

has 98 ml8s and 57 ml9s

If there are ~ 1.8 billion ED 18-puzzles - that means there would be perhaps ~150 million 18 puzzles which share an ml8. Completing a investigation on that would be too onerous.

There were a bank of 18s available by gfroyle but i dont know if they are still available. Certainly 18s generated within the closed group {-1+1} of 800million [anon17] arnt random by any means.

Making new 18s with a fixed ml8 isnt as quick as before. Even with restricting the {-2+2} to the original template.

More thought needed to see how worthwhile this all is !

C
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 243
:

Items
PostPosted: Sun Mar 13, 2011 7:55 am    Post subject: re: 18s Reply with quote

coloin wrote:
There were a bank of 18s available by gfroyle
but i dont know if they are still available.

i have this vague memory that gsf had saved those 20 milliion 18s
and even posted them in 40 chunks
-- but i don't see them now on his page
    not that they'd really be random
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 484
:
Location: NJ USA

Items
PostPosted: Thu Mar 17, 2011 4:28 pm    Post subject: Re: re: 18s Reply with quote

Pat wrote:
coloin wrote:
There were a bank of 18s available by gfroyle
but i dont know if they are still available.

i have this vague memory that gsf had saved those 20 milliion 18s
and even posted them in 40 chunks
-- but i don't see them now on his page
    not that they'd really be random

I did a quick scan of the usual suspect machines and only found a file
generated from symmetric 18's with 3 clues removed
Back to top
View user's profile Send private message Visit poster's website
coloin

Joined: 05 May 2005
Posts: 187
:

Items
PostPosted: Thu Mar 17, 2011 10:38 pm    Post subject: Reply with quote

Well there would be no shortage of 18s ... heres my thoughts on this.
blue wrote:
pattern 1104 has 1 automorphism, occurs 8998 times in 6412 puzzles

well if the motivation were to find another new 17.....

on those 17-puzzles with pattern 1104 [for example]
with a fixed ml8 - generate 18s with {-1+2}{-1+1} - keep this as a "searched" file - [no new 17 within {-2+2}]

from any of the "random 18s", identify the ?10% which have the ml8 pattern 1104
perge the ones which are in the "searched" file
generate successive new 18s which have the ml8 {-1+1} or same template {-2+2} this can be quick.

any non-minimal 18s with a superfluos clue in the clues other than the ml8 - will give a new 17

gsf please could you possibly provide a function akin to blue

"identify and print the morph of puzzle x which has y ml8" ?

C
Back to top
View user's profile Send private message
chautygorcy

Joined: 27 Apr 2012
Posts: 3
:
Location: Nome

Items
PostPosted: Fri Apr 27, 2012 6:43 am    Post subject: Reply with quote

I'm not conversant with the manipulations involved with removing clues and testing if they can be substituted with others, but it might be advantageous to record every way the signature pattern can be hit rather than just the canonical one.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT
Goto page Previous  1, 2, 3
Page 3 of 3

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron
FREE FORUM HOSTING by AtFreeForum. Terms of Service - Privacy Policy
FASHION ACCESSORIES - BLING BLING - LADIES WATCHES - KOREAN CHILDREN CLOTHING - ONLINE BARGAIN STORE - FASHION JEWELLERIES