News for hackers. Stuff that matters.
Re:Solving NP-hard puzzles with the oldest trick in the book by petters on Thursday October 14, 2021 @01:44AM (#28860869)
How is this puzzle NP-hard? Genuine question, because of the number of pieces is bounded, it's solvable with a shortest path in a graph with a polynomial number of nodes.
Re:Solving NP-hard puzzles with the oldest trick in the book by taintegral on Thursday October 14, 2021 @02:00AM (#28860955)
Bounding the maximum number of actors is just an optimization for the cases we want to solve. Of course if you wanted to really solve any case you would need infinite space, and that’s not achievable either. If you desired, you can also just omit that particular optimization. :) I think a better way to phrase it is that we are writing a solver for a reasonable subset of inputs to an NP-hard problem.
Re:Solving NP-hard puzzles with the oldest trick in the book by contravariant on Thursday October 14, 2021 @07:38AM (#28862962)
Wouldn't the size of the graph grow something like $n^k / k!$ ? This is not polynomial in $k$.
Re:Solving NP-hard puzzles with the oldest trick in the book by lostmsu on Friday October 15, 2021 @03:56PM (#28882382)
lim (k -> 0) (n^k / (k!)) is actually 0. k! grows faster than n^k for any constant n.
Re:Solving NP-hard puzzles with the oldest trick in the book by contravariant on Saturday October 16, 2021 @09:56AM (#28887909)
I should have been a bit more careful I suppose, but in practice you can't increase k indefinitely without also increasing n anyway. In particular n >= k, so at worst it would be something like k^k / k!.
Re:Solving NP-hard puzzles with the oldest trick in the book by taintegral on Friday October 15, 2021 @07:17PM (#28884231)
Really not sure why the state space would only grow as n^k / k!. As well as what n and k are in this case. Adding more tiles or more actors would both dramatically increase the size of the state space for that input.
Re:Solving NP-hard puzzles with the oldest trick in the book by lostmsu on Saturday October 16, 2021 @12:25AM (#28885543)
That question should go to the parent comment. I only corrected the assumption.

On your comment though, I don't think there's much of "drama" in increasing the state space. Really it is just under 2 bits per cell by width by height. I would say it grows exponentially to the size of the board.