How many ways to arrange Lego bricks on a Lego board?

Question

Let's say I have a board like this one (though significantly smaller, it's 4x7)

and I have two 2x3 bricks.

I'd like to know how many ways to arrange the bricks on the board. The bricks should stay inside the board and they should not overlay.

Doing some calculations/estimations, I came up with ~285 arrangements, but I couldn't figure out a more "scientific" method. I'd also like to "create" a formula taking into account variables like the board size, the number of bricks and their size. Thanks in advance.

Answer 1

The following 316 arrangements are possible: (some are symmetric; enumerated with a C# program)

111.
111.
222.
222.
....
....
....

111.
111.
....
222.
222.
....
....

111.
111.
....
....
222.
222.
....

111.
111.
....
....
....
222.
222.

111.
111.
.222
.222
....
....
....

111.
111.
....
.222
.222
....
....

111.
111.
....
....
.222
.222
....

111.
111.
....
....
....
.222
.222

111.
111.
22..
22..
22..
....
....

111.
111.
....
22..
22..
22..
....

111.
111.
....
....
22..
22..
22..

111.
111.
.22.
.22.
.22.
....
....

111.
111.
....
.22.
.22.
.22.
....

111.
111.
....
....
.22.
.22.
.22.

111.
111.
..22
..22
..22
....
....

111.
111.
....
..22
..22
..22
....

111.
111.
....
....
..22
..22
..22

....
111.
111.
222.
222.
....
....

....
111.
111.
....
222.
222.
....

....
111.
111.
....
....
222.
222.

....
111.
111.
.222
.222
....
....

....
111.
111.
....
.222
.222
....

....
111.
111.
....
....
.222
.222

....
111.
111.
22..
22..
22..
....

....
111.
111.
....
22..
22..
22..

....
111.
111.
.22.
.22.
.22.
....

....
111.
111.
....
.22.
.22.
.22.

....
111.
111.
..22
..22
..22
....

....
111.
111.
....
..22
..22
..22

222.
222.
111.
111.
....
....
....

....
....
111.
111.
222.
222.
....

....
....
111.
111.
....
222.
222.

.222
.222
111.
111.
....
....
....

....
....
111.
111.
.222
.222
....

....
....
111.
111.
....
.222
.222

....
....
111.
111.
22..
22..
22..

....
....
111.
111.
.22.
.22.
.22.

....
....
111.
111.
..22
..22
..22

222.
222.
....
111.
111.
....
....

....
222.
222.
111.
111.
....
....

....
....
....
111.
111.
222.
222.

.222
.222
....
111.
111.
....
....

....
.222
.222
111.
111.
....
....

....
....
....
111.
111.
.222
.222

22..
22..
22..
111.
111.
....
....

.22.
.22.
.22.
111.
111.
....
....

..22
..22
..22
111.
111.
....
....

222.
222.
....
....
111.
111.
....

....
222.
222.
....
111.
111.
....

....
....
222.
222.
111.
111.
....

.222
.222
....
....
111.
111.
....

....
.222
.222
....
111.
111.
....

....
....
.222
.222
111.
111.
....

22..
22..
22..
....
111.
111.
....

....
22..
22..
22..
111.
111.
....

.22.
.22.
.22.
....
111.
111.
....

....
.22.
.22.
.22.
111.
111.
....

..22
..22
..22
....
111.
111.
....

....
..22
..22
..22
111.
111.
....

222.
222.
....
....
....
111.
111.

....
222.
222.
....
....
111.
111.

....
....
222.
222.
....
111.
111.

....
....
....
222.
222.
111.
111.

.222
.222
....
....
....
111.
111.

....
.222
.222
....
....
111.
111.

....
....
.222
.222
....
111.
111.

....
....
....
.222
.222
111.
111.

22..
22..
22..
....
....
111.
111.

....
22..
22..
22..
....
111.
111.

....
....
22..
22..
22..
111.
111.

.22.
.22.
.22.
....
....
111.
111.

....
.22.
.22.
.22.
....
111.
111.

....
....
.22.
.22.
.22.
111.
111.

..22
..22
..22
....
....
111.
111.

....
..22
..22
..22
....
111.
111.

....
....
..22
..22
..22
111.
111.

.111
.111
222.
222.
....
....
....

.111
.111
....
222.
222.
....
....

.111
.111
....
....
222.
222.
....

.111
.111
....
....
....
222.
222.

.111
.111
.222
.222
....
....
....

.111
.111
....
.222
.222
....
....

.111
.111
....
....
.222
.222
....

.111
.111
....
....
....
.222
.222

.111
.111
22..
22..
22..
....
....

.111
.111
....
22..
22..
22..
....

.111
.111
....
....
22..
22..
22..

.111
.111
.22.
.22.
.22.
....
....

.111
.111
....
.22.
.22.
.22.
....

.111
.111
....
....
.22.
.22.
.22.

.111
.111
..22
..22
..22
....
....

.111
.111
....
..22
..22
..22
....

.111
.111
....
....
..22
..22
..22

....
.111
.111
222.
222.
....
....

....
.111
.111
....
222.
222.
....

....
.111
.111
....
....
222.
222.

....
.111
.111
.222
.222
....
....

....
.111
.111
....
.222
.222
....

....
.111
.111
....
....
.222
.222

....
.111
.111
22..
22..
22..
....

....
.111
.111
....
22..
22..
22..

....
.111
.111
.22.
.22.
.22.
....

....
.111
.111
....
.22.
.22.
.22.

....
.111
.111
..22
..22
..22
....

....
.111
.111
....
..22
..22
..22

222.
222.
.111
.111
....
....
....

....
....
.111
.111
222.
222.
....

....
....
.111
.111
....
222.
222.

.222
.222
.111
.111
....
....
....

....
....
.111
.111
.222
.222
....

....
....
.111
.111
....
.222
.222

....
....
.111
.111
22..
22..
22..

....
....
.111
.111
.22.
.22.
.22.

....
....
.111
.111
..22
..22
..22

222.
222.
....
.111
.111
....
....

....
222.
222.
.111
.111
....
....

....
....
....
.111
.111
222.
222.

.222
.222
....
.111
.111
....
....

....
.222
.222
.111
.111
....
....

....
....
....
.111
.111
.222
.222

22..
22..
22..
.111
.111
....
....

.22.
.22.
.22.
.111
.111
....
....

..22
..22
..22
.111
.111
....
....

222.
222.
....
....
.111
.111
....

....
222.
222.
....
.111
.111
....

....
....
222.
222.
.111
.111
....

.222
.222
....
....
.111
.111
....

....
.222
.222
....
.111
.111
....

....
....
.222
.222
.111
.111
....

22..
22..
22..
....
.111
.111
....

....
22..
22..
22..
.111
.111
....

.22.
.22.
.22.
....
.111
.111
....

....
.22.
.22.
.22.
.111
.111
....

..22
..22
..22
....
.111
.111
....

....
..22
..22
..22
.111
.111
....

222.
222.
....
....
....
.111
.111

....
222.
222.
....
....
.111
.111

....
....
222.
222.
....
.111
.111

....
....
....
222.
222.
.111
.111

.222
.222
....
....
....
.111
.111

....
.222
.222
....
....
.111
.111

....
....
.222
.222
....
.111
.111

....
....
....
.222
.222
.111
.111

22..
22..
22..
....
....
.111
.111

....
22..
22..
22..
....
.111
.111

....
....
22..
22..
22..
.111
.111

.22.
.22.
.22.
....
....
.111
.111

....
.22.
.22.
.22.
....
.111
.111

....
....
.22.
.22.
.22.
.111
.111

..22
..22
..22
....
....
.111
.111

....
..22
..22
..22
....
.111
.111

....
....
..22
..22
..22
.111
.111

11..
11..
11..
222.
222.
....
....

11..
11..
11..
....
222.
222.
....

11..
11..
11..
....
....
222.
222.

11..
11..
11..
.222
.222
....
....

11..
11..
11..
....
.222
.222
....

11..
11..
11..
....
....
.222
.222

11..
11..
11..
22..
22..
22..
....

11..
11..
11..
....
22..
22..
22..

11..
11..
11..
.22.
.22.
.22.
....

11..
11..
11..
....
.22.
.22.
.22.

1122
1122
1122
....
....
....
....

11..
1122
1122
..22
....
....
....

11..
11..
1122
..22
..22
....
....

11..
11..
11..
..22
..22
..22
....

11..
11..
11..
....
..22
..22
..22

....
11..
11..
11..
222.
222.
....

....
11..
11..
11..
....
222.
222.

....
11..
11..
11..
.222
.222
....

....
11..
11..
11..
....
.222
.222

....
11..
11..
11..
22..
22..
22..

....
11..
11..
11..
.22.
.22.
.22.

..22
1122
1122
11..
....
....
....

....
1122
1122
1122
....
....
....

....
11..
1122
1122
..22
....
....

....
11..
11..
1122
..22
..22
....

....
11..
11..
11..
..22
..22
..22

222.
222.
11..
11..
11..
....
....

....
....
11..
11..
11..
222.
222.

.222
.222
11..
11..
11..
....
....

....
....
11..
11..
11..
.222
.222

..22
..22
1122
11..
11..
....
....

....
..22
1122
1122
11..
....
....

....
....
1122
1122
1122
....
....

....
....
11..
1122
1122
..22
....

....
....
11..
11..
1122
..22
..22

222.
222.
....
11..
11..
11..
....

....
222.
222.
11..
11..
11..
....

.222
.222
....
11..
11..
11..
....

....
.222
.222
11..
11..
11..
....

22..
22..
22..
11..
11..
11..
....

.22.
.22.
.22.
11..
11..
11..
....

..22
..22
..22
11..
11..
11..
....

....
..22
..22
1122
11..
11..
....

....
....
..22
1122
1122
11..
....

....
....
....
1122
1122
1122
....

....
....
....
11..
1122
1122
..22

222.
222.
....
....
11..
11..
11..

....
222.
222.
....
11..
11..
11..

....
....
222.
222.
11..
11..
11..

.222
.222
....
....
11..
11..
11..

....
.222
.222
....
11..
11..
11..

....
....
.222
.222
11..
11..
11..

22..
22..
22..
....
11..
11..
11..

....
22..
22..
22..
11..
11..
11..

.22.
.22.
.22.
....
11..
11..
11..

....
.22.
.22.
.22.
11..
11..
11..

..22
..22
..22
....
11..
11..
11..

....
..22
..22
..22
11..
11..
11..

....
....
..22
..22
1122
11..
11..

....
....
....
..22
1122
1122
11..

....
....
....
....
1122
1122
1122

.11.
.11.
.11.
222.
222.
....
....

.11.
.11.
.11.
....
222.
222.
....

.11.
.11.
.11.
....
....
222.
222.

.11.
.11.
.11.
.222
.222
....
....

.11.
.11.
.11.
....
.222
.222
....

.11.
.11.
.11.
....
....
.222
.222

.11.
.11.
.11.
22..
22..
22..
....

.11.
.11.
.11.
....
22..
22..
22..

.11.
.11.
.11.
.22.
.22.
.22.
....

.11.
.11.
.11.
....
.22.
.22.
.22.

.11.
.11.
.11.
..22
..22
..22
....

.11.
.11.
.11.
....
..22
..22
..22

....
.11.
.11.
.11.
222.
222.
....

....
.11.
.11.
.11.
....
222.
222.

....
.11.
.11.
.11.
.222
.222
....

....
.11.
.11.
.11.
....
.222
.222

....
.11.
.11.
.11.
22..
22..
22..

....
.11.
.11.
.11.
.22.
.22.
.22.

....
.11.
.11.
.11.
..22
..22
..22

222.
222.
.11.
.11.
.11.
....
....

....
....
.11.
.11.
.11.
222.
222.

.222
.222
.11.
.11.
.11.
....
....

....
....
.11.
.11.
.11.
.222
.222

222.
222.
....
.11.
.11.
.11.
....

....
222.
222.
.11.
.11.
.11.
....

.222
.222
....
.11.
.11.
.11.
....

....
.222
.222
.11.
.11.
.11.
....

22..
22..
22..
.11.
.11.
.11.
....

.22.
.22.
.22.
.11.
.11.
.11.
....

..22
..22
..22
.11.
.11.
.11.
....

222.
222.
....
....
.11.
.11.
.11.

....
222.
222.
....
.11.
.11.
.11.

....
....
222.
222.
.11.
.11.
.11.

.222
.222
....
....
.11.
.11.
.11.

....
.222
.222
....
.11.
.11.
.11.

....
....
.222
.222
.11.
.11.
.11.

22..
22..
22..
....
.11.
.11.
.11.

....
22..
22..
22..
.11.
.11.
.11.

.22.
.22.
.22.
....
.11.
.11.
.11.

....
.22.
.22.
.22.
.11.
.11.
.11.

..22
..22
..22
....
.11.
.11.
.11.

....
..22
..22
..22
.11.
.11.
.11.

..11
..11
..11
222.
222.
....
....

..11
..11
..11
....
222.
222.
....

..11
..11
..11
....
....
222.
222.

..11
..11
..11
.222
.222
....
....

..11
..11
..11
....
.222
.222
....

..11
..11
..11
....
....
.222
.222

2211
2211
2211
....
....
....
....

..11
2211
2211
22..
....
....
....

..11
..11
2211
22..
22..
....
....

..11
..11
..11
22..
22..
22..
....

..11
..11
..11
....
22..
22..
22..

..11
..11
..11
.22.
.22.
.22.
....

..11
..11
..11
....
.22.
.22.
.22.

..11
..11
..11
..22
..22
..22
....

..11
..11
..11
....
..22
..22
..22

....
..11
..11
..11
222.
222.
....

....
..11
..11
..11
....
222.
222.

....
..11
..11
..11
.222
.222
....

....
..11
..11
..11
....
.222
.222

22..
2211
2211
..11
....
....
....

....
2211
2211
2211
....
....
....

....
..11
2211
2211
22..
....
....

....
..11
..11
2211
22..
22..
....

....
..11
..11
..11
22..
22..
22..

....
..11
..11
..11
.22.
.22.
.22.

....
..11
..11
..11
..22
..22
..22

222.
222.
..11
..11
..11
....
....

....
....
..11
..11
..11
222.
222.

.222
.222
..11
..11
..11
....
....

....
....
..11
..11
..11
.222
.222

22..
22..
2211
..11
..11
....
....

....
22..
2211
2211
..11
....
....

....
....
2211
2211
2211
....
....

....
....
..11
2211
2211
22..
....

....
....
..11
..11
2211
22..
22..

222.
222.
....
..11
..11
..11
....

....
222.
222.
..11
..11
..11
....

.222
.222
....
..11
..11
..11
....

....
.222
.222
..11
..11
..11
....

22..
22..
22..
..11
..11
..11
....

....
22..
22..
2211
..11
..11
....

....
....
22..
2211
2211
..11
....

....
....
....
2211
2211
2211
....

....
....
....
..11
2211
2211
22..

.22.
.22.
.22.
..11
..11
..11
....

..22
..22
..22
..11
..11
..11
....

222.
222.
....
....
..11
..11
..11

....
222.
222.
....
..11
..11
..11

....
....
222.
222.
..11
..11
..11

.222
.222
....
....
..11
..11
..11

....
.222
.222
....
..11
..11
..11

....
....
.222
.222
..11
..11
..11

22..
22..
22..
....
..11
..11
..11

....
22..
22..
22..
..11
..11
..11

....
....
22..
22..
2211
..11
..11

....
....
....
22..
2211
2211
..11

....
....
....
....
2211
2211
2211

.22.
.22.
.22.
....
..11
..11
..11

....
.22.
.22.
.22.
..11
..11
..11

..22
..22
..22
....
..11
..11
..11

....
..22
..22
..22
..11
..11
..11

Arrangements: 316

---

This can be verified using a Python script gleaned from here:

def genboard(x, y, w, h):
    for dx in range(w):
        for dy in range(h):
            yield x + dx, y + dy

def f(board, bricks, width, height):
    if not bricks:
        return 1
    total = 0
    for w, h in (bricks[0], reversed(bricks[0])):
        for x in range(width - (w-1)):
            for y in range(height - (h-1)):
                p = set(genboard(x, y, w, h))
                if not (board & p):
                    total += f(board | p, bricks[1:], width, height)
    return total

def main():
    board = set()
    bricks = [(2, 3), (2,3)]
    print f(board, bricks, 4, 7)

main()

I have to confess that my C# code to produce the list of arangements is much longer.

Answer 2

A 2nd attempt to enumerate the arrangements, this time in a recursive fashion using C#: (also arrives at 316 arrangements)

using System;

namespace akLegoPlaces
{
    class Program
    {
        static int[,] board = new int[4, 7];   //  columns and rows of our Lego base board
        static int[][] bricks = new int[][] { new int[] { 2, 3 }, new int[] { 2, 3 }};

        static int count = 0;
        static int boardCols = board.GetLength(0);
        static int boardRows = board.GetLength(1);

        static void Main(string[] args)
        {
            placeBricksRecursively(0);

            Console.WriteLine("Arrangements: " + count);
        }

        static bool placeOrRemoveBrick(int[] brick, int brickNo, int left, int top, bool rotate, bool clear)
        {
            bool ret = true;

            for (int phase = 0; ret && (phase <= 1); phase++)
                for (int x = left; ret && (x < left + brick[rotate ? 1 : 0]); x++)
                    for (int y = top; ret && (y < top + brick[rotate ? 0 : 1]); y++)
                        if ((x < boardCols) && (y < boardRows))
                        {
                            if (phase == 0)
                            //  check if point is occupied
                            {
                                ret = (board[x, y] == (clear ? brickNo : 0));
                            }
                            else
                            //  set or clear point
                            {
                                board[x, y] = clear ? 0 : brickNo;
                            }
                        }
                        else
                        {
                            ret = false;
                        }

            return ret;
        }

        static void placeBricksRecursively(int brickNo)
        {
            if (brickNo >= bricks.Length)
            //  end of recursion reached
            {
                ++count;
                show();
                return;
            }

            bool rotate = false; 

            do
            {
                for (int x = 0; x + bricks[brickNo][rotate ? 1 : 0] - 1 < boardCols; x++)
                    for (int y = 0; y + bricks[brickNo][rotate ? 0 : 1] - 1 < boardRows; y++)
                        if (placeOrRemoveBrick(bricks[brickNo], brickNo + 1, x, y, rotate, clear: false))
                        {
                            placeBricksRecursively(brickNo + 1);
                            placeOrRemoveBrick(bricks[brickNo], brickNo + 1, x, y, rotate, clear: true);
                        }
            }
            while (rotate = !rotate);
        }

        static void show()
        {
            string margin = count.ToString().PadLeft(3, ' ') + ":";
            string s;

            for (int y = 0; y < boardRows; y++)
            {
                s = margin;
                for (int x = 0; x < boardCols; x++)
                {
                    s += (board[x, y] == 0) ? "." : board[x, y].ToString();
                }
                Console.WriteLine(s);
                margin = "    ";
            }

            Console.WriteLine("");
        }
    }
}

My code scans the board to find all positions where brick 1 can be placed. This is done in an outer loop to consider rotated as well as non-rotated placements.

Once a position for brick 1 is selected, a nested inner loop (or recursive call) is started to again scan all positions for brick 2.

The board is modelled as 2D array. A brick is "placed" by putting its number (1 or 2) in all covered board positions. A brick can only be placed, if all 2x3 positions are unoccupied (=0).

After every placement, the placement is undone (cleared) before trying the next alternative. Recursion has the advantage, that you can enumerate placements for n bricks quite easily.

Answer 3

In an $n$ by $m$ board, there are $(n-1)(m-2)$ ways to place one brick vertically, and $(n-2)(m-1)$ ways to place one brick horizontally.

If you place the first brick in the middle (with at least $2$ empty rows/column at its sides), it prevents $5*3 + 4*4 = 31$ positions for the other brick.

This gives you $(n-5)(m-6)[(n-1)(m-2)-31]$ ways to place the first brick in the middle and then the second brick anywhere else.

Next, you can investigate the cases where the first brick is close to a border (there are 4 situations to consider) or a corner (there are 4 cases too), in which case this removes slightly less positions for the second brick.

When $n$ and $m$ are larger or equal to $7$, there is no situation where both opposite edges are too close to a brick, so these are enough. Once you add up everything and divide by $2$ you should obtain some polynomial $P(n,m)$ of degree $2$ in $n$ and $m$ (separately). Since this polynomial is symmetric, it takes the form $P(n,m) = a + b.(n+m) + c.(nm) + d.(n+m)nm + e.(n+m)^2 + f.(nm)^2$.

If you don't feel like doing the case analysis, you may compute $6$ values of $P(n,m)$ and use them to recover the values of the coefficients $a,b,c,d,e,f$.

On smaller boards (when one or more of the dimensions are less than $7$), you have to do some more case analysis. In the end you get $25$ particular values for the small values of $n$ and $m$ (when $1 < n,m < 7$), $5$ degree $2$ polynomials $P_k(n)$ for a thin long board of size $k*n$ or $n*k$ with $1 < k < 7 \le n$, and the polynomial $P(n,m)$ for when $n,m \ge 7$.

---

If you have a fixed finite set of bricks, there still exists some polynomial giving the correct answer for large enough values of $n,m$, though it quickly gets difficult to compute.

But I don't think there is a formula that allows you to change the set of bricks.

Answer 4

A general approach to this type of problem is the inclusion-exclusion principle. The idea is to count all the possible configurations of the bricks (ignoring overlaps), then subtract configurations where a single pair of bricks overlap (ignoring overlaps with the rest of the bricks), then add back in configurations that have multiple overlaps (since they were removed multiple times), and so on. This effectively reduces the problem of counting full configurations to the problem of enumerating clusters, and allows you to write the number of configurations as a polynomial in the dimensions of the board.

Let $K_{m,n}(M,N)$ be the number of ways to place an $m \times n$ brick or cluster of bricks with $180^\circ$ rotational symmetry on an $M \times N$ board (taking $m\le n$ and $M\le N$ with no loss of generality). If $n \le M$, this is given by $$K_{m,n}(M,N)=(M-m+1)(N-n+1)+(M-n+1)(N-m+1) \\ =2MN-(M+N)(m+n-2)+2(m-1)(n-1).$$ If the object only fits lengthwise (because $m \le M < n \le N$), then $$K_{m,n}(M,N)=(M-m+1)(N-n+1);$$ and obviously $K_{m,n}(M,N)=0$ if the object doesn't fit at all. An object with no rotational symmetry can be placed in twice this many ways, and one with $90^\circ$ rotational symmetry can be placed in half this many distinct ways.

The number of ways to place two distinguishable $2\times 3$ bricks without worrying about overlaps is just $\left(K_{2,3}(M,N)\right)^2$. You then need to subtract the overlap configurations. To do this, enumerate the different (up to rotational symmetry) ways to place one brick so that it overlaps another, keeping track of the size and symmetry of each such "cluster". You can do this by hand. It turns out that there is one symmetric $2\times 3$ cluster (bricks right on top of each other); non-symmetric clusters with parallel bricks of size $3\times 3$, $3\times 4$ (two of them), $3\times 5$ (two of them), $2\times 5$, and $2\times 4$; and non-symmetric clusters with perpendicular bricks of size $3\times 3$ (two of them), $3\times 4$ (four of them), and $4\times 4$ (two of them). The number of overlap configurations is therefore $$ K_{2,3}+2\cdot\left(3K_{3,3}+6K_{3,4}+2K_{3,5}+K_{2,5}+K_{2,4}+2K_{4,4}\right). $$ Now, if we fix the size of the board to be $4\times 7$, and calculate $$ \begin{eqnarray} K_{2,3}(4,7) &=& 27 \\ K_{3,3}(4,7) &=& 20 \\ K_{2,4}(4,7) &=& 18 \\ K_{3,4}(4,7) &=& 13 \\ K_{4,4}(4,7) &=& 8 \\ K_{2,5}(4,7) &=& 9 \\ K_{3,5}(4,7) &=& 6, \\ \end{eqnarray} $$ we find the total number of legal configurations to be $$ 27^2 - 27-2\cdot\left(3\cdot 20 + 6\cdot 13 + 2\cdot 6 + 9 + 18 + 2\cdot 8\right) = 316, $$ as calculated in other answers.