Can this pattern be made with dominoes?

Question

Given a pattern of squares on a grid, determine if it is possible to create that pattern with non-overlapping dominoes. In case you are not familiar, a domino is a rectangular shape created by joining exactly two squares at their edges.

Examples

For the pattern on the left, O represents an occupied cell on the grid and . represents an empty cell. For the pattern to the right of the first |, numbers and letters will be used to mark individual dominoes in a possible solution

Possible

O  |  1  |  This is the trivial case: 
O  |  1  |  a single domino laid vertically

. O . .  |  . 2 . .  |  This can be created with three
O O O O  |  1 2 3 3  |  dominoes in a simple pattern
O . . .  |  1 . . .  |

O O O O  |  1 1 2 2  |  A simple rectangular grid with
O O O O  |  3 3 4 4  |  even width is easily tiled with
O O O O  |  5 5 6 6  |  horizontally-laid dominoes

O O O  |  1 1 2  |  Four dominoes laid radially
O . O  |  3 . 2  |
O O O  |  3 4 4  |

. O O .  |  . 1 1 .  |  Dominoes do not need to touch
O . O .  |  2 . 3 .  |  and the grid may contain empty
O . O .  |  2 . 3 .  |  cells along an edge

. O . . O O O O O .  |  . K . . R R S S N .  |  A 10x10 test case and
O O O . . O . . O .  |  U K J . . 5 . . N .  |  one of its solutions
O . O . . O . O O O  |  U . J . . 5 . C C Q  |
O O O O O O . O . O  |  T B B 4 1 1 . 7 . Q  |
O . . O O O . O . .  |  T . . 4 6 6 . 7 . .  |
. . O O O . O O O .  |  . . 2 3 3 . 8 8 D .  |
O O O . . O . . O .  |  I I 2 . . 9 . . D .  |
. . O O O O . O O O  |  . . G O O 9 . E E L  |
. . O . . O O O . O  |  . . G . . A F F . L  |
O O . O O O . . O O  |  M M . H H A . . P P  |

Not Possible

O  |  You need at least two occupied cells to fit a domino

O .  |  Dominoes are squares joined by edges, not corners
. O  |

O  |  It is always impossible to create a pattern with an odd
O  |  number of squares with dominoes
O  |

O O . O  |  No matter how you lay the first few dominoes,
. O O O  |  at least two squares are always separated
. O . O  |

O O O .  |  This is a slightly more complicated version of the above
O . O O  |
O O O .  |
. O O O  |

. O . . . .  |  A small test case that cannot be decided with
O O O O O O  |  a chessboard painting algorithm
. . . . O .  |

. O O O O O . O O O  |  A 10x10 example test case
O O O . . O . . . O  |  
. . O . O . O O O .  |  This pattern is almost possible
. O . . O . . . O O  |  except that the bottom-left corner
. O O O O O O O . O  |  contains an arrangement which is
. . . . O . . O O O  |  impossible to make with dominoes
O O O O O . O . . .  | 
O . O . . . O . . O  | 
. O O O . O O . O O  |
. . . O O . O O O .  |

. O O O O O O O O O  |  A pathological case for a chessboard
O O O O O O O O O .  |  painting algorithm.
O O O O O O O O O O  |
O O O O O O O O O O  |  This is also a pathological case for
O O O O O O O O O O  |  a backtracking algorithm.
O O O O O O O O O O  |
O O O O O O O O O O  |
O O O O O O O O O O  |
O O O O O O O O O O  |
O O O O O O O O O O  |

Rules and Scoring

• This is Code Golf, so shortest code wins
• Use any convenient I/O method.
• Valid input formats for the grid include, but are not limited to:
  • Array of arrays
  • Height, width, array
  • Array of integers representing each row (or column) in binary
  • A string representation similar to the examples above
  • A PNG image
