代码#

#[derive(Debug, Clone)]
struct Block {
  w: usize,
  h: usize,
  x: usize,
  y: usize,
}

const GRID_WIDTH: usize = 8;
const GRID_HEIGHT: usize = 14;

struct Solver {
  cnt: usize,
  blocks: Vec<Vec<Block>>,
  grid: [[usize; GRID_WIDTH]; GRID_HEIGHT],
  tag: [[usize; GRID_WIDTH]; GRID_HEIGHT],
  found: bool,
  result: Option<[[usize; GRID_WIDTH]; GRID_HEIGHT]>,
}

impl Solver {
  fn new(grid: [[usize; GRID_WIDTH]; GRID_HEIGHT]) -> Self {
    Self {
      cnt: 0,
      blocks: vec![Vec::new(); 100],
      grid,
      tag: [[0; GRID_WIDTH]; GRID_HEIGHT],
      found: false,
      result: None,
    }
  }

  fn dfs(&mut self, st: usize) {
    if self.found {
      return;
    }
    if st == self.cnt {
      self.found = true;
      self.result = Some(self.tag);
      return;
    }

    // 先收集所有可能的块到一个临时向量中
    let current_blocks: Vec<Block> = self.blocks[st].clone();
    for block in current_blocks {
      let mut valid = true;
      // 检查是否可以放置
      for i in 0..block.w {
        for j in 0..block.h {
          let xx = block.x + i;
          let yy = block.y + j;
          if self.tag[xx][yy] != 0 {
            valid = false;
            break;
          }
        }
        if !valid {
          break;
        }
      }
      if !valid {
        continue;
      }

      // 放置方块
      for i in 0..block.w {
        for j in 0..block.h {
          self.tag[block.x + i][block.y + j] = st + 1;
        }
      }

      self.dfs(st + 1);

      if self.found {
        return;
      }

      // 回溯，移除方块
      for i in 0..block.w {
        for j in 0..block.h {
          self.tag[block.x + i][block.y + j] = 0;
        }
      }
    }
  }

  fn solve(&mut self) -> Option<[[usize; GRID_WIDTH]; GRID_HEIGHT]> {
    // 先找出所有数字格子
    for i in 0..GRID_HEIGHT {
      for j in 0..GRID_WIDTH {
        if self.grid[i][j] > 0 {
          let area = self.grid[i][j];
          // 枚举所有可能的长和宽
          for w in 1..=area {
            if area % w == 0 {
              let h = area / w;
              // 枚举所有可能的位置
              for x in i.saturating_sub(w - 1)..=i {
                for y in j.saturating_sub(h - 1)..=j {
                  if x + w <= GRID_HEIGHT && y + h <= GRID_WIDTH {
                    // 检查是否只覆盖了一个数字
                    let mut count = 0;
                    let mut valid = true;
                    for dx in 0..w {
                      for dy in 0..h {
                        if self.grid[x + dx][y + dy] > 0 {
                          count += 1;
                          if count > 1 {
                            valid = false;
                            break;
                          }
                        }
                      }
                      if !valid {
                        break;
                      }
                    }
                    if valid && count == 1 {
                      self.blocks[self.cnt].push(Block { w, h, x, y });
                    }
                  }
                }
              }
            }
          }
          self.cnt += 1;
        }
      }
    }
    // 开始搜索
    self.dfs(0);
    self.result
  }
}

fn main() {
  let mut solver = Solver::new(grid);
  solver.solve();
}

思路#

Block 表示玩家绘制的方块信息：

• x 与 y 为坐标
• w 与 h 为尺寸

GRID_WIDTH 和 GRID_HEIGHT 是网格的尺寸，每日一题中的网格就是 14 行 8 列的。 谜题网格中的数字是需要填入的方块的面积，后文会称作子谜题。

Solver 记录着一些解题过程中的状态：

• cnt 表示当前处理的子谜题编号
• blocks 表示每个子谜题可能填入的方块的位置和尺寸，是个二维数组，子谜题编号作为“键”
• grid 是谜题网格，一个二维数组
• tag 为标记表，将已放置的方块具体填入网格中，如 [[1, 1, 2, 3, 3, 3]]
• found 为找到最终解的标志
• result 为最终解，是 tag 的引用

预处理：

1. 先找出谜题里带数字的格子，也就是我们要填入的每个方块的面积
2. 然后通过面积计算出所有的长和宽组合，比如 2 可以拆分成 w1 h2 或者 w2 h1
3. 把所有的组合，按不同的摆放方式去带入棋盘，主要是检查是否只覆盖了当前子谜题，排除不可能的摆放
4. 将剩余的可能存入 blocks

接着使用深度优先搜索，计算合适的摆放方法：

1. 按子谜题编号逐个尝试，使用 blocks 中预存的方块，进行摆放
2. 放置结果保存在 tag 中，要保证不和其他子谜题的答案冲突
3. 放置成功后就递归处理下一个子谜题
4. 遇到所有摆放都不可能的子谜题，那就是之前的摆放有错，回到上一步，继续尝试
5. 成功处理完所有子谜题后，设置 found 标志，结束搜索

效果#