如何计算 随机数量的正方形可以拼成多边形的数量？

Question

大家玩过 俄罗斯方块吧,里面所有的图形都是由四个正方形组成的，我想做一个程序来算出并画出n个相同的正方形可以画出的多边形的数量，旋转后一样的算一个，大神有什么好的算法？
谢谢！

Answer 1

我没有想到什么太好的方法，不过递推和暴力剪枝可以试一下。
我的思路是这样的：
首先确定这个是可以通过递推做的，因为n=4组成的所有的多边形可以由n=3组成的所有多边形的基础上再添加一个正方形推出来的。
所以，我们可以从n=1的时候出发。
1.n=1，就只有一种多边形，毫无问题。
2.n=2，从n=1的基础上再添加一个正方形，我们可以放置的位置为 上下左右 4个方向，各自加入1个正方形，这样获得了4个新的多边形，然后进行旋转去重，去掉重复的，这样就得到了n=2的答案。
3.n=3，从n=2的基础上再添加一个正方形，对每一个可以防止新的正方形的位置尝试放置正方形，这样总共可以获得6个新的多边形，然后再进行旋转去重，就可以得到n=3的答案。
4.。。类推。

思路图是这样的，程序可以实现，不过挺麻烦的