用俄罗斯方块方块填满整个2D数组（俄罗斯方块棋盘），不留空格（Java）

Question

假设我有一个二维整数数组...

int[][] board = new int[10][20];

public void initBoard()
{
    for(int r = 0; r < 10; r++)
        for(int c = 0; c < 20; c++)
            board[r][c] = 0;
}

0代表无形状方块，方块编号为1-7：

1 - Z 形

2 - S 形

3 - 直线形

4 - T 形

5 - 方块形

6 - L 形

7 - 反 L 形

如何用随机的形状填满整个数组并不留空格。

注意：我已经让游戏运行起来了，现在想做一些不同的改变，但仍然使用俄罗斯方块的玩法。

- Nick Marinelli

---

定义“最佳”。使用最少的块？这可能主要包括使用大多数/仅有最多块的形状。有很多很多选项，只需尝试每次填充2-3行，就足够容易了。 - Bernhard Barker

最好是指最容易/最有效的。没有块数量要求。我宁愿每次使用相等数量（尽可能多）的每个块。 - Nick Marinelli

最简单的方法就是用方框形状或线条形状填充它，不是吗？ - Sam Holder

Answer 1

这实际上是一个非常复杂的问题。在计算机科学中，它被称为装箱问题，根据你想要完成的确切任务性质，有很多可能的算法和方法。

通常情况下，这个问题很难，非常难，事实上，找到最优解是NP难的。想了解更多信息，请查看来自MIT的Demaine等人的研究论文。

- JohnnyO

---

是啊，我已经搜寻了几个小时并且自己进行测试，但结果很少。我可能会创建一些预定义的数组来使用。 - Nick Marinelli

为了了解你想做的事情是否可行，你需要更具体地说明你试图实现的目标。 - JohnnyO

Answer 2

这并不像看起来那么容易。实际上，它是一个NP难问题。矩形装箱问题类似, 你可以从那个稍微简单一点的问题开始。

- Adam Stelmaszczyk

---

计算机科学领域的事情似乎从来都不像看起来那么简单，哈哈。是啊，我可能会只是创建一堆预定义的数组。 - Nick Marinelli

是的，你可以尝试“工程师的方法”；）预定义或随机抛掷方块...或者两者都可以-从几个块中制作小矩形，然后将它们随机放置在由矩形制成的网格的每个单元格中。 - Adam Stelmaszczyk

我...没有想到那个。那是一个好主意。 - Nick Marinelli