Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

enter image description here

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.

share|improve this question
    
Are your bricks of the same color? Or should they be treated as distinct? –  Axel Kemper Oct 7 '13 at 21:01
    
@AxelKemper The bricks are the same color. But different colors wouldn't matter anyway. –  pine trees are cool Oct 8 '13 at 7:23
    
Different colors would increase the number of arrangements. I doubt that there is an analytical method to compute the number for the general case. For brick 1 alone, there are 27 possible locations which differ in horizontal/vertical coordinate and/or orientation. Brick 2 is more difficult to enumerate, as some locations are fully/partially blocked by brick 1. –  Axel Kemper Oct 8 '13 at 8:36
    
So this problem "can't" be solved? –  pine trees are cool Oct 8 '13 at 14:25
    
One should never say never ... It is possible to write a program which enumerates all arrangements. This would be a depth-first/breadth-first backtracking algorithm. A clean "scientific" formula is at least not known to me. –  Axel Kemper Oct 8 '13 at 14:45

4 Answers 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.

share|improve this answer
    
Wow, this is though for me. Plus, i'm not english so it will take another two or three readings before i'll understand it. But thank you for your input; i really appreciate that. –  pine trees are cool Oct 10 '13 at 19:25

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.

share|improve this answer
    
Thank you for the answer, i re-did the calculations and i also came up with 316. I'd like to create a simple script to find all the arrangements and i suppose you also used one: can you input me to te right direction? I think i'll use bidimensional arrays and maybe recursion. Again, thank you for tour help and patience. –  pine trees are cool Oct 9 '13 at 8:30
    
Yes, I have used a C# program with recursion and two-dimensional arrays. Answers are limited to 30,000 characters, but I can post a Google Drive link to let you have the code. –  Axel Kemper Oct 9 '13 at 8:59
    
That would be MUCH appreciated. –  pine trees are cool Oct 9 '13 at 17:10
    
I have included very compact Python enumeration procedure and the link to my (iterative and far less compact) C# code in the answer. –  Axel Kemper Oct 9 '13 at 21:41

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.

share|improve this answer
    
Thank you for your input. I shared this problem with a friend and we came up with a similar analysis, not as deep as yours tho, we're only high school students and that's a bit advanced for us. Still, thank you for helping us! –  pine trees are cool Oct 10 '13 at 18:31

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.

share|improve this answer
    
I really want to thank you for your dedication, i really appreciate that. However, i'm a beginner programmer and i couldn't understand the whole code, nor the Python one (i know a bit of C# and a bit of Python but i never went too deep), so i'm asking you to write it in pseudo-code so i can completely understand it and perhaps rewrite it (maybe in c or in a simpler c#). –  pine trees are cool Oct 10 '13 at 18:20
    
Please have a look at the comments I've added in my answer. For a start, I would recommend to run through my iterative C# implementation using the free Microsoft Visual Studio 2012 C# debugger. –  Axel Kemper Oct 10 '13 at 19:14
    
Okay, so let's say i place brick1 at 0,0 in the board and then i move around brick2 and i get 15 arrangements (i hope that's the right number, ha!). Then i have to move brick1 in 0,1 (or any other location) and do the same thing again. How to keep trace of the places brick1 has already been? I mean, how to choose where to put the bricks? Scanning the entire board? That's (i think) the point i can't get right. –  pine trees are cool Oct 10 '13 at 19:31
    
You don't have to keep a trace. The current position of brick 1 is marked by writing 1 to all ocupied grid positions. Then brick 2 can be placed (and marked with '2') on positions which are all clear (=0). For every placement the complete board is scanned from left to right and top to bottom for "placable" positions. –  Axel Kemper Oct 10 '13 at 19:50
    
But if you clear the board everytime you find an arrangement, shouldn't the program keep counting the same arrangement infinite times? Or it's just me talking nonsense? –  pine trees are cool Oct 10 '13 at 20:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.