从数独小游戏看纯端侧算法应用:回溯求解、唯一解出题与 ArkUI 刷新粒度

举报
yd_286131434 发表于 2026/11/16 08:30:30 2026/11/16
【摘要】 结合鸿蒙实践案例「数独小游戏」,梳理纯端侧算法应用的设计取舍:Int8Array 棋盘与行列宫位掩码、MRV 剪枝的回溯求解与「数到 2 就停」的唯一解校验、挖洞出题与难度分级、预置题库与 TaskPool 的取舍、ArkUI 三层状态与刷新粒度,以及计时、撤销、存档校验和十条上线排查清单。

一、算法类小游戏和 CRUD 应用不是一回事

最近在鸿蒙开发实践中心的案例列表第二页翻到「数独小游戏」:HarmonyOS + ArkUI 纯端侧实现,内置 54 道分级题库,支持实时行列宫冲突校验与通关进度本地持久化。没有账号、没有服务端、没有支付。这类案例看着简单,其实把三类问题压在了一起:算法要正确、交互要跟手、状态要能恢复。

维度 常规 CRUD 应用 纯端侧算法应用
正确性来源 服务端数据与接口 本地算法实现,错了没人兜底
性能瓶颈 网络与列表渲染 搜索 / 递归计算,容易卡主线程
内容生产 运营配置或接口下发 预置题库或本地生成
状态恢复 重新拉一次接口即可 必须自己持久化完整局面
典型事故 接口超时、缓存脏 出题多解、点击掉帧、进度丢失

二、棋盘数据结构:一维数组 + 位掩码

9×9 用 Int8Array(81) 就够,0 表示空格。行列宫换算很固定:row = Math.floor(i / 9)、col = i % 9、box = Math.floor(row / 3) * 3 + Math.floor(col / 3)。

真正影响手感的是冲突校验。每落一子都去遍历同行、同列、同宫的 20 个格子,虽然也能跑,但候选数计算、提示、高亮都要反复做,很快变成一堆重复循环。更干净的做法是维护三个位掩码数组:某格候选 = FULL & ~(rowMask[r] | colMask[c] | boxMask[b]),一次位运算搞定。

const FULL = 0x1ff // 低 9 位全 1,表示数字 1~9 都可选

function boxOf(i: number): number {
  const r = Math.floor(i / 9), c = i % 9
  return Math.floor(r / 3) * 3 + Math.floor(c / 3)
}

class Board {
  cells: Int8Array = new Int8Array(81)
  private rowMask = new Int32Array(9)
  private colMask = new Int32Array(9)
  private boxMask = new Int32Array(9)

  candidates(i: number): number {
    return FULL & ~(this.rowMask[Math.floor(i / 9)] |
                    this.colMask[i % 9] |
                    this.boxMask[boxOf(i)])
  }

  place(i: number, n: number): boolean {
    const bit = 1 << (n - 1)
    if ((this.candidates(i) & bit) === 0) return false
    this.cells[i] = n
    this.rowMask[Math.floor(i / 9)] |= bit
    this.colMask[i % 9] |= bit
    this.boxMask[boxOf(i)] |= bit
    return true
  }

  clear(i: number) {
    this.cells[i] = 0
    this.rebuildMasks() // 从 cells 重算,最稳
  }
}

这里有个很容易写错的地方:移除数字时不能简单 mask &= ~bit。撤销、擦除、挖洞都会触发移除,一旦掩码和实际盘面不同步,后面所有候选与冲突判定都会错,而且很难复现。从 cells 重算三个掩码只有 81 次循环,成本可以忽略,却能让状态始终自洽。

三、回溯求解:MRV 剪枝与「数到 2 就停」

朴素地按 0~80 顺序递归试填,搜索树会大得离谱。两个优化是必需的:

  1. MRV(最少候选优先):每步选候选数最少的空格先试,分支数骤减。
  2. 候选按位枚举 mask & -mask 取最低位,避免循环 1~9 逐个判断。

出题和合法性校验需要判断「是否唯一解」,但不需要数完所有解——数到 2 立即返回即可:

function countSolutions(board: Board, limit: number): number {
  let best = -1, bestMask = 0, bestCount = 10
  for (let i = 0; i < 81; i++) {
    if (board.cells[i] !== 0) continue
    const m = board.candidates(i)
    const cnt = popcount(m)
    if (cnt === 0) return 0          // 死路
    if (cnt < bestCount) {
      best = i; bestMask = m; bestCount = cnt
      if (cnt === 1) break
    }
  }
  if (best === -1) return 1          // 已填满且合法
  let total = 0
  let m = bestMask
  while (m !== 0) {
    const bit = m & -m
    m ^= bit
    const n = 32 - Math.clz32(bit)  // 位序即数字
    const snap = board.snapshot()
    board.place(best, n)
    total += countSolutions(board, limit - total)
    board.restore(snap)
    if (total >= limit) break
  }
  return total
}

注意 limit 传的是「还差几个就够」,不是固定 2;否则嵌套递归会多算很多分支。另外别忘了给递归加深度上限或超时保护,遇到脏数据时能优雅退出,而不是把主线程挂死。

四、出题:挖洞 + 唯一解校验,难度不能只看空格数

生成流程是先用随机顺序跑回溯得到一个合法终盘,再按随机顺序挖格:每挖一格调用 countSolutions(board, 2),只要解不唯一就回填。

