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.
[ Parent
| on HN ]
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.