Inspired by this challenge from puzzling.SE.
Polyominoes are fun - you can fill all sorts of shapes with them. But as soon as you have limits on what polyominoes you can use, you sadly start running into shapes you can't fill.
Today we'll be looking at the L tromino - a shape made up of three conjoined squares, in such a way that all three squares are of the same size, and there is a corner which they all share. It looks like this:
Now, given a shape made out of equal-size squares as input, the challenge is to find out whether that shape can be filled using only non-overlapping L-trominoes that are placed entirely within the input figure. You may have any number of these trominoes, and you may rotate each of them by any integer multiple of 90°.
Rules
- The challenge is to make a program or function.
- Your program will recieve as input a two-dimensional list of values.
- Each entry in the list will contain one of two consistent values of your choice - one to signify that a square should be filled, and the other to signify that it shouldn't.
- You may assume there will be at least one row and at least one column, and that every row and every column will contain at least one cell that needs to be filled. You may also either assume that all rows have been padded to be of equal length, or that they contain nothing after their last filled cell - you may also independently assume either of those for the columns. That is to say, with
1
as squares you need to fill, and0
as squares you need to not fill, you only need to be able to handle one of these four inputs (if given one of the others, your program's behaviour is undefined):
1 1 0
1 1 1
0 1 0
1 1
1 1 1
0 1
1 1 0
1 1 1
1
1 1
1 1 1
1
- To fill some square, you must also fill two other squares. Exactly two of the three squares filled must be diagonally adjacent to (sharing a corner with) eachothers, and they must both be orthogonally adjacent to (sharing a side with) the third.
- You may assume the input shape is contiguous.
- You may assume the input's dimensions will be no greater than 5x5.
- You may not assume the number of rows and the number of columns in the input will be equal. Originally, all this question's test cases featured inputs with an equal number of rows and columns. This was a result of poorly chosen test cases and was not intended to indicate that this would be the case for all inputs.
- Your program either needs to output a single consistent value of your choice if filling exactly the squares specified by the input with L-trominoes is possible, and any other value if it is impossible, or vice versa. For example, you may decide to output
false
if the input shape can be filled, in which case that is the only acceptable output for shapes that can be filled, and any output exceptfalse
is acceptable for input shapes that can't be filled. - However, the output of your program must not vary between runs given identical input, if said input is valid. That means if you have output
2
for some particular valid input, any later runs with exactly that input must also output2
. - This is code-golf - make your code as short as you can.
Examples
The examples use 1
and 0
to represent squares that should and shouldn't be filled respectively, uses true
as the only output for fillable shapes, and false
as the only output for non-fillable shapes.
1 -> false
0 1
1 1 -> true
1 1 1
1 1 1
1 1 1 -> false
0 1 0
1 1 1
0 0 1 -> false
1 0 0
1 1 1
0 1 1 -> true
1 1 0
1 0 1
1 1 1
1 0 1 -> false
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1 -> true
0 1 1 1
1 1 0 1
1 1 1 1
0 1 1 0 -> true
0 1 1 1
1 1 1 1
1 1 1 0
0 1 1 0 -> true
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 0 -> true
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1 -> false
1 1 1 1 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1 -> true
1
s so I'd assume it isn't always a multiple of 3. \$\endgroup\$