function makePuzzle(level: 'easy' | 'normal' | 'hard'): Int8Array {
  const board = randomFullBoard()
  const order = shuffle([...Array(81).keys()])
  const targetHoles = { easy: 36, normal: 46, hard: 54 }[level]
  let holes = 0
  for (const i of order) {
    if (holes >= targetHoles) break
    const saved = board.cells[i]
    board.clear(i)                 // 重算掩码,见上一节
    if (countSolutions(board, 2) !== 1) {
      board.place(i, saved)        // 多解,回填
    } else {
      holes++
    }
  }
  return board.cells.slice()
}

三个坑值得记下来:

  • 空格数不等于难度:54 个空但每格都是唯一候选,可能比 40 个空、需要试探的题更简单。分级应统计解题过程中所需的最难技巧,或至少记录最大回溯次数,别只数空格。
  • 对称挖洞:为了视觉工整常按中心对称成对挖,实现时要成对校验唯一解,别只校验了一格。
  • 别在 UI 线程出题:挖洞要跑几十次求解,低端机上可能几百毫秒到数秒。放 TaskPool / Worker,或者干脆预置题库。
出题方式 首屏延迟 可复现性 内容量 适用场景
运行时生成 高,必须异步 差,除非固定种子 无限 每日挑战
预置题库 极低 好,便于分享关卡号 受包体限制 分级闯关
混合(预置 + 按需生成) 低 好 灵活 案例里的 54 道分级题库属于这类

固定随机种子(比如 xorshift)能让「同一关卡号」在任何设备得到同一道题,这对成绩对比和分享链接很关键。

五、ArkUI 刷新粒度:81 个格子不等于 81 次重绘

9×9 只有 81 格,Grid + ForEach 完全够用,不需要自定义绘制。真正的问题是刷新粒度:把整个棋盘塞进一个 @State 数组,改一格会让 81 个 GridItem 全部参与 diff,点击时能看到轻微闪烁。

建议分三层:

  • 模型层:Board(cells + 三个掩码),纯数据,不进状态观测。
  • 视图状态:每格一个轻量视图对象(显示值、是否冲突、候选笔记、是否选中),配一个 @State version 计数器。
  • 交互状态:选中格、当前数字、笔记模式,单独 @State,与棋盘数据解耦。
@Observed
class CellView {
  value: number = 0
  conflict: boolean = false
  notes: number = 0        // 候选位掩码
  selected: boolean = false
}

@Entry
@Component
struct SudokuPage {
  @State cells: CellView[] = Array.from({ length: 81 }, () => new CellView())
  @State version: number = 0
  private board: Board = new Board()

  onCellInput(i: number, n: number) {
    if (!this.board.place(i, n)) {
      this.cells[i].conflict = true
      return
    }
    this.cells[i].value = n
    this.cells[i].conflict = false
    this.refreshPeers(i)    // 只更新同行/列/宫相关格的冲突标记
    this.version += 1
  }
}

ForEach 的 key 用格子索引(稳定),不要用对象引用;冲突高亮只刷新相关 20 格并去重;候选笔记存位掩码而不是数字数组,一个 number 就够了。

六、计时、撤销与生命周期

  • 计时:不要用 setInterval 累加秒数,应用切后台被挂起后会少算。记录 startAt 与 pausedTotal,用 Date.now() - startAt - pausedTotal 算,在 onBackground / onForeground 里补暂停时长。
  • 撤销:命令栈存 { index, before, after, notesBefore, notesAfter },一次「落子 + 冲突刷新」算一步。撤销时必须同时还原掩码与视图标记,只改显示值会留下幽灵冲突。
  • 存档:Preferences 存 { version, puzzleId, cells, notes, elapsedMs, updatedAt }。版本号必须留,将来改结构要做迁移;读取时校验长度 81 与取值 0~9,损坏就回退到初始题面而不是崩溃。
interface SaveData {
  version: number
  puzzleId: string
  cells: number[]
  notes: number[]
  elapsedMs: number
  updatedAt: number
}

function isValidSave(s: SaveData): boolean {
  return s.version === 1 &&
         Array.isArray(s.cells) && s.cells.length === 81 &&
         s.cells.every((n) => Number.isInteger(n) && n >= 0 && n <= 9)
}

七、上线前排查清单

  1. 出现多解题:挖洞后是否每次都做了「数到 2 就停」的唯一解校验。
  2. 擦除数字后冲突标记残留:掩码是否重算,而不是简单按位清除。
  3. 难度分级名不副实:是否统计解题技巧 / 回溯次数,而非只数空格。
  4. 点「新的一局」卡顿:出题是否放在 UI 线程,是否改用 TaskPool 或预置题库。
  5. 改一格整盘闪一下:@State 是否放了整个棋盘、ForEach key 是否稳定。
  6. 冲突高亮漏格:是否覆盖同行、同列、同宫共 20 个相关格并去重。
  7. 切后台回来计时变少:是否用时间戳差值,并在生命周期里补暂停时长。
  8. 撤销后冲突提示不消失:命令是否同时还原掩码与视图标记。
  9. 版本升级后老存档打不开:是否有 version 与迁移 / 回退逻辑。
  10. 审核被拒:是否申请了网络、位置等与「无账号无网络」定位无关的权限。

小结

纯端侧算法应用的难点从来不在界面,而在三件事:算法要有可验证的正确性(唯一解、冲突判定)、计算要躲开 UI 线程、状态要能完整恢复。把棋盘模型、视图状态、交互状态分层之后,题库、笔记、提示、每日挑战都只是往上加功能;反过来,如果一开始就把 81 格的显示和求解数据混在一个 @State 里,后面每个功能都会伴随一次整盘重绘。

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0)

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。