Placing Dominoes On A Chequerboard

Question

How many ways can one place (unlabelled) dominoes on a square chequerboard such that the number placed horizontally is equal to the number placed vertically?

The dominoes must align with, and may not protrude, the chequerboard and may not overlap.

This is OEIS sequence A330658, 1, 1, 1, 23, 1608, 371500, 328956227, 1126022690953, ...

Challenge

Given the side length of the chequerboard, \$n\$, produce the number of ways to arrange dominoes as described above, \$a(n)\$, in as few bytes as possible in your chosen programming language. Alternatively you may use any of the sequence defaults.

You do not have to handle \$n=0\$
If you're producing a list/generator/etc. it may start either:

• 1, 1, 23, 1608, ... or,
• 1, 1, 1, 23, 1608, ...

A Worked Example, \$n=3\$

There are \$23\$ ways to place an equal number of horizontal and vertical dominoes on a three by three board. Here they are represented as 0 where no dominoes lie and labelling cells where distinct dominoes lie as positive integers:

There is one way to place zero in each direction:

0 0 0
0 0 0
0 0 0

There are twenty ways to place one in each direction:

1 1 0   1 1 0   1 1 0   1 1 2      0 0 2      2 0 0      2 1 1   0 1 1   0 1 1   0 1 1
2 0 0   0 2 0   0 0 2   0 0 2      1 1 2      2 1 1      2 0 0   2 0 0   0 2 0   0 0 2
2 0 0   0 2 0   0 0 2   0 0 0      0 0 0      0 0 0      0 0 0   2 0 0   0 2 0   0 0 2

2 0 0   0 2 0   0 0 2   0 0 0      0 0 0      0 0 0      0 0 0   2 0 0   0 2 0   0 0 2
2 0 0   0 2 0   0 0 2   0 0 2      1 1 2      2 1 1      2 0 0   2 0 0   0 2 0   0 0 2
1 1 0   1 1 0   1 1 0   1 1 2      0 0 2      2 0 0      2 1 1   0 1 1   0 1 1   0 1 1

There are two ways to place two in each direction:

1 1 2   2 1 1
3 0 2   2 0 3
3 4 4   4 4 3

There are no ways to place more than two in each direction.

\$1+20+2=23 \implies a(3)=23\$

Answer 1

APL (Dyalog Extended), 61 bytes

{+/∊{(∪≡⊢)¨(,2,/m)[M],.,⍉C[M←⍵⌂cmat≢C]}¨0,⍳≢C←,2,⌿⊢m←⍵⊥¨⍳,⍨⍵}

Try it online!

Finally got how to circumvent the funky inner assignment on Extended ;-)

The difference with the one below is that dfns is auto-loaded under ⌂, and a no-op is added after assignment into m.

^{I have a 68-byte Unicode and 60-byte Extended solution by rewriting from scratch; it is left as an exercise for the reader.}

---

APL (Dyalog Unicode), ⁷² 69 bytes

⎕CY'dfns'
{+/∊{(∪≡⊢)¨(,2,/m)[M],.,⍉C[M←⍵cmat≢C]}¨0,⍳≢C←,2,⌿m←⍵⊥¨⍳,⍨⍵}

Try it online!

Non-recursive brute force. This works the other way around: generate all possible horizontal/vertical domino placements, generate all possible combinations of n horizontal and n vertical placements, and count the ones that don't have any duplicated cells.

Ungolfed with comments

⎕CY'dfns'  ⍝ Load dfns library to access function "cmat"

