The Magnets Puzzle is NP-Complete

情報処理学会

この論文をさがす

説明

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 ------------------------------

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