[PDF][PDF] A Paper on Pencils: A Pencil and Paper Puzzle

P is NP-Complete - Conference on Computational Geometry (CCCG …, 2018 - academia.edu
P is NP-Complete
Conference on Computational Geometry (CCCG 2018), 2018academia.edu
Pencils is a paper-and-pencil puzzle created by Japanese publisher Nikoli. A puzzle is an m-
by-n grid where some squares hold a number or a pencil tip that is pointed in one of the
cardinal directions. The goal is to draw 'pencils' that partition the squares of the grid. Each
pencil occupies 2k+ 1 squares for some k≥ 1. A k-pencil has a horizontal or vertical body of
length k, a tip pointing away from one end of the body, and a lead that is a path of k squares
starting from the tip. In addition, any number inside a body must match the body's size. We …
Abstract
Pencils is a paper-and-pencil puzzle created by Japanese publisher Nikoli. A puzzle is an m-by-n grid where some squares hold a number or a pencil tip that is pointed in one of the cardinal directions. The goal is to draw ‘pencils’ that partition the squares of the grid. Each pencil occupies 2k+ 1 squares for some k≥ 1. A k-pencil has a horizontal or vertical body of length k, a tip pointing away from one end of the body, and a lead that is a path of k squares starting from the tip. In addition, any number inside a body must match the body’s size. We show that Pencils is NP-complete even when limited to 1-pencils and 2-pencils.
academia.edu
以上显示的是最相近的搜索结果。 查看全部搜索结果