The text file
http://www.pisquaredoversix.force9.co.uk/2680.txt
consists of 2680 lines. Each line contains five integers. Each of these
integers is in the range 0 to 244. The challenge is to select 49 of the 2680
lines in such a way that each of the numbers from 0 to 244 is present in the
selection.

I do not know if there is a solution to this challenge.

--
Clive Tooth
http://www.clivetooth.dk

"The Last Danish Pastry" <cli...@gmail.com> wrote:

Can't give you a solution, but here is a partial containing 45 'disjoint' lines:
   5    6   11   12   19
  29   35   36   37   42
  33   39   40   41   48
  99  147  148  149  196
 103  151  152  153  202
 133  175  182  189  238
 139  181  188  195  244
   1    8    9   15  245
   7   14   49   56  105
  13   20   55   62  111
  43   44   91   92  141
  46   47   96   97  145
 197  198  203  204  211
 200  201  208  209  215
 224  231  232  233  239
 230  235  236  237  243
   2    3   50   51  100
   4   52   53   54  101
  21   28   77   84  126
  27   34   83   90  132
  38   45   80   87  136
 108  150  157  164  199
 112  154  161  210  217
 118  160  167  216  223
 142  190  191  240  241
 143  192  193  194  242
  10   16   17   18   23
  22   70   71   72  119
  25   26   75   76  124
  63   64  113  114  162
  61   67   68   69   74
  79   85   86   93   94
  32   81   88   95  137
 120  168  169  218  219
 206  207  212  213  220
 214  221  222  227  228
 131  138  173  180  229
 135  183  184  185  234
  24   31   66   73  122
  60  102  109  158  165
 172  178  179  186  187
  58   59  106  107  156
 110  115  116  117  123
 121  127  128  129  134
 163  170  171  176  177

--
Patrick Hamlyn   posting from Perth, Western Australia
Windsurfing capital of the Southern Hemisphere
Moderator: polyforms group (polyforms-subscr...@egroups.com)

Somebody claiming to be "The Last Danish Pastry" <cli...@gmail.com>
wrote in news:35hl3sF4lc07pU1@individual.net:

Sounds like a job for a programmer who's good at doing recursion.  
Unfortunately, I'm not such a programmer.  (If anybody can come up with a
good solution in Perl, I'd like to see it.)

--
Ted <fedya at bestweb dot net>
TV Announcer: It's 11:00.  Do you know where your children are?
Homer: I told you last night, *no*!
<http://www.snpp.com/episodes/4F06.html>

news:u3l7v0dkmugcnbdaiimsafnhfdreqf7b3d@4ax.com...

Thanks for that. I already know several sets of 48 disjoint lines. Here is
one such set which excludes just the numbers (0 49 98 147 196):

   1   2   9  10  16
   3   4  51  52 101
   5  53  54  55 102
   6  11  12  13  19
   7  14  63  70 112
   8  56  57  58 107
  15  21  22  23  28
  17  59  66  73 122
  18  60  67 116 123
  20  27  62  69 118
  24  25  30  31  38
  26  74  75  76 125
  29  35  36  37  42
  32  39  40  45  46
  33  34  81  82 131
  41  83  90  97 146
  43  44  93  94 142
  47  48  95  96 145
  50  99 106 113 155
  61 108 109 110 158
  64  71  72  77  78
  65 114 115 162 163
  68 117 124 159 166
  79  84  85  86  92
  80 129 130 177 178
  87  88 135 136 185
  89 137 138 139 186
  91 126 133 140 182
 100 148 149 198 199
 103 104 151 152 201
 105 154 161 168 210
 111 153 160 167 202
 119 120 127 128 134
 121 170 171 172 220
 132 181 188 223 230
 141 189 190 239 240
 143 191 192 241 242
 144 193 194 195 243
 150 156 157 164 165
 169 175 176 183 184
 173 174 179 180 187
 197 203 204 205 212
 200 206 207 208 213
 209 214 215 216 222
 211 217 218 219 224
 221 226 227 228 234
 225 231 232 233 238
 229 235 236 237 244

