[SOLVED] 题目求助｜一天一烧脑日历拼图解法
Zou Zhipeng
9320
2021.06.11
2021.06.17
发布于 未知归属地
BFS剪枝题目求助日历 FloodFill技术交流

简介

O1CN01twIfzA1hUkExhUq9V_!!143314281.jpg

全家福
IMG_5339.JPG

没错, 就是这个破玩意. 杀死了无数脑细胞.

前两行是月份, 每行 6 个. 后 5 行是 1-31, 共 31 个数字.

然后给了 8 个积木, 全部拼进去以后正好可以剩下两个空位, 一个月份一个日期, 可以拼出 1 月 1 日到 12 月 31 日的每一天. 比如今天 (6 月 11 日), 就是这个样子. (比较顺利, 也拼了个把小时)

IMG_5336.JPG

现在想要通过算法来把这个拼图解出来.

思路

将拼图抽象为一个数组, 0 表示未填,1 表示已填, 如 6 月 11 日就可以表示为:

board = [
  0, 0, 0, 0, 0, 1, 1
  0, 0, 0, 0, 0, 0, 1
  0, 0, 0, 0, 0, 0, 0
  0, 0, 1, 0, 0, 0, 0
  0, 0, 0, 0, 0, 0, 0
  0, 0, 0, 0, 0, 0, 0
  0, 0, 0, 1, 1, 1, 1
];

8 种积木, 可以抽象出 47 种不同的形状, 我给做了简单的命名

rec // 长方形的
No.1
1, 1, 1
1, 1, 1
No.2
1, 1
1, 1
1, 1

ao // 长得像凹的
No.1
1, 0, 1
1, 1, 1
No.2
1, 1
1, 0
1, 1
No.3
1, 1, 1
1, 0, 1
No.4
1, 1
0, 1
1, 1

long_l // 长 L 形
No.1
1, 0
1, 0
1, 0
1, 1
No.2
1, 1
1, 0
1, 0
1, 0
No.3
0, 1
0, 1
0, 1
1, 1
No.4
1, 1
0, 1
0, 1
0, 1
No.5
1, 1, 1, 1
1, 0, 0, 0
No.6
1, 1, 1, 1
0, 0, 0, 1
No.7
1, 0, 0, 0
1, 1, 1, 1
No.8
0, 0, 0, 1
1, 1, 1, 1

short_l // 短 L 形, 对称的
No.1
1, 0, 0
1, 0, 0
1, 1, 1
No.2
1, 1, 1
1, 0, 0
1, 0, 0
No.3
1, 1, 1
0, 0, 1
0, 0, 1
No.4
0, 0, 1
0, 0, 1
1, 1, 1


less_rec // 缺了一个角的长方形
No.1
1, 1, 1
1, 1, 0
No.2
1, 1, 1
0, 1, 1
No.3
1, 1, 0
1, 1, 1
No.4
0, 1, 1
1, 1, 1
No.5
1, 0
1, 1
1, 1
No.6
0, 1
1, 1
1, 1
No.7
1, 1
1, 1
1, 0
No.8
1, 1
1, 1
0, 1

t // T 形, 虽然不太对称
No.1
1, 1, 1, 1
0, 1, 0, 0
No.2
1, 1, 1, 1
0, 0, 1, 0
No.3
0, 0, 1, 0
1, 1, 1, 1
No.4
0, 1, 0, 0
1, 1, 1, 1
No.5
1, 0
1, 1
1, 0
1, 0
No.6
1, 0
1, 0
1, 1
1, 0
No.7
0, 1
1, 1
0, 1
0, 1
No.8
0, 1
0, 1
1, 1
0, 1

long_flash // 长的闪电
No.1
0, 1, 1, 1
1, 1, 0, 0
No.2
1, 1, 1, 0
0, 0, 1, 1
No.3
0, 0, 1, 1
1, 1, 1, 0
No.4
1, 1, 0, 0
0, 1, 1, 1
No.5
0, 1
1, 1
1, 0
1, 0
No.6
1, 0
1, 1
0, 1
0, 1
No.7
0, 1
0, 1
1, 1
1, 0
No.8
1, 0
1, 0
1, 1
0, 1

short_flash // 短的闪电, 旋转对称的
No.1
1, 0, 0
1, 1, 1
0, 0, 1
No.2
0, 0, 1
1, 1, 1
1, 0, 0
No.3
1, 1, 0
0, 1, 0
0, 1, 1
No.4
0, 1, 1
0, 1, 0
1, 1, 0

现在要做的就是将这些抽象出来的方块依次放入抽象出来的 board.

实践

将以上 47 种方块依次放入 board, [0,0] 到 [6,6] (每一块都至少两行或两列, 可以少计算最后一行和最后一列), 判断是否超出 board, 或者覆盖了原来值为 1 的位置, 同时参考 FloodFill 问题, 判断是否有孤岛, 且孤岛面积小于 5 (积木的最小面积就是 5), 这些情况都可以忽略.

这里就已经产生了 586 种可能.

考虑 BFS 算法, 将这 586 中可能加入到一个队列中.

