Is it a Hamiltonian cycle on a grid?

16

2

A Hamiltonian path in a graph is a path that visits each vertex exactly once; a Hamiltonian cycle is a Hamiltonian path that is a cycle – the path forms a simple closed loop. In this challenge the graph will be a n x n grid, where n is an even number greater than 2. Here is an example of a Hamiltonian cycle on 12x12 rectangular grid:

+---------------+   +-----------------------+
|               |   |                       |
+-----------+   |   +---+   +-----------+   |
            |   |       |   |           |   |
+-------+   |   +---+   |   +-------+   |   |
|       |   |       |   |           |   |   |
|   +---+   |   +---+   |   +-------+   +---+
|   |       |   |       |   |               
|   +-------+   +---+   |   +---------------+
|                   |   |                   |
+---+   +-------+   |   |   +-----------+   |
    |   |       |   |   |   |           |   |
+---+   +---+   |   +---+   +---+   +---+   |
|           |   |               |   |       |
+---+   +---+   |   +-----------+   +---+   |
    |   |       |   |                   |   |
+---+   +---+   |   +---+   +-------+   |   |
|           |   |       |   |       |   |   |
+-------+   |   +-------+   +---+   |   |   |
        |   |                   |   |   |   |
+-------+   |   +---------------+   +---+   |
|           |   |                           |
+-----------+   +---------------------------+

The path visits each vertex exactly once and forms a simple closed loop that do not intersect or touches itself. The grid points are not shown so that the ASCII graphic is not cluttered. There are three - (---) between two horizontally connected vertices or 3 spaces if the vertices are not connected. A single | connects two vertically adjacent vertices, spaces are used otherwise. Since the grid is not visible, the + is used only where the path takes a turn. The path will never be broken - if a segment connects two vertices, it will be --- and never - -.

Task:

You will be given an ASCII representation of a path and you need to check if it is a Hamiltonian cycle on a grid. Write a full program or a function that solves this problem.

Input:

ASCII representation of a path. It can be: - A mutliline string; - A list of strings - A list/array of characters or any format that is convenient for you. You can have an optional parameter n for the size of the grid. You can use alternatve ASCII representation, just explain it.

Output:

  • A consistent value indicating that the path is a Hamiltonian cycle on a grid
  • A consistent value indicating that the path is not a Hamiltonian cycle on a grid. There can be several reasons for this: The path doesn’t visit all vertices; the path crosses/touches itself; there are two or more paths and not a single one. You don’t need to specify the reason – just return/print a consistent falsy value.

Test cases:

Truthy:

Optional `n` = 6

+-----------+   +---+
|           |   |   |
|   +-------+   |   |
|   |           |   |
|   +-----------+   |
|                   |
+---+   +-------+   |
    |   |       |   |
+---+   +---+   |   |
|           |   |   |
+-----------+   +---+

+-------------------+
|                   |
|   +---------------+
|   |               
|   |   +-----------+
|   |   |           |
|   |   |   +---+   |
|   |   |   |   |   |
|   +---+   |   |   |
|           |   |   |
+-----------+   +---+

+---+   +-----------+
|   |   |           |
|   |   |   +-------+
|   |   |   |       
|   |   |   +-------+
|   |   |           |
|   +---+   +-------+
|           |       
|   +---+   +-------+
|   |   |           |
+---+   +-----------+


Optional `n` = 8

+---------------------------+
|                           |
+---+   +-----------+   +---+
    |   |           |   |   
+---+   +---+   +---+   +---+
|           |   |           |
|   +---+   |   +---+   +---+
|   |   |   |       |   |   
+---+   |   +---+   |   +---+
        |       |   |       |
+---+   +-------+   +---+   |
|   |                   |   |
|   +-------------------+   |
|                           |
+---------------------------+

+-------------------+   +---+
|                   |   |   |
+-------+   +---+   |   |   |
        |   |   |   |   |   |