--
Clive Tooth
http://www.clivetooth.dk

) Somebody claiming to be "The Last Danish Pastry" <cli...@gmail.com>
) wrote in news:35hl3sF4lc07pU1@individual.net:
)
)> The text file
)> http://www.pisquaredoversix.force9.co.uk/2680.txt
)> consists of 2680 lines. Each line contains five integers. Each of
)> these integers is in the range 0 to 244. The challenge is to select
)> 49 of the 2680 lines in such a way that each of the numbers from 0 to
)> 244 is present in the selection.
)>
)> I do not know if there is a solution to this challenge.
)
) Sounds like a job for a programmer who's good at doing recursion.  
) Unfortunately, I'm not such a programmer.  (If anybody can come up with a
) good solution in Perl, I'd like to see it.)

I've a gut feeling it's an NP-hard problem, maybe even NP-complete.
Not sure though.

If you do a simple recursive search the search space is going to be waaay
too big to find a solution in a reasonable time.

Hmm, as an afterthought, if the list includes 0-244 _inclusive_, then that
means that you can't have any overlapping whatsoever, which would tend to
make searching a lot easier.  Still hard, though, but not quite as hard.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

In article <35hl3sF4lc07...@individual.net>,
The Last Danish Pastry <cli...@gmail.com> wrote:

Consider the graph with vertices corresponding to your lines,
and an edge (i-j) if lines i and j are disjoint.  You need a 49-clique
in this graph.  

A greedy algorithm (at each stage adding the candidate such that
the set of vertices joined to all members of the current clique is
as large as possible} produced a maximal clique of size 45.  So far
using tabu search the best I've found is size 46.  

Of course, if a 48-colouring of the graph could be found, it would be
a proof that there is no such 49-clique.

Robert Israel                                isr...@math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel
University of British Columbia            Vancouver, BC, Canada

"The Last Danish Pastry" <cli...@gmail.com> wrote:

There is some sort of structure to your set of lines. This number of randomly
generated lines would not allow partials anywhere near as good to be generated.

Such structure can frequently be used to accelerate the search, sometimes
dramatically.

But it's tricky to work out what that structure might be... unless you can shed
some light on how this set was generated?
--
Patrick Hamlyn   posting from Perth, Western Australia
Windsurfing capital of the Southern Hemisphere
Moderator: polyforms group (polyforms-subscr...@egroups.com)

Some of the structure can be gleaned from the frequency counts of the vertices.

The 8 rarest vertices occur 6 times each, the 24 next-rarest occur 18 times
each, etc. Decidedly non-random. Also there seems to be some sort of pattern
underlying the ordering of the vertices, althought that's less obvious. The 8
rarest nodes are all even, the next 24 are odd, then 20 even/8 odd, then all
even again, etc

The 9 vertices which occur most often (120 times each) are labelled in three
equispaced clumps - 114-116, 121-123, 128-130.

Similar grouping occurs in the 30 vertices which occur 100 times - in this case
we have the same runs of 3 with spacing of 5, then a gap of 26, run of 3, then
gaps of 4,4,3,4, then a central 4, then the entire series is repeated in
reverse, so the 100-frequencies are symmetrically distributed. Similar symmetric
runs occur elsewhere - eg the spacing of the commonest 8 vertices is
6-36-6-148-6-36-6

