The Magnets Puzzle is NP-Complete

IPSJ

Search this article

Description

In a Magnets puzzle, one must pack magnets in a box subject to polarity and numeric constraints. We show that deciding solvability of Magnets instances is NP-complete. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.20(2012) No.3 (online) DOI　http://dx.doi.org/10.2197/ipsjjip.20.707 ------------------------------

In a Magnets puzzle, one must pack magnets in a box subject to polarity and numeric constraints. We show that deciding solvability of Magnets instances is NP-complete. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.20(2012) No.3 (online) DOI　http://dx.doi.org/10.2197/ipsjjip.20.707 ------------------------------

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top