Is it a Hamiltonian cycle on a grid?

Question

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.

Do we have to use the ASCII representation given? Or can we use an alternative ASCII representation? — Nick Kennedy, Oct 26, 2019 at 12:44
Are we allowed to take inputs drawn with only a single - (rather than ---) as the horizontal connector? — Jonah, Oct 26, 2019 at 12:55

Neil · Accepted Answer · 2019-10-26 20:04:37Z

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 -).

edited Oct 26, 2019 at 20:04

answered Oct 26, 2019 at 12:17

Neil

166k12 gold badges69 silver badges273 bronze badges

\$\begingroup\$ You can use alternatve ASCII representation. \$\endgroup\$
– Galen Ivanov
Oct 26, 2019 at 13:49
\$\begingroup\$ @GalenIvanov Would this be acceptable? \$\endgroup\$
– Neil
Oct 26, 2019 at 19:19
\$\begingroup\$ Yes, it is acceptable. \$\endgroup\$
– Galen Ivanov
Oct 26, 2019 at 19:21
\$\begingroup\$ @GalenIvanov How about this? \$\endgroup\$
– Neil
Oct 26, 2019 at 19:28
1

\$\begingroup\$ @GalenIvanov Thanks, but I think it would be possible to fool the algorithm in that case. \$\endgroup\$
– Neil
Oct 26, 2019 at 20:05

| Show 1 more comment

Jonathan Allan · Accepted Answer · 2019-10-28 02:42:49Z

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?

Community · Accepted Answer · 2020-06-17 09:04:33Z

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.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 26, 2019 at 10:25

Arnauld

189k20 gold badges171 silver badges631 bronze badges

\$\begingroup\$ You can use alternatve ASCII representation. \$\endgroup\$
– Galen Ivanov
Oct 26, 2019 at 13:49
1

\$\begingroup\$ @GalenIvanov Thanks for the notification. That would not help much in my case, because I'm just testing space vs not-space. \$\endgroup\$
– Arnauld
Oct 26, 2019 at 17:42
\$\begingroup\$ Can we take the input as a matrix of zeros and ones? \$\endgroup\$
– Jonah
Oct 29, 2019 at 1:47

Add a comment |

Nick Kennedy · Accepted Answer · 2019-10-26 21:49:18Z

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.

answered Oct 26, 2019 at 21:49

Nick Kennedy

19.1k3 gold badges16 silver badges40 bronze badges

Add a comment |

Jonah · Accepted Answer · 2019-10-29 01:43:24Z

2

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.

answered Oct 29, 2019 at 1:43

Jonah

33k4 gold badges38 silver badges92 bronze badges

Add a comment |

Stack Exchange Network

Is it a Hamiltonian cycle on a grid?

Task:

Input:

Output:

Test cases:

Wining criteria:

5 Answers 5

Charcoal, 63 55 46 bytes

Jelly, 34 bytes

How?

JavaScript (ES7), 126 124 122 bytes

How?

Jelly, 54 bytes

J, 125 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
decision-problem
grid
or ask your own question.

Hot Network Questions

Is it a Hamiltonian cycle on a grid?

Task:

Input:

Output:

Test cases:

Wining criteria:

5 Answers 5

Charcoal, 63 55 46 bytes

Jelly, 34 bytes

How?

JavaScript (ES7), 126 124 122 bytes

How?

Jelly, 54 bytes

J, 125 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfdecision-problemgrid or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
decision-problem
grid
or ask your own question.