将 n×n 板切割成 n 个连接的 n-minos 的最快实现

Question

我正在尝试创建一个谜题，让玩家使用 n 个连接的 n-minos 拼凑出一个 n×n 的网格（定义：n 个 1×1 块的连接块，例如，每个俄罗斯方块都是 4-米诺）。然而，尽管对人类来说似乎很容易，但事实证明，首先要生成一种切割网格的方法是一项挑战。

示例板

对于人类来说，通过递归遵循以下 logic/pseudo-code:

来生成这样的解决方案是一项相对容易的任务

:start_of_recursion:

从一个随机的 "least connected" 块开始（连接到它的成员最少的端、角、边缘块）作为起始 mino 块

:start_of_recursion:
- 从当前米诺的随机棋子中随机可用的方向制作"grow"
  - 如果"grow"导致剩余棋盘"separated"（如果分离区域不是n的倍数），尝试其他位置和方向
    - 如果已经尝试了所有位置和方向，则恢复到以前的电路板配置（真的不应该发生吗？）
- 如果已经达到size-n，退出递归
:end_of_recursion:
如果棋盘已经填满，退出递归

:end_of_recursion:

执行此例程似乎生成了一种 O(n^2) 的解决方案生成方法，但事实证明，条件检查对于计算机而言确实非常昂贵。为了确定板是否已连接，人类只需检查剩余区域内的任何 "gap"，并以几乎 O(1) 的方式处理一个简单的非重叠图，而我的代码实现需要到 "spread" 从图上的一个点到它的邻近区域，并在传播完成后检查是否有任何点位于可及范围之外（最多 O(n)）。由于在最内层迭代中每次都要执行此检查，因此它将复杂性退化为 O(n^(3+)) 问题并且变得非常低效。

有没有一种方法可以用类似于人类认知的方式来检查"gap"？还是可以从根本上思考问题，简化成计算机更容易解决的问题？

Answer 1

您的问题听起来像是 bin packing problem. I would approach this by constraint satisfaction method. Below I'll use Minizinc 伪代码的变体。

一个棋盘由单元格组成，每个单元格可以从几个单元格中着色成一种颜色。我们可以这样表示：

int: rows;
int: cols;
int: colors_num;

array [1...colors_num] of int: colors;
array [1..rows,1..cols] of var colors: board;

接下来，我们添加约束。例如，如果一个单元格的颜色为 A，则至少 1 个相邻的单元格必须具有相同的颜色 A：

constraint forall (c in colors) (
  if board[i, j] == c then
    at_least (1, [board[i-1, j], board[i+1, j], board[i, j-1], board[i,j+1]], c)
  else
    true
  endif

您可以将所有 allowed/prohibited 形状描述为约束，或使用其他一些引入可能切割的智能方法。

约束满足度应该比您的递归方法多更有效。但是，它的可扩展性不是很好 - 如果您尝试为一个巨大的棋盘（成百上千个 cells/colors）生成游戏，生成 minos 将需要相当长的时间和内存。

将 n×n 板切割成 n 个连接的 n-minos 的最快实现

fastest implementation to cut n×n board into n connected n-minos

complexity-theory

graph-theory