Counting tilings of regions is a related problem with Domino tiling (https://en.wikipedia.org/wiki/Domino_tiling ). This article will bring a general algorithm that can deal with all shaped regions.
- Counting tilings of regions
In short, in geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominos, shapes formed by the union of two unit squares meeting edge-to-edge.
The number of tilings of a region is very sensitive to boundary conditions and can change dramatically with apparently insignificant changes in the shape of the region. Actually, for abnormal shapes, such a shape with a hole, the counting is very hard to be solved.
Although there are some smart algorithms to solve special shapes, to my best of knowledge, there is no efficient algorithm to deal with a general shape.
2. State-based dynamic programming
If we use a brute force method to solve this kind of problem, the combinations will grow exponentially.
We will use State-based dynamic programming. Here a shape with tiling information is called a state. Original shape and fully tiled shape are all a state.
For any state, regarding the top left untiled cell, there are only 2 options:
Option Right: to use a 1x2 to tile it and its right side cell.
Option Down: to use a 2x1 domino shape to tile it and its downside cell.
If due to some reason, both option right side and option downside can not be used. The state can not generate a valid tiling plan.
In a fake formula,
count(current_state)= count(new_state_if_go_right)+ count(new_state_if_go_down) (if there are untiled cells)
or 1 (if all cells have been tiled)
Regarding a 2x3 grid, if we use an integer to indicate a cell, for example, the top left cell is 0 and bottom right is 6–1=5, and we treat the state as a number in the range of [0, 2⁶ -1] then
The initial state is 0 and the fully tiled state is 2⁶-1.
count(0)=count(2⁰+2¹)+count(2⁰+2⁴)
In other words:
count(0)=count(3)+count(17).
count(2⁶-1)=1
Sounds interesting?
3. The performance
Without optimization, on an old laptop the performance is as the following:
This is the Aztec diamond tiling( https://en.wikipedia.org/wiki/Aztec_diamond )
Duration(ms):728
Total counting tilings:1024
Total checked states:8425
This is 4x7 grid
Duration(ms):221
Total counting tilings:781
Total checked states:3921
This is 5x5 grid
Duration(ms):66
Total counting tilings:0
Total checked states:1189
This is 6x6 grid
Duration(ms):1877
Total counting tilings:6728
Total checked states:33094
4. Further improvement by memorization
Of course, we may use memorization to improve efficiency. For a state, definitely the counting number is fixed. We don’t need to calculate it again and again.
And due to the shape can be mirrored, flipped, actually, the memorization can be improved greatly.
5. More generalization on the shape of a domino (beyond 1x2 rectangle)
This algorithm supports all kinds of a shaped region. But so far, the shape of a domino is fixed as a 1x2 rectangle. It’s not too difficult to support all kinds of domino shape.
6. The source code
The source code has been published at Github (https://github.com/MRYingLEE/Algo_Cpp/blob/master/BetterSolutions/titling.cpp )
You may use it at your will. Of course, you are appreciated to credit me.