从队列中依次取出一种可能, 重复初始化的过程, 剪枝掉不可能的情况. (添加一种剪枝, 即积木名字已使用, 所以每个队列元素都要记录已使用的积木名字)

可放入的话, 更新 board, 记录已使用的积木名字, 并加入到队列中.

已使用的积木名字数为 8, 即找到一种可能.

问题

时间复杂度和空间复杂度都爆炸, 实际上, 我 8G 的电脑, 内存全部给到, 都跑不完.

求助

欢迎提供思路和代码, 感激不尽.

已解决, 6 月 17 日更新

还是想得太多了, 让我们还原一下游戏玩法.

拿到这个游戏, 我们是怎么进行的?

  1. step1, 从 8 块积木中任选一块, 放入到棋盘中合法的位置 (不能出界; 不能覆盖当前月份和日期; 「优化」每块积木至少占据 5 个格子, 所以不能有面积小于 5 的孤岛);
  2. step2, 从剩下 7 块积木中任选一块, 放入到棋盘中合法的位置 (不能出界; 不能覆盖当前月份和日期; 「优化」每块积木至少占据 5 个格子, 所以不能有面积小于 5 的孤岛; 也不能和第一块积木有重合);
  3. 重复 step2, 直至所有积木都摆放到棋盘中, 得到一个可行解; 或者有积木无法放置, 从棋盘中拿出上一步摆放的积木, 放置到不同的位置, 以此类推.

以上步骤想到了什么? 这不就是典型的 DFS 加剪枝 (回溯) 的过程么?

进一步, 能用 DFS 处理的问题肯定可以改为使用 BFS 处理.

假设有数量无限的棋盘和积木, 将 step1 扩展开来, 比如说先放矩形的积木, 一共有 36 种合法位置, 这样生成了 36 个不同的棋盘;

在这 36 个棋盘的基础上, 每个棋盘执行 step2, 可扩展出上千个不同的棋盘;

以此类推, 直至找到一个可行解.

相当于开了天眼, 这样类似水波纹一层一层的扩展开来, 是典型的 BFS 模式.

抽象出棋盘

用数字 0 表示当前格子可以放入积木, 1 表示当前格子已被占, 不可以放入积木.

// 7*7 的方格
$board = array_fill(0, 7, array_fill(0, 7, 0));
// 几个特殊位置特殊处理
$board[0][6] = $board[1][6] = $board[6][3] = $board[6][4] = $board[6][5] = $board[6][6] = 1;

// 以 6 月 16 日为例
$board[0][5] = $board[4][1] = 1;

当前 board 结果为:

0, 0, 0, 0, 0, 1, 1
0, 0, 0, 0, 0, 0, 1
0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0
0, 1, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0
0, 0, 0, 1, 1, 1, 1

抽象出积木

$rec = [
  [[1, 1, 1], [1, 1, 1]],
  [[1, 1], [1, 1], [1, 1]],
];
$ao = [
  [[1, 0, 1], [1, 1, 1]],
  [[1, 1, 1], [1, 0, 1]],
  [[1, 1], [1, 0], [1, 1]],
  [[1, 1], [0, 1], [1, 1]],
];
$long_l = [
  [[1, 0], [1, 0], [1, 0], [1, 1]],
  [[1, 1], [1, 0], [1, 0], [1, 0]],
  [[0, 1], [0, 1], [0, 1], [1, 1]],
  [[1, 1], [0, 1], [0, 1], [0, 1]],
  [[1, 1, 1, 1], [1, 0, 0, 0]],
  [[1, 1, 1, 1], [0, 0, 0, 1]],
  [[1, 0, 0, 0], [1, 1, 1, 1]],
  [[0, 0, 0, 1], [1, 1, 1, 1]],
];
$short_l = [
  [[1, 0, 0], [1, 0, 0], [1, 1, 1]],
  [[1, 1, 1], [1, 0, 0], [1, 0, 0]],
  [[1, 1, 1], [0, 0, 1], [0, 0, 1]],
  [[0, 0, 1], [0, 0, 1], [1, 1, 1]],
];
$less_rec = [
  [[1, 1, 1], [1, 1, 0]],
  [[1, 1, 1], [0, 1, 1]],
  [[1, 1, 0], [1, 1, 1]],
  [[0, 1, 1], [1, 1, 1]],
  [[1, 0], [1, 1], [1, 1]],
  [[0, 1], [1, 1], [1, 1]],
  [[1, 1], [1, 1], [1, 0]],
  [[1, 1], [1, 1], [0, 1]],
];
$t = [
  [[1, 1, 1, 1], [0, 1, 0, 0]],
  [[1, 1, 1, 1], [0, 0, 1, 0]],
  [[0, 0, 1, 0], [1, 1, 1, 1]],
  [[0, 1, 0, 0], [1, 1, 1, 1]],
  [[1, 0], [1, 1], [1, 0], [1, 0]],
  [[1, 0], [1, 0], [1, 1], [1, 0]],
  [[0, 1], [1, 1], [0, 1], [0, 1]],
  [[0, 1], [0, 1], [1, 1], [0, 1]],
];
$long_flash = [
  [[0, 1, 1, 1], [1, 1, 0, 0]],
  [[1, 1, 1, 0], [0, 0, 1, 1]],
  [[0, 0, 1, 1], [1, 1, 1, 0]],
  [[1, 1, 0, 0], [0, 1, 1, 1]],
  [[0, 1], [1, 1], [1, 0], [1, 0]],
  [[1, 0], [1, 1], [0, 1], [0, 1]],
  [[0, 1], [0, 1], [1, 1], [1, 0]],
  [[1, 0], [1, 0], [1, 1], [0, 1]],
];
$short_flash = [
  [[1, 0, 0], [1, 1, 1], [0, 0, 1]],
  [[0, 0, 1], [1, 1, 1], [1, 0, 0]],
  [[1, 1, 0], [0, 1, 0], [0, 1, 1]],
  [[0, 1, 1], [0, 1, 0], [1, 1, 0]],
];
$allShapes = compact('rec', 'short_flash', 'short_l', 'ao', 'long_flash', 't', 'long_l', 'less_rec');

