All of the Boards

Question

Problem source: https://oj.vnoi.info/problem/backtrack_j

We have these two shapes:

#.
##

and

.#
##

Let's call the first shape the L and the second shape the flipped L.

On a 4x4 board, there are 16 cells. Each cell can be either free or occupied. In all the illustrations, # represents an occupied cell and . represents a free cell.

Your job is to print all 4x4 boards that can be completely filled using the L shape and the flipped L shape. You are not allowed to rotate or flip the shapes, but you can put them anywhere you want as long as the shape isn't clashing with existing occupied cells. You are allowed to represent the boards in any reasonable format and print them in any order.

Here is an example of a board that can be filled:

.##.
....
.##.
....

We can perform these steps to fill the whole board.

Step 1: Fill an L at the top left corner

###.
##..
.##.
....

Step 2: Fill a flipped L at the top right corner

####
####
.##.
....

Step 3: Fill an L at the bottom left corner

####
####
###.
##..

Step 4: Fill a flipped L at the bottom right corner

####
####
####
####

Here is an example of a board that can't be filled:

#...
....
....
....

No matter how hard you try, it's just impossible to fill the board.

Sample output:

###.
#...
....
....

##.#
#...
....
....

#.##
...#
....
....

.###
...#
....
....

####
##.#
....
....

####
#.##
....
....

#.#.
....
#.#.
....

.##.
....
#.#.
....

#..#
....
#.#.
....

.#.#
....
#.#.
....

###.
##..
#.#.
....

##.#
##..
#.#.
....

##.#
#..#
#.#.
....

#.##
#..#
#.#.
....

#.##
..##
#.#.
....

.###
..##
#.#.
....

####
####
#.#.
....

#.#.
....
.##.
....

.##.
....
.##.
....

#..#
....
.##.
....

.#.#
....
.##.
....

###.
##..
.##.
....

##.#
##..
.##.
....

##.#
#..#
.##.
....

#.##
#..#
.##.
....

#.##
..##
.##.
....

.###
..##
.##.
....

####
####
.##.
....

#.#.
....
#..#
....

.##.
....
#..#
....

#..#
....
#..#
....

.#.#
....
#..#
....

###.
##..
#..#
....

##.#
##..
#..#
....

##.#
#..#
#..#
....

#.##
#..#
#..#
....

#.##
..##
#..#
....

.###
..##
#..#
....

####
####
#..#
....

#.#.
....
.#.#
....

.##.
....
.#.#
....

#..#
....
.#.#
....

.#.#
....
.#.#
....

###.
##..
.#.#
....

##.#
##..
.#.#
....

##.#
#..#
.#.#
....

#.##
#..#
.#.#
....

#.##
..##
.#.#
....

.###
..##
.#.#
....

####
####
.#.#
....

###.
#...
#...
##..

##.#
#...
#...
##..

#.##
...#
#...
##..

.###
...#
#...
##..

####
##.#
#...
##..

####
#.##
#...
##..

###.
#...
..#.
##..

##.#
#...
..#.
##..

###.
.#..
..#.
##..

##.#
.#..
..#.
##..

##.#
...#
..#.
##..

#.##
...#
..#.
##..

####
#.##
..#.
##..

####
.###
..#.
##..

#.#.
....
###.
##..

.##.
....
###.
##..

#..#
....
###.
##..

.#.#
....
###.
##..

###.
##..
###.
##..

##.#
##..
###.
##..

##.#
#..#
###.
##..

#.##
#..#
###.
##..

#.##
..##
###.
##..

.###
..##
###.
##..

####
####
###.
##..

###.
#...
...#
##..

##.#
#...
...#
##..

###.
.#..
...#
##..

##.#
.#..
...#
##..

##.#
...#
...#
##..

#.##
...#
...#
##..

####
#.##
...#
##..

####
.###
...#
##..

#.#.
....
##.#
##..

.##.
....
##.#
##..

