Anonymous user
Talk:Solve a Hidato puzzle: Difference between revisions
→Any good general algorithm?
Line 102:
:: The reason this is [[wp:NP-complete|hard]] is that it is really the finding of a [[wp:Hamiltonian path|Hamiltonian path]] (on a graph with a bound on the number of links per node); you just add in a (possibly non-planar) link between start and finish to see that this must be the case. I don't really feel like putting lots of effort into cracking very hard problems like this other than by simple brute force. Moreover, because it ''is'' finding a Hamiltonian path, there must be cases which are not easy for either computers or humans to solve. (Do I know what they are? No, but an easy solution to arbitrary Hidato would have tremendous application to many other problems like cryptography.)
:: (I'd have written about this earlier, but there's some kind of weird proxy stopping me from posting to RC from home.) –[[User:Dkf|Donal Fellows]] 16:33, 6 May 2012 (UTC)
::: I'm not sure Hidato is really equiv to a general Hamiltioian path problem -- is it known to be NP-complete? Hidato is much more constrained in that it has a unique solution requirement; its nodes can have only up to eight neighbors; and more importantly, spatial proximity between nodes are tightly related to the connectivity between them. Although I do agree that if a problem isn't mathematically well understood (as in, having a known effective algorithm), it's generally not worth putting too much effort into it. --[[User:Ledrug|Ledrug]] 17:49, 6 May 2012 (UTC)
== Short C version ==
| |||