Re: 2680 challenge

From: Patrick Hamlyn (path_at_multipro.N_OcomSP_AM.au)
Date: 01/25/05 

Date: Tue, 25 Jan 2005 16:03:28 GMT

"Brian Hetrick" <bhetrick@notinnedmeats.iname.com> wrote:

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

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-subscribe@egroups.com)