ruby - 将网格拆分成随机大小的矩形

Question

我有一个 500 x 400 像素的正方形，里面有一个 100 像素的网格。现在我想用捕捉到网格的较小随机大小的正方形填充那个正方形。这意味着较小的正方形的大小可以是 100、200、300 或 400 像素。它们的大小和位置需要是随机的，因此每次运行时输出看起来都会不同。

此图像显示了大正方形、它的网格以及我尝试创建的带有较小正方形的可能输出。

我在 Ruby/Sinatra 中使用 DIV 生成这个，但我想这个问题对于要使用的实际算法更为普遍。

关于如何用最少的代码做到这一点有什么建议吗？

Answer 1

这种方法需要很多代码，但我想我会做的是使用 Donald Knuth 的 Dancing Links 算法 (DLX)(或其他一些算法)来找到所有 em> 正方形的可能排列。您可以提前计算出这些安排，然后您可以在需要时快速/随机选择一个。

您可以在此处阅读他关于该算法及其在五联骨牌(与您的问题非常相似)中的应用的论文:

http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz

http://en.wikipedia.org/wiki/Dancing_Links