Maximal saturated domino covering of a rectangle

Question

Inspired by this OEIS entry.

Background

A saturated domino covering is a placement of dominoes over an area such that

1. the dominoes are completely inside the area,
2. the dominoes entirely cover the given area,
3. the dominoes may overlap, and
4. removal of any domino reveals an uncovered cell (thus failing to satisfy condition 2).

The following is an example of a maximal such covering of 3 × 3 rectangle (since dominoes may overlap, each domino is drawn separately):

AA.   B..   ..C   ...   ...   ...
...   B..   ..C   .D.   ...   ...
...   ...   ...   .D.   EE.   .FF

Challenge

Given the dimensions (width and height) of a rectangle, compute the maximum number of dominoes in its saturated domino covering.

You can assume the input is valid: the width and height are positive integers, and 1 × 1 will not be given as input.

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

Test cases

A193764 gives the answers for square boards. The following test cases were verified with this Python + Z3 code (not supported on TIO).

Only the test cases for n <= m are shown for brevity, but your code should not assume so; it should give the same answer for n and m swapped.

n m => answer
1 2 => 1
1 3 => 2
1 9 => 6
1 10 => 6
2 2 => 2
2 3 => 4
2 5 => 7
3 3 => 6
3 4 => 8
3 7 => 15
4 4 => 12
4 7 => 21

Answer 1

Sagemath, 60 bytes

lambda m,n:m*n-len(graphs.GridGraph([m,n]).dominating_set())

Try it online!

---

From Saturated Domino Coverings by Buchanan et al:

Corollary 6.3: If \$B\$ is a rectangular \$m \times n\$ board, then \$d(B) = |B| - \gamma(G_{m,n})\$.

Where \$\gamma(\ldots)\$ is the domination number and \$G_{m,n}\$ is a grid graph. We also clearly have that if \$B\$ represents an \$m\times n\$ board then \$|B| = mn\$.

Answer 2

JavaScript (ES6), 120 bytes

A shorter (and slower) version, using the same algorithm with eval() and two for loops.

Expects (m)(n).

m=>n=>eval("for(M=0,b=1<<m*n;b--;)for(k=j=m*n;j--?b>>j&1&&k--||(b<<m|b>>m|(j%m&&b*2)|(~j%m&&b/2))>>j&1:k>M&&!(M=k););M")

Try it online!

Or try an implementation in C (gcc) (127 bytes) which can process the last test case on TIO.

---

JavaScript (ES6), 128 bytes

Expects (m)(n).

m=>n=>[...Array(1<<m*n)].map(M=(_,b)=>(g=j=>j--?b>>j&1&&k--||(b<<m|b>>m|(j%m&&b*2)|(~j%m&&b/2))>>j&1?g(j):0:k<M?0:M=k)(k=m*n))|M

Try it online!

How?

This is based on the formula used by Sisyphus, except that we have to actually compute \$\gamma(G_{m,n})\$ since there's obviously no JS built-in for that.

For each \$b\$, \$0\le b<2^{m\times n}\$, we test whether at least one of the following conditions is true for all \$j\$, \$0\le j<m\times n\$:

• the \$j\$-th bit of \$b\$ is set
• or the \$j\$-th bit of \$b\$ is adjacent to a set bit in \$b\$ when re-arranging the bits in a grid of size \$m\times n\$

If this is successful, the set bits in \$b\$ represent the vertices of a valid dominating set of the \$m\times n\$ grid graph.

While doing that, we also compute the number \$k\$, which is equal to \$m\times n\$ minus the total number of bits that are set in \$b\$. We update the final result \$M\$ to \$k\$ whenever \$b\$ is a valid bit mask and \$k\ge M\$.

Commented

m => n =>                 // (m, n) = size of the grid
[...Array(1 << m * n)]    // build an array of 2 ** (m * n) values
.map(M =                  // initialize M to a non-numeric value
(_, b) => (               // for each b, 0 <= b < 2 ** (m * n):
  g = j =>                //   g is a recursive function taking a counter j
    j-- ?                 //     decrement j; if it was not equal to 0:
      b >> j & 1          //       if the j-th bit of b is set:
        && k--            //         decrement k
      ||                  //       otherwise, we compute a bit mask where all bits of
      (                   //       b adjacent to the j-th bit in the grid are shifted
                          //       to the rightmost position and OR'd together:
        b << m |          //         this is the bit 'below'
        b >> m |          //         this is the bit 'above'
        (j % m && b * 2)  //         this is the bit 'on the right', which is valid
        |                 //         only if j mod m = 0
        (~j % m && b / 2) //         this is the bit 'on the left', which is valid
                          //         only if (j + 1) mod m = 0
      ) >> j & 1          //       test the least significant bit of the result
      ?                   //       if one of the above tests is successful:
        g(j)              //         do a recursive call
      :                   //       else:
        0                 //         abort
    :                     //     else:
      k < M ? 0 : M = k   //       if k is better than M, update M to k
  )(k = m * n)            //   initial call to g with j = k = m * n
) | M                     // end of map(); return M

Answer 3

05AB1E, 33 bytes

*LIô2FD€ü2€`sø}\«æʒ˜D¢2ô2@PO_}éθg

Input as two loose integers.

Try it online or verify the small test cases.

Explanation:

Step 1: Get a list of all possible dominos based on the input-dimensions:

*              # Multiply the two (implicit) inputs together
 L             # Pop and push a list in the range [1, n*m]
  Iô           # Split it into parts equal to the second input
    2F         # Loop 2 times:
      D        #  Duplicate the matrix at the top of the stack
       €       #  For each row:
        ü2     #   Create overlapping pairs
          €`   #  Flatten it one level down to a list of pairs
            s  #  Swap so the copy is at the top of the stack
             ø #  Zip/Transpose; swapping rows/columns
     }\        # After the loop: discard to leftover copy
       «       # And merge the two list of pairs together

Step 2: Create all possible combination of dominos:

æ              # Get the powerset of this list of pairs

Step 3: Filter every possible combination so only valid ones are left that comply to all four rules:

ʒ              # Filter the list of list of pairs by:
 ˜             #  Flatten the list of pairs to a list of integers
  D            #  Duplicate it
   ¢           #  Count each integer in the flattened list
    2ô         #  Convert it back to a list of pairs
               #  (unfortunately `¢` doesn't vectorize apparently, otherwise `D˜¢` would
               #   have sufficed..)
      2@       #  Check for each count if it's >= 2
        P      #  Check if this is truthy for both values within a pair
         O     #  Sum the checks of all pairs together
          _    #  And check that this is 0 (thus falsey for all of them)
}              # Close the filter

Step 4: Get the length of the longest valid board of dominos, and print it as our result:

é              # Sort the list of list of pairs by length
 θ             # Pop and push the last/longest list of pairs
  g            # And pop and push its length
               # (after which it is output implicitly as result)

Answer 4

Jelly, 39 bytes

ṙJḊÑ$€¬Ȧ
ẎQL=³×⁴¤
pp`_/ṢF⁼ʋƇØ.ŒPÇƇÑƇL€Ṁ

Try it online!

This is kinda (very) clunky lol. Haven't used Jelly in a while.

Will golf for a bit before I give a full explanation, but basically how it works is it generates all of the cells, and then gets all adjacent pairs to get all dominoes, then takes the powerset and filters for valid states by two conditions: firstly, using the second line to ensure all squares are covered, and secondly, using the first line to ensure condition 4 by checking all modifications of removing one domino and making sure all fail condition 2 using the second line.

Answer 5

Charcoal, 60 bytes

ＮθＮη⊞υ×1×θηＦθＦηＦυ«⎚⪪ληＪκι¿∧ΣＫＫ№ＫＶ1«ＵＭΦＫＶΣμ0¹⊞υ⪫ＫＡω»»⎚Ｉ⌈Ｅυ№ι0

Try it online! Link is to verbose version of code. Brute force, so 4 × 7 times out on TIO. Explanation:

ＮθＮη

Input the dimensions of the rectangle.

⊞υ×1×θη

Start a breadth-first search with a string of 1s representing an empty rectangle.

ＦθＦη

Loop over each row and column.

Ｆυ«

Loop over each rectangle discovered so far.

⎚⪪λη

Wrap the string to the size of the rectangle and output it on a clear canvas.

Ｊκι

Jump to the cell under consideration.

¿∧ΣＫＫ№ＫＶ1«

If both the cell and at least one neighbour are empty, then:

ＵＭΦＫＶΣμ0

Change all of the neighbours to 0s (somewhat arbitrary choice; any non-digit except - would also work).

¹

Change the cell itself to - (chosen for golfiness of course).

⊞υ⪫ＫＡω

Save the resulting rectangle.

»»⎚Ｉ⌈Ｅυ№ι0

Print the maximum number of dominoes that were placed. (I can't believe that it's possible for the code to place more dominoes and yet fail to cover the rectangle than its best result that does cover the rectangle.)

Answer 6

Jelly, 24 bytes

pŒcạ/SỊƊƇŒPẎċⱮⱮ$Ṃ€ṀỊƲƇṪL

A dyadic Link accepting the dimensions which yields the maximal number of dominos which may be placed.

Try it online! (Too slow for the last three test-cases, but here are all the others.)

How?

Make all grid-contained dominos as pairs of coordinates, then filter the power-set of these to those sets which don't contain any domino whose coordinates are both contained by others, then return the length of the longest such set.

pŒcạ/SỊƊƇŒPẎċⱮⱮ$Ṃ€ṀỊƲƇṪL - Link: n; m
p                        - Cartesian product (all coordinates)
 Œc                      - all pairs (of coordinates)
        Ƈ                - filter keep those for which:
       Ɗ                 -   last three links as a monad:
    /                    -     reduce (the pair) by:
   ạ                     -       absolute difference
     S                   -       sum
      Ị                  -       insignificant? (effectively: equals 1?)
                           (-> all grid-contained dominos)
         ŒP              - power-set (ordered by length)
                     Ƈ   - filter keep those (sets of dominos) for which:
                    Ʋ    -   last four links as a monad:
               $         -     last two links as a monad:
           Ẏ             -       tighten (-> list of all coordinates used)
              Ɱ          -       map (across the dominos in the set) with:
             Ɱ           -         map (across the coordinates in the domino) with:
            ċ            -           count (of the coordinate in all coordinates used)
                Ṃ€       -     minimum of each
                  Ṁ      -     maximum
                   Ị     -     insignificant? (effectively: equals 1?)
                      Ṫ  - tail
                       L - length