6
$\begingroup$

How can I find the non-self-intersecting loop that uses the least amount of straight lines (curves left/right as often as possible every turn) and still loops back on itself?

Here's an example we have calculated for 8x8:

Image

Here is an example we have calculated for a 6x6:

Image

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Does it have to touch every square, or could you just draw one small square loop? $\endgroup$
    – Ben McKay
    Nov 23, 2020 at 22:14
  • $\begingroup$ @BenMcKay it must touch every square $\endgroup$
    – Tzlil
    Nov 25, 2020 at 13:13
  • $\begingroup$ Do you also need to have longest straight segment as short as possible and occur as seldom as possible, or you just need to minimize total length of straight segments longer than 1? $\endgroup$
    – მამუკა ჯიბლაძე
    Nov 25, 2020 at 17:57
  • $\begingroup$ @მამუკაჯიბლაძე i only need to minimize the total amount of straight lines, the length of straight segments in it does not matter $\endgroup$
    – Tzlil
    Nov 27, 2020 at 15:36
  • $\begingroup$ By straight lines you mean straight line segments of length two or more? $\endgroup$
    – მამუკა ჯიბლაძე
    Nov 27, 2020 at 19:35

2 Answers 2

Reset to default
7
$\begingroup$

This problem is a special case of the quadratic traveling salesman problem in which the cost for traversing three consecutive nodes that have no turn is $1$ and the cost is $0$ otherwise. Because your graph is bipartite, the problem is infeasible when the number of nodes is odd. For $n\in\{2,4,6,8\}$, the optimal objective values are $0, 4, 8, 8$, so your two examples are optimal. For $n=10$, the optimal objective value is $12$:

enter image description here

For $n=12$, the optimal objective value is $12$: enter image description here

For $10 \times 14$, the optimal objective value is $14$: enter image description here

Improve this answer
$\endgroup$
4
  • $\begingroup$ Nice! Your $12\times12$ solution yields immediately $f(4a,2b)\le4a$ by cloning the 4 columns #3 to 6 (with then tweaking 3 segments to reproduce the inner $8\times4$ pattern to the left), which increases $f$ each time by $4$. $\quad$ What does your program yield for $10\times14$? $\endgroup$
    – Wolfgang
    Nov 24, 2020 at 8:47
  • $\begingroup$ Thank you for the $10\times14$ example, so for reasons of parity, $f(10,14)$ is $12$ or $14$. I had thought your program does some kind of exhaustive search. (BTW, how can you know it is bigger than $10$? - From the various examples, it is now obvious that a lower bound is given by the number of "zigzag parts" in the loop, as each "corner" between them needs at least one straight segment to link them without self-overlap). This argument shows that $f$ is not bounded, in fact it seems well possible that it yields $f(a,b)\ge\min(a,b)$. $\endgroup$
    – Wolfgang
    Nov 24, 2020 at 20:16
  • $\begingroup$ ... But it seems tricky to capture what happens at the boundaries between two "zigzag parts". E.g. it makes sense to consider the cross at the right in your $10\times10$ loop as the union of 3 such zigzag parts (kind of direction changes), yet the straight segments are not between them, though at least 2 of the 3 are obviously required. $\endgroup$
    – Wolfgang
    Nov 24, 2020 at 20:39
  • $\begingroup$ I am using integer linear programming, which yields lower bounds via relaxation. $\endgroup$
    – RobPratt
    Nov 24, 2020 at 21:42
0
$\begingroup$

For a $m\times n$ rectangle (where $mn$ must be even), denote by $f(m,n)$ the minimal number of cell centers with straight lines (centers corresponding to lattice points in the below images).
I can show at least that for a $4a\times 2b$ rectangle, we have $f(4a,2b)\le 4a$.

The following construction is somewhat canonical, given the snake like shape at a "higher level", i.e. when looking in terms of $4\times4$ subsquares. It starts with the construction in the first image for $f(12,12)=12$ (which is optimal by RobPratt's answer). Cloning a pair of middle rows in the way an Excel table would do it, $f$ does not increase, thus we obtain $f(12,12+2k)\le 12$. And the four columns in the yellow frame may be cloned by mirroring horizontally, which makes for a bigger snake and increases $f$ by $4$, thus $f(16,12+2k)\le 16$. The second image should be self-explaining how to iterate that.

enter image description here I am sure that the bound is sharp whenever $2b\ge4a$. As said in the comments, looking at what are the blue components in RobPratt's pictures (i.e. the "zigzag parts" in the loop), it is quite clear that the number of those components is a lower bound for $f$, as each "corner" between them needs at least one straight segment to link them without self-overlap or unconnected corner points. But this argument would still need to be made rigorous. It would very probably imply $f(m,n)\ge\min(m,n)$, which would then be sharp whenever $\min(m,n)\equiv0\pmod4$ and $n$ even. (It seems like when one of the sides is odd, $f$ is bigger and does not only depend on the minimum.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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