NP-completeness of two pencil puzzles: Yajilin and Country Road

Authors

  • Ishibashi, Ayaka
  • Sato, Yuichi
  • Iwata, Shigeki

Abstract

Two pencil puzzles, Yajilin and Country Road, are shown NP-complete. Modified versions of the Hamiltonian cycle problem on planar undirected graphs are reduced to the puzzle problems to show NP-hardness.

Published

2012-06-09

How to Cite

Ishibashi, Ayaka, Sato, Yuichi, & Iwata, Shigeki. (2012). NP-completeness of two pencil puzzles: Yajilin and Country Road. Utilitas Mathematica, 88. Retrieved from https://utilitasmathematica.com/index.php/Index/article/view/863

Issue

Vol. 88 (2012): Volume 88, 2012

Section

Articles

Citation Check