+---+   |   |   |   +---+   |
|   |   |   |   |           |
|   |   +---+   |   +---+   |
|   |           |   |   |   |
|   +-----------+   |   |   |
|                   |   |   |
+---+   +-----------+   |   |
    |   |               |   |
+---+   +-----------+   |   |
|                   |   |   |
+-------------------+   +---+

+---+   +-------------------+
|   |   |                   |
|   |   +---+   +-----------+
|   |       |   |           
|   +---+   |   +-----------+
|       |   |               |
|   +---+   +---+   +---+   |
|   |           |   |   |   |
|   +-----------+   |   |   |
|                   |   |   |
|   +-------+   +---+   |   |
|   |       |   |       |   |
|   |   +---+   +---+   |   |
|   |   |           |   |   |
+---+   +-----------+   +---+


Optional `n` = 12

+---+   +-----------+   +-------------------+
|   |   |           |   |                   |
|   |   +-------+   |   +---+   +-----------+
|   |           |   |       |   |           
|   +-------+   |   +-------+   +---+   +---+
|           |   |                   |   |   |
|   +-------+   +---+   +-------+   |   |   |
|   |               |   |       |   |   |   |
|   +---------------+   |   +---+   +---+   |
|                       |   |               |
|   +-------+   +-------+   +-----------+   |
|   |       |   |                       |   |
|   |   +---+   |   +-------------------+   |
|   |   |       |   |                       |
|   |   +-------+   +-----------------------+
|   |                                       
|   +-------------------------------+   +---+
|                                   |   |   |
+-------+   +-------+   +---+   +---+   |   |
        |   |       |   |   |   |       |   |
+-------+   +---+   |   |   |   +-------+   |
|               |   |   |   |               |
+---------------+   +---+   +---------------+

+---+   +---------------------------+   +---+
|   |   |                           |   |   |
|   |   |   +-------+   +-----------+   |   |
|   |   |   |       |   |               |   |
|   |   |   +---+   |   +-------+   +---+   |
|   |   |       |   |           |   |       |
|   |   +---+   |   |   +---+   |   |   +---+
|   |       |   |   |   |   |   |   |   |   
|   +-------+   |   +---+   |   +---+   +---+
|               |           |               |
+---+   +---+   |   +---+   +-------+   +---+
    |   |   |   |   |   |           |   |   
+---+   |   |   +---+   +---+   +---+   +---+
|       |   |               |   |           |
|   +---+   +---------------+   +---+   +---+
|   |                               |   |   
|   +-----------+   +---+   +-------+   +---+
|               |   |   |   |               |
|   +-------+   |   |   |   |   +-------+   |
|   |       |   |   |   |   |   |       |   |
|   |   +---+   |   |   +---+   +---+   |   |
|   |   |       |   |               |   |   |
+---+   +-------+   +---------------+   +---+

+---------------------------+   +---+   +---+
|                           |   |   |   |   |
|   +---------------+   +---+   |   +---+   |
|   |               |   |       |           |
|   |   +---+   +---+   +-------+   +---+   |
|   |   |   |   |                   |   |   |
|   +---+   |   +---------------+   |   |   |
|           |                   |   |   |   |
+-------+   +---+   +-----------+   |   |   |
        |       |   |               |   |   |
+---+   |   +---+   |   +-----------+   |   |
|   |   |   |       |   |               |   |
|   +---+   |   +---+   |   +-----------+   |
|           |   |       |   |               |
|   +-------+   +---+   |   |   +-------+   |
|   |               |   |   |   |       |   |
|   |   +-----------+   |   |   |   +---+   |
|   |   |               |   |   |   |       |
|   |   |   +-------+   |   +---+   +---+   |
|   |   |   |       |   |               |   |
|   |   |   |   +---+   +-------+   +---+   |
|   |   |   |   |               |   |       |
+---+   +---+   +---------------+   +-------+

Falsy:

Optional `n` = 6