具体为什么这样排序, 后面会解释.

初始化解空间

先拿出一块积木放入到棋盘中, 作为起点. 将「生成的棋盘」和「积木放入的顺序」一起加入到队列中, 用于 BFS 搜索.

protected function init(string $shapeName, array $shapeList, array $board, SplQueue $queue): SplQueue
{
  // 每个形状在每个位置都尝试一下, 作为起点
  // 每一块都至少两行或两列 可以少计算最后一行和最后一列
  for ($i = 0; $i < 6; ++$i) {
    for ($j = 0; $j < 6; ++$j) {
      foreach ($shapeList as $k => $shape) {
        $newBoard = $this->dropOneShape($board, $shape, $i, $j);
        // 当前积木 ($shapeName) 当前方向 ($k) 不可放入到当前位置 ($i, $j), 继续搜索
        if ($newBoard === false) {
          continue;
        }
				
        // 队列节点记录当前棋盘状态以及到达当前棋盘的路径
        $queue->enqueue(['board' => $newBoard, 'path' => [[$i, $j, $shapeName, $k]]]);
      }
    }
  }

  return $queue;
}

dropOneShape() 辅助方法

/**
 * 放置一块, 棋盘变成什么样子了
 * @param array $board
 * @param array $shape
 * @param int $x
 * @param int $y
 * @return array|false
*/
public function dropOneShape(array $board, array $shape, int $x, int $y)
{
  foreach ($shape as $i => $row) {
    // 当前 shape 的一行
    foreach ($row as $j => $grid) {
      // 当前 shape 的一个格子

      // 当前 grid 值为 0, 不可能引起冲突, 直接忽略
      if ($grid === 0) {
        continue;
      }

      $newX = $x + $i;
      $newY = $y + $j;

      // 越界
      if ($newX >= 7 || $newY >= 7) {
        return false;
      }

      // 重合
      if ($board[$newX][$newY] === 1) {
        return false;
      }

      $board[$newX][$newY] = $grid;
    }
  }

  // 剪枝, 优化的很明显
  if ($this->minArea($board) < 5) {
    return false;
  }

  return $board;
}

分别将 8 块积木带入到初始化方法中, 得到的结果为:

// 积木名数组, 按解空间从小到大排序
$names = array_keys($allShapes);
// 先放一块, 作为起点. 矩形的起点结果最少
$queue = $this->init($names[0], $allShapes[$names[0]], $board, new SplQueue());
rec, init queue count=36
short_flash, init queue count=54
short_l, init queue count=60
ao, init queue count=61
long_flash, init queue count=99
t, init queue count=100
long_l, init queue count=106
less_rec, init queue count=144

这就解释了上述积木数组为什么那样排序.

剪枝

实际上, 如果不进行该剪枝操作, 时间和内存都是不可接受的, 即根本无法完成计算.

这里借鉴了 695. 岛屿的最大面积 的思路. 将已填入的部分 (1) 视为海洋, 未填入的部分 (0) 视为陆地, 填入的积木将棋盘分隔为几个孤岛, 由于积木的最小格子数为 5, 所以只要有孤岛面积小于 5, 就没有必要继续进行搜索了.

/**
 * 空的地方作为岛屿, 找岛屿的最小面积, <5 无效
 * @return int|mixed
*/
public function minArea($board)
{
  $min = 49;
  for ($i = 0; $i < 7; ++$i) {
    for ($j = 0; $j < 7; ++$j) {
      if ($board[$i][$j] === 0) {
        $area = $this->dfs($board, $i, $j);
        $min = min($min, $area);
        if ($min < 5) {
          return $min;
        }
      }
    }
  }

  return $min;
}
private function dfs(&$board, $i, $j)
{
  // 越界
  if (!(0 <= $i && $i < 7 && 0 <= $j && $j < 7)) {
    return 0;
  }
  // 本例中, 0 为陆地
  if ($board[$i][$j] !== 0) {
    return 0;
  }

  // floodFill
  $board[$i][$j] = 2;

  return 1 +
    +$this->dfs($board, $i - 1, $j)
    + $this->dfs($board, $i + 1, $j)
    + $this->dfs($board, $i, $j - 1)
    + $this->dfs($board, $i, $j + 1);
}

