Counting maximal domino placements

Question

Background

A maximal domino placement (MDP) on a rectangular grid is a non-overlapping placement of zero or more dominoes, so that no more dominoes can be added without overlapping some existing domino.

Alternatively, it can be thought of as a tiling using dominoes and monominoes (single square pieces) so that no two monominoes are adjacent to each other.

For example, the following are a few MDPs on a 3x3 grid: (-s and |s represent horizontal and vertical dominoes, and os represent holes respectively.)

--|   --|   --o
|o|   --|   o--
|--   --o   --o

There are exactly five MDPs on 2x3, and eleven on 2x4. Rotation and/or reflection of a placement is different from original unless they exactly coincide.

|||   |--   --|   o--   --o
|||   |--   --|   --o   o--

||||   ||--   |--|   |o--   |--o   --||
||||   ||--   |--|   |--o   |o--   --||

--o|   ----   o--|   o--o   ----
o--|   o--o   --o|   ----   ----

In the graph-theoretical sense, an MDP is equivalent to a maximal matching (maximal independent edge set) in the grid graph of given size.

Challenge

Given the width and height of a grid, count the number of distinct maximal domino placements on it.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

A288026 is the table of values read by antidiagonals.

w|h| 1  2   3     4      5       6
---+------------------------------
1  | 1  1   2     2      3       4
2  | 1  2   5    11     24      51
3  | 2  5  22    75    264     941
4  | 2 11  75   400   2357   13407
5  | 3 24 264  2357  22228  207423
6  | 4 51 941 13407 207423 3136370

Answer 1

JavaScript (ES2021), 177 bytes

m=>n=>(g=i=>m*n>i?![-1,1,3,4,6].map(k=>g(i+1,(a[i/n|0]??=[])[i%n]=k)):S+=!a.some((r,y)=>r.some((c,x)=>~c?(c%2?a[y+c-2]?.[x]^c:r[x+c-5]^c)-2:r[x+1]<0|a[y+1]?.[x]<0)))(S=0,a=[])|S

Certainly can be golfed, but I don't know how. Terrible performance \$O(5^{mn})\$.

f=m=>n=>(g=i=>m*n>i?![-1,1,3,4,6].map(k=>g(i+1,(a[i/n|0]??=[])[i%n]=k)):S+=!a.some((r,y)=>r.some((c,x)=>~c?(c%2?a[y+c-2]?.[x]^c:r[x+c-5]^c)-2:r[x+1]<0|a[y+1]?.[x]<0)))(S=0,a=[])|S
console.log(`f(2,4) =`,f(2)(4))

Answer 2

Jelly, 34 bytes

Ẏ⁹ḟƑƇṭ€⁸Ṣ€ȯW)ẎQ
;þ;Z$,Ɲ€ẎW€çƬ$ṪLo1

Try it online!

A dyadic link taking the dimensions as the left and right arguments and returning an integer. The TIO footer generates a 4x4 table similar to the one in the question; the argument for the footer is the size of the table to generate.

Full explanation to follow, but in brief this generates all possible dominoes and then builds all possible lists of those dominoes that don’t have any overlaps. It would be fairly straightforward to extend this to larger polyominoes (though the first part of the code would be a bit more complex); here’s an initial attempt.

Answer 3

Python 3, 250 225 219 bytes