; Two paths
+-------------------+
|                   |
|   +-----------+   |
|   |           |   |
|   +-----------+   |
|                   |
+-------+   +-------+
        |   |       
+-------+   +-------+
|                   |
+-------------------+

; Two paths
+-------+   +-------+
|       |   |       |
|   +---+   +-------+
|   |               
|   +---------------+
|                   |
|   +-----------+   |
|   |           |   |
|   +---+   +---+   |
|       |   |       |
+-------+   +-------+

; The path doesn't visit each vertex
+-----------+   +---+
|           |   |   |
|           |   |   |
|           |   |   |
+-------+   +---+   |
        |           |
+---+   +---+   +---+
|   |       |   |   
|   +-------+   +---+
|                   |
+-------------------+

; The path doesn't visit each vertex and touches itself
; (so visits some points more than once)
+-------------------+
|                   |
|   +-----------+   |
|   |           |   |
|   |   +-------+   |
|   |   |           |
|   |   +-------+   |
|   |           |   |
+---+-----------+   |
    |               |
    +---------------+

; The path doesn't form a loop and touches itself
+---+   +---+   +---+
|   |   |   |   |   |
|   |   |   |   |   |
|   |   |   |   |   |
|   |   |   |   |   |
|   |   |   |   |   |
|   |   |   |   |   |
|   |   |   |   |   |
|   |   |   |   |   |
|   |   |   |   |   | 
+---+---+   +---+---+

Optional `n` = 8

; Two paths
+-------------------+   +---+
|                   |   |   |
|   +-----------+   |   |   |
|   |           |   |   |   |
|   +-------+   |   +---+   |
|           |   |           |
+-------+   |   +-----------+
        |   |               
+---+   +---+   +-----------+
|   |           |           |
|   |   +---+   |   +-------+
|   |   |   |   |   |       
|   +---+   +---+   +-------+
|                           |
+---------------------------+

; The path doesn't visit each vertex
+---------------+   +-------+
|               |   |       |
|   +-------+   +---+       |
|   |       |               |
|   |   +---+   +---+       |
|   |   |       |   |       |
|   |   +-------+   +-------+
|   |                       
|   |   +-------------------+
|   |   |                   |
|   +---+   +---+   +---+   |
|           |   |   |   |   |
|   +---+   |   |   |   |   |
|   |   |   |   |   |   |   |
+---+   +---+   +---+   +---+


; The path doesn't visit each vertex
+---------------+   +-------+
|               |   |       |
|   +-----------+   +---+   |
|   |                   |   |
|   +---+   +-----------+   |
|       |   |               |
+---+   |   +-------+   +---+
    |   |           |   |   
+---+   +-------+   |   |    
|               |   |   |    
|   +-----------+   |   |    
|   |               |   |   
|   +---------------+   +---+
|                           |
+---------------------------+

; Two paths
+-----------+   +-----------+
|           |   |           |
|   +---+   |   |   +-------+
|   |   |   |   |   |       
|   |   |   |   |   +-------+
|   |   |   |   |           |
+---+   |   |   +-------+   |
        |   |           |   |
+---+   |   +-----------+   |
|   |   |                   |
|   |   |   +-----------+   |
|   |   |   |           |   |
|   +---+   +-----------+   |
|                           |
+---------------------------+

; The path touches itself (so visits some points more than once)
+---+   +-------------------+
|   |   |                   |
|   |   |   +---+   +-------+
|   |   |   |   |   |       
|   +---+   |   |   |   +---+
|           |   |   |   |   |
+---+   +---+   |   |   |   |
    |   |       |   |   |   |
+---+   +-------+---+---+   |
|               |   |       |
+-------+   +---+   +---+   |
        |   |           |   |
+-------+   +-----------+   |
|                           |
+---------------------------+

; The path doesn't form a loop
+---------------+   +-------+
|               |           |
+-------+   +   +-------+   |
        |   |           |   |