My best guess is that the mechanism used to generate this set was designed to
produce a set with high likelihood of a solution, without actually either
seeding or guaranteeing one.

      0            6
      6            6
     42            6
     48            6
    196            6
    202            6
    238            6
    244            6
      1           18
      5           18
      7           18
     13           18
     35           18
     41           18
     43           18
     47           18
     49           18
     55           18
     91           18
     97           18
    147           18
    153           18
    189           18
    195           18
    197           18
    201           18
    203           18
    209           18
    231           18
    237           18
    239           18
    243           18
      2           22
      3           22
      4           22
     14           22
     20           22
     21           22
     27           22
     28           22
     34           22
     44           22
     45           22
     46           22
     98           22
    104           22
    140           22
    146           22
    198           22
    199           22
    200           22
    210           22
    216           22
    217           22
    223           22
    224           22
    230           22
    240           22
    241           22
    242           22
      8           38
     12           38
     36           38
     40           38
     50           38
     54           38
     56           38
     62           38
     84           38
     90           38
     92           38
     96           38
    148           38
    152           38
    154           38
    160           38
    182           38
    188           38
    190           38
    194           38
    204           38
    208           38
    232           38
    236           38
      9           48
     10           48
     11           48
     15           48
     19           48
     22           48
     26           48
     29           48
     33           48
     37           48
     38           48
     39           48
     51           48
     52           48
     53           48
     63           48
     69           48
     70           48
     76           48
     77           48
     83           48
     93           48
     94           48
     95           48
     99           48
    103           48
    105           48
    111           48
    133           48
    139           48
    141           48
    145           48
    149           48
    150           48
    151           48
    161           48
    167           48
    168           48
    174           48
    175           48
    181           48
    191           48
    192           48
    193           48
    205           48
    206           48
    207           48
    211           48
    215           48
    218           48
    222           48
    225           48
    229           48
    233           48
    234           48
    235           48
     16           60
     17           60
     18           60
     23           60
     24           60
     25           60
     30           60
     31           60
     32           60
    100           60
    101           60
    102           60
    112           60
    118           60
    119           60
    125           60
    126           60
    132           60
    142           60
    143           60
    144           60
    212           60
    213           60
    214           60
    219           60
    220           60
    221           60
    226           60
    227           60
    228           60
     57           66
     61           66
     85           66
     89           66
    155           66
    159           66
    183           66
    187           66
     58           82
     59           82
     60           82
     64           82
     68           82
     71           82
     75           82
     78           82
     82           82
     86           82
     87           82
     88           82
    106           82
    110           82
    134           82
    138           82
    156           82
    157           82
    158           82
    162           82
    166           82
    169           82
    173           82
    176           82
    180           82
    184           82
    185           82
    186           82
     65          100
     66          100
     67          100
     72          100
     73          100
     74          100
     79          100
     80          100
     81          100
    107          100
    108          100
    109          100
    113          100
    117          100
    120          100
    124          100
    127          100
    131          100
    135          100
    136          100
    137          100
    163          100
    164          100
    165          100
    170          100
    171          100
    172          100
    177          100
    178          100
    179          100
    114          120
    115          120
    116          120
    121          120
    122          120
    123          120
    128          120
    129          120
    130          120

--
Patrick Hamlyn   posting from Perth, Western Australia
Windsurfing capital of the Southern Hemisphere
Moderator: polyforms group (polyforms-subscr...@egroups.com)

The space of potential solutions has about 4x10^230 elements, which
would take some time to enumerate.

I wrote a simple recursive search (well, someone had to do it), and it
found sets of 1 to 42 disjoint lines in a second, a 43-line set in
three minutes, and a 44-line set in four hours. I suspect the matter
making up the CPU will decay into iron and quit semiconducting before
the search finds a complete solution.

Erm, how can something with a fixed size be NP-anything?
Just like cracking AES, it's O(1).

--
Excerpt from Geoff Bulter's Proscriptive Dictionary:
  aaa     Don't use this, there's no such word
  aaaa    Don't use this, there's no such word
  aaaaa   Don't use this, there's no such word

In sci.math Robert Israel <isr...@math.ubc.ca> wrote:

An interesting problem.

I don't see why a 48-colouring would preclude the presence of a 49-clique?

Can you explain why?

A 48-clique does exist (as posted by the OP) and I'd rather not spend any
more time on this problem if a 49-clique cannot exist. Here's my
reasoning:-

Consider a simpler problem where there are only 5 lines of 5 numbers each
and the goal is to find a 3-clique (of 0-14 inclusive).

A: 0 1 2 3 4
B: 5 6 7 8 9
C: 10 11 12 13 14
D: 0 5 10 3 4
E: 1 6 11 7 8

