A heuristic approach to domino grid problem

NABIYEV V., PEHLİVAN H.

INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS, cilt.54, sa.4, ss.1056-1068, 2023 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 54 Sayı: 4
  • Basım Tarihi: 2023
  • Doi Numarası: 10.1007/s13226-022-00321-x
  • Dergi Adı: INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, INSPEC, zbMATH
  • Sayfa Sayıları: ss.1056-1068
  • Anahtar Kelimeler: Domino tiling, Heuristic search, Bigraphs, Perfect matching, Enumeration, TILINGS, NUMBER, DIMERS
  • Karadeniz Teknik Üniversitesi Adresli: Evet

Özet

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.