#..#
....
##.#
##..

.#.#
....
##.#
##..

###.
##..
##.#
##..

##.#
##..
##.#
##..

##.#
#..#
##.#
##..

#.##
#..#
##.#
##..

#.##
..##
##.#
##..

.###
..##
##.#
##..

####
####
##.#
##..

##.#
#...
#...
#..#

#.##
#...
#...
#..#

#.##
..#.
#...
#..#

.###
..#.
#...
#..#

####
###.
#...
#..#

#.##
...#
#...
#..#

.###
...#
#...
#..#

####
##.#
#...
#..#

###.
#...
...#
#..#

##.#
#...
...#
#..#

###.
.#..
...#
#..#

##.#
.#..
...#
#..#

##.#
...#
...#
#..#

#.##
...#
...#
#..#

####
#.##
...#
#..#

####
.###
...#
#..#

#.#.
....
##.#
#..#

.##.
....
##.#
#..#

#..#
....
##.#
#..#

.#.#
....
##.#
#..#

###.
##..
##.#
#..#

##.#
##..
##.#
#..#

##.#
#..#
##.#
#..#

#.##
#..#
##.#
#..#

#.##
..##
##.#
#..#

.###
..##
##.#
#..#

####
####
##.#
#..#

#.#.
....
#.##
#..#

.##.
....
#.##
#..#

#..#
....
#.##
#..#

.#.#
....
#.##
#..#

###.
##..
#.##
#..#

##.#
##..
#.##
#..#

##.#
#..#
#.##
#..#

#.##
#..#
#.##
#..#

#.##
..##
#.##
#..#

.###
..##
#.##
#..#

####
####
#.##
#..#

##.#
#...
#...
..##

#.##
#...
#...
..##

#.##
..#.
#...
..##

.###
..#.
#...
..##

####
###.
#...
..##

#.##
...#
#...
..##

.###
...#
#...
..##

####
##.#
#...
..##

##.#
#...
.#..
..##

#.##
#...
.#..
..##

#.##
..#.
.#..
..##

.###
..#.
.#..
..##

####
###.
.#..
..##

#.##
...#
.#..
..##

.###
...#
.#..
..##

####
##.#
.#..
..##

###.
#...
...#
..##

##.#
#...
...#
..##

#.##
...#
...#
..##

.###
...#
...#
..##

####
##.#
...#
..##

####
#.##
...#
..##

#.#.
....
#.##
..##

.##.
....
#.##
..##

#..#
....
#.##
..##

.#.#
....
#.##
..##

###.
##..
#.##
..##

##.#
##..
#.##
..##

##.#
#..#
#.##
..##

#.##
#..#
#.##
..##

#.##
..##
#.##
..##

.###
..##
#.##
..##

####
####
#.##
..##

#.#.
....
.###
..##

.##.
....
.###
..##

#..#
....
.###
..##

.#.#
....
.###
..##

###.
##..
.###
..##

##.#
##..
.###
..##

##.#
#..#
.###
..##

#.##
#..#
.###
..##

#.##
..##
.###
..##

.###
..##
.###
..##

####
####
.###
..##

##.#
....
....
####

#.##
....
....
####

####
#.#.
....
####

####
.##.
....
####

####
#..#
....
####

####
.#.#
....
####

##.#
#...
##..
####

#.##
#...
##..
####

#.##
..#.
##..
####

.###
..#.
##..
####

####
###.
##..
####

#.##
...#
##..
####

.###
...#
##..
####

####
##.#
##..
####

###.
#...
#..#
####

##.#
#...
#..#
####

#.##
...#
#..#
####

.###
...#
#..#
####

####
##.#
#..#
####

####
#.##
#..#
####

###.
#...
..##
####

##.#
#...
..##
####

###.
.#..
..##
####

##.#
.#..
..##
####

##.#
...#
..##
####

#.##
...#
..##
####

####
#.##
..##
####

####
.###
..##
####

