Talk:Solve a Hidato puzzle: Difference between revisions
Content added Content deleted
(→Any good general algorithm?: Suspicion remains) |
|||
| Line 103: | Line 103: | ||
:: (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'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) |
::: 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) |
||
:::: I'm also not ''sure'' that is HP, but the suspicion remains. I couldn't find anything in WP on requirements on connectivity for graphs doing HP; maybe there is something, but I couldn't find it. (Graph theory isn't my specialty, not at all.) –[[User:Dkf|Donal Fellows]] 08:55, 7 May 2012 (UTC) |
|||
== Short C version == |
== Short C version == |
||