BFS 过程

// 当前搜索了几层, 初始化已经有了一层
$level = 1;

// 当前队列不为空, 就进行 BFS 搜索
while (!$queue->isEmpty()) {
  // 当前层共有多少个队列节点
  $queueCount = $queue->count();
  echo 'current queue count = ' . $queueCount, PHP_EOL;
  // 每一次遍历所有队列, 都拿出一块积木来
  $curName = $names[$level];
  $curShapes = $allShapes[$curName] ?? [];
  if (empty($curShapes)) {
    // 防止没有解的情况发生
    echo 'end, nothing to drop', PHP_EOL;

    return false;
  }

  echo sprintf('at level %d, drop %s', $level, $curName), PHP_EOL;

  for ($index = 0; $index < $queueCount; ++$index) {
    $cur = $queue->dequeue();
    // 当前积木的每种形状都尝试一下, 这里和初始化函数基本一致
    foreach ($curShapes as $k => $shape) {
      for ($i = 0; $i < 6; ++$i) {
        for ($j = 0; $j < 6; ++$j) {
          $newBoard = $this->dropOneShape($cur['board'], $shape, $i, $j);
          // 当前积木 ($name) 当前方向 ($k) 不可放入到当前位置 ($i, $j), 继续搜索
          if ($newBoard === false) {
            continue;
          }

          // 回溯
          $cur['path'][] = [$i, $j, $curName, $k];
					
          // 当前积木可放, 即时判断是否搜索到可行解, 返回即可
          if ($level === 7) {
            echo 'found it', PHP_EOL;
            // 格式化输出一个可行解
            $this->dumpResult($cur['path'], $allShapes);

            return true;
          }

          $queue->enqueue(['board' => $newBoard, 'path' => $cur['path']]);
          // 回溯, 恢复现场
          array_pop($cur['path']);
        }
      }
    }
  }
  
  // 扩散到下一层
  $level++;
}

// 队列为空还没有找到可行解
return false;

完整代码

Calender.php

class Calendar
{
    public function aPuzzleEachDay(array $board, array $allShapes): bool
    {
				// 积木名数组, 按解空间从小到大排序
        $names = array_keys($allShapes);
        // 先放一块, 作为起点. 矩形的起点结果最少
        $queue = $this->init($names[0], $allShapes[$names[0]], $board, new SplQueue());
        // 当前搜索了几层, 初始化已经有了一层
        $level = 1;

        // 当前队列不为空, 就进行 BFS 搜索
        while (!$queue->isEmpty()) {
            // 当前层共有多少个队列节点
            $queueCount = $queue->count();
            echo 'current queue count = ' . $queueCount, PHP_EOL;
            // 每一次遍历所有队列, 都拿出一块积木来
            $curName = $names[$level];
            $curShapes = $allShapes[$curName] ?? [];
            if (empty($curShapes)) {
                // 防止没有解的情况发生
                echo 'end, nothing to drop', PHP_EOL;

                return false;
            }

            echo sprintf('at level %d, drop %s', $level, $curName), PHP_EOL;
            for ($index = 0; $index < $queueCount; ++$index) {
                $cur = $queue->dequeue();
                // 当前积木的每种形状都尝试一下, 这里和初始化函数基本一致
                foreach ($curShapes as $k => $shape) {
                    for ($i = 0; $i < 6; ++$i) {
                        for ($j = 0; $j < 6; ++$j) {
                            $newBoard = $this->dropOneShape($cur['board'], $shape, $i, $j);
                            // 当前积木 ($name) 当前方向 ($k) 不可放入到当前位置 ($i, $j), 继续搜索
                            if ($newBoard === false) {
                                continue;
                            }

                            // 回溯
                            $cur['path'][] = [$i, $j, $curName, $k];

                            // 当前积木可放, 即时判断是否搜索到可行解, 返回即可
                            if ($level === 7) {
                                echo 'found it', PHP_EOL;
                                $this->dumpResult($cur['path'], $allShapes);

                                return true;
                            }

                            $queue->enqueue(['board' => $newBoard, 'path' => $cur['path']]);
                            // 回溯, 恢复现场
                            array_pop($cur['path']);
                        }
                    }
                }
            }

            // 扩散到下一层
            $level++;
        }

        // 队列为空还没有找到可行解
        return false;
    }

    private function dumpBoard(array $board)
    {
        echo 'board', PHP_EOL;
        foreach ($board as $row) {
            echo implode(', ', $row), PHP_EOL;
        }
    }

    /**
     * 空的地方作为岛屿, 找岛屿的最小面积, <5 无效
     * @return int|mixed
     */
    public function minArea($board)
    {
        $min = 49;
        for ($i = 0; $i < 7; ++$i) {
            for ($j = 0; $j < 7; ++$j) {
                if ($board[$i][$j] === 0) {
                    $area = $this->dfs($board, $i, $j);
                    $min = min($min, $area);
                    if ($min < 5) {
                        return $min;
                    }
                }
            }
        }

        return $min;
    }

