为 Double-Choco 益智游戏生成可解决的谜题。高效的数据结构和算法可以用在什么地方？

Question

我正在努力实施一款名为 Double-Choco 的益智棋盘游戏，由 Nikoli 杂志发布

其中棋盘是一个二维矩阵，其单元格为白色或灰色。目标是通过在虚线上绘制实线将网格划分为块。每个块必须包含一对具有相同形式（大小和形状）的白色单元格和灰色单元格区域，一个区域可以旋转或相对区域的镜像，一个区域可以有一个数字表示该颜色的单元格数量在街区里。

我正在寻求有关选择数据结构和形成算法以自动为该游戏生成可解谜题的帮助。

我正在使用 JavaScript 实现，这是我目前正在考虑的方法：

• 从具有所需大小的空白二维矩阵开始。
• 为白色区域选择一个随机区域大小，在 2 到棋盘大小的一半之间（四舍五入到最接近的偶数），其中形成该区域的单元格可用且未被占用
• 检查是否可以在具有相同形状和大小的板上获取匹配的相对区域。
• 如果没有：检查是否有旋转或镜像区域的空间。
• 如果不是：返回步骤2
• 如果是：重新检查整个板子是否有违规（主要是如果有一个被包围的奇数块离开
• 若有违规：回到步骤2
• 将（2 个区域的）方块的单元格标记为已占用
• 转到第2步直到棋盘被填满

至于数据结构，我想到了使用图形，但我无法将其包裹在脑海中。也许像 2-dim 矩阵一样处理区域？

我不确定这种方法是否最优，或者是否有更好的数据结构和算法可供使用。你会推荐什么数据结构和算法来为这个棋盘游戏生成可解决的谜题？任何帮助或建议将不胜感激。

Answer 1

我想去：

• cell

  s 的 

  2 d XxY 数组：

      let cell = {
          x: Number, // just for passing them down easier, I assign coords too
          y: Number,
          color: "white" | "black",
          number: null | Number,
          top: true | false,
          bottom: true | false,
          left: true | false,
          right: true | false,
          taken: false, // | true
          block: []
      }
  

• 运行并提取每个块（其坐标在数组中）

  function take(cell, cellFor) {
      cell.taken = true
      if (!cell.top)    take(cells[cell.y-1][cell.x], cellFor)
      if (!cell.bottom) take(cells[cell.y+1][cell.x], cellFor)
      if (!cell.left)   take(cells[cell.y][cell.x - 1], cellFor)
      if (!cell.right)  take(cells[cell.y][cell.x + 1], cellFor)
  }
  
  for (let row of cells)
      for (let cell of row)
          if (!cell.taken) take(cell, cell)
  

我能想到的最短代码。 假设你有 2x2 和

[(0,0),(1,0)]

作为块。

• take(cell[0][0])

  ：
  • 带

    (1,0)

    到

    (0,0)

    的街区，因为它的

    .right

    是

    false

  • 不要添加

    (1,0)

    因为它的

    .bottom

    是

    true

• 不要

  take(cell[0][1])

  因为当

  (0,0)

  运行时，它需要

  (0,1)

  作为它的块

• take(cell[0][1])

  ...

我想你看到了模式。老实说会有bug，我没试过。它只是一个概念。还需要对数组长度检查和其他无聊的东西进行微调。

cellFor

参数用于引用启动

take

序列的单元格。

您必须将其“解析”为

cells.flat().filter(bock=>block.length)

.

注意我没有使用

.number

和

.color

。一旦你有了积木，你就可以用你的积木里的细胞来检查它。
这种

take

风格用于创建块。我基本上给出了一个极简的方法来提取块。
花了一些时间，但如果我的算法有缺陷，我深表歉意。