SliferSkyd's blog

Hamilton cycles in a grid
By SliferSkyd, history, 4 years ago, In English

Hello,

Given a grid N x M (N x M <= 100). Your task is to count how many Hamilton cycles in this graph. Are there any algorithms to solve this?

Thanks!

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Considering your name, it's probably solved with Dynamic Programming.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Problem: https://acm.timus.ru/problem.aspx?space=1&num=1519&locale=en You can find solutions to this problem online. In China the approach is known as 'CDQ DP,' if I'm not mistaken (I'm not Chinese). If I remember correctly, the gist of the idea is to perform the broken profile dp with the profile representing a correct bracket sequence. Hashing is also used as you need more than two possibilities for cell state.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think it's harder version of described problem. In original one there are no single word about obstacles. So it should be doable without broken profile dp. Anyway, thanks for sharing. I was in doubt if this harder version is solvable with same constraints.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't think so. Obstacles are rather irrelevant. You just skip transitions whenever there is an obstacle.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You probably didn't get my point. Your approach will work for both versions, but I'm sure that version without obstacles is possible to do with a simpler method. I will think about it in my free time.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 3   Vote: I like it +6 Vote: I do not like it

          Well, maybe. I just get my intuition from the usual broken profile DP applied to board tiling with 1x2 tiles. There is no better solution in realm of competitive programming than using broken profile DP, and this approach is the same if you had a board with obstacles. Note, there is a complex solution to this problem if you look here: https://acm.timus.ru/problem.aspx?space=1&num=1594. But I definitely think it is even harder to come up with a solution for the hamiltonian cycle.

          → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hmm, can you talk more about the solution using broken profile dp??

    → Reply