NP-hardness of Square Breaker Puzzle

IPSJ

Bibliographic Information

Other Title
  • Square BreakerパズルのNP困難性
Published
2002-11-15
Resource Type
conference paper
Publisher
情報処理学会

Description

Square BreakerはInternational Collegiate Programming Contest（ICPC）2001年アジア予選taejon大会で出題されたマッチ棒を使ったパズルである．この問題は，NP困難であると予想されていたが，証明はされていなかった．本論文ではこの問題がNP困難であることを証明する．証明の結果自体には予想されたことでもありインパクトはないが，証明の過程自体は興味深いと思われる．

Square Breaker is a puzzle with matchsticks, which appeared as a problem of International Collegiate Programming Contest (ICPC) Asia regional Taejon in 2001. This problem has been assumed to be a NP-hard problem, but the proof has not been done. In this paper, we show that the problem is NP-hard. Although the result itself has been assumed to be true, the proof process is seemed to be interesting.

Journal

Details 詳細情報について

Report a problem

Back to top