2

I solve acm-icpc problem a kind of graph theory.

Traveling Spiders is a logical puzzle that needs a sequence of systematic choices among many alternatives. The puzzle assumes a geometric object whose surface is partitioned into a set of areas called cells that are usually congruent, or very similar in their shapes and sizes. A spider may move around freely on the surface of the object, but, can move forward from a cell to only one of its neighboring cells in each step. Now, given some pairs of male and female spiders, initially positioned all in different cells, we want to find a set of paths that, respectively, leads each male spider to his partner. The only condition is that every cell of the object must be visited once and only once by a male spider during their traversal.

the cube exists in the space [0, 2n] x [0, 2n] x [0, 2n], and n can be 2 <= n <= 50.

we have to find one hamiltonian path when I game two position start from A to B.

and print all of path(1 0 1 -> 1 0 3 -> .... -> 3 1 4).

My friend said it is can't see general answer. because It is quite difficult to exact planar graph. and It cannot judge hamiltonian path or not.

how I can find hamiltonian path in general case?;

HostileFork says dont trust SE
  • 32,904
  • 11
  • 98
  • 167
Silvester
  • 2,819
  • 5
  • 22
  • 23

2 Answers2

3

Looks like Gray code problem, specifically n-ary Gray code.

Gray codes are Hamiltonian cycles, but you are looking for a Hamiltonian path with end vertices A and B. I'm not sure, but maybe Monotonic Gray codes can help. If cube vertices can be partitioned in V_i, so that V_0 = {A}, V_n = {B}, than construction in article can solve problem.

Edit: There is a reference, on Wikipedia page, to Knuth's draft of n-tuple generation from The Art Volume 4A.

Ante
  • 5,350
  • 6
  • 23
  • 46
  • @David: It is by construction. H_n is union of 0 + H_{n-1} and 1 + inverse H_{n-1}. – Ante Nov 23 '11 at 10:04
  • But the union is also true for the other 5 gray codes in a rubic cube i.e. octree. Isn't this just a recursive function? Why is a gray code a hamiltonian cycle? – Micromega Nov 23 '11 at 10:14
  • Original Gray code asked only for reflected code property (only one change). It is also Hamiltonian cycle by construction (easy to prove with induction). Other definitions and constructions, as I can recall, ask for Hamiltonian cycle property. – Ante Nov 23 '11 at 10:51
  • Thus cyclic isn't recursive? What's the difference? – Micromega Nov 23 '11 at 11:14
  • Cycle means that first and last vertex in a path are same. What do you mean with recursive? – Ante Nov 23 '11 at 11:18
  • Nothing, but I had really trouble to find a hamiltonian path with the fleury algorithm. Could it help to solve the task of a rubic cube? – Micromega Nov 23 '11 at 11:24
  • Fleury's algorithm is for finding Eulerian paths and cycles, not Hamiltonian. – Ante Nov 23 '11 at 13:39
  • From Wikipedia: Eulerian cycle is a Eulerian trail which starts and ends on the same vertex. – Micromega Nov 23 '11 at 14:50
  • Eulerian path visits every edge exactly once, while Hamiltonian path visits each vertex exactly once. Similar definitions, but very different topics :-) – Ante Nov 23 '11 at 15:36
  • I know what is a vertex and what is an edge and I know what is a gray code and what is a hamiltonian path but I'm confused now. – Micromega Nov 23 '11 at 15:40
  • http://stackoverflow.com/questions/3269013/difference-between-hamiltonian-path-and-euler-path – Micromega Nov 23 '11 at 18:04
1

The problem is NP complete and you need to brute force every possible path. See here: Algorithms to find the number of Hamiltonian paths in a graph. However, in your task there is a shortcut because it's a rubic cube and a gray code traversal of a rubics cube is a hamiltonian path. There are 6 ways of a gray code traversal of a rubic cube. For example if you have an octree and you find a hamiltonian path most likely you have found a space-filling-curve reducing the 3d to a 1d complexity. Then you can sort the path from top to bottom or from bottom to top. When you have the other 5 space-filling-curves you can have other lists. Here is a link that explains the difference between an euler path and a hamiltonian path: Difference between hamiltonian path and euler path. Here is an example of a hilbert curve http://www.tiac.net/~sw/2008/10/Hilbert/ and it uses a binary-reflected code, not a n-ary code or a monotonic gray code.

Community
  • 1
  • 1
Micromega
  • 12,486
  • 7
  • 35
  • 72
  • I don't think he wants all paths, just one. "print all of path" -- I understand this as "print all the steps in the path you found". – Tom Sirgedas Nov 23 '11 at 21:44