Monday, 8 June 2015

strategy - You Sign Me Right Round


enter image description here


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.


enter image description here



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.

enter image description here
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.

enter image description here
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).

enter image description here
The result turned out to be what I intended: each corner filled in succession clockwise.



No comments:

Post a Comment

Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...