f←{  ⍝ Main function; ⍵←1-based index n (does not handle 0)

  m←⍵⊥¨⍳,⍨⍵  ⍝ n-by-n matrix of unique integers
        ,⍨⍵  ⍝ [n n]
       ⍳     ⍝ Nested matrix having [1..n;1..n]
    ⍵⊥¨      ⍝ Compute n×i+j for each cell containing [i j]

  R←,2,/m  ⍝ Horizontal domino placements
     2,/m  ⍝ From the matrix m, pair horizontally consecutive cells
    ,      ⍝ Flatten the outermost layer to make it a nested vector
  C←,2,⌿m  ⍝ Vertical domino placements, using ⌿ instead of /

  +/(0,⍳≢R){M←⍺cmat⍵⋄+/(∪≡⊢)¨,R[M],.,⍉C[M]}¨≢R  ⍝ Count the placements
    (0,⍳≢R){                              }¨≢R  ⍝ For each ⍺←0..length(≢) of R with ⍵←R,
            M←⍺cmat⍵                        ⍝ Generate all combinations to use for R and C
                    ⋄        ,R[M],.,⍉C[M]  ⍝ Concatenate all combinations of R with all combinations of C
                     +/(∪≡⊢)¨  ⍝ Count the ones whose cell values are all unique
  +/  ⍝ Sum all the counts
}

Answer 2

Charcoal, 88 84 66 bytes

Ｎθ⊞υ⁰ＦυＦ×¹⁵Ｘ⁴⊖Φ×θθ﹪κθＦ∧¬＆ικ×θ⊖θ«≔×Ｘ⁴λ⊕Ｘ⁴θη≧｜ικ¿¬∨＆κη№υ｜κη⊞υ｜κη»ＩＬυ

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input n.

⊞υ⁰