    private function dfs(&$board, $i, $j)
    {
        // 越界
        if (!(0 <= $i && $i < 7 && 0 <= $j && $j < 7)) {
            return 0;
        }
        // 本例中, 0 为陆地
        if ($board[$i][$j] !== 0) {
            return 0;
        }

        // floodFill
        $board[$i][$j] = 2;

        return 1 +
            +$this->dfs($board, $i - 1, $j)
            + $this->dfs($board, $i + 1, $j)
            + $this->dfs($board, $i, $j - 1)
            + $this->dfs($board, $i, $j + 1);
    }

    protected function init(string $shapeName, array $shapeList, array $board, SplQueue $queue): SplQueue
    {
        // 每个形状在每个位置都尝试一下, 作为起点
        // 每一块都至少两行或两列 可以少计算最后一行和最后一列
        for ($i = 0; $i < 6; ++$i) {
            for ($j = 0; $j < 6; ++$j) {
                foreach ($shapeList as $k => $shape) {
                    $newBoard = $this->dropOneShape($board, $shape, $i, $j);
                    if ($newBoard === false) {
                        continue;
                    }

                    $queue->enqueue(['board' => $newBoard, 'path' => [[$i, $j, $shapeName, $k]]]);
                }
            }
        }

        return $queue;
    }

    /**
     * 放置一块, 棋盘变成什么样子了
     * @param array $board
     * @param array $shape
     * @param int $x
     * @param int $y
     * @return array|false
     */
    public function dropOneShape(array $board, array $shape, int $x, int $y)
    {
        foreach ($shape as $i => $row) {
            // 当前 shape 的一行
            foreach ($row as $j => $grid) {
                // 当前 shape 的一个格子

                // 当前 grid 值为 0, 不可能引起冲突, 直接忽略
                if ($grid === 0) {
                    continue;
                }

                $newX = $x + $i;
                $newY = $y + $j;

                // 越界
                if ($newX >= 7 || $newY >= 7) {
                    return false;
                }

                // 重合
                if ($board[$newX][$newY] === 1) {
                    return false;
                }

                $board[$newX][$newY] = $grid;
            }
        }

        // 剪枝, 优化的很明显
        if ($this->minArea($board) < 5) {
            return false;
        }

        return $board;
    }

    private function dumpResult($path, $allShapes)
    {
        foreach ($path as $item) {
            echo sprintf('at %d,%d drop:', $item[0], $item[1]), PHP_EOL;
            $shape = $allShapes[$item[2]][$item[3]];
            foreach ($shape as $row) {
                echo implode(',', $row), PHP_EOL;
            }
        }
    }
}

index.php

$t1 = microtime(true);
// 7*7 的方格
$board = array_fill(0, 7, array_fill(0, 7, 0));
$board[0][6] = $board[1][6] = $board[6][3] = $board[6][4] = $board[6][5] = $board[6][6] = 1;
// 6 月 16 日
$board[0][5] = $board[4][1] = 1;

$rec = [
    [[1, 1, 1], [1, 1, 1]],
    [[1, 1], [1, 1], [1, 1]],
];
$ao = [
    [[1, 0, 1], [1, 1, 1]],
    [[1, 1, 1], [1, 0, 1]],
    [[1, 1], [1, 0], [1, 1]],
    [[1, 1], [0, 1], [1, 1]],
];
$long_l = [
    [[1, 0], [1, 0], [1, 0], [1, 1]],
    [[1, 1], [1, 0], [1, 0], [1, 0]],
    [[0, 1], [0, 1], [0, 1], [1, 1]],
    [[1, 1], [0, 1], [0, 1], [0, 1]],
    [[1, 1, 1, 1], [1, 0, 0, 0]],
    [[1, 1, 1, 1], [0, 0, 0, 1]],
    [[1, 0, 0, 0], [1, 1, 1, 1]],
    [[0, 0, 0, 1], [1, 1, 1, 1]],
];
$short_l = [
    [[1, 0, 0], [1, 0, 0], [1, 1, 1]],
    [[1, 1, 1], [1, 0, 0], [1, 0, 0]],
    [[1, 1, 1], [0, 0, 1], [0, 0, 1]],
    [[0, 0, 1], [0, 0, 1], [1, 1, 1]],
];
$less_rec = [
    [[1, 1, 1], [1, 1, 0]],
    [[1, 1, 1], [0, 1, 1]],
    [[1, 1, 0], [1, 1, 1]],
    [[0, 1, 1], [1, 1, 1]],
    [[1, 0], [1, 1], [1, 1]],
    [[0, 1], [1, 1], [1, 1]],
    [[1, 1], [1, 1], [1, 0]],
    [[1, 1], [1, 1], [0, 1]],
];
$t = [
    [[1, 1, 1, 1], [0, 1, 0, 0]],
    [[1, 1, 1, 1], [0, 0, 1, 0]],
    [[0, 0, 1, 0], [1, 1, 1, 1]],
    [[0, 1, 0, 0], [1, 1, 1, 1]],
    [[1, 0], [1, 1], [1, 0], [1, 0]],
    [[1, 0], [1, 0], [1, 1], [1, 0]],
    [[0, 1], [1, 1], [0, 1], [0, 1]],
    [[0, 1], [0, 1], [1, 1], [0, 1]],
];
$long_flash = [
    [[0, 1, 1, 1], [1, 1, 0, 0]],
    [[1, 1, 1, 0], [0, 0, 1, 1]],
    [[0, 0, 1, 1], [1, 1, 1, 0]],
    [[1, 1, 0, 0], [0, 1, 1, 1]],
    [[0, 1], [1, 1], [1, 0], [1, 0]],
    [[1, 0], [1, 1], [0, 1], [0, 1]],
    [[0, 1], [0, 1], [1, 1], [1, 0]],
    [[1, 0], [1, 0], [1, 1], [0, 1]],
];
$short_flash = [
    [[1, 0, 0], [1, 1, 1], [0, 0, 1]],
    [[0, 0, 1], [1, 1, 1], [1, 0, 0]],
    [[1, 1, 0], [0, 1, 0], [0, 1, 1]],
    [[0, 1, 1], [0, 1, 0], [1, 1, 0]],
];