#.#.
....
####
####

.##.
....
####
####

#..#
....
####
####

.#.#
....
####
####

###.
##..
####
####

##.#
##..
####
####

##.#
#..#
####
####

#.##
#..#
####
####

#.##
..##
####
####

.###
..##
####
####

####
####
####
####

This is code-golf, the shortest code (in bytes) wins.

Answer 1

Python, 122 bytes (-2 thanks to @ovs)

A=0,19,35
for d in(2,16)*2:A={x|y*d for x in A for y in A if 1>x&y*d}
for i in A:print(f"{i:019_b}_".translate(33*"#.\n"))

Attempt This Online!

Previous Python, 124 bytes (-1 thanks to @xnor)

A={0,19,35}
for d in(2,16)*2:A={x|y*d for x in A for y in A if 1>x&y*d}
for i in A:print(f"{i:019_b}_".translate(33*"#.\n"))

Attempt This Online!

Previous Python, 126 bytes

A={0,19,35}
for d in(1,4)*2:A|={(x|y<<d)*(1>x&y<<d)for x in A for y in A}
for i in A:print(f"{i:019_b}_".translate(33*"#.\n"))

Attempt This Online!

Answer 2

Wolfram Language (Mathematica), 249 230 224 210 bytes

(r={f=Table[1,{4},{4}]};p={e={1,1},{0,2},{2,0}};q=Flatten[Table[ArrayPad[k,{i,j}],{k,{{{1,0},e},{{0,1},e}}},{i,p},{j,p}],2];(a=#;r=Join[r,v=Select[a-#&/@q,AllTrue[#,(#>=0&),2]&]];Table[#0[e],{e,v}])&@f;Union@r)

Try it online!

Recursive solution based on the next fact :
If given matrix is valid and we remove from it "L" or "anti-L", then the new matrix will be valid too.

All valid boards in a single picture:

Ungolfed version as explanation:

init = Table[1, {4}, {4}];
result = {init};
forms = {{{1, 0}, {1, 1}}, {{0, 1}, {1, 1}}};
pads = {{1, 1}, {0, 2}, {2, 0}};
patterns = 
  Flatten[Table[
    ArrayPad[k, {i, j}], {k, forms}, {i, pads}, {j, pads}], 2];
main[arr_] := 
  With[{nextValid = 
     Select[arr - # & /@ patterns, AllTrue[#, (# >= 0 &)] &, 2]},
   result = Join[result, nextValid];
   main[#] & /@ nextValid
   ];
main@init;
output = Union@result;

The longest part of code is a preparing of matrix patterns.
I'll try to golf it harder!
That's all. Add a some mad golfing, and can’t improve the algorithm anymore (

Answer 3

JavaScript (ES6), 159 bytes

A rather lenghty port of loopy walt's answer.

f=(A=new Set([0,19,35]),d=2)=>(B=[...A])[99]?B.map(v=>(g=k=>k--?"#."[v>>k&1]+[`
`[k&3]]+g(k):'')(16)).join`
`:f(A,d^18,B.map(x=>B.map(y=>x&y*d||A.add(x|y*d))))

Try it online!

Answer 4

Nekomata, 28 bytes

2r↕1:ÐÐ3r~ᵑᵐç3r~ᵑçaᵐᶜ{0*}∑2<

Attempt This Online!

Outputs 215 4×4 matrices using 1s for free and 0s for occupied cells.

Explanation

2r↕1:ÐÐ3r~ᵑᵐç3r~ᵑçaᵐᶜ{0*}∑2<
2r↕1:ÐÐ                         Push [[0,1],[1,1]] or [[1,0],[1,1]]
       3r~ᵑᵐç                   Prepend 0, 1 or 2 zeros to each sublist
             3r~ᵑç              Prepend 0, 1 or 2 zeros to the list
                  a             Get all possible values as a list
                   ᵐᶜ{0*}       Optionally multiply each value by zero
                         ∑      Take the sum
                          2<    Check if all numbers in the result is less than 2

Answer 5

Haskell, 152 bytes

import Data.List
r=[[[r,c]|r<-[0..3],c<-[0..3],notElem[r,c]l]|l<-concat<$>subsequences[[[r-1,c+t],[r,c],[r,c+1]]|r<-[1..3],c<-[0..2],t<-[0,1]],l==nub l]

Try it online!

Answer 6

05AB1E, 33 bytes

56āδš<TÝ37SKδ+€`æε˜ÐÙQiX16Å0rǝ4ô,

Outputs as a list of matrices of 0s for . and 1s for #.

Try it online or try it online with pretty-printing footer. (Pretty slow, so only outputs about 175 of them before timing out on TIO.)

Explanation:

Step 1: Push the 0-based indices of the two shapes at every possible position on the (flattened) 4x4 board:

56āδš<            # Push the indices of the two L-shapes in the top-left corner of the
                  # (flattened) board:
56                #  Push 56
  ā               #  Push a list in the range [1,length] (without popping): [1,2]
   δ              #  Apply double-vectorized:
    š             #   Prepend: [[1,5,6],[2,5,6]]
     <            #  Decrease each inner value by 1: [[0,4,5],[1,4,5]]
TÝ37SKδ+€`        # Combine it with every position these 2x2-shapes can be on the 4x4
                  # board:
TÝ                #  Push a list in the range [0,10]
  37SK            #  Remove the 3 and 7: [0,1,2,4,5,6,8,9,10]
δ                 #  Apply double-vectorized
 +                #   Add the values together
  €`              #  Flatten it one level down

Try just step 1 online.

Step 2: Get all possible 0..length combinations of these possible shape-positions, and check if they can be combined without overlapping indices:

æ                 # Get the powerset of this list of lists shape-indices
 ε                # Foreach over each inner list:
  ˜               #  Flatten it to a single list of indices
   ÐÙQ            #  Check if all indices are unique:
   Ð              #   Triplicate the list of indices
    Ù             #   Uniquify the top copy
     Q            #   Check if the top two lists are still the same

Try just the first two steps online.

Step 3: For each valid list of indices, create the board-matrix and output it:

      i           #  If the earlier check is truthy:
       X          #   Push a 1
        16Å0      #   Push a list of 16 0s
            r     #   Reverse the stack from indices,1,16x0 to 16x0,1,indices
                  #   (where the indices are from the triplcate of step 2)
             ǝ    #   Insert a 1 into the list of 16 0s at the given indices
              4ô  #   Split the list into parts of size 4
                , #   Pop and output this 4x4 matrix with trailing newline

Answer 7

Charcoal, 47 bytes

⊞υ⁵⁴¹²⁰⁰Ｆ¹³Ｆ×Ｘ²ι⟦³⁵¦⁶⁷⟧ＦυＦ¬＆λκ⊞υ⁺λκＥυＥ⪪⍘鲦⁵Φλξ

Try it online! Link is to verbose version of code. Outputs 215 4×4 grids using 1s for free and 0s for occupied cells. Explanation:

⊞υ⁵⁴¹²⁰⁰

Start with a completely occupied grid. 541200 is 10000100001000010000 in binary, where the 0s are occupied cells and the 1s are separators; the grid is obtained by splitting the bits into rows of 5 and then deleting the first column.

Ｆ¹³

Loop over all valid and some invalid (3, 4, 8 and 9) shape positions. (Invalid shape positions intersect the separators thus preventing shapes from being removed at those positions.)

Ｆ×Ｘ²ι⟦³⁵¦⁶⁷⟧

Loop over the bit patterns that represent the two L shapes at that position.

Ｆυ

Loop over the existing boards.

Ｆ¬＆λκ⊞υ⁺λκ

If the shape can be removed then add the new board.

ＥυＥ⪪⍘鲦⁵Φλξ

Output the discovered boards.