Talk:Solve a Hidato puzzle: Difference between revisions
Content added Content deleted
(→Any good general algorithm?: Hidato ≡ Hamiltonian Path = NP complete) |
|||
| Line 99: | Line 99: | ||
: Heeey, who you callin' evil? |
: Heeey, who you callin' evil? |
||
: I was curious if anyone has a good heuristic method that's reasonably simple and works for most cases, like the one used in knight's tour, but I guess it's a bit asking for much. It's just that a task with only an exponential brute force general solution is somewhat disappointing -- oh well. --[[User:Ledrug|Ledrug]] 11:35, 3 May 2012 (UTC) |
: I was curious if anyone has a good heuristic method that's reasonably simple and works for most cases, like the one used in knight's tour, but I guess it's a bit asking for much. It's just that a task with only an exponential brute force general solution is somewhat disappointing -- oh well. --[[User:Ledrug|Ledrug]] 11:35, 3 May 2012 (UTC) |
||
:: “Evil” is actually quite complimentary. |
|||
:: 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) |
|||
== Short C version == |
== Short C version == |
||