12

Suppose some figure on the squared paper. Sides of the figure go straight on the lines of squared paper. Figure may have any (not even convex) shape. How to find the maximum number of dominoes (1x2 rectangular) that can be placed in that figure. It is not allowed to put domino over another one. It is allowed to put domino only in such way, when its sides fall exactly on the lines of squared paper.

Knut Herrmann
  • 30,880
  • 4
  • 31
  • 67
Sergey Demyanov
  • 2,655
  • 1
  • 17
  • 9
  • 1
    what have you tried to find out yourself? what exactly is your problem here? can you give some examples? is this homework? – oezi Jan 24 '11 at 09:07
  • it is not a homework, I got this problem from my friend, tried to solve it with pencil and paper and could not. Now I don't know any solution except brute force. I tried several euristics, but there is always an example when my solution is not best. – Sergey Demyanov Jan 24 '11 at 09:10
  • @Sega: you need to state the question more precisely or it will probably be closed. How is the boundary defined, for example ? – Paul R Jan 24 '11 at 09:17
  • I rewrited the question and added some statements about the shape. – Sergey Demyanov Jan 24 '11 at 09:22
  • what does it mean I represent my question? – Sergey Demyanov Jan 24 '11 at 09:26
  • How connected is the figure? Is there a path between any two squares (without using diagonals)? – Svante Jan 24 '11 at 10:18
  • Svante, I think it is not important, cause it is simple to get all such connected figures, and to solve problem for each separately. – Sergey Demyanov Jan 24 '11 at 11:12

2 Answers2

15

Looks like the maximum cardinality matching problem in a bipartite graph. The squares are the vertices and the dominoes are the edges that belong to the matching.

To see that the graph is bipartite, imagine the squares are checkerboard-painted. Black ones only neighbour white ones and vice versa.

Rafał Dowgird
  • 43,216
  • 11
  • 77
  • 90
0

You can classify squares by the number of neighbor free squares as type 0, 1, 2, 3 or 4.

I believe that should work:

  1. find a type 1 square, place there a domino in the only possible way and repeat

  2. else, find a free corner formed by two contiguous type 2 and type 3 squares, place there a domino and go to 1

  3. else, place a domino in any type 2 square and go to 1

  4. you are done

salva
  • 9,943
  • 4
  • 29
  • 57