There exists a 2-clique (D,E) but that does not preclude the possibility
of the maximal 3-clique (A,B,C) existing.

In this example, (D,E) and (A,B,C) are unconnected graphs. Changing E to
be:

E: 1 6 7 8 9

would add an edge (C,E) and connect the two subgraphs but still not
affect the fact that both a 2-clique and a 3-clique exists.

Regards,

-Alex

) Erm, how can something with a fixed size be NP-anything?
) Just like cracking AES, it's O(1).

I was talking about the general problem of finding a smallest covering
subset, obviously.  Saying something is O(1) because the size is fixed
is meaningless nitpicking in my opinion.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

In article <Xns95E7871CE8DAD8jUwe9053kODf78sf...@ID-121946.user.dfncis.de>,

We can simplify the problem.  For 49 of the lines to produce
all 245 numbers, they must be pairwise disjoint, and if this
is the case, they produce the answer.  So one can start with
the "disjointness" graph, and try to find a complete subgraph
of order 49.
--
This address is for information only.  I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hru...@stat.purdue.edu         Phone: (765)494-6054   FAX: (765)494-0558

This is a well-obfuscated way of asking if 5x7x7 box can be packed with
the F-pentomino.  To see what is an F-pentomino, convert any line of the
text file into base-7 and plot the (three) resultant 7:ary digits in 3D.

There are 2680 orientations of an F-pentomino within a 5x7x7 box, and a
quick (sample-based) check suggests that they are all represented in the
text file.  Selecting a set of 49 non-overlapping integer lines hence is
equivalent to finding a set of 49 F-pentominoes that fill the box.

Quick scan of the net indicates that this may be an open problem in the
art of packing theory...

http://www.mathematik.uni-bielefeld.de/~sillke/PENTA/qu-prime

[See "7) F1 box 5x7x7" near the end of the article.]

 - Risto -

news:dba955d3.0501241129.6e06321@posting.google.com...

Yes, you have spotted what I was really asking.

The "48 line" set that I mentioned in another reply corresponds to the
packing (large and small) in this picture:
http://www.pisquaredoversix.force9.co.uk/48.png
The coin is a (Canadian) quarter.

My apologies to all for the deception... I was wondering if presenting the
question in the way that I did would lead to any new lines of attack on this
open problem.

--
Clive Tooth
http://www.clivetooth.dk

Because in any clique all vertices would have to be different colours.

He said a 48-clique, not a 48-colouring.
A k-colouring of a graph is an assignment of a colour (a member of
{1,2,...,k}) to each vertex, so that neighbouring vertices are always
different colours.

Robert Israel                                isr...@math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel
University of British Columbia            Vancouver, BC, Canada

After reading this, I thought "well, there's no need for me to try
it". But I couldn't resist doing a little playing around anyway.

One idea was simply grab the first line of numbers and sequentially
try to fit succeeding lines. And then try each line as the starting
point (wrapping as necessary) and finding which starting point
produces the best fit. Took all of about 30 seconds to try all 2680
lines as starting points. Result: a 44-line set starting at line 25.

I've tried a couple other ideas trying to get lucky (finding an
answer without testing them all) and haven't gotten anything
better than 44 lines.

The more or less brute-force search is currently at a 45 line partial
solution, and has been holding at that for the last 24 hours.

I made a minor search space optimization which will not miss any
solution to the problem as a whole, but which perhaps will more slowly
yields partial solutions.  When the first empty cell of a partial
solution is k, then only lines that fill cell k first are even
examined to see if they extend the partial solution.  That is, when
the partial solution has cells 1 through k-1 filled, only lines that
fill cell k and larger cells are candidates for inclusion.

On 24 Jan 2005 11:29:42 -0800, rlank...@hotmail.com (Risto Lankinen)
wrote:

Speaking of pentominos. I was wondering at breakast this morning if
anyone had ever baked doughnuts in the shape of pentominos ... would
need a catchy name to sell ... cinnamonios?