• You may assume input grids are rectangular (not jagged)
• Your solution should return answers within a reasonable amount of time (it should not time out on Try It Online, for example) for inputs up to 10x10 and be able to theoretically work for a grid of any size if given enough time and space.

Answer 1

Charcoal, 120 bytes

ＷＳ⊞υιυＦＬυＦＬ§υι«Ｊκι¿⁼ＫＫO«≔⟦ω⟧θＷθ«≔Φurdl№⪪α¹⊟ＫＤ²✳μλ¿λ«≔§λ⁰λ✳λλ≔ＫＫηＰ§dlur⌕urdlλ¿⁼ηO≔⟦⟧θ«Ｍ✳η⊞θη⊞θＫＫ»»«≔⊟θλ✳λ↧λ✳ＫＫ↧⊟θ»»ＵＭＫＡ↥λ

Try it online! Link is to verbose version of code. Takes input as a newline-terminated list of strings. Outputs a completed board or throws an exception if it can't find a solution. Note: While I know that the algorithm definitely fails on an illegal board, my golfing may mean that it's not 100% successful on legal boards, so feel free to find a counterexample and I'll adapt the code. Explanation: Based on the maximum flow algorithm, so should run in polynomial time (possibly O(n²) in the number of dominoes, as each of the n dominoes might decide to rotate all of the n-1 dominoes already placed).

ＷＳ⊞υιυ

Read and print the input.

ＦＬυＦＬ§υι«

Loop over all cells of the input.

Ｊκι¿⁼ＫＫO«

If the current cell is an O, then:

≔⟦ω⟧θＷθ«

Start a depth-first search of the board.

≔Φurdl№⪪α¹⊟ＫＤ²✳μλ

Find Os and already placed dominoes in adjacent cells.

¿λ«

If there is at least one O or domino, then:

≔§λ⁰λ

Choose the first direction.

✳λλ

Overwrite the current cell with that direction, and move in that direction.

≔ＫＫη

Grab the adjacent cell.

Ｐ§dlur⌕urdlλ

Overwrite it with the reverse direction, creating a domino.

¿⁼ηO≔⟦⟧θ«

If this was an O, then we successfully placed a domino, so terminate the search.

Ｍ✳η⊞θη⊞θＫＫ»»

Otherwise we just rotated a domino, so move to where its other end used to be, and save its direction.

«≔⊟θλ✳λ↧λ✳ＫＫ↧⊟θ

If there were no valid moves, then rotate the last domino on the stack back and back up to the previous position.

»»ＵＭＫＡ↥λ

