I opted to brute force it. There appear to be 9628 solutions. Code and solutions over here.
The puzzle itself presents a directed graph and then asks you to find a path that hits all nodes once and only once, starting and ending at specific nodes. This is essentially the Traveling Salesman Problem. In the general case this is known to be a NP-hard problem (i.e.: there isn't much in the way of shortcuts). I imagine a similar puzzle designed around the arrangement and discovery of "artifacts" (like 1->8 and 31->26) would make for a puzzle where brute forcing is less desirable.
I'm best with C#, JavaScript, and Python these days. Out of those Python seemed the obvious choice for quick a mock-up of this sort.
The algorithm started out as a straight-up recursive brute force using just a tracking queue. Optimizations included:
- adding a
set
(they're much faster for searching collections),
- a fixed length queue with separate actual length tracking (faster to change values rather than
.append()
/del
; since searching the set
is much faster, we can get away with using .add()
/.discard()
; this also allowed me to remove the list copying I had going on),
- move stuff out of the inner loop
Doing all of this feels like code golf but you're optimizing for speed rather than size. There's probably more optimizations that could be made but, by then, it was fast enough that I'd gotten an answer before I'd figured out the next optimization. Even so, it still took 15-20 minutes to run and about an hour to code.
cells = [
None,
[2,7,8], # 1 start
[7,9], # 2 b diagnal
[2,4,9], # 3 y adjacent
[2,6,14,16,18], # 4 r 2space
[4,6,11], # 5 y
[5,12], # 6 y
[8,13], # 7 y
[2,7,9,14], # 8 y
[3,8,10,15], # 9 y
[3,5,15,17], # 10 b
[5,10,12,17], # 11 y
[5,17], # 12 b
[3,15,25,27], # 13 r
[7,9,19,21], # 14 b
[8,10,20,22], # 15 b
[2,4,6,14,18,26,28,30], # 16 r
[10,12,22,24], # 17 b
[11,23], # 18 b
[13,20,25], # 19 y
[13,15,25,27], # 20 b
[14,16,26,28], # 21 b
[16,21,23,28], # 22 y
[16,18,28,30], # 23 b
[10,12,22,34,36], # 24 r
[20,32], # 25 b
[14,16,28], # 26 r
[21,26,28,33], # 27 y
[21,23,33,35], # 28 b
[23,28,30,35], # 29 y
[24,29,36], # 30 y
[26], # 31 b
[26,31,33], # 32 y
[19,21,23,31,35], # 33 r
[27,29], # 34 b
[29,34,36] # 35 y
]
results = []
historyl = [None] * len(cells)
historys = set()
f = open('out.txt','w')
def find(this = 1, depth = 0):
#print historyl, this
if this == 36 and depth == 35:
r = historyl[:depth]
r.append(this)
results.append(r)
print r
print >>f, r
elif this != 36:
historyl[depth] = this
for x in cells[this]:
if x not in historys:
historys.add(this)
find(x, depth+1)
historys.discard(this)
find()
f.close()
13 -> 21
allowed? $\endgroup$