A heuristic approach to domino grid problem

Vasif V. Nabiyev () and Hüseyin Pehlivan ()
Additional contact information
Vasif V. Nabiyev: Karadeniz Technical University
Hüseyin Pehlivan: Karadeniz Technical University

Indian Journal of Pure and Applied Mathematics, 2023, vol. 54, issue 4, 1056-1068

Abstract: Abstract Dominoes have been the main subject of many theoretical and practical studies, which have primarily focused on the solutions to domino tiling problems. The domino grid problem is a different type of tiling problems in which the aim is to find a complete set of dominoes on a two-dimensional grid arranged in a patternless fashion. Tiling problems are generally solved using combinatorial search methods because the grid can be organized into a large number of possible domino patterns. This paper addresses an efficient solution to the domino grid problem, using a heuristic approach governed by some state-specific rules. The problem is represented by a bipartite graph and a possible solution is obtained by computing a perfect matching in the graph, based on the degrees and positions of dominoes. For different grid layouts, the search space of the problem is explored, enumerating the total number of state evaluations required to generate all possible solutions.

Keywords: Domino tiling; Heuristic search; Bigraphs; Perfect matching; Enumeration; 05B45; 05B50; 90C59; 90C27; 05A15 (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13226-022-00321-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:indpam:v:54:y:2023:i:4:d:10.1007_s13226-022-00321-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/13226

DOI: 10.1007/s13226-022-00321-x

Access Statistics for this article

Indian Journal of Pure and Applied Mathematics is currently edited by Nidhi Chandhoke

More articles in Indian Journal of Pure and Applied Mathematics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().