Start the list of results with an empty chequerboard of size n. This is represented using an integer in base 4 of n² digits with each digit representing an element of the array in row-major order, 0 for empty, 1 for half of a vertical domino and 3 for half of a horizontal domino. (2 is unused, but that's code golf for you.)

Ｆυ

Perform a breadth-first search of chequerboards.

Ｆ×¹⁵Ｘ⁴⊖Φ×θθ﹪κθ

Consider all squares of the current chequerboard that are not on the left column, then decrement the index, giving the squares that are not on the right column, then convert to a pair of base 4 digits 33 representing a horizontal domino on those two squares.

Ｆ∧¬＆ικ×θ⊖θ«

Check whether those squares are empty on the current chequerboard. If so, then consider all of the squares of the current chequerboard, except for the bottom row.

≔×Ｘ⁴λ⊕Ｘ⁴θη

Calculate the base 4 digits corresponding to a vertical domino at that square.

≧｜ικ

Merge the current chequerboard with the current horizontal domino.

¿¬∨＆κη№υ｜κη⊞υ｜κη

If the vertical domino does not overlap the merged chequerboard and the domino arrangement including the vertical domino has not yet been seen then add it to the list.

»ＩＬυ

Output the number of arrangements found.

Answer 3

JavaScript (ES6),  150 133  126 bytes

n=>(g=(a,k=0,y=n,x,h=d=>a[(b=[...a])[y-!~d]|=m=2+d<<x,y]&m?0:g(b,k+~~d,y,-~x))=>(x%=n)||y--?h()+(y&&h(-1))+(x^n-1&&h(1)):!k)``

Try it online!

Commented

The board is described as an array of \$n\$ bit masks. We start at \$(0,n-1)\$ and attempt to put either a horizontal domino, a vertical domino or no domino at all at each position, going from right to left and bottom to top:

$$\begin{matrix} (n-1,0)&\cdots&(1,0)&(0,0)\\ (n-1,1)&\cdots&(1,1)&(0,1)\\ \vdots&&\vdots&\vdots\\ (n-1,n-1)&\cdots&(1,n-1)&(0,n-1) \end{matrix}$$

For horizontal dominoes, we test the bits at \$(x,y)\$ and \$(x+1,y)\$ and set both of them if the location is available. For vertical dominoes, we only test the bit at \$(x,y)\$ and set the one at \$(x,y-1)\$ if the location is available.

The helper function \$h\$ is used to process the tests and the recursive calls to its parent function \$g\$ in the scope of which it's defined:

h = d =>                // helper function taking a direction d:
                        //   -1 = vertical, undefined = no domino, 1 = horizontal
  a[                    // test a[]:
    (b = [...a])        //   b[] = copy of the current board
    [y - !~d] |=        //   apply the mask m to either b[y] or b[y - 1]
      m =               //   set m to:
        2 + d << x,     //     3 << x for horizontal, 1 << x for vertical,
                        //     or 0 for no domino (NaN << x)
    y                   //   test a[y]
  ] & m ?               // if there's a collision:
    0                   //   do nothing and leave the final result unchanged
  :                     // else:
    g(                  //   do a recursive call to g:
      b,                //     use the updated board
      k + ~~d,          //     add d to k
      y,                //     leave y unchanged
      -~x               //     increment x
    )                   //   end of recursive call

Below is the main recursive function \$g\$:

g = (                   // main recursive function taking:
  a,                    //   a[] = board
  k = 0,                //   k = counter which is incremented when a horizontal
                        //       domino is put on the board and decremented when
                        //       a vertical domino is used
  y = n, x,             //   (x, y) = current position
  h = ...               //   h = helper function (see above)
) =>                    //
  (x %= n) ||           // turn x = n into x = 0
  y--                   // decrement y if x = 0
  ?                     // if we haven't reached the end of the board:
    h() +               //   try to put no domino
    (y && h(-1)) +      //   if y > 0, try to put a vertical domino
    (x ^ n - 1 && h(1)) //   if x < n - 1, try to put a horizontal domino
  :                     // else:
    !k                  //   return 1 if k = 0 (meaning that we've put as many
                        //   horizontal dominoes as vertical ones)

Answer 4

Clingo, 98 bytes

{v(1..n,2..n)}.{h(2..n,1..n)}.:-{v(I,J)}=C,{h(I,J)}!=C.:-I=1..n,J=1..n,2{v(I,J..J+1);h(I..I+1,J)}.

Wow, I'm just describing the problem, and it's still bigger than most of the more explicit solutions!

A commented version:

% Select some positions for vertical dominoes,
% v(I,J) is meant to also cover (I,J-1).
{v(1..n,2..n)}.

% Select some positions for horizontal dominoes,
% h(I,J) is meant to also cover (I-1,J).
{h(2..n,1..n)}.

% Constraints:

% The selections must not have different sizes:
:- {v(I,J)}=C,{h(I,J)}!=C.

% No position can be covered by two or more dominoes:
:- I=1..n,J=1..n,2{v(I,J..J+1);h(I..I+1,J)}

Save the program in a file dom.lp and give n as command line argument as shown below. The result is the number of models reported.

Here is an example run:

$ clingo -c n=5 dom.lp -q 0 
clingo version 5.1.0
Reading from dom.lp
Solving...
SATISFIABLE

Models       : 371500
Calls        : 1
Time         : 2.519s (Solving: 2.51s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 2.510s

-q stops clingo from printing solutions, 0 tells it to search for all solutions. Performance can be increased with the option --config=frumpy. With it, I was able to compute n=6 in 48 min.

In Debian, clingo is in the gringo packet.

Answer 5

Jelly, 38 31 bytes

-7 bytes thanks to Jonathan Allan

’»1p⁸U+Ø.żƊŒPẈĠịƊpU$€ẎḅFQƑɗ€⁹S‘

TIO can run successfully for n=1,2,3, but it times out for n>3 since this is a brute force solution. I have verified n=4 on my computer.

Try it online!

Commented

’»1p⁸U+Ø.żƊŒPẈĠịƊpU$€ẎḅFQƑɗ€⁹S‘  # main link
’  p³                            # [1..n-1] Cartesian product with [1..n]
 »1                              # [1..n] x [1..n] if n=1 to avoid empty list output
     U                           # reverse, yielding list of pairs from ex. [1,1] to [3,2] for n=3 (tops of vertical dominoes)
      +Ø.                        # add [0,1] to each pair to get coordinates of bottoms of vertical dominoes
         żƊ                      # zip with the tops list to get a list of pairs of pairs: [[[1,1], [1,2]], ...]  
           ŒPẈĠịƊ                # take the powerset to get all possible vertical dominoes, and group these subsets by length
                   U             # switch coordinates to get grouped horizontal domino sets
                  p $€           # Cartesian product of each set of horizontal dominoes with each set of vertical dominos of the same count
                      Ẏ          # tighten to get a single list of domino sets
                       ḅFQƑɗ€⁹   # 1 for each set pair if it is a valid arrangement of dominoes, otherwise 0 (check for no repeat coordinates)
                              S‘ # sum to find the count of valid arrangements, and increment for the case where there are no 0's