COMPULSORY UPGRADE!!! Request an upgrade NOW! 32+ Pre-installed Modifications! 3 Server Locations to choose from: USA, UK and JAPAN.
11th December 2012 - setBB: All servers are upgraded to run using SSD drive. Click Here to report problems!
| View previous topic :: View next topic |
| Author |
Message |
| blue
| | Joined: 12 May 2010 | | Posts: 318 | | : | |
Items |
|
 Posted: Wed May 18, 2011 10:17 pm Post subject: |
 |
|
| mathimagics wrote: | | blue wrote: | | When I'm using the SAT solver, I run it a 2nd time, with one long clause added... |
Aren't all SAT clauses long? Or is is just the list that's long  |
For sudoku, just the list. Most of the clauses are (~a | ~b) clauses ("weak link" clauses), and a few are (a1 | ... | aN) clauses ("strong link" clauses), where the grid is NxN. When it's a for a puzzle with "clues", rather than an empty grid for a GDL, some of the variables are known coming in. In that case, you can either add a bunch of "single literal" clauses, corresponding to the clues, or you can prune down the SAT problem, by 1) determining which candidates are forced false, by the "weak links", and 2) removing any clauses that are satisfied by the "knowns" at that point, and 3) removing "known false" candidates from the "strong link" clauses. The MiniSAT solver, that I use, will do all of that for you, if you add the single literal clauses for the "clues", before adding the remaining clauses.
| mathimagics wrote: | | A good result on the quick quiz, except you mean orthogonal. So solutions are relatively rare, eg no Latin square GDL will be solvable for N=6. Wonder if every cell is critical, hmmmm ... |
"Orthogonal", right. Thanks. Good question about critical cells, for N=6 !
| mathimagics wrote: | Sorry, I'm probably telling you all about the bleeding obvious (my ideal Mastermind special subject) ...  |
Not to worry ... it's all interesting stuff, and all fairly new to me.
Are there things like "mutually orthogonal" LS triples, etc ? |
|
| Back to top |
|
 |
| blue
| | Joined: 12 May 2010 | | Posts: 318 | | : | |
Items |
|
| Posted: Wed May 18, 2011 10:20 pm Post subject: |
|
|
| mathimagics wrote: | My hopes for some evidence to support the possibility that the Contig GDL problem might not be NP-complete have just taken a hammering ...
These are random GDL's, like really random, a constant shuffling of a "deck" of 81 cards.
Can you believe that? I'm shattered! |
Wow! Amazing. |
|
| Back to top |
|
|
| mathimagics
| | Joined: 01 Apr 2010 | | Posts: 73 | | : | | Location: Canberra, Australia |
Items |
|
| Posted: Thu May 19, 2011 2:05 am Post subject: |
|
|
I tested an example of a 6x6 Latin Square used as a GDL and found that every block had a critical cell, and every other cell appeared in some critical pair.
Sets of 3 or more mutually orthogonal Latin Squares exist but for order N Latin Squares the most you can get in a set is N-1, and that's not always possible. The maximum number is known for small N, but for general N no formula is known.
Some remarkable results from the latest batch tests:
Percentage of GDL samples that were invalid | Code: |
N Contiguous Arbitrary
=============================
6 3.1% 96%
7 1.5% 93%
8 1.2% 62%
9 1.1% 1.1%
10 .4% 0
|
The trend for CGDL's is pretty clear, it's getting harder and harder (for me, anyway) to randomly generate an invalid CGDL.
The same trend I think also applies to arbitrary random GDL's. The reason (I think) for the high attrition rates for N=6, N=7 and N=8 are that these random GDL's have diddly-squat in the way of contiguous regions.
I display them as coloured squares and as they flash by you can see what an "unnatural state" contiguity is. Can also see that my idea of sitting and waiting for just one contig pattern to pass by could be a long wait indeed, even for modest N.
My point is that testing these GDL's is very much an indirect way of asking - does this (almost) Latin Square have an (almost) orthogonal mate?
Thus the answer is almost always no for N=6 (there are no OLS at all for N=6), and almost always no for N=7 (just 7 main classes), and mostly no for N=8 (2165 main classes).
The sudden dropaway beyond N=8, combined with the absence on any figures on the web, suggests that orthogonal pairs are very common beyond that.
The Sloane sequences normally have the latest knowledge in these areas but its entry for numbers of OLS (A072377) only goes up to N = 4, which is pitiful. |
|
| Back to top |
|
|
| mathimagics
| | Joined: 01 Apr 2010 | | Posts: 73 | | : | | Location: Canberra, Australia |
Items |
|
| Posted: Thu May 19, 2011 5:36 am Post subject: |
|
|
Here's another interesting GDL specimen:
ABBBCCAAABBCDEAABCDEEEECDDFEFCDDFFFF
I wasn't expecting a rank 4 to turn up in a 6x6 grid. |
|
| Back to top |
|
|
| blue
| | Joined: 12 May 2010 | | Posts: 318 | | : | |
Items |
|
| Posted: Thu May 19, 2011 7:32 am Post subject: |
|
|
| mathimagics wrote: | | I wasn't expecting a rank 4 to turn up in a 6x6 grid. |
Interesting specimen, yes 
I tried to produce one using my "Markov chain" generator.
I didn't find any in the first 100k, and only found one in the next 100k.
It was a mirror image of the one you found !
Do you happen to know how many contiguous GDL's exist, at size 6 ?
On another train of thought ... after reading your post where you wrote:
| mathimagics wrote: | | My hopes for some evidence to support the possibility that the Contig GDL problem might not be NP-complete have just taken a hammering ... |
I've (off and on), been pondering the question of why you have been focusing on critical cells, pairs, and the like, for invalid layouts.
Does it have anything to do with this stuff stuff from the Wikipedia page on "co-NP" problems ?
| Quote: | | A problem (script)X is a member of co-NP if and only if its complement, (script)X(bar), is in the complexity class NP. In simple terms, co-NP is the class of problems for which efficiently verifiable proofs of no instances, sometimes called counterexamples, exist. |
| Quote: | | NP and co-NP are also thought to be unequal. If so, then no NP-complete problem can be in co-NP and no co-NP-complete problem can be in NP. |
| Quote: | | If a problem can be shown to be in both NP and co-NP, that is generally accepted as strong evidence that the problem is probably not NP-complete (since otherwise NP = co-NP). |
That, and the fact that the problems of the form: "Does this GDL layout, have a solution ?", are definitely in the class NP.
Thanks,
Blue. |
|
| Back to top |
|
|
| mathimagics
| | Joined: 01 Apr 2010 | | Posts: 73 | | : | | Location: Canberra, Australia |
Items |
|
| Posted: Thu May 19, 2011 3:15 pm Post subject: |
|
|
| blue wrote: | | Do you happen to know how many contiguous GDL's exist, at size 6 ? |
That depends on how we define "sameness". My first attempt at enumeration gave me 456,000 candidates. I then filtered these down to 45,972 "different" forms by eliminating equivalents under rotation and/or reflection. And also "normalising" any that had complete rows by moving those to the top.
Oh yes, and just 2098 of these were invalid.
I think these 46K objects are "different", but some of them are still isotopic, however. They look distinct but are row/col permutations of each other, and so the Latin Squares that are their solutions must all be in the same isotopy class.
I think this only happens in N=6 because 6 has factors so you can have 2 blocks forming 4x3 rectangles. These 3 examples are a case in point:
| Code: |
A A A B B B A A A A A A A A A A A A
A C C D D B A A C D B B A C A B D B
A A C D B B A C C D D B A C C D D B
C C C D D D C C C D D D C C C D D D
E E E E E E E E E E E E E E E E E E
F F F F F F F F F F F F F F F F F F |
If you could see the image representations you can see that there are 3 slightly different patterns in the 4x3 rectangles. Each has two copies of the same pattern. Another 3 can be formed by giving them 2 different patterns.
All 6 appear in my "distinct CGDL" list, but are in the same isotopy class. I'm not sure whether I should filter these out as well or not.
Haven't done N=7 yet, because it will only be possible if I re-engineer the code, which enumerates to a file and then I run the filter. For N=7 we could be talking gigabytes in the frst stage, however, so I need to do filtering inside the enumeration, at each recursion level, to keep it all under control.
N = 8 is not going to happen, the number of objects is just too humungous.
N = 5 yielded 496 "different" CGDL's, just 8 of these are invalid.
The enumeration code was tricky, and enumeration algorithmically seems to be just as "hard" as random generation.
And I have a new variation on the problem - if I have a given completed Latin Square, what CGDL's match it? This sounded easy to me, so I left it to last, but well, you know, it's not quite as simple as it appears. |
|
| Back to top |
|
|
| mathimagics
| | Joined: 01 Apr 2010 | | Posts: 73 | | : | | Location: Canberra, Australia |
Items |
|
| Posted: Thu May 19, 2011 3:27 pm Post subject: |
|
|
| blue wrote: | I've (off and on), been pondering the question of why you have been focusing on critical cells, pairs, and the like, for invalid layouts.
Does it have anything to do with this stuff from the Wikipedia page on "co-NP" problems ? |
Just the fact that the complexity of the decision problem for contiguous GDL's is unresolved, really. It's kind of challenging.
So very little is proven in this area, so little is known and I just kind of hoped that some sort of result was possible that would suggest that contiguous made a difference, that a problem wrt a Jigsaw layout was not as complex as a problem wrt arbitrary ones. |
|
| Back to top |
|
|
| blue
| | Joined: 12 May 2010 | | Posts: 318 | | : | |
Items |
|
| Posted: Fri May 20, 2011 9:13 pm Post subject: |
|
|
Here's another interesting 6x6 specimen.
It doesn't have critical cells, or critical pairs, triples or quadruples with cells in the same row, same column, or same block, but it does have critical triples like (1,5), (1,6), (2,5).
| Code: | A A A A A B
A C C C B B
C C D D E B
C D D F E B
D D F F E B
F F F E E E |
|
|
| Back to top |
|
|
| mathimagics
| | Joined: 01 Apr 2010 | | Posts: 73 | | : | | Location: Canberra, Australia |
Items |
|
| Posted: Sat May 21, 2011 2:49 am Post subject: |
|
|
That's really rank 3, I think. It's like "Case 2" of your examples above (*), since all 3 cells must have different values.
This, and all of your previous examples, need the critical-set definition to be adjusted. Something like "any set of k cells where no initial value combinations allow any k+1-template to be formed.
This is another reason why templates interest me - I can't think of a more concise indicator of the reason for a layout to be invalid.
* it'd be nice to be able to link to individual posts, but I can't see how that's done here.
PS: OK, yes it can be done, but it ain't easy to work out the post id number. After much huffing and puffing found your examples HERE |
|
| Back to top |
|
|
| mathimagics
| | Joined: 01 Apr 2010 | | Posts: 73 | | : | | Location: Canberra, Australia |
Items |
|
| Posted: Sat May 21, 2011 4:45 am Post subject: |
|
|
You'll see over here that I've come across a new decision problem regarding completability of partial Jigsaw layouts.
It's certainly a rich field to plough if you're interested in growing tough problems! |
|
| Back to top |
|
|
| Pat
 | | Joined: 06 Sep 2006 | | Posts: 242 | | : | |
Items |
|
| Posted: Mon May 23, 2011 12:27 pm Post subject: |
|
|
| mathimagics wrote: | | it'd be nice to be able to link to individual posts |
right-click the little icon [  Posted: 2011.May.23 Mon ] and Copy Shortcut |
|
| Back to top |
|
|
| mathimagics
| | Joined: 01 Apr 2010 | | Posts: 73 | | : | | Location: Canberra, Australia |
Items |
|
| Posted: Mon May 23, 2011 2:41 pm Post subject: |
|
|
Thanks for that, rookery man!
I never replied to your post, rude of me. I can see why they would call a set of row/col spanning cells a rookery. It's cute, but every time I see the word I keep thinking of rooks = crows, rookeries = places where many crows are kept => so a rookery is a "murder scene"!
It's a classic case of word association football. |
|
| Back to top |
|
|
| |
|
|
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
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