Somebody claiming to be "Brian Hetrick" <bhetr...@notinnedmeats.iname.com>
wrote in news:9PmdnQAY-doV0mncRVn-sw@comcast.com:

It's actually quite a bit less than that: Since eight of the numbers only
appear six times each, you can sequester those 36 lines (since six of them
have to appear in the solution) and then look for another 41 lines out of
the remaining 2632.  That means there's "only" slightly more than
8.56*10^96 possible solutions.  :-)

--
Ted <fedya at bestweb dot net>
TV Announcer: It's 11:00.  Do you know where your children are?
Homer: I told you last night, *no*!
<http://www.snpp.com/episodes/4F06.html>

"The Last Danish Pastry" <cli...@gmail.com> wrote in message
news:35l9hcF4m1nomU1@individual.net...

Nice work, Risto; much better than the remark I was going to make: The rows
fall into 1340 pairs of the form
(a, b, c, d, e)
(244-e, 244-d, 244-c, 244-b, 244-a)
Here's a tabulation of the pairs of row numbers, 1-based:
http://www3.telus.net/ldh/math/pairs.txt
No row (a, b, c, d, e) satisfies both
e=244-a
and
d=244-b
but there are twelve rows satisfying the second condition and all have
c=122.

In sci.math Robert Israel <isr...@math.ubc.ca> wrote:

Ah. Thank you for the clarification.

Regards,

-Alex

I wrote a program which does this sort of search some years ago.

It is much the same as yours, except for an extra few steps:

1. Count how often each of the 245 vertices occurs.
2. Define a canonical sort-order based on rarest-vertex first.
3. Order the vertices within each line using that order.
4. Order the lines using that canonical order.

Now the lines fall naturally into 'sections': Section 1 is the six lines
starting with vertex 0, Section 2 is six lines starting with vertex 6, etc - the
first (rarest) eight vertices all appear 6 times.

We need only consider six possibilities for the first 'node' - ie those lines in
section 1.

Likewise, for node 'N' we need only consider those lines in section 'N'.

We can't omit any section unless the vertex starting that section is already in
one of the previously selected lines, because then the vertex which starts each
line of that section could never appear in the solution, which would preclude a
solution since every vertex must appear once.

Using this algorithm, I find 48-partials at a steady rate, but it will still
take too long to complete the search.

A significant speed-up would be to re-evaluate (and re-order) all the remaining
disjoint lines after each node. This leads to much earlier backtracking since
empty sections allow one to backtrack immediately.

I haven't worked out how to make use of the symmetry of the graph to further
reduce the search space. The symmetry is a consequence of the source of this
problem, identified by Risto Lankinen as the packing of the solid F-pentomino
into a 5*7*7 box. The 8 rarest vertices correspond to the 8 corners of the box.

It could be that I'm already getting the maximum benefit by selecting a fixed
(and arbitrary) order for those 8 'rarest' vertices.

A further speed-up may be to use a breadth-first search to identify the most
promising nodes to search first -
Ply 1 - start with all 6 ways of selecting the first line.
Ply 2 - for each of these, add the second line in all 6 possible ways (36 nodes
so far)
Ply 3 - 6 times each of the 36, 216 nodes.
repeat until we run out of room (say 10 million nodes)
At this point, we define a score for each node, being something like the number
of disjoint lines remaining in each section, and at each ply we keep the 10
million best-scoring nodes.

At a certain ply we switch to exhaustive searching of the remainder, and now of
course we have a good probability that we're searching the best-scoring nodes
first.
--
Patrick Hamlyn   posting from Perth, Western Australia
Windsurfing capital of the Southern Hemisphere
Moderator: polyforms group (polyforms-subscr...@egroups.com)

news:ngpcv0dbms7ufm7ehn6fk6b5jtnkcv3pub@4ax.com...

If you can accumulate a lot of 48-partials you could log them and then try
to analyze them, looking for some pattern - and perhaps being able to prove
that the five missing numbers cannot be in the shape of the F-pentomino.

I tried this some time ago but I could not find any pattern in the "holes";

--
Clive Tooth
http://www.clivetooth.dk