5
$\begingroup$

This puzzle serves as the more concrete sequel to my previous post; in particular, see that post for the rules of the game. Rather than (implicitly) demanding a description of a polynomial-time algorithm for solving all such puzzles—an answer I myself didn't/still don't have—this post has a smaller, well-defined scope: Which of the three arrow sequences below are admissible, and which are inadmissible?

  1. ↑↓↓←↑↓←↑↓↓←↑→←→↓↑↑↓→↑↓←↑↓↓↑←↑↓
  2. →↓↓↑→↓↑→↓↓↑↓↑→↑↓↓↑→↑↓←↓↑↑↓←→←→←↑
  3. ↓↓↑↓↓↓↓→←→↓↑↓↓←→←→↓↓→↓↑←→↓↓↓↓↓→←→↓↓→←↓↓→

These puzzles are meant to be analyzed by hand (in particular, I solved them by hand with less than a single sheet of scrap paper each), and any solutions should be human-derivable and human-checkable. I made them of such a size that a brute force algorithm I coded fails to be feasible at about the ~25 arrow size and only gets exponentially worse from there (the above are of size 30, 32, and 40), but I'll hedge my bets that someone might have better hardware or more efficient implementation and so add the no-computers tag (but feel free to use computers to try to understand the problem in general!).

Here are some example sequences that may be useful for practice before tackling the big ones up above:

  1. ↑↑→→
  2. ←↑↑→
  3. ↑→↑↓←↓
  4. ↑←←↑↓→→↓→↑↓←
  5. ↑→↓←↑→↓←
  6. ↑→↑←↑←→↓→
  7. →←→↓→→←←←→↑←

Concerning the three big sequences that officially comprise this puzzle, it may happen that they are first figured out by different posters. In that case, I will accept whoever's answer attains the most points according to the scheme (1) = 30 points, (2) = 32 points, (3) = 40 points.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Hi! Are you still interested in that stuff? I've written a backtracking solver that (I think) solves the three examples here in 3 seconds or so on my old ramshackle laptop. I'm not 100% sure it's correct and am reluctant to share my filthy code, but the algo is straightforward: manage a dl list of tile border crossings (with some special rules for torus - a nightmare to debug!) and insert the crossings one after the other recursivly exhausting all possibilities. It takes just a few hundred recursion steps and finds 6/0/0 solutions. $\endgroup$
    – loopy walt
    Commented May 11, 2021 at 12:45
  • $\begingroup$ Yeah, I'm still interested. Particularly in the details of your brute force search, since you must have some implemented some smarter means of eliminating non-viable candidates than I did for my program. $\endgroup$
    – Feryll
    Commented May 11, 2021 at 17:40
  • 1
    $\begingroup$ It's conceptually very simple, just a tree search: insert path elements one by one each at all possible insertion sites and backtracking whenever you hit a dead end. The main difficulty is bookkeeping. I hold the path elements in order and additionally as doubly linked list representing their arrangement on the boundary. Now to determine the possible insertion sites you need to walk the boundary alternating between boundary ordering (each step spans an insertion site) and path ordering (each step spans a non accessible region). Getting this right I found rather tricky... $\endgroup$
    – loopy walt
    Commented May 11, 2021 at 18:10
  • $\begingroup$ That's a little inexplicable, then, as my (-o2 compiled) Haskell program does the same thing; at any point, the arrow sequence tells you which side of the square to connect to, so, just try all out all the options there recursively. Does your program treat e.g. the N eastward traversal points as already existing, or does it know how to arbitrarily subdivide areas between (available) traversal points? Mine just does the former, and is a factor that could be improved. $\endgroup$
    – Feryll
    Commented May 12, 2021 at 9:59
  • 1
    $\begingroup$ It does the latter. I have no clean argument but shouldn't that potentially account for a huge difference in complexity? Whenever there is a stretch of k neighbouring connection points and there is a substantial chunk of downstream paths that never come back to that area that's a factor of k right away. $\endgroup$
    – loopy walt
    Commented May 12, 2021 at 10:17

2 Answers 2

Reset to default
2
$\begingroup$

Sequence 1:

Admissible

enter image description here

Sequence 3:

Not Admissible

enter image description here

We can look at a specific chunk of the sequence, n this case →↓↑↓↓←, and if it cannot be drawn, the entire sequence is not admissible. The top image shows how the first couple of directions must happen. Below it are the two scenarios depending on whether the blue segment begins going to the left or right. Either way, it leads to not being able to go left for its sixth move, making the sequence not admissible.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Well done. Although you didn't get the second sequence, since you answered two out of the three problems first, as promised by the post, I'll award you the accepted answer status. I actually had a totally different way of dismissing the third sequence. $\endgroup$
    – Feryll
    Commented May 2, 2021 at 22:21
  • $\begingroup$ Also, any word on how you managed to identify these individually impossible subsequences? $\endgroup$
    – Feryll
    Commented May 2, 2021 at 22:31
  • $\begingroup$ Essentially I just drew out sequence 3, and although there was occasional bifurcation, for most arrows there was only one way to do it. When I came to some point where the line could not continue, I isolated that chunk of the sequence to see if it was itself impossible and came to the above conclusion about sequence 3. $\endgroup$
    – SeptaCube
    Commented May 3, 2021 at 2:17
2
$\begingroup$

My solution(s)

Of the 3 sequences, only 1 is admissible
enter image description here

Since I was confused myself about the correctness, I 'stole' the coloring of the other solution
enter image description here

This is how I did it

enter image description here

Improve this answer
$\endgroup$
4
  • $\begingroup$ Nicely done. Mind explaining what those two graphs are indicating? Or how it is that you got the admissible sequence's diagram while still being confused about the correctness? I'd be curious to hear about your methods in general and how closely they line up with my own. $\endgroup$
    – Feryll
    Commented May 2, 2021 at 22:20
  • $\begingroup$ Graphs: Subsequences have to stay in each others 'bandwidth', so can differ 1 in how much they drop the same distance further right: Going 1 to the right 3green drops 3 more (drops 5) than 3red (drops 2), so would cross green lines that start lower (1 starts in each tile). Similarly there is a difference of 2 drops (-1 vs +1) when 2red and 2 blue move 2 tiles to the right. $\endgroup$
    – Retudin
    Commented May 3, 2021 at 9:25
  • $\begingroup$ Correctness: when looking at the other solution, the differences made me double check my solution and I lost track of where I was (and for a moment I thought I made a mistake). Adding colors helped me see that my solution was also correct, and the now made colored one seemed a useful addition to to my answer $\endgroup$
    – Retudin
    Commented May 3, 2021 at 9:30
  • $\begingroup$ Ah, thank you very much for the clarifications. Your diagramming is interesting. $\endgroup$
    – Feryll
    Commented May 3, 2021 at 18:32

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.