Matchstick puzzles on a grid

DOI10.1007/S00373-019-02078-3MaRDI QIDQ2308506zbMATH OpenOpenAlexFDO

Authors Y. Takenaga, Shohei Mishiba, Haruka Sugiyama

Publication date 3 April 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-019-02078-3

zbMATH Keywords

algorithmNP-completenesspuzzlestring matching

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Recommendations

• Edge-matching problems with rotations
• Strategy and Complexity of The Game of Squares
• A graph-theoretical approach to solving scramble squares puzzles
• Tatamibari is NP-complete
• Solving general lattice puzzles

Cites work

• Faster algorithms for string matching with k mismatches
• Games, puzzles, and computation
• Hashiwokakero is NP-complete
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• NP-completeness of two pencil puzzles: Yajilin and Country Road
• On string matching with mismatches
• Shikaku and Ripple Effect are NP-complete

Cited in

(2)

• Sliding piece puzzles with oriented tiles
• scientific article; zbMATH DE number 7132810 (Why is no real title available?)

This page was built for publication: Matchstick puzzles on a grid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2308506)