tiling a 2xn checkerboard with square tetrominoes and dominoes
Jonathan Post
jvospost3 at gmail.com
Sun Feb 18 03:20:53 CET 2007
UVa 10918
From Algorithmist
http://www.algorithmist.com/index.php/UVa_10918
Table of contents
1 10918 - Tri Tiling
2 Summary
3 Explanation
4 Input
5 Output
10918 - Tri Tiling
Tri Tiling (http://acm.uva.es/p/v109/10918.html)
Summary
Determine in how many ways can a 3xN rectangle be completely tiled
with 2x1 dominoes.
Explanation
It's a typical problem on dynamic programming. One possible solution
is described below.
Let f(n) be the number of tilings of a 3xN rectangle (which is what
we're looking for) and let g(n) denote the number of tilings of a 3xN
rectangle with one of its corner squares removed.
These functions satisfy the recurrent relations: f(n) = f(n - 2) +
2g(n - 1),g(n) = f(n - 1) + g(n - 2). The formulas can be illustrated
as follows:
******** AA******* AA****** A*******
******** = BB******* + B******* + A*******
******** CC******* B******* BB******
f(n) = f(n-2) + g(n-1) + g(n-1)
******** A******** AA*******
******** = A******** + BB*******
******* ******** CC******
g(n) = f(n-1) + g(n-2)
The boundary values for the relations are: f(0) = 1,f(1) = 0,g(0) = 0,g(1) = 1.
For any odd value of N, the number of tilings of a 3xN rectangle is 0.
[edit]
Input
0
1
2
8
12
30
-1
[edit]
Output
1
0
3
153
2131
299303201
More information about the SeqFan
mailing list