Search

In this paper, we propose an integer linear programming model whose solutions are the aperiodic rhythms tiling with a given rhythm A. We show how it can be used to define an iterative algorithm that, given a period n, finds all the rhythms which tile with a given rhythm A and also to efficiently check the necessity of the Coven-Meyerowitz condition (T2). To conclude, we run several experiments to validate the time efficiency of the model.

We study the computational hardness of the tiling puzzle with polyominoes, where a polyomino is a rectilinear polygon (i.e., a polygon made by connecting unit squares.) In the tiling problem, we are given a rectilinear polygon P and a set S of polyominoes, and asked whether P can be covered without any overlap using translated copies of polyominoes in S. In this paper, we focus on trominoes and bars as polyominoes; a tromino is a polyomino consisting of three unit squares, and a bar is a rectangle of either height one or width one. Notice that there are essentially two shapes of trominoes, that is, I-shape (i.e., a bar) and L-shape. We consider the tiling problem when restricted to only L-shape trominoes, only I-shape trominoes, both L-shape and I-shape trominoes, or only two bars. In this paper, we prove that the tiling problem remains NP-complete even for such restricted sets of polyominoes. All reductions are carefully designed so that we can also prove the #P-completeness and ASP-completeness of the counting and the another-solution-problem variants, respectively.Our results answer two open questions proposed by Moore and Robson (2001) and Pak and Yang (2013)., identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/15100

We study the computational hardness of the tiling puzzle with polyominoes, where a polyomino is a rectilinear polygon (i.e., a polygon made by connecting unit squares.) In the tiling problem, we are given a rectilinear polygon P and a set S of polyominoes, and asked whether P can be covered without any overlap using translated copies of polyominoes in S. In this paper, we focus on trominoes and bars as polyominoes; a tromino is a polyomino consisting of three unit squares, and a bar is a rectangle of either height one or width one. Notice that there are essentially two shapes of trominoes, that is, I-shape (i.e., a bar) and L-shape. We consider the tiling problem when restricted to only L-shape trominoes, only I-shape trominoes, both L-shape and I-shape trominoes, or only two bars. In this paper, we prove that the tiling problem remains NP-complete even for such restricted sets of polyominoes. All reductions are carefully designed so that we can also prove the #P-completeness and ASP-completeness of the counting and the another-solution-problem variants, respectively.Our results answer two open questions proposed by Moore and Robson (2001) and Pak and Yang (2013).