$allShapes = compact('rec', 'short_flash', 'short_l', 'ao', 'long_flash', 't', 'long_l', 'less_rec');
var_dump((new Calendar())->aPuzzleEachDay($board, $allShapes));

function convert($size): string
{
    $unit = ['b', 'kb', 'mb', 'gb', 'tb', 'pb'];

    return @round($size / (1024 ** ($i = floor(log($size, 1024)))), 2) . ' ' . $unit[$i];
}

echo 'memory usage=' . convert(memory_get_usage(true)), PHP_EOL;
$t2 = microtime(true);
echo 'time consumed=' . ($t2 - $t1) * 1000 . 'ms', PHP_EOL;

跑一下试试

// 当前队列长度
current queue count = 36
at level 1, drop short_flash
current queue count = 796
at level 2, drop short_l
current queue count = 5715
at level 3, drop ao
current queue count = 6594
at level 4, drop long_flash
current queue count = 2914
at level 5, drop t
current queue count = 731
at level 6, drop long_l
current queue count = 173
at level 7, drop less_rec
// 找到了一个可行解
found it
at 0,0 drop:
1,1,1
1,1,1
at 2,0 drop:
1,0,0
1,1,1
0,0,1
at 4,0 drop:
1,0,0
1,0,0
1,1,1
at 2,4 drop:
1,1
0,1
1,1
at 2,1 drop:
1,1,1,0
0,0,1,1
at 4,1 drop:
0,0,1,0
1,1,1,1
at 2,5 drop:
0,1
0,1
0,1
1,1
at 0,3 drop:
1,1,0
1,1,1
bool(true)
// 内存使用量
memory usage=22 mb
// 执行时间
time consumed=2866.140127182ms

3 秒内完成搜索, 还是可以接受的.

就是这样:

IMG_5406.JPG

尝试将 allShapes 数组倒序排列, 得到的结果为:

memory usage=774 mb
time consumed=81989.147901535ms

完全不可接受.

那么还能不能继续优化了? 或者还有其他解法? TODO

拓展 1: 有多少种解法

对代码做简单的改动即可得到每一天的解法数量.

