Cover a board with dominoes
Given an arbitrarily sized and shaped board of squares, find
- If there is a way to cover it with dominoes (2x1 squares) such that each square is covered and no two squares overlap.
- If there is a way to cover it, the number of different ways it can be covered.
Bonus:
- For each domino covering in 2 above, draw/write the covering.
- Generate a board with a specified number of domino coverings. Even more bonus: draw/write all the coverings.
Input would be passed as an array
of chars
(or a string
, whatever your program can read from a file passed via stdin
) where a square is represented by '■'
and an empty space is represented by ' '
. The input for bonus two would be an int
(or long, if you wanted to allow for very many coverings).
The output should be at least the number of coverings, with 0 being valid to mean there are no coverings. Bonus 1 could vary depending on your language/library. You could use a graphics toolkit to actually draw the board and dominoes, or make some form of ASCII representation of it and write it to a file or stdout
. Bonus 2 would work the same; either draw it or write it.
Example input file 1:
■■
Output: 1
Example input file 2:
■
■■■
Output: 0
Example input file 3:
■■■■
■■■■
Output: 5
Example input file 4:
■
■■■
■
■
■■■
■
Output: 1
Example input file 5:
■■■■
■■■■
■■■■
Output: 10