from itertools import*
def f(w,h):
 p=[[0]*w]
 while h:h-=1;p=[n for r in p for n in product(*[[k%3//2*3,1,2][::k%3+1]for k in r])if('0'in str(n).replace('0, 0',''))<1>("1, 1"in str(n))]
 return sum(1-(2in u)for u in p)

-25 bytes thanks to @ovs

-6 bytes thanks to @Jakque

Try it online!

How it works

We store each row as a list of w values from [0,1,2,3], then transition from each row to the next while following constraints. Vertical constraints are determined by the table at the start of "Rules" in the code below. Horizontal constraints are determined by checking run lengths to ensure that two 0s are not adjacent, and runs of 1s are an even length.

Probably can be golfed through a wise relabelling, but that would not be fun.

def possible(w, h):
    """
    0: empty; now you must place a domino
    1: is a horizontal domino; now you have freedom
    2: starts a vertical domino; must end it
    3: ends a vertical domino; now you have freedom

    Rules:
    0 →   1,2
    1 → 0,1,2
    2 →       3
    3 → 0,1,2

    0 cannot be next to a 0
    1 is horizontal domino (must have runs of even length)
    """
    if h == 0:
        yield [1 for _ in range(w)]
    else:
        for row in possible(w, h - 1):
            for new_row in itertools.product(
                *[{0: [1, 2], 1: [0, 1, 2], 2: [3], 3: [0, 1, 2]}[k] for k in row]
            ):
                valid = True
                for i, j in itertools.groupby(new_row):
                    L = len(list(j))
                    if i == 0 and L > 1:
                        valid = False
                    elif i == 1 and L % 2 == 1:
                        valid = False
                if valid:
                    yield new_row


def num_possible(w, h):
    return len([p for p in possible(w, h) if 2 not in p])

Answer 4

Jelly,  45  24 bytes

pŒcạ/S$ÐṂŒPẎ€f€ẠȧQƑʋ@ƇƊL

A dyadic Link that accepts the two dimensions and yields the count.

Try it online! Note: It brute forces across the powerset of all possible dominoes so is incredibly inefficient.

How?

pŒcạ/S$ÐṂŒPẎ€f€ẠȧQƑʋ@ƇƊL - Link: integer, n; integer m
p                        - (n) cartesian product (m) -> list of all coordinates
 Œc                      - pairs -> all pairs of coordinates, once each
       ÐṂ                - keep those which are minimal under:
      $                  -   last two links as a monad, f(pair of coordinates):
    /                    -     reduce (the pair of coordinates) by:
   ạ                     -       absolute difference
     S                   -     sum
                           -> all possible dominoes, once each, as pairs of coordinates
                      Ɗ  - last three links as a monad, f(all dominoes):
         ŒP              -   power set -> all sets of dominoes (including overlaps)
           Ẏ€            -   tighten each -> coordinates used by each set of dominoes
                     Ƈ   -   filter keep those (potential sets) for which:
                    @    -     with swapped arguments...
                   ʋ     -     ...last four links as a dyad, f(all dominos, potential set):
              €          -       for each (domino in all dominoes):
             f           -         keep those (coordinates of the domino) which are in (the coordinates used by the potential set)
               Ạ         -       all? (i.e only single empties / no touching monominoes?)
                  Ƒ      -       is (potential set) invariant under:
                 Q       -         deduplication? -> truthy if no overlaps
                ȧ        -       (only single empties) logical AND (no overlaps)
                       L - length

Answer 5

JavaScript (ES6),  169  164 bytes

Expects (width)(height).

w=>h=>(g=(o,x,y,d,q)=>{for(d=2;d--;)for(x=w-!d;x--;)for(y=h-d;y--;)(o[y]|o[y+d])&(m=3>>d<<x)||g(b=[...o],[0,d,h].map(i=>q=b[y+i]|=m));q|g[o+=o]?0:g[o]=++n})(n=[])|n

Try it online!

Or much faster for 167 bytes:

w=>h=>(g=(o,x,y,d,q=g[o+o])=>{for(d=2*!q;d--;)for(x=w-!d;x--;)for(y=h-d;y--;)(o[y]|o[y+d])&(m=3>>d<<x)||g(b=[...o],[0,d,h].map(i=>q=b[y+i]|=m));g[o+o]=q||++n})(n=[])|n

Try it online!

How?

We use \$o[\:]\$ as an array of bitmasks. This array is split into two areas. An exact representation of all dominoes is stored in the first area (\$0\le y <h\$), whereas only the upper parts of the dominoes are stored in the second area (\$h \le y < 2h\$).

It means that a horizontal domino is stored the same way in both areas, but a vertical domino is stored as a single cell in the second area:

This allows us to distinguish between two grids which are filled the same way but with different orientations of the dominoes.

The recursive function \$g\$ attempts to insert dominoes at all possible positions \$(x,y)\$ and with either orientation (horizontal when \$d=0\$, vertical when \$d=1\$), using 3 nested for loops:

for(d = 2; d--;)
  for(x = w - !d; x--;)
    for(y = h - d; y--;)

The collision test is:

(o[y] | o[y + d]) & (m = 3 >> d << x)

which is:

• o[y] & (m = 3 << x) when \$d=0\$
• (o[y] | o[y + 1]) & (m = 1 << x) when \$d=1\$

Whenever a new domino is inserted, we make a copy of \$o[\:]\$ in \$b[\:]\$ and do:

[ 0,  // insert the upper part in area 1
  d,  // insert the lower part in area 1 if d = 1
      // (or just overwrite the upper part if d = 0)
  h   // insert the upper part in area 2
]
.map(i => q = b[y + i] |= m)

Answer 6

Charcoal, 112 94 86 bytes

ＮθＮη≔⁰ζ⊞υＥ²ζＦυ«≔ωδＦ×θηＦ²«≔×⊕Ｘ²∨ληＸ²κε¿∧⎇λ﹪⊕κη‹κ×⊖θη¬＆εΣι«≔Ｅι⁺μ×⁼λνε먪№υδ⊞υδ»»≧⁺¬δζ»Ｉζ

Try it online! Link is to verbose version of code. Takes 30s on TIO to do 4×4 but smaller areas are quicker. Explanation:

ＮθＮη

Input the width and height.

≔⁰ζ⊞υ

Start with zero placements.

⊞υＥ²ζ

Start enumerating placements with one that has no vertical or horizontal dominoes.

Ｆυ«

Loop through the placements.

≔ωδ

Assume that there are no possible dominoes.

Ｆ×θηＦ²«

Loop through all potential dominoes.

≔×⊕Ｘ²∨ληＸ²κε

Create a bitmask for this domino.

¿∧⎇λ﹪⊕κη‹κ×⊖θη¬＆εΣι«

If this domino doesn't wrap around, and there is room to place a domino without overlapping any existing domino, then...

≔Ｅι⁺μ×⁼λνεδ

Add a domino in the appropriate orientation.

¿¬№υδ⊞υδ

Add this if it is a new placement.

»»≧⁺¬δζ

Increment the number if this is a maximal placement i.e. no dominoes were found.

»Ｉζ

Output the final number of maximal placements.