class Calendar
{
    public function aPuzzleEachDay(array $board, array $allShapes)
    {
        $resultCount = 0;
        ...
        while (!$queue->isEmpty()) {
          ...
          if (empty($curShapes)) {
            break;
          }
          ...
          // 当前积木可放, 即时判断是否搜索到可行解, 返回即可
          if ($level === 7) {
            $resultCount++;
          }  
          ...
        return $resultCount;
    }
  ...
}

输出结果为:

int(38)
memory usage=22 mb
time consumed=2754.9610137939ms

时间和内存消耗基本不变, 6 月 16 日找到了 38 种可行解.

拓展 2: 哪一天解最多 (1月25日, 216 种), 哪一天解最少 (10月6日, 7 种)

棋盘初始化改一下数字即可

// 遍历初始化棋盘
for ($month = 1; $month <= 12; ++$month) {
    $row1 = floor(($month - 1) / 6);
    $col1 = ($month - 1) % 6;
    $board[$row1][$col1] = 1;
    for ($day = 1; $day <= 31; ++$day) {
        $row2 = floor(($day - 1) / 7) + 2;
        $col2 = ($day - 1) % 7;
        $board[$row2][$col2] = 1;
        $count = (new Calendar())->aPuzzleEachDay($board, $allShapes);
        echo sprintf('%d月%d日, solution count=%d', $month, $day, $count), PHP_EOL;
        // 恢复
        $board[$row2][$col2] = 0;
    }
    // 恢复
    $board[$row1][$col1] = 0;
}

输出结果, 多到超乎预期:

1月1日, solution count=64
1月2日, solution count=109
1月3日, solution count=47
1月4日, solution count=103
1月5日, solution count=83
1月6日, solution count=24
1月7日, solution count=188
1月8日, solution count=79
1月9日, solution count=127
1月10日, solution count=77
1月11日, solution count=74
1月12日, solution count=60
1月13日, solution count=129
1月14日, solution count=88
1月15日, solution count=87
1月16日, solution count=70
1月17日, solution count=133
1月18日, solution count=69
1月19日, solution count=104
1月20日, solution count=195
1月21日, solution count=104
1月22日, solution count=78
1月23日, solution count=188
1月24日, solution count=48
1月25日, solution count=216
1月26日, solution count=84
1月27日, solution count=85
1月28日, solution count=145
1月29日, solution count=74
1月30日, solution count=119
1月31日, solution count=170

2月1日, solution count=73
2月2日, solution count=45
2月3日, solution count=22
2月4日, solution count=41
2月5日, solution count=49
2月6日, solution count=27
2月7日, solution count=88
2月8日, solution count=48
2月9日, solution count=32
2月10日, solution count=47
2月11日, solution count=26
2月12日, solution count=31
2月13日, solution count=59
2月14日, solution count=31
2月15日, solution count=28
2月16日, solution count=26
2月17日, solution count=55
2月18日, solution count=35
2月19日, solution count=45
2月20日, solution count=67
2月21日, solution count=29
2月22日, solution count=25
2月23日, solution count=81
2月24日, solution count=21
2月25日, solution count=78
2月26日, solution count=63
2月27日, solution count=47
2月28日, solution count=81
2月29日, solution count=64

3月1日, solution count=17
3月2日, solution count=24
3月3日, solution count=39
3月4日, solution count=57
3月5日, solution count=32
3月6日, solution count=16
3月7日, solution count=86
3月8日, solution count=66
3月9日, solution count=71
3月10日, solution count=27
3月11日, solution count=40
3月12日, solution count=40
3月13日, solution count=53
3月14日, solution count=44
3月15日, solution count=39
3月16日, solution count=30
3月17日, solution count=60
3月18日, solution count=22
3月19日, solution count=52
3月20日, solution count=61
3月21日, solution count=29
3月22日, solution count=29
3月23日, solution count=92
3月24日, solution count=24
3月25日, solution count=61
3月26日, solution count=72
3月27日, solution count=49
3月28日, solution count=80
3月29日, solution count=49
3月30日, solution count=18
3月31日, solution count=107

4月1日, solution count=55
4月2日, solution count=49
4月3日, solution count=78
4月4日, solution count=56
4月5日, solution count=63
4月6日, solution count=8
4月7日, solution count=104
4月8日, solution count=111
4月9日, solution count=52
4月10日, solution count=88
4月11日, solution count=68
4月12日, solution count=47
4月13日, solution count=63
4月14日, solution count=62
4月15日, solution count=59
4月16日, solution count=61
4月17日, solution count=62
4月18日, solution count=41
4月19日, solution count=52
4月20日, solution count=123
4月21日, solution count=76
4月22日, solution count=49
4月23日, solution count=145
4月24日, solution count=26
4月25日, solution count=116
4月26日, solution count=81
4月27日, solution count=68
4月28日, solution count=140
4月29日, solution count=84
4月30日, solution count=52

5月1日, solution count=57
5月2日, solution count=62
5月3日, solution count=32
5月4日, solution count=47
5月5日, solution count=56
5月6日, solution count=23
5月7日, solution count=116
5月8日, solution count=42
5月9日, solution count=33
5月10日, solution count=48
5月11日, solution count=51
5月12日, solution count=23
5月13日, solution count=77
5月14日, solution count=53
5月15日, solution count=56
5月16日, solution count=43
5月17日, solution count=67
5月18日, solution count=36
5月19日, solution count=46
5月20日, solution count=62
5月21日, solution count=36
5月22日, solution count=16
5月23日, solution count=87
5月24日, solution count=14
5月25日, solution count=101
5月26日, solution count=53
5月27日, solution count=47
5月28日, solution count=130
5月29日, solution count=66
5月30日, solution count=79
5月31日, solution count=87

6月1日, solution count=56
6月2日, solution count=49
6月3日, solution count=54
6月4日, solution count=48
6月5日, solution count=50
6月6日, solution count=24
6月7日, solution count=191
6月8日, solution count=85
6月9日, solution count=52
6月10日, solution count=44
6月11日, solution count=78
6月12日, solution count=45
6月13日, solution count=44
6月14日, solution count=61
6月15日, solution count=57
6月16日, solution count=38
6月17日, solution count=75
6月18日, solution count=42
6月19日, solution count=86
6月20日, solution count=114
6月21日, solution count=57
6月22日, solution count=35
6月23日, solution count=102
6月24日, solution count=31
6月25日, solution count=150
6月26日, solution count=73
6月27日, solution count=73
6月28日, solution count=163
6月29日, solution count=57
6月30日, solution count=39

7月1日, solution count=99
7月2日, solution count=19
7月3日, solution count=27
7月4日, solution count=70
7月5日, solution count=34
7月6日, solution count=12
7月7日, solution count=125
7月8日, solution count=63
7月9日, solution count=72
7月10日, solution count=40
7月11日, solution count=43
7月12日, solution count=37
7月13日, solution count=70
7月14日, solution count=48
7月15日, solution count=28
7月16日, solution count=40
7月17日, solution count=109
7月18日, solution count=43
7月19日, solution count=61
7月20日, solution count=108
7月21日, solution count=52
7月22日, solution count=24
7月23日, solution count=78
7月24日, solution count=22
7月25日, solution count=97
7月26日, solution count=38
7月27日, solution count=68
7月28日, solution count=133
7月29日, solution count=42
7月30日, solution count=51
7月31日, solution count=82

8月1日, solution count=68
8月2日, solution count=85
8月3日, solution count=40
8月4日, solution count=94
8月5日, solution count=76
8月6日, solution count=44
8月7日, solution count=172
8月8日, solution count=105
8月9日, solution count=88
8月10日, solution count=87
8月11日, solution count=57
8月12日, solution count=59
8月13日, solution count=120
8月14日, solution count=70
8月15日, solution count=72
8月16日, solution count=85
8月17日, solution count=107
8月18日, solution count=65
8月19日, solution count=100
8月20日, solution count=116
8月21日, solution count=53
8月22日, solution count=41
8月23日, solution count=129
8月24日, solution count=24
8月25日, solution count=161
8月26日, solution count=84
8月27日, solution count=111
8月28日, solution count=189
8月29日, solution count=82
8月30日, solution count=78
8月31日, solution count=151

9月1日, solution count=34
9月2日, solution count=18
9月3日, solution count=49
9月4日, solution count=38
9月5日, solution count=25
9月6日, solution count=27
9月7日, solution count=92
9月8日, solution count=50
9月9日, solution count=43
9月10日, solution count=51
9月11日, solution count=36
9月12日, solution count=20
9月13日, solution count=46
9月14日, solution count=21
9月15日, solution count=58
9月16日, solution count=42
9月17日, solution count=52
9月18日, solution count=34
9月19日, solution count=33
9月20日, solution count=70
9月21日, solution count=38
9月22日, solution count=29
9月23日, solution count=85
9月24日, solution count=24
9月25日, solution count=54
9月26日, solution count=48
9月27日, solution count=39
9月28日, solution count=78
9月29日, solution count=48
9月30日, solution count=36

10月1日, solution count=58
10月2日, solution count=34
10月3日, solution count=28
10月4日, solution count=59
10月5日, solution count=13
10月6日, solution count=7
10月7日, solution count=92
10月8日, solution count=50
10月9日, solution count=36
10月10日, solution count=59
10月11日, solution count=28
10月12日, solution count=16
10月13日, solution count=52
10月14日, solution count=54
10月15日, solution count=43
10月16日, solution count=26
10月17日, solution count=48
10月18日, solution count=26
10月19日, solution count=50
10月20日, solution count=67
10月21日, solution count=25
10月22日, solution count=27
10月23日, solution count=87
10月24日, solution count=22
10月25日, solution count=85
10月26日, solution count=36
10月27日, solution count=29
10月28日, solution count=95
10月29日, solution count=56
10月30日, solution count=29
10月31日, solution count=106

11月1日, solution count=82
11月2日, solution count=91
11月3日, solution count=75
11月4日, solution count=68
11月5日, solution count=178
11月6日, solution count=33
11月7日, solution count=179
11月8日, solution count=108
11月9日, solution count=72
11月10日, solution count=97
11月11日, solution count=102
11月12日, solution count=92
11月13日, solution count=78
11月14日, solution count=76
11月15日, solution count=67
11月16日, solution count=64
11月17日, solution count=115
11月18日, solution count=81
11月19日, solution count=82
11月20日, solution count=164
11月21日, solution count=104
11月22日, solution count=40
11月23日, solution count=101
11月24日, solution count=35
11月25日, solution count=155
11月26日, solution count=106
11月27日, solution count=86
11月28日, solution count=183
11月29日, solution count=85
11月30日, solution count=74

12月1日, solution count=26
12月2日, solution count=32
12月3日, solution count=67
12月4日, solution count=45
12月5日, solution count=32
12月6日, solution count=66
12月7日, solution count=125
12月8日, solution count=67
12月9日, solution count=73
12月10日, solution count=66
12月11日, solution count=44
12月12日, solution count=78
12月13日, solution count=99
12月14日, solution count=39
12月15日, solution count=81
12月16日, solution count=68
12月17日, solution count=82
12月18日, solution count=38
12月19日, solution count=59
12月20日, solution count=103
12月21日, solution count=44
12月22日, solution count=49
12月23日, solution count=115
12月24日, solution count=30
12月25日, solution count=92
12月26日, solution count=48
12月27日, solution count=71
12月28日, solution count=164
12月29日, solution count=54
12月30日, solution count=60
12月31日, solution count=77

拓展 3: 棋盘如何设计

是否还有其他设计方式? TODO

拓展 4: 积木如何设计

是否还有其他设计方式? TODO

拓展 5: 相关游戏

华容道, 拼图问题, 数独, 八皇后等.

评论 (6)