FPGA Central

Consider the grid shown below.

There are 4 electrical "switch pairs" which need to be connected to
make the overall connection work.

---------------------------------------------------------
| | | | | | | | | | | | | | |
---------------------------------------------------------
| | | | | | | | | | | | | | c`|
---------------------------------------------------------
| | | | | | | | | | | | | | |
---------------------------------------------------------
| | | | b | | | | | | | | | | |
---------------------------------------------------------
| | | | | | | | | | | | | d'| |
---------------------------------------------------------
| | | | | | | | | | | | | | |
---------------------------------------------------------
| | | | | | | | | | | | | | |
---------------------------------------------------------
| | | | | | a | | | | | a`| | | |
---------------------------------------------------------
| | | | | | | | | | | | | | |
---------------------------------------------------------
| | | | | | | | | | | | | | |
---------------------------------------------------------
| | | | | | | | | | | b`| | | |
---------------------------------------------------------
| | | | | | | d | | | | | | | |
---------------------------------------------------------
| | | | | | | | | | | | | | |
---------------------------------------------------------
| | c | | | | | | | | | | | | |
---------------------------------------------------------

The paths are

a --- a' (path A)
b --- b' (path B)
c --- c' (path C)
d --- d' (path D)

There would be two possible routes to connect these paths. The
connection can follow either 1) horizontal then vertical direction,
or 2) vertical then horizontal direction. There ie no other way that
the path between the electrical switches could be made. Thus every
possible path here would make a bounded rectangle encompassing the
pair of switches.

The following rule is to be followed for making up these paths:

If a switch p belonging to one path lies in the bounded rectangle
formed by the switches belonging to another path, then path p must be
connected first.

SO - What would be the order of connectivity of this set of paths?

AND - Develop a generalized procedure to implement this strategy!

Thanks,
Chris

"Chris Jones" <[email protected]> wrote in message
news:[email protected] om...
> Consider the grid shown below.
>
> There are 4 electrical "switch pairs" which need to be connected to
> make the overall connection work.
>
> ---------------------------------------------------------
> | | | | | | | | | | | | | | |
> ---------------------------------------------------------
> | | | | | | | | | | | | | | c`|
> ---------------------------------------------------------
> | | | | | | | | | | | | | | |
> ---------------------------------------------------------
> | | | | b | | | | | | | | | | |
> ---------------------------------------------------------
> | | | | | | | | | | | | | d'| |
> ---------------------------------------------------------
> | | | | | | | | | | | | | | |
> ---------------------------------------------------------
> | | | | | | | | | | | | | | |
> ---------------------------------------------------------
> | | | | | | a | | | | | a`| | | |
> ---------------------------------------------------------
> | | | | | | | | | | | | | | |
> ---------------------------------------------------------
> | | | | | | | | | | | | | | |
> ---------------------------------------------------------
> | | | | | | | | | | | b`| | | |
> ---------------------------------------------------------
> | | | | | | | d | | | | | | | |
> ---------------------------------------------------------
> | | | | | | | | | | | | | | |
> ---------------------------------------------------------
> | | c | | | | | | | | | | | | |
> ---------------------------------------------------------
>
> The paths are
>
> a --- a' (path A)
> b --- b' (path B)
> c --- c' (path C)
> d --- d' (path D)
>
> There would be two possible routes to connect these paths. The
> connection can follow either 1) horizontal then vertical direction,
> or 2) vertical then horizontal direction. There ie no other way that
> the path between the electrical switches could be made. Thus every
> possible path here would make a bounded rectangle encompassing the
> pair of switches.
>
> The following rule is to be followed for making up these paths:
>
> If a switch p belonging to one path lies in the bounded rectangle
> formed by the switches belonging to another path, then path p must be
> connected first.
>
> SO - What would be the order of connectivity of this set of paths?
>
> AND - Develop a generalized procedure to implement this strategy!
>
> Thanks,
> Chris

The strategy will not work in general. Consider the network:

a b -
- a' b'

It's easy to see a connection solution, but b is in the boundary of a-a',
and a' is in the boundary of b-b', so your strategy will not work here.

Also, you need to consider how to deal with unsolvable networks.

Chris Jones wrote:
> Consider the grid shown below.
>
> There are 4 electrical "switch pairs" which need to be connected to
> make the overall connection work.
>
> ---------------------------------------------------------
> | | | | | | | | | | | | | | |
> ---------------------------------------------------------
> | | | | | | | | | | | | | | c`|
> ---------------------------------------------------------
> | | | | | | | | | | | | | | |
> ---------------------------------------------------------
> | | | | b | | | | | | | | | | |
> ---------------------------------------------------------
> | | | | | | | | | | | | | d'| |
> ---------------------------------------------------------
> | | | | | | | | | | | | | | |
> ---------------------------------------------------------
> | | | | | | | | | | | | | | |
> ---------------------------------------------------------
> | | | | | | a | | | | | a`| | | |
> ---------------------------------------------------------
> | | | | | | | | | | | | | | |
> ---------------------------------------------------------
> | | | | | | | | | | | | | | |
> ---------------------------------------------------------
> | | | | | | | | | | | b`| | | |
> ---------------------------------------------------------
> | | | | | | | d | | | | | | | |
> ---------------------------------------------------------
> | | | | | | | | | | | | | | |
> ---------------------------------------------------------
> | | c | | | | | | | | | | | | |
> ---------------------------------------------------------
>
> The paths are
>
> a --- a' (path A)
> b --- b' (path B)
> c --- c' (path C)
> d --- d' (path D)
>
> There would be two possible routes to connect these paths. The
> connection can follow either 1) horizontal then vertical direction,
> or 2) vertical then horizontal direction. There ie no other way that
> the path between the electrical switches could be made. Thus every
> possible path here would make a bounded rectangle encompassing the
> pair of switches.
>
> The following rule is to be followed for making up these paths:
>
> If a switch p belonging to one path lies in the bounded rectangle
> formed by the switches belonging to another path, then path p must be
> connected first.
>
> SO - What would be the order of connectivity of this set of paths?
>
> AND - Develop a generalized procedure to implement this strategy!
>
> Thanks,
> Chris


First, determine how you would do this in your head. Then try to do it
on paper. Then pretend to be a dumb computer and do it on paper again.
Then you should have a good idea how the program will work.

Seems, unless I've misread it, that this network is soluble in
alphabetical order:
a-a': trivial.
b-b': across/down fails because of a-a'; down/across works.
c-c': could go either way
d-d': up/right crosses a-a' but right/up is ok.

So in my head I'm marking cells that have been visited by existing
connections, then for subsequent connections considering if those cells
are already occupied. It's not hard to see that in other arrangements,
abcd might not be possible but some other order is, so you'll need to
run through the possible variations from abcd to dcba, listing the
orders that work.

Dave.