# Is it a Hamiltonian cycle on a grid?

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

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? Commented Oct 26, 2019 at 12:44
• Are we allowed to take inputs drawn with only a single - (rather than ---) as the horizontal connector? Commented Oct 26, 2019 at 12:55
• @Nick Kennedy Yes, you can. Commented Oct 26, 2019 at 13:44
• @Jonah Yes, you can. Commented Oct 26, 2019 at 13:45

# Charcoal, 6355 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 -).

• You can use alternatve ASCII representation. Commented Oct 26, 2019 at 13:49
• @GalenIvanov Would this be acceptable?
– Neil
Commented Oct 26, 2019 at 19:19
• Yes, it is acceptable. Commented Oct 26, 2019 at 19:21
– Neil
Commented Oct 26, 2019 at 19:28
• @GalenIvanov Thanks, but I think it would be possible to fool the algorithm in that case.
– Neil
Commented Oct 26, 2019 at 20:05

# 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:
Ƈ                    -     filter keep if (find neighbours):
ạ                         -         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:
Ṗ            - 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?


# 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!

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. • You can use alternatve ASCII representation. Commented Oct 26, 2019 at 13:49 • @GalenIvanov Thanks for the notification. That would not help much in my case, because I'm just testing space vs not-space. Commented Oct 26, 2019 at 17:42 • Can we take the input as a matrix of zeros and ones? Commented Oct 29, 2019 at 1:47 # 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. # 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.