Talk:Mutagen Puzzle

multiple solutions for the puzzle

There are multiple solutions possible. For instance, adding an atom that doesn't do anything. For this page's example, there's a shorter solution available:

Io-3 Io-2 Echo-1 Io-3 Solis-2 Io-1

Are there some boundaries on solution's length? I can see that a naive depth-first search (even with epeli's pruning method) chokes on lengths between 6 and 8. I assume that my computed solution has the shortest length, given iterative deepening. Maybe there's some unused optimization in depth-first that I could take into account. sthalik (talk) 12:31, 3 December 2018 (CST)

Actually what problem does this puzzle generalize to? Is it just graph search like I'm naively assuming right now? sthalik (talk) 12:41, 3 December 2018 (CST)

I found a working solution! Do it depth-first assuming no cycles BUT as depth limit is reached, reset it to zero, clear cycles bitmask, and decrement ncycles. Only stop once ncycles is zero. sthalik (talk) 16:47, 3 December 2018 (CST)

Yup, many puzzles have infinite solutions through repeated no-op mutagens. Nice catch with the example, I hadn't paid careful attention to it as I didn't write it.

There are boundaries to the length of the generated solution, but that's inconsequential to players. In practice most puzzles have more than one solution and longer solutions are often easier for humans to find and reason about, as appears to have been the case with the article's example. :)

IIRC somebody else came up with the pruning method and although it's great for puzzles that benefit from it, programs can't rely on it as optimization. You often can't exclude any mutagens, so a general-purpose solver must be fast enough to deal with all 15 of them.

I reckon the most efficient way to solve mutagen puzzles programmatically is a depth-first search algorithm with custom heuristic for scoring compounds based on how close to Exitus they are. Micro-optimizations for bruteforce searches are a waste of time. I mean my solver's original test implementation was a piece of javascript that did string manipulation and rendered each step it took to HTML. You can't get much slower per-step performance than that, yet it was already fast enough to solve most puzzles in milliseconds. A good heuristic might walk straight into a solution for all puzzles - mine solves only about 80% like that. But the real benefit (for my application, anyways) is relatively low CPU time cost for flagging broken puzzles as unsolvable with reasonable confidence. - epeli (talk) 00:38, 5 December 2018 (CST)