Matchstick Puzzles on a Grid
| Autor: | Haruka Sugiyama, Yasuhiko Takenaga, Shohei Mishiba |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Square tiling
0211 other engineering and technologies Brute-force search 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology String searching algorithm Grid 01 natural sciences Theoretical Computer Science Combinatorics Reduction (complexity) 010201 computation theory & mathematics Bounded function Discrete Mathematics and Combinatorics Constant (mathematics) Algorithm Time complexity Mathematics |
| Zdroj: | Graphs and Combinatorics. 36:347-357 |
| ISSN: | 1435-5914 0911-0119 |
| DOI: | 10.1007/s00373-019-02078-3 |
| Popis: | In this paper, we consider two kinds of matchstick puzzles. In both puzzles, matchsticks can be placed only on the edges of a square grid. The first problem is to make a given placement of matchsticks by moving the designated number of matchsticks. We show an algorithm to solve this problem using string matching with errors that is faster than exhaustive search. The second problem is to make the designated number of squares by moving the designated number of matchsticks. We show that this problem is NP-complete by reduction from circuit-SAT. We also show that the problem can be solved in polynomial time if the width of the grid is bounded by a constant. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink