Asgaard <asgaard@Cor.sos.sll.se> writes:
On Sun, 22 Sep 1996, Timothy C. May wrote:
Suppose a tile is placed at some place on the grid, and another tile (possibly a different tile, possibly the same type of tile) is placed some distance away on the grid. The problem is this: Can a "domino snake" be found which reaches from the first tile to the second tile, with the constraint that edges must match up on all tiles? (And all tiles must be in normal grid locations, of course)
Intuitively (but very well not, I'm not informed enough to know) this might be a suitable problem for Hellman's DNA computer, the one used for chaining the shortest route including a defined number of cities?
Solving such a problem is easy to break down into parallel steps, but the advantage of using the infinite plane (or even a plane with "really large" boundaries) which Tim mentioned is that you can make the search space larger than anything which can possibly be solved in a reasonable amount of time by these methods. For example, factoring composites of very large primes can also be done by such massively parallel systems, but othe individual parts are no faster (actually they are almost always slower) than regular computing elements. Given a large enough search space even a parallel system runs out of processing elements. jim