algorithm - 俄罗斯方 block 的 n 个 block 的不同有效 block

Question

这是我 friend 昨天问我的问题，我相信这是他看到的一个面试问题。规则很简单，对于 n=4，有 5 个不同的部分:

ooo
 o

  o
ooo

oo
oo

oooo

oo
 oo

对于给定的n，您需要计算不同部分的数量。

不同意味着这四个是相同的:

ooo   o  o   o
  o ooo  o   o
         oo oo 

我没能解决这个问题，因为当n > 4时，问题变得更加复杂，我什至不知道它属于哪类问题。它看起来像一个DFS，但你可以同时选择多个方向。删除重复项也很重要。

Answer 1

以下是来自 wiki 的解决方案

Each polyomino of order n+1 can be obtained by adding a square to a polyomino of order n. This leads to algorithms for generating polyominoes inductively.

Most simply, given a list of polyominoes of order n, squares may be added next to each polyomino in each possible position, and the resulting polyomino of order n+1 added to the list if not a duplicate of one already found; refinements in ordering the enumeration and marking adjacent squares that should not be considered reduce the number of cases that need to be checked for duplicates.[9] This method may be used to enumerate either free or fixed polyominoes.

A more sophisticated method, described by Redelmeier, has been used by many authors as a way of not only counting polyominoes (without requiring that all polyominoes of order n be stored in order to enumerate those of order n+1), but also proving upper bounds on their number. The basic idea is that we begin with a single square, and from there, recursively add squares. Depending on the details, it may count each n-omino n times, once from starting from each of its n squares, or may be arranged to count each once only.

The simplest implementation involves adding one square at a time. Beginning with an initial square, number the adjacent squares, clockwise from the top, 1, 2, 3, and 4. Now pick a number between 1 and 4, and add a square at that location. Number the unnumbered adjacent squares, starting with 5. Then, pick a number larger than the previously picked number, and add that square. Continue picking a number larger than the number of the current square, adding that square, and then numbering the new adjacent squares. When n squares have been created, an n-omino has been created.

This method ensures that each fixed polyomino is counted exactly n times, once for each starting square. It can be optimized so that it counts each polyomino only once, rather than n times. Starting with the initial square, declare it to be the lower-left square of the polyomino. Simply do not number any square that is on a lower row, or left of the square on the same row. This is the version described by Redelmeier.

If one wishes to count free polyominoes instead, then one may check for symmetries after creating each n-omino. However, it is faster[10] to generate symmetric polyominoes separately (by a variation of this method)[11] and so determine the number of free polyominoes by Burnside's lemma.

The most modern algorithm for enumerating the fixed polyominoes was discovered by Iwan Jensen.[12] An improvement on Andrew Conway's method,[13] it is exponentially faster than the previous methods (however, its running time is still exponential in n).

Both Conway's and Jensen's versions of the transfer-matrix method involve counting the number of polyominoes that have a certain width. Computing the number for all widths gives the total number of polyominoes. The basic idea behind the method is that possible beginning rows are considered, and then to determine the minimum number of squares needed to complete the polyomino of the given width. Combined with the use of generating functions, this technique is able to count many polyominoes at once, thus enabling it to run many times faster than methods that have to generate every polyomino.

Although it has excellent running time, the tradeoff is that this algorithm uses exponential amounts of memory (many gigabytes of memory are needed for n above 50), is much harder to program than the other methods, and can't currently be used to count free polyominoes.

对我来说，这已经足够了。不过，我真正想计算的是免费多联骨牌的数量，但似乎没有简单的解决方案。如果我在面试中被问到这个问题，我只会给出上面提到的算法来计算固定多联骨牌的数量，然后删除重复的多联骨牌来计算自由多联骨牌。