从数独小游戏看纯端侧算法应用:回溯求解、唯一解出题与 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 顺序递归试填,搜索树会大得离谱。两个优化是必需的:
- MRV(最少候选优先):每步选候选数最少的空格先试,分支数骤减。
- 候选按位枚举
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)
}
七、上线前排查清单
- 出现多解题:挖洞后是否每次都做了「数到 2 就停」的唯一解校验。
- 擦除数字后冲突标记残留:掩码是否重算,而不是简单按位清除。
- 难度分级名不副实:是否统计解题技巧 / 回溯次数,而非只数空格。
- 点「新的一局」卡顿:出题是否放在 UI 线程,是否改用 TaskPool 或预置题库。
- 改一格整盘闪一下:
@State是否放了整个棋盘、ForEach key 是否稳定。 - 冲突高亮漏格:是否覆盖同行、同列、同宫共 20 个相关格并去重。
- 切后台回来计时变少:是否用时间戳差值,并在生命周期里补暂停时长。
- 撤销后冲突提示不消失:命令是否同时还原掩码与视图标记。
- 版本升级后老存档打不开:是否有 version 与迁移 / 回退逻辑。
- 审核被拒:是否申请了网络、位置等与「无账号无网络」定位无关的权限。
小结
纯端侧算法应用的难点从来不在界面,而在三件事:算法要有可验证的正确性(唯一解、冲突判定)、计算要躲开 UI 线程、状态要能完整恢复。把棋盘模型、视图状态、交互状态分层之后,题库、笔记、提示、每日挑战都只是往上加功能;反过来,如果一开始就把 81 格的显示和求解数据混在一个 @State 里,后面每个功能都会伴随一次整盘重绘。
- 点赞
- 收藏
- 关注作者
评论(0)