36 square rooms are arranged in a 6x6 grid. The outside wall of the grid has no doors. All other walls have exactly one door, for a total of 60 doors. A guard follows a path that takes him through as many doors as possible, never going through the same door twice (he may enter a room twice, as long as he uses different doors.) What is the maximum number of doors he can use if:
Extensions: Repeat for 3x3 to 8x8 grids.
Source: Original.
The question is actually a graph question.
Find the maximum subgraph which has an Euler path or Euler circuit.
On even length sides the solution is obvious. On the sides (which have 3 edges) clear every other door along the side. If he can start and end in different cells just add one door. This is maximal because each removal solves 2 "problems".
The solution for odd sizes is almost as simple, follow the same algorithm starting from opposite corners.
Note that there are 2 moves which don't solve "problems", just move them away. Since there are corners with 2 consecutive doors not visited, adding a
corner and its 2 doors solves for finishing in a different cell.
numbers: (total, circle, non-circle)
3: 12 8 10
4: 24 20 21
5: 40 32 34
6: 60 52 53
7: 84 72 74
8: 112 100 101
general solution:
(code): X Y
Odd: n*(n-1)*2 X-2*n+2 Y+2
Even: n*(n-1)*2 X-2*n+4 Y+1
Kirk Bresniker adds:
I searched these on OEIS and while the circular case didn't hit, the non-circular did hit with a match to your problem:
http://www.research.att.com/~njas/sequences/A049486A049486 Maximum length of non-crossing path on n X n square lattice.