• DocumentCode
    3696842
  • Title

    Satogaeri, Hebi, and Suraromu Are NP-Complete

  • Author

    Shohei Kanehiro;Yasuhiko Takenaga

  • Author_Institution
    Grad. Sch. of Inf. &
  • fYear
    2015
  • fDate
    7/1/2015 12:00:00 AM
  • Firstpage
    46
  • Lastpage
    51
  • Abstract
    Pencil puzzles are the puzzles such that people write answers on problems printed on paper. In this paper, we deal with three pencil puzzles, Satogaeri, Hebi and Suraromu. We show that the problems to decide the solvability of these puzzles are NP-complete. Also, in all of these puzzles, we show that there exist the rules without which the puzzles remain NP-complete.
  • Keywords
    "Logic gates","Wires","Games","Polynomials","Tracking","Turning","Scientific computing"
  • Publisher
    ieee
  • Conference_Titel
    Applied Computing and Information Technology/2nd International Conference on Computational Science and Intelligence (ACIT-CSI), 2015 3rd International Conference on
  • Type

    conf

  • DOI
    10.1109/ACIT-CSI.2015.17
  • Filename
    7336032
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3696842