After successfully placing a domino, uppercase all the dominoes. This allows them to participate in rotations for the next pair of Os. (Sadly MapAssign(Uppercase, PeekAll()); doesn't work.

Example: Consider the following grid:

OOOO
O..O

The first O is readily covered with an rl domino, resulting in this:

rlOO
O..O

Another rl domino is then placed, resulting in this:

RLrl
O..O

The next O doesn't have an adjacent O, but there is an adjacent domino, so we try rotating it:

dORL
u..O

We still don't have an adjacent O, but there is now another domino that we can rotate (180° around the R):

drlO
u..O

Finally we can place a domino to cover the now adjacent Os:

drld
u..u

Answer 2

JavaScript (V8), 129 bytes

f=(g,p=d=>(n=2,v=g.map((r,i)=>r.map((c,j)=>c*n&&(n>1?~(y=i+d,x=j+!d):i==y&j==x)?!n--:c)),n?n>1:f(v)))=>g in f?f[g]:f[g]=p(0)|p(1)

Try it online!

Receives the input as a 2-dimensional array of booleans and returns 0 for false or 1 for true.

Explanation

Solves the problem recursively calling itself with a single domino removed from the grid. If it is called with an empty grid (which will happen if the initial grid only contained valid domino positions) then it returns true. At each call it tries removing the top-left position containing a domino, calling itself with either the horizontal or vertical orientation removed.

f=(g,
// p = function to remove the top-left domino and recurse if the remove succeeded
p=d=>(
// n = squares remaining for removal
n=2,
// v = grid after removal
v=g.map((r,i)=>r.map((c,j)=>c*n&&(n>1?~(y=i+d,x=j+!d):i==y&j==x)?!n--:c)),
// if n=2 the grid was empty so we return true, if n=1 we could not remove the domino
// if n=0 the domino was successfully removed and we recurse
n?n>1:f(v))
// try removing the top-left square with a horizontal or vertical domino
// and cache results
)=>g in f?f[g]:f[g]=p(0)|p(1)

Answer 3

Picat, 163 bytes

import sat.
f(R,C,L)=>Z=[I:I in 1..R*C,L[I]=1],E=[{{I,J},B}:I in Z,J in Z,J-I in[1,C],J mod C!=J-I,B::0..1],foreach(I in Z)1#=sum([B:{T,B}in E,I in T])end,E.solve.

Try it on Picat Web IDE!

Takes three arguments, where R and C are the number of rows and columns respectively, and L is a flat list of zeros and ones where 1 indicates an occupied cell. The predicate succeeds if there is a solution, and fails otherwise.

With import cp instead, the last test case takes forever to solve. sat solves them instantly when tested on my local machine.

The list Z contains the 1-based indices of 1s in L. For example, given an input of

R = 3, C = 4, L = [
    0, 1, 0, 0,
    1, 1, 1, 1,
    1, 0, 0, 0
]

then Z is [2, 5, 6, 7, 8, 9]. If using Z instead of L is an acceptable input format, the code size goes down to 138 bytes:

import sat.
f(R,C,Z)=>E=[{{I,J},B}:I in Z,J in Z,J-I in[1,C],J mod C!=J-I,B::0..1],foreach(I in Z)1#=sum([B:{T,B}in E,I in T])end,E.solve.

Ungolfed with comments:

import sat. % use SAT solver

f(R,C,L) =>
    Z = [I:I in 1..R*C,L[I]=1], % list of vertex IDs
    E = [{{I,J},B}: % list of edges and associated boolean variables,
                    % where B=1 means {I,J} is the part of a matching
        I in Z,J in Z, % for all possible vertex IDs
        J-I in[1,C], % J comes on the right of I (+1) or directly below (+C)
        J mod C!=J-I, % a clever way to remove the case where
                      % "right" wraps around the border:
                      % for this to be false, J-I should be 1 (not C),
                      % and then J mod C = 1.
        B::0..1 % for each valid edge, create a boolean variable
    ],
    foreach(I in Z) % for each vertex,
        1#=sum([B:{T,B}in E,I in T]) % exactly one incident edge must be used
        % this is one way to specify perfect matching
    end,
    solve(E). % solve the problem; success <=> a solution exists

Answer 4

JavaScript (V8), 103 bytes

a=>a.reduce((p,v)=>p.map(u=>u&~v||(S=(m,i)=>m<i?q[m]=m:S(m,i+i,~m&i||S(m-i,i)))(v-u,3),q=[])&&q,[0])[0]

Try it online!

Input array of binaries, output 0 to accept, undefined to reject. It can be convert to truthy / falsy by +2 bytes (append +1), but I believe returning two distinct constant values may be acceptable.

// We use 1 to denote occupied cells, while 0 for empty cells
// And convert above binary as a single number to represent the row
// So `0b1100010` is as same as `OO...O.`
// And specially, `0` is used for an empty row
a=> // input matrix as described above
a.reduce( // for each row
  (p, // p is an array of rows
      // `1` is used if some cells on last row need to be filled with
      //     vertical dominoes cross last row and this row
      // `0` is used if some cells is empty or already filled with
      //     dominoes used before
      // `p` store value `n` with index `n`
      //     or in other words `p[n]` will always equals `n`
      //     `p[m]` will be a hole of array if some value `m` is not
      //     presented in `p`
   v  // current row
  )=>p.map(
    u=> // one possible pattern while unfilled last row
    u&~v|| // if you can use vertical dominoes to fill unfilled
           //     cells on last row, you need to fill these cells
           //     and check if there are some horizontal dominoes
           //     may be used in following recursive function
           // if you cannot fell these cells
           //     you do not ever need to search
    (S=(
      m, // unfilled cells on current row
      i  // a horizontal dominoes
    )=>
     m<i? // if this horizontal domino already moved out the
          // boundary of current row, we stop search
       q[m]=m: // store current unfilled cells pattern to `q` the
               //     variable will be used for next iteration
       S(m,i+i, // move the horizontal domino a cell left
                //     and have it a try by recursion
         ~m&i|| // if current domino may be placed (if cells under
                //     current domino are occupied)
         S(m-i,i) // fill these cells and search recursively
       ))(
         v-u, // fill last row by vertical dominoes and see what left
         3    // a horizontal domino placed on right most
      ),
    q=[] // possible patterns left after current row
  )&&q,
  [0] // nothing is required to be filled before first row
      // so `0` is a valid pattern here
)[0] // check if everything may be just filled

For matrix with \$p\cdot q\$ size, its time complexity seems to be \$O\left(\left(\sqrt{5}+1\right)^{p}\cdot q\right)\$.

Answer 5

Wolfram Language, 82 bytes

(v=Join@@Position[#,1])==Sort[List@@Join@@FindEdgeCover@Subgraph[GridGraph@#2,v]]&

Try it online!

Takes two inputs: an array where 1 represents an occupied cell (unoccupied may be anything else), and a list of the width followed by the height.

This answer takes a graph theory approach using built-in language features. The core of my method is generating a minimum edge cover over a graph representing the occupied spaces (placing the dominoes) and checking whether any vertices are repeated (seeing whether any dominoes overlap).

Part-by-part rundown:

(v=Join@@Position[#,1])     (*generate list of vertices*)
  ==                        (*check if equal to*)
Sort[List@@Join@@           (*the sorted list of vertices from*)
  FindEdgeCover@            (*a minimal edge cover of*)
  Subgraph[GridGraph@#2,v]  (*the graph, generated as a subgraph of a grid graph*)
]&

Answer 6

Ruby, 94 82 bytes

12 bytes saved thanks to Dingus!

f=->s{n=s=~/O/
n&&[0,s=~/,/].all?{|i|t=s+?.*i;t[j=i-~n]>?.?(t[n]=t[j]=?.;f[t]):1}}

Try it online!

A recursive function taking input as a comma separated string (this saves one byte over a newline separated string.) A terminating comma is required, at least for single line input, to enable the function to determine the width of the rectangle.

Works by finding the first available O and checking if another O exists to the right or below. If so, both are deleted and the function calls itself to try to eliminate all remaining Os

Returns false if a solution is possible and true if not.

Commented code

f=->s{n=s=~/O/             #n=index of first O. If there are none, return nil (board is blank)
n&&                        #if an O was found, look for another O to the right and below it
 [0,s=~/,/].all?{|i|       #iterate twice, 0+1 is offset for second O to right, (s=~/,/ the index of the first comma)+1 is offset for second O below 
  t=s+?.*i                 #make a copy of argument s, with some additional .'s added to the end of it to ensure check for an O below doesn't go out of bounds.
   t[j=i-~n]>?. ?          #if a second O (any ASCII character after ".") is found (to the right or below the first)...   [Note: i-~n = i+1+n]
    (t[n]=t[j]=?.;f[t]):1  #...overwrite both of them with .'s and then call the function recursively to eliminate the remaining O's.
 }                         #otherwise return 1 (truthy) to indicate it was not possible to match an entire domino in this direction
}                          #return n&& [0,s=~/,/].all?{...} (n false if already solved, loop false if a solution found by deleting domino in either vertical or horizontal direction.