A heuristic approach to domino grid problem

NABIYEV V., PEHLİVAN H.

INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS, vol.54, no.4, pp.1056-1068, 2023 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 54 Issue: 4
  • Publication Date: 2023
  • Doi Number: 10.1007/s13226-022-00321-x
  • Journal Name: INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, INSPEC, zbMATH
  • Page Numbers: pp.1056-1068
  • Keywords: Domino tiling, Heuristic search, Bigraphs, Perfect matching, Enumeration, TILINGS, NUMBER, DIMERS
  • Karadeniz Technical University Affiliated: Yes

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.