[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]
# [Charcoal](https://github.com/somebody1234/Charcoal), 120 bytes
```
ＷＳ⊞υιυＦＬυＦＬ§υι«Ｊκι¿⁼ＫＫO«≔⟦ω⟧θＷθ«≔Φurdl№⪪α¹⊟ＫＤ²✳μλ¿λ«≔§λ⁰λ✳λλ≔ＫＫηＰ§dlur⌕urdlλ¿⁼ηO≔⟦⟧θ«Ｍ✳η⊞θη⊞θＫＫ»»«≔⊟θλ✳λ↧λ✳ＫＫ↧⊟θ»»ＵＭＫＡ↥λ
```
[Try it online!](https://tio.run/##hVFNa4QwED0nvyJ4imCl7bWnpe3Cll0Utj2VHkSza9jR@JHsFoq/3SYmWW2hNGJMZt68efPMy6zLRQbjeCk5MEI3daPkXna8PtIwJKnqS6oiwsMHnOqgpEqfDqIjdMvqo9RJjVreV3JTF@zTFuncF0YvqmpeBT1ZGsQPhD63KoOepoydaBiRIAksFK36nh9r@n75iEhr0MgJa23eA9YcJOtooLoCgog8CqW17RvgkmYRudOcqWgm/ifesVxyUdP7iMyXKjQrIjA1mUSBa@F7@FEgIrczElkfZiZY5Fyln6t04Z0CyZupzpMGBahOK1/zuriOAVqSrViYVHp/vDdXaxBi0DMnGu3EmS1klZ4KTT@xndVcA1amiw5mH8iC0Q@jjWz/mX8rLqzLs57p2x8w12yJtcyuwPQ37y5rHkVVZdoWU7ICME6@Nc2PBgMexjFO4jgxK8Zmm676aL86ghOb1Q@2UJPC7vSrzFJNZXHs0dgB9YbHmzN8Aw "Charcoal – 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 `O`s 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 `O`s. (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 `O`s:
```
drld
u..u
```
[Answer]
# [JavaScript (V8)](https://v8.dev/), 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!](https://tio.run/##rVZbU9w2FH7XrzjMZMAuxgFC2pSMYWgobXrJtg156AAzaG3ZK2JLrqTdZQv0r9MjyVc2PLVzdrWy9twvn3VDF1SnitdmZ/Hm8TFPgiKqkyw5CkSyHy2SIq5oHQQq4mFypPxDGt3gQ/qV2NwMxNHe8T/BKuHbWXSb3GxvZOEhT5LV5k2S3IbHG2Jn5zANw0gcI@dhHizCEGUL4ALy4/yiuDq0S1IHu@F9HeyFj6kU2kBKNdPnas4ggWsyAbgH2HPr@YxrwI@ZMTCKLzgtHfchjNgoaC6KkkEmKy4klJRnsGDK8JSW5YqQGCYQI1nmGPa7vdOfUgFTBqli1LAMltzM0KBiDG148pb24RWS3XszTNvArO2qRts1NYYpQbyluBFq9@SJMqtu3@1PWgWKpYaKYl5SBYXi3pORmLV/gGT3bMEEcmToLMbAqOblCgwv2RfkXiN9jWT3M6n431IYm5gdl6g2mtbF3kG7O5Nz1QfsBBTNuMurDbX1LHb8ZOisd9Vnf9Jlf89lxe5PW62ZBCENCIbOG4mfeTprlHtOW7FXzZ6KzPWDS1FFV5DaaLASrKrN6lmxlJWlBlpKUaAKYFnB@r6YdNR6@bM7/wPpI9KH5vwE9nZv93bBsKZtrTeklYwHq@X@hFp@ciev3dpqkYKBzIEbDVqWc8NxCjq//dqn8RM@9UreIf3e57m13BfiHL5DOmiy/A1@G/Y@zOEwnLvdgesOz@6adcw8zEvcjEEMb5BOPftzCXiP5IftW7eePtU@DtWe/@CeLPv3SL/07GOXena7nsAZUuzZx17HnfZfkWL4EenEnf@GhOzXbwkZwNAZLfUQh/6Uc9@X1ECJU2bALCXINJ3XHE99V2HP5twgFPg5IWTytMOpYqD/muOPhhvJBYpOV64JdeR6P5VKMKWJD4401t8bO9y0XNIVgk1VS635FKECDXq4QpsN7njcws6WWdZIi3k1Zcq2Wmva8XTzPulwqU3pB4kTZdUhTCxhhbGXOGB22nKuMPacLTvxiAxrN0pPa85G3TivWU2VxVfSdyshw95qsR4BteTFzCCcVRIVpBLREYHcYjNiusZpsSFZp@hULhiZdEUe6Bs4R0j8ZFhap9txZrfUIXA31msd3SaI9AM6ngznfVsKV7NKorK2YiReU@cVstuU1Zi1GTUupKk0RlY7Jcvbnhh5PyxWg3vaFp0qha8OVjFhYDnjqX0pkLizFY/CHjdSRT@ztcaYPMEKFySZjALoskLGYNFVo490mCuyFlBfDkzgTJaysO9tj6@5VNgR6YxpPZVUZWRd1BegxlQYbsG9LPAVZ2ZV/AXeyVPsHNrvOrDU0g/WujPPClOY0vSzUbj8Fy/@n2MLajZzgUe2CwdtETZbjXcMll3ZAbq46O5dEV6u5uwqahgdBkaQ25@rqxDuCMBAm@X5aByuOPZY43yaYOtSXIqt0LO77kRe95JOWpEY73BVEPYCW6G7ZJYIiJAcwUUcx3YfK1aXNGXBS7i/vI@3XxYRbG2FV47ZQq5l9r9JAlsTtPp2YBShZ14aNJsH1n7zH88haP7ZSLpUhFArbJzg@sWd//MBgqXCS0LoQnaXzUvx4m4cwcOluG7UMvu@WNeBs2vvc6FneyAPj/8C "JavaScript (V8) – 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]
# [JavaScript (V8)](https://v8.dev/), 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!](https://tio.run/##lVZJc9s2FL7jV7yTRU1leE9dt3LGrZPWaWumtXPoOJ4JREISEpKgAVBLR5O/7j4ABBc5OnSeBEHg25cP/MwWTCdKlGZ/cf48HT@z8SWjiqdVwqOoHC2G48uS5qyMqvFltfd1sdlEd@MoHwl8kP8kXj895I/j/OLOHn0nRl/zPbHZ4L99gSzDYbTYr0Ynw9HT@OFxuLf3NHo4fBzi99lwbRKmuYYxfCIxwAbgyK33c6EBP2bOwSixECwDy3kBPTYGWhSzjEMqc1FIyJhIYcGVEQnLsjUhFGKgSJaZwnGzd/oTVsCEQ6I4MzyFpTBzNKg4RxuevKVjOEGye28G/RWFs52XaLtkxnBVEG@J1kJhT7aUWXXHbn8VFCieGFbMqowpmCnhPemJWfunSHbPF7xAjhSdxRg40yJbgxEZ/4bcGdIrJLufSyX@lYWxidl3iQrRBBdbB@3uraxUG7ATUCwVLq821OAZdfyk66x31Wc/brJ/5LJi99dBayqhkAYKjs4biZ8qmdfKPaet2Em9Z0Xq@sGlKGdrSGw0WAmel2a9UyzhWaaBZbKYoQrg6Yy3fRE3FLz83Z3/jXSHdFufX8HR4eroEGzHuka03pAgSTur5f6AWt65kzO3Bi2y4CCnIIwGLbPKCFnoxm@/tmn8gP9aJb8g/dXmOVhuC3EPPyOd1ln@Hr81extmdxju3e7UdYdnd83aZ@7mhdZjQOEc6dqz70rADZIfth/cer2tvR@qPf/V/bPsb5D@aNn7LrXsdr2Ct0jUs/e9po32P5Eo/IZ05c7fI/m5tE//kZXvP2Ygw2kyYJYSZJJUpcBT3z3Ym1NhcOT9PBASb3cyUxz0U4U/Gj5LUaDoZO2aTY9cjydSFVxp4oMI1m@MHWKWLdkaQSUvpdZigpCABj0soc0aXzw@YQfLNK2liyqfcGVbKph2PM1cxw3@hNTdSpwcqw7hYAlrjD3DQbJTNRUKY5/yZSM@It0a9dITzNmoa@c1L5myOErariSk20MB0xE4MzGbG4StXKKCRCIKImBbDEbs1jgVNiTrFJvIBSdxU8yOvo5zhNCtoQhOh7HlK@aQthnfF50bEkTaQexPgPM@lMLVLJeoLFSM0BfqvEK@SniJWZsz40KaSGNkvp/xaeiJnvfdYtX4pm3RmVJ4RfCcFwaWc5FY8Ce0sUV7YfcbKWdf@IvGiLcwwQVJ4l4ATVZIHxSaarSRdnNFXgQU/HqP0Ri8stB7O1feqUnGki9wYKMynLwUrFFcZlLhNSQwlmTOtZ5IpuwVRrEyXH1LsO5b7LCzw9pKfRfgRXJ67g36o53SAQcs1NTvGEuBntdNn2B7qt2mOyacUdZxg8Kd3ClpBxPfTixuTK05022@3i2/LRlKTHdw/M/jT1TjbJpo8LH4WAyG7iVwBeNLWFF8LcujYfu8fprZp7cOmCgiguY3hYmywLYZ2Bc/ZDTJPDp4oPHjwczLLawcLmMYxAN4jbfYBRwOqcXSaDAYjuAY3yR/JKR5Z6RTqd5gK0XGSpYKWyuaRga5nv8D "JavaScript (V8) – 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]
# [Wolfram Language](https://www.wolfram.com/language/), 82 bytes
```
(v=Join@@Position[#,1])==Sort[List@@Join@@FindEdgeCover@Subgraph[GridGraph@#2,v]]&
```
[Try it online!](https://tio.run/##XYzNCsIwEITvfQqhIAp7Se01EBAtiIdCjyGEaP/20ETS2Evx2WPaomh3YBmGb6ZTrq065fCufE39bqAXg5qx3PTo0GgeAxF7SgtjHb9i7xhbgDPq8lQ21dEMlWXF89ZY9Wh5ZrHMJsfiBAYhtj63qB2v@UiAvGBMwhci@qYSCMigaPO5wM36TSZChnYKh7/2QsoVu26vmYUg814a9vwb "Wolfram Language (Mathematica) – 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](https://en.wikipedia.org/wiki/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]
# [Ruby](https://www.ruby-lang.org/), ~~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!](https://tio.run/##XVDLboMwELzzFYhDlLSbob02cvgEfwDyIZGCSkUpis0hyuPX6dprE1rLsnfHs@udOY/HyzQ1aru3115Z9Sh1mfWrVf1GPqHS4NB11fXW3pyyrxVe2p2rv1S7ffRmX6Fau7o3iiGjKuya2pnNx/v9Pg2js3kx/FjbHrsT5c2hs5d87a/TpsiyIW/qQpOmwuSSQAOkeREHYDxyAjIfC5h5AZwxaA0PxuMJA75Wh/YIqVB4p8ba5@FrCUEx@lcmrUIZkNgUidCih5fob7@fDrjz6D7ZAr6XDsyCuPciI/EmieUn@VPjjwdBR1AAISy8SHOm6SEjR01IoHQWNhOSKkqmIHoVcIqmhDIgGRRET78 "Ruby – 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 `O`s
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. 
```
]