In my code I'll define a recursive function y
. The function y
takes a list of 2D-coordinates and returns the number of different domino tilings using these coordinates. E.g. y([[0,0], [0,1]]) = 1
(one horizontal domino), y([[0,0], [1,1]]) = 0
(coordinates are not adjacent) and y([[0,0], [0,1], [1,0], [1,1]]) = 2
(either two horizontal or two vertical dominoes). After defining the function I'll call it with all coordinates [x,y]
with x in [0, 1, m-1], y in [0, 1, n-1]
.
How does the recursive function work? It's quite simple. If the list of coords is empty, there is exactly one valid tiling and y
returns 1
.
Otherwise I take the first coordinate in the list b[0]
, and search the remaining coordinates for a neighbors. If there is no neighbor to b[0]
, then there is no tiling possible, therefore I return 0. If there is one or more neighbors, then the number of tilings is (the number of tilings where I connect b[0]
with the first neighbor via a domina, plus the number of tilings where I connect b[0]
with the second neighbor, plus ...) So I call the function recursively for each neighbor with the shortened list (by removing the two coords b[0]
and neighbor). Afterwards I sum up all results and return them.
Because of the order of the coords there are always only two neighbors possible, the one on the right side and the one below. But my algorithm doesn't care about that.