This is a 9x9 grid, with a sign in the center cell like shown. You can add signs to this grid one at a time following these rules:
- Each sign placed must point to the next sign placed
- Placed signs become obstacles, so future signs cannot point through them
- Every new sign turns right (90 deg clockwise of last sign)
- An older sign may not become blocked by newer signs
What is the maximum number of signs you can place on this grid?
For sake of clarity, if you would like to answer this question, please use this numbered notation. It's easier to understand.
Sorry if this puzzle is a little open-ended. I think I have the maximum but I've been wrong before, and that was just today.
Answer
Edit: my answer was inadequate. Only downvotes now please.
@Oray asked to follow up his answer and I found a fault in my previous work, resulting in
50 signs.
It's neat the way it ends up in the corner.
This 50-solution was found fairly quickly but the code ran for 15 minutes.
My original and obsolete answer was
36 signs.Looking at the left-hand diagram below, one obvious solution taking a spiral path is 18 signs.
However I felt sure that could be improved if the signs were placed closer together; the shorter each path, the more signs can be placed. As no sign may block the path between two other signs, I thought an interwoven arabesque pattern such as in the right-hand diagram would do that. The idea was that each corner could be filled in turn, moving to the next corner.But I got in such a terrible tangle that I decided to write a recursive solution in C code that explored all possible solutions. It turned out to be feasible and all routes were explored within a few seconds, giving only one solution (with an alternative position for the last sign).
The result turned out to be what I intended: each corner filled in succession clockwise.
No comments:
Post a Comment