View Forum Topic

Author	Message
rabbott Posts: 1649	Posted 09:35 Dec 14, 2019 \| Here are a number of web pages that discuss the computational complexity of puzzles. Quite a few are NP-hard or NP-complete. A Survey of NP-complete puzzles. Wikipedia page of NP-complete problems, including a section on puzzles. Computational complexity of games and puzzles. As we discussed in class Nurikabe is known to be NP-complete. Here's a start on a MiniZinc solver for it. It's not finished, though. Last edited by rabbott at 09:36 Dec 14, 2019.

Author

Message

rabbott

Posts: 1649

Posted 09:35 Dec 14, 2019 |

Here are a number of web pages that discuss the computational complexity of puzzles. Quite a few are NP-hard or NP-complete.

As we discussed in class Nurikabe is known to be NP-complete. Here's a start on a MiniZinc solver for it. It's not finished, though.

Last edited by rabbott at 09:36 Dec 14, 2019.