22
\$\begingroup\$

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.
\$\endgroup\$
7
  • \$\begingroup\$ What a lovely question! \$\endgroup\$ – Anush Mar 23 at 20:02
  • \$\begingroup\$ Suggested test case: .OOOOOOOOO/OOOOOOOOO. followed by 8 rows of 10 O’s. It cannot be made by domino’s. As when paint 10x10 board as chessboard, all two dots are placed in same color cells. \$\endgroup\$ – tsh Mar 24 at 4:26
  • \$\begingroup\$ All current testcases may be solved by painting chessboards. So I would suggest another testcase: . O . . . . / O O O O O O / . . . . O . -> false \$\endgroup\$ – tsh Mar 24 at 5:34
  • \$\begingroup\$ @tsh I'm not sure what you mean by a chessboard painting algorithm, but I added those test cases. \$\endgroup\$ – Beefster Mar 24 at 15:14
  • \$\begingroup\$ Say chessboard, I meant. Chessboard is a grid painted with black and white. Considering placing dominoes on chessboard, each domino would always use 1 black cell and 1 white cell. So we just count how many O‘s are placed on black vs white cells. And the layout cannot be made by dominos if these two numbers are not equal. Although equality of these two numbers does not mean it must be possible layout. \$\endgroup\$ – tsh Mar 24 at 23:44
4
\$\begingroup\$

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)
\$\endgroup\$
3
  • \$\begingroup\$ "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 maybe this approach may not work for last testcase. \$\endgroup\$ – tsh Mar 25 at 1:20
  • \$\begingroup\$ a large testcase \$\endgroup\$ – tsh Mar 25 at 1:21
  • \$\begingroup\$ updated to run in time \$\endgroup\$ – user81655 Mar 28 at 0:05
3
\$\begingroup\$

Charcoal, 120 bytes

WS⊞υιυFLυFL§υι«Jκι¿⁼KKO«≔⟦ω⟧θWθ«≔Φurdl№⪪α¹⊟KD²✳μλ¿λ«≔§λ⁰λ✳λλ≔KKηP§dlur⌕urdlλ¿⁼ηO≔⟦⟧θ«M✳η⊞θη⊞θKK»»«≔⊟θλ✳λ↧λ✳KK↧⊟θ»»UMKA↥λ

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).

WS⊞υιυ

Read and print the input.

FLυFL§υι«

Loop over all cells of the input.

Jκι¿⁼KKO«

If the current cell is an O, then:

≔⟦ω⟧θWθ«

Start a depth-first search of the board.

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

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.

≔KKη

Grab the adjacent cell.

P§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.

M✳η⊞θη⊞θKK»»

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

«≔⊟θλ✳λ↧λ✳KK↧⊟θ

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

»»UMKA↥λ

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
\$\endgroup\$
2
\$\begingroup\$

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)\$.

\$\endgroup\$
1
  • \$\begingroup\$ I'm only sure that time complexity is at most \$O\left(\left(\sqrt{5}+1\right)^p\cdot q\right)\$ and at least \$\Omega\left(\left(\frac{\sqrt{5}+3}{2}\right)^p\cdot q\right)\$. But I don't know how to prove its time complexity... :( \$\endgroup\$ – tsh Mar 25 at 1:44
2
\$\begingroup\$

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*)
]&
\$\endgroup\$
3
  • \$\begingroup\$ Maybe this is the first answer works in polynomial time? \$\endgroup\$ – tsh Mar 24 at 7:05
  • \$\begingroup\$ @tsh It's hard to say for certain, but that seems likely. \$\endgroup\$ – DanTheMan Mar 24 at 7:41
  • \$\begingroup\$ 65 bytes \$\endgroup\$ – att Apr 6 at 16:49
2
\$\begingroup\$

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. 
\$\endgroup\$
2
  • \$\begingroup\$ @Dingus OMG - all? was the thing I was looking for. You made some other nice improvements. Thanks - Ir's 2am here and I'm in bed - Will edit it in tomorrow. \$\endgroup\$ – Level River St Mar 24 at 2:05
  • \$\begingroup\$ "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". But this one would time out for this 10x10 testcase \$\endgroup\$ – tsh Mar 25 at 1:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.