+-------+   +-----------+   |
|                           |
|   +-------------------+   |
|   |                   |   |
|   +---+   +-----------+   |
|       |   |               |
|   +---+   +-----------+   |
|   |                   |   |
|   +---------------+   |   |
|                   |   |   |
+-------------------+   +---+

Wining criteria:

The shortest solution in bytes in each language wins. I'll highly appreciate if you add explanation of the code and the algorithm you used.

Galen Ivanov

Posted 2019-10-26T08:53:30.637

Reputation: 13 815

Do we have to use the ASCII representation given? Or can we use an alternative ASCII representation? – Nick Kennedy – 2019-10-26T12:44:03.807

Are we allowed to take inputs drawn with only a single - (rather than ---) as the horizontal connector? – Jonah – 2019-10-26T12:55:27.847

@Nick Kennedy Yes, you can. – Galen Ivanov – 2019-10-26T13:44:56.077

@Jonah Yes, you can. – Galen Ivanov – 2019-10-26T13:45:20.593

Answers

5

Charcoal, 63 55 46 bytes

ＡＭ↗ Ｗ⁼№ＫＶ#¹«✳⊗⁻¹⌕ＫＶ#¦ ¿¬∨﹪ⅈ⁴﹪ⅉ²⊞υω»¿‹ＬυＸＮ²⎚«⎚¹

Try it online! Link is to verbose version of code. Edit: Saved 8 bytes by using a more cumbersome but still acceptable input format. Saved 9 bytes by requiring the path only uses #s. Explanation:

Ａ

Copy the path to the canvas.

Ｍ↗

Print a space one square in from the bottom-left corner (the print command left the cursor one square below the bottom-left corner). This should break the loop of #s into a line.

Ｗ⁼№ＫＶ#¹«

Try to follow the line to its end, following the path of #s that used to have two neighbours.

✳⊗⁻¹⌕ＫＶ#¦

Overwrite the line as we go.

¿¬∨﹪ⅈ⁴﹪ⅉ²⊞υω»

Keep track of how many vertices we meet along the way.

 ¿‹ＬυＸＮ²⎚

Check whether we managed to visit every vertex. If not, then just clear the canvas.

«⎚¹

If we visited every vertex then output 1 as a truthy value (which actually prints as -).

Neil

Posted 2019-10-26T08:53:30.637

Reputation: 95 035

You can use alternatve ASCII representation. – Galen Ivanov – 2019-10-26T13:49:58.080

@GalenIvanov Would this be acceptable?

– Neil – 2019-10-26T19:19:30.933

Yes, it is acceptable. – Galen Ivanov – 2019-10-26T19:21:34.737

@GalenIvanov How about this?

– Neil – 2019-10-26T19:28:43.553

Yes, it's fine. You can even have only one # horizontally instead of ### – Galen Ivanov – 2019-10-26T19:53:35.610

1@GalenIvanov Thanks, but I think it would be possible to fool the algorithm in that case. – Neil – 2019-10-26T20:05:26.990

5

Jelly, 34 bytes

Ø1©ȧn⁶µŒṪạ®SỊƊƇḢ©Wḟ@ƲƬṖṪ<3Ȧȧm2m€4Ȧ

A monadic Link accepting a list of lists of characters (the lines) which yields 1 for a Hamiltonian or 0 otherwise. Uses the layout in the question (any non-space chars as path parts will work).

Try it online! Or see the test-suite.

How?

Starts at the top-left, [1,1], and finds a neighbouring non-space until no neighbours can be found, then checks if the final position is the neighbour below the top-left, [2,1], (to confirm the path was a loop) and that no other non-spaces remain (to confirm there were not multiple paths). If so a final check is made that all the vertices were non-spaces too.

Ø1©ȧn⁶µŒṪạ®SỊƊƇḢ©Wḟ@ƲƬṖṪ<3Ȧȧm2m€4Ȧ - Link: list of lines, M
Ø1                                 - literal [1,1]
  ©                                - (copy this to the register and yield it)
   ȧ                               - logical AND (with M) -> M 
     ⁶                             - literal space character
    n                              - not equal? (vectorises)
      µ                            - new monadic chain, call that N
       ŒṪ                          - truthy multidimensional indices
                     Ƭ             - collect up while distinct, applying:
                    Ʋ              -   last four links as a monad:
              Ƈ                    -     filter keep if (find neighbours):
             Ɗ                     -       last three links as a monad:
         ạ                         -         absolute difference (vectorises):
          ®                        -           current register value
           S                       -         sum
            Ị                      -         insignificant? (abs(z)<=1)
               Ḣ                   -     head (a neighbour [x,y] or 0 if none)
                ©                  -     (copy this to the register and yield it)
                 W                 -     wrap in a list
                   @               -     with swapped arguments:
                  ḟ                -       filter discard
                      Ṗ            - remove rightmost
                       Ṫ           - get rightmost (or 0 if none)
                        <3         - less than three? (vectorises)
                          Ȧ        - all non-zero when flattened?
                           ȧ       - logical AND (with N) -> 
                                   - (i.e. N if the entire path looped from [1,1]
                                   -  back to [2,1] leaving nothing unconsumed
                                   -  else 0)
                            m2     - every 2nd value
                              m€4  - every 4th value of each
                                 Ȧ - all non-zero when flattened?

Jonathan Allan

Posted 2019-10-26T08:53:30.637

Reputation: 67 804

4

JavaScript (ES7),  126 124  122 bytes

Takes input as (n)(matrix). Returns a Boolean value.

n=>g=(m,X=k=0,Y=0,d=0)=>m.map((r,y)=>r.map((c,x)=>++c|(x-X)**2+(y-Y)**2-1||g(m,x,r[++d,x%4|y%2||k++,x]=y)))|d>1?k=g:k==n*n

Try it online!

How?

Starting at \$(0,0)\$, we flood-fill the path and increment a counter \$k\$ each time we go through a cell \$(x,y)\$ such that \$x\equiv 0\pmod 4\$ and \$y\equiv 0\pmod 2\$.

At the end of the process, we must have \$k=n^2\$.

We additionally make sure that no cell has more than 2 neighbors. If it does happen, we set \$k\$ to a non-numeric value to force the final test to fail.

Arnauld

Posted 2019-10-26T08:53:30.637

Reputation: 111 334

You can use alternatve ASCII representation. – Galen Ivanov – 2019-10-26T13:49:31.223

1@GalenIvanov Thanks for the notification. That would not help much in my case, because I'm just testing space vs not-space. – Arnauld – 2019-10-26T17:42:54.120

Can we take the input as a matrix of zeros and ones? – Jonah – 2019-10-29T01:47:18.217

3

Jelly, 54 bytes

n⁶,Z$µØ0jm2N,¹ƇɗƝ)m2)Z×LƊ€2¦Ẏ€;"/µØ-ḟN}Ḣɗ,+¥ƭƒịṪ¥¥ƬL=L

Try it online!

A monadic link which takes a list of strings as input and returns a boolean. The strings use the format of the question but omitting every other character (so half the width). Full explanation to follow.

Nick Kennedy

Posted 2019-10-26T08:53:30.637

Reputation: 11 829

1

J, 125 bytes

p=.((,-)#:1 2)|.!.0]
f=.([:(''-:2 0~.@-.~[:,]*+/@p)' '~:])*1-1 e.[:([:,@(,]+1=(2|#\)*/4|#\@|:)([:>./]*"2 p)^:_)_(<0 0)}' '~:]

Try it online!

Just a first draft, but all test cases are passing. Will attempt to golf and add explanation this week.

Jonah

Posted 2019-10-26T08:53:30.637

Reputation: 8 729

Asked: 2019-10-26T08:53:30.637

Viewed: 398 times

Active: 2019-10-29T01:43:24.723