目录

1. 概述
2. 工具功能
3. 核心实现
4. 实战案例
5. 编译过程详解
6. 工具扩展
7. 最佳实践
8. 常见问题

---

概述

本文档介绍如何在 Kotlin Multiplatform (KMP) 鸿蒙跨端开发中实现一个完整的数独求解系统。这个案例展示了如何使用 Kotlin 的回溯算法、约束满足问题和递归来创建一个功能丰富的数独求解工具。通过 KMP，这个工具可以无缝编译到 JavaScript，在 OpenHarmony 应用中运行，并支持用户输入进行实时处理。

工具的特点

• 数独求解：使用回溯算法求解数独
• 有效性检查：验证初始数独的合法性
• 约束验证：检查行、列、3×3 方格的约束
• 性能分析：统计求解步数和填充信息
• 可视化展示：用 ASCII 字符展示原始和求解后的数独
• 跨端兼容：一份 Kotlin 代码可同时服务多个平台

---

工具功能

1. 数独输入

• 格式：81 个数字字符串，0 表示空格
• 验证：检查输入长度和格式
• 合法性：验证初始数独是否有效

2. 有效性检查

• 行检查：确保每行没有重复数字
• 列检查：确保每列没有重复数字
• 方格检查：确保每个 3×3 方格没有重复数字

3. 回溯求解

• 递归算法：使用递归回溯求解
• 约束检查：在每个位置检查约束
• 步数统计：记录求解过程中的步数

4. 结果分析

• 求解状态：是否可解
• 步数统计：求解过程中的尝试次数
• 填充信息：最终填充的数字个数

5. 可视化展示

• 原始数独：显示输入的数独
• 求解结果：显示求解后的数独
• 格式化：用 ASCII 字符清晰展示

---

核心实现

1. 数独网格初始化

val board = Array(9) { IntArray(9) }
for (i in 0 until 81) {
    board[i / 9][i % 9] = puzzleStr[i].toString().toInt()
}

这段代码实现了从一维字符串到二维数独网格的转换。首先创建一个 9×9 的二维整数数组来表示数独网格。然后遍历输入字符串的 81 个字符，对于每个字符，使用 i / 9 计算行索引，i % 9 计算列索引，将字符转换为整数后填入对应的网格位置。这个转换方法利用了整数除法和模运算的性质，将一维索引映射到二维坐标。例如，索引 0 对应 (0,0)，索引 9 对应 (1,0)，索引 10 对应 (1,1)，以此类推。

2. 有效性检查

fun isValidInitial(): Boolean {
    for (i in 0 until 9) {
        val rowSet = mutableSetOf<Int>()
        val colSet = mutableSetOf<Int>()
        val boxSet = mutableSetOf<Int>()
        
        for (j in 0 until 9) {
            // 检查行
            if (board[i][j] != 0) {
                if (board[i][j] in rowSet) return false
                rowSet.add(board[i][j])
            }
            
            // 检查列
            if (board[j][i] != 0) {
                if (board[j][i] in colSet) return false
                colSet.add(board[j][i])
            }
            
            // 检查 3×3 方格
            val boxRow = (i / 3) * 3 + j / 3
            val boxCol = (i % 3) * 3 + j % 3
            if (board[boxRow][boxCol] != 0) {
                if (board[boxRow][boxCol] in boxSet) return false
                boxSet.add(board[boxRow][boxCol])
            }
        }
    }
    return true
}

这段代码验证初始数独是否满足数独的基本约束。对于每一行（i 从 0 到 8），创建三个集合来分别存储该行、该列和对应 3×3 方格中已出现的数字。然后对每一列（j 从 0 到 8）进行检查：首先检查行约束，如果当前格子不为 0 且已在 rowSet 中出现过，说明该行有重复数字，返回 false；然后检查列约束，使用 board[j][i] 访问第 i 列第 j 行的元素；最后检查 3×3 方格约束，通过 (i / 3) * 3 + j / 3 和 (i % 3) * 3 + j % 3 计算方格内的坐标。如果所有检查都通过，返回 true。

3. 约束检查

fun isValid(row: Int, col: Int, num: Int): Boolean {
    // 检查行
    for (j in 0 until 9) {
        if (board[row][j] == num) return false
    }
    
    // 检查列
    for (i in 0 until 9) {
        if (board[i][col] == num) return false
    }
    
    // 检查 3×3 方格
    val boxRow = (row / 3) * 3
    val boxCol = (col / 3) * 3
    for (i in boxRow until boxRow + 3) {
        for (j in boxCol until boxCol + 3) {
            if (board[i][j] == num) return false
        }
    }
    
    return true
}

这段代码检查在指定位置 (row, col) 放置数字 num 是否满足数独的约束。首先检查该行是否已存在这个数字，通过遍历该行的所有列。然后检查该列是否已存在这个数字，通过遍历该列的所有行。最后检查该数字所在的 3×3 方格是否已存在这个数字，通过计算方格的起始坐标 (boxRow, boxCol)，然后遍历该方格内的所有 9 个格子。如果在任何地方都没有找到重复的数字，返回 true，表示可以在该位置放置这个数字。这个函数是回溯算法的关键，用于剪枝搜索空间。

4. 回溯求解

fun solve(): Boolean {
    steps++
    
    // 找到下一个空格
    for (i in 0 until 9) {
        for (j in 0 until 9) {
            if (board[i][j] == 0) {
                // 尝试填入 1-9
                for (num in 1..9) {
                    if (isValid(i, j, num)) {
                        board[i][j] = num
                        
                        if (solve()) {
                            return true
                        }
                        
                        // 回溯
                        board[i][j] = 0
                    }
                }
                return false
            }
        }
    }
    
    // 所有格子都填满了
    return true
}

这段代码实现了数独求解的核心回溯算法。首先递增 steps 计数器用于统计求解步数。然后遍历整个 9×9 网格，寻找第一个空格（值为 0 的格子）。对于找到的空格，尝试填入 1 到 9 的每个数字。对于每个数字，先检查是否满足约束（使用 isValid 函数），如果满足则填入该数字，然后递归调用 solve() 继续求解。如果递归调用返回 true，说明找到了解，直接返回 true。如果递归调用返回 false，说明这个选择不对，需要回溯，将该格子恢复为 0，继续尝试下一个数字。如果所有 1-9 都尝试过都不行，返回 false。如果遍历完整个网格都没有找到空格，说明所有格子都已填满，返回 true 表示找到了一个完整的解。

5. ASCII 可视化

val originalStr = puzzleStr.chunked(9).mapIndexed { i, row ->
    "  " + row.mapIndexed { j, char ->
        val num = char.toString().toInt()
        if (num == 0) "·" else num.toString()
    }.joinToString(" ") +
    if ((i + 1) % 3 == 0 && i < 8) "\n  ─────────────────" else ""
}.joinToString("\n")

这段代码将数独字符串转换为可视化的 ASCII 格式。首先使用 chunked(9) 将 81 个字符分成 9 组，每组代表一行。然后对每一行使用 mapIndexed 进行处理，其中 i 是行号。对于每一行中的每个字符，将其转换为整数，如果是 0 则显示为"·“（表示空格），否则显示数字本身。使用 joinToString(" ") 在数字之间添加空格。最后，如果当前行是第 3、6、9 行（即 (i + 1) % 3 == 0），就在该行后面添加一条分隔线"─────────────────”，用来区分 3×3 的方格。最后使用 joinToString("\n") 将所有行连接起来，形成一个完整的可视化数独。

---

实战案例

案例：完整的数独求解器

Kotlin 源代码

@OptIn(ExperimentalJsExport::class)
@JsExport
fun sudokuSolver(inputPuzzle: String = "530070000600195000098000060800060003400803001700020006060000280000419005000080079"): String {
    // 解析输入
    val puzzleStr = inputPuzzle.trim().replace(" ", "").replace("\n", "")
    
    if (puzzleStr.length != 81) {
        return "❌ 错误: 数独必须包含 81 个数字"
    }
    
    // 验证输入格式
    if (!puzzleStr.all { it.isDigit() }) {
        return "❌ 错误: 数独只能包含数字 0-9"
    }
    
    // 1. 将字符串转换为 9×9 网格
    val board = Array(9) { IntArray(9) }
    for (i in 0 until 81) {
        board[i / 9][i % 9] = puzzleStr[i].toString().toInt()
    }
    
    // 2. 统计初始信息
    val initialCount = puzzleStr.count { it != '0' }
    val emptyCount = 81 - initialCount
    
    // 3. 检查初始数独的有效性
    fun isValidInitial(): Boolean {
        // ... 检查逻辑
        return true
    }
    
    if (!isValidInitial()) {
        return "❌ 错误: 初始数独无效"
    }
    
    // 4. 检查某个位置是否可以放置数字
    fun isValid(row: Int, col: Int, num: Int): Boolean {
        // ... 检查逻辑
        return true
    }
    
    // 5. 使用回溯算法求解
    var steps = 0
    
    fun solve(): Boolean {
        steps++
        
        for (i in 0 until 9) {
            for (j in 0 until 9) {
                if (board[i][j] == 0) {
                    for (num in 1..9) {
                        if (isValid(i, j, num)) {
                            board[i][j] = num
                            
                            if (solve()) {
                                return true
                            }
                            
                            board[i][j] = 0
                        }
                    }
                    return false
                }
            }
        }
        
        return true
    }
    
    val isSolvable = solve()
    
    // 6. 生成输出
    return "🎮 数独求解器\n" +
           "━━━━━━━━━━━━━━━━━━━━━\n" +
           "1️⃣ 数独信息:\n" +
           "  初始数字: $initialCount 个\n" +
           "  空格数: $emptyCount 个\n" +
           "  总格子: 81 个\n\n" +
           "3️⃣ 求解结果:\n" +
           "  是否可解: ${if (isSolvable) "✅ 是" else "❌ 否"}\n" +
           "  求解步数: $steps 步\n\n" +
           "✅ 求解完成！"
}

这是数独求解器的核心实现函数。函数使用 @OptIn(ExperimentalJsExport::class) 和 @JsExport 注解，使其可以被编译成 JavaScript 并在 ArkTS 中调用。函数首先进行输入验证：使用 trim() 移除首尾空白，使用 replace() 移除所有空格和换行符，然后检查长度是否为 81，检查是否只包含数字。然后将字符串转换为 9×9 网格，统计初始数字个数和空格个数。接着检查初始数独的有效性，如果无效则返回错误信息。然后定义 isValid 函数用于检查约束，定义 solve 函数用于回溯求解。最后生成格式化的输出结果，包含数独信息、求解状态和求解步数。

ArkTS 调用代码（带输入框）

import { sudokuSolver } from './hellokjs';

@Entry
@Component
struct Index {
  @State message: string = '加载中...';
  @State results: string[] = [];
  @State caseTitle: string = '数独求解器';
  @State inputText: string = '530070000600195000098000060800060003400803001700020006060000280000419005000080079';

  aboutToAppear(): void {
    this.loadResults();
  }

  loadResults(): void {
    try {
      const results: string[] = [];
      const algorithmResult: string = sudokuSolver(this.inputText);
      results.push(algorithmResult);
      
      this.results = results;
      this.message = '✓ 求解完成';
    } catch (error) {
      const errorMessage = error instanceof Error ? error.message : String(error);
      this.message = `✗ 错误: ${errorMessage}`;
    }
  }

  build() {
    Column() {
      // 顶部标题栏
      Row() {
        Text('KMP 鸿蒙跨端')
          .fontSize(16)
          .fontWeight(FontWeight.Bold)
          .fontColor(Color.White)
        Spacer()
        Text('Kotlin 案例')
          .fontSize(14)
          .fontColor(Color.White)
      }
      .width('100%')
      .height(50)
      .backgroundColor('#3b82f6')
      .padding({ left: 20, right: 20 })
      .alignItems(VerticalAlign.Center)
      .justifyContent(FlexAlign.SpaceBetween)

      // 案例标题
      Column() {
        Text(this.caseTitle)
          .fontSize(20)
          .fontWeight(FontWeight.Bold)
          .fontColor('#1f2937')
        Text(this.message)
          .fontSize(13)
          .fontColor('#6b7280')
          .margin({ top: 5 })
      }
      .width('100%')
      .padding({ left: 20, right: 20, top: 20, bottom: 15 })
      .alignItems(HorizontalAlign.Start)

      // 输入框区域
      Column() {
        Text('输入数独 (81 个数字, 0 表示空格):')
          .fontSize(14)
          .fontWeight(FontWeight.Bold)
          .fontColor('#1f2937')
          .margin({ bottom: 8 })
        
        TextInput({ placeholder: '输入 81 个数字的数独...', text: this.inputText })
          .width('100%')
          .height(80)
          .padding(12)
          .border({ width: 1, color: '#d1d5db' })
          .borderRadius(6)
          .onChange((value: string) => {
            this.inputText = value
          })
        
        Button('求解')
          .width('100%')
          .height(40)
          .margin({ top: 12 })
          .backgroundColor('#3b82f6')
          .fontColor(Color.White)
          .onClick(() => {
            this.loadResults()
          })
      }
      .width('100%')
      .padding({ left: 16, right: 16, bottom: 16 })

      // 结果显示区域
      Scroll() {
        Column() {
          ForEach(this.results, (result: string) => {
            Column() {
              Text(result)
                .fontSize(13)
                .fontFamily('monospace')
                .fontColor('#374151')
                .width('100%')
                .margin({ top: 10 })
            }
            .width('100%')
            .padding(16)
            .backgroundColor(Color.White)
            .border({ width: 1, color: '#e5e7eb' })
            .borderRadius(8)
            .margin({ bottom: 12 })
          })
        }
        .width('100%')
        .padding({ left: 16, right: 16 })
      }
      .layoutWeight(1)
      .width('100%')

      // 底部按钮区域
      Row() {
        Button('示例')
          .width('48%')
          .height(44)
          .backgroundColor('#10b981')
          .fontColor(Color.White)
          .fontSize(14)
          .onClick(() => {
            this.inputText = '530070000600195000098000060800060003400803001700020006060000280000419005000080079'
            this.loadResults()
          })

        Button('清空')
          .width('48%')
          .height(44)
          .backgroundColor('#6b7280')
          .fontColor(Color.White)
          .fontSize(14)
          .onClick(() => {
            this.inputText = ''
            this.results = []
          })
      }
      .width('100%')
      .padding({ left: 16, right: 16, bottom: 20 })
    }
    .width('100%')
    .height('100%')
    .backgroundColor('#f9fafb')
  }
}

这段 ArkTS 代码是鸿蒙应用的用户界面实现，通过 import 语句导入之前编译的 Kotlin 函数。使用 @State 装饰器定义四个响应式状态变量：message 用于显示状态信息，results 存储求解结果，caseTitle 显示标题，inputText 存储用户输入的数独。aboutToAppear() 生命周期函数在组件加载时自动调用 loadResults() 进行初始求解。loadResults() 方法调用 Kotlin 函数并处理结果，使用 try-catch 捕获异常。build() 方法构建整个 UI 布局，分为五个部分：顶部蓝色标题栏、案例标题和状态信息、用户输入区域（包含文本输入框和求解按钮）、可滚动的结果显示区域以及底部的示例数据和清空按钮。整个界面采用响应式设计，使用 Flexbox 布局和现代化的配色方案。

---

编译过程详解

Kotlin 到 JavaScript 的转换

Kotlin 特性	JavaScript 等价物
Array	数组 []
IntArray	嵌套数组
mutableSetOf	Set 对象
in 操作符	includes() 方法
递归函数	递归函数

关键转换点

1. 多维数组：转换为嵌套数组
2. 集合操作：转换为 Set 对象
3. 递归算法：直接转换为 JavaScript 递归
4. 约束检查：转换为循环检查

---

工具扩展

扩展 1：添加数独生成

fun generateSudoku(difficulty: Int = 3): String {
    val board = Array(9) { IntArray(9) { 0 } }
    
    // 生成完整的有效数独
    fun fillBoard(): Boolean {
        for (i in 0 until 9) {
            for (j in 0 until 9) {
                if (board[i][j] == 0) {
                    for (num in (1..9).shuffled()) {
                        if (isValid(i, j, num)) {
                            board[i][j] = num
                            if (fillBoard()) return true
                            board[i][j] = 0
                        }
                    }
                    return false
                }
            }
        }
        return true
    }
    
    fillBoard()
    
    // 移除数字以创建谜题
    val puzzle = board.map { it.copyOf() }.toTypedArray()
    var removed = 0
    val targetRemoved = difficulty * 9
    
    while (removed < targetRemoved) {
        val i = (0 until 9).random()
        val j = (0 until 9).random()
        
        if (puzzle[i][j] != 0) {
            puzzle[i][j] = 0
            removed++
        }
    }
    
    return puzzle.joinToString("") { row ->
        row.joinToString("") { it.toString() }
    }
}

这个函数实现了数独的自动生成功能。首先创建一个空的 9×9 网格，然后定义 fillBoard 函数来生成一个完整的有效数独。fillBoard 使用回溯算法，对于每个空格，尝试用 1-9 的随机排列来填充。使用 (1..9).shuffled() 可以随机打乱数字顺序，增加生成的多样性。生成完整数独后，通过随机移除数字来创建谜题。移除的数字个数由 difficulty 参数控制，difficulty * 9 表示要移除的数字个数。最后将二维数组转换回一维字符串格式。这个函数可以生成不同难度的数独谜题。

扩展 2：添加难度评分

fun calculateDifficulty(): Int {
    val emptyCount = puzzleStr.count { it == '0' }
    
    return when {
        emptyCount <= 20 -> 5  // 非常困难
        emptyCount <= 30 -> 4  // 困难
        emptyCount <= 40 -> 3  // 中等
        emptyCount <= 50 -> 2  // 简单
        else -> 1              // 非常简单
    }
}

这个函数根据空格的个数来评估数独的难度。空格越多，数独越困难，因为需要填充的位置越多，搜索空间越大。函数首先统计输入字符串中 ‘0’ 的个数（表示空格），然后使用 when 表达式根据空格个数返回难度等级（1-5）。难度评分的标准是：空格个数 ≤ 20 为非常困难（5 级），≤ 30 为困难（4 级），≤ 40 为中等（3 级），≤ 50 为简单（2 级），> 50 为非常简单（1 级）。这个评分方法简单有效，可以帮助用户了解数独的难度。

扩展 3：添加多解检测

fun countSolutions(): Int {
    var count = 0
    
    fun solve(): Boolean {
        for (i in 0 until 9) {
            for (j in 0 until 9) {
                if (board[i][j] == 0) {
                    for (num in 1..9) {
                        if (isValid(i, j, num)) {
                            board[i][j] = num
                            
                            if (solve()) {
                                count++
                                if (count > 1) return true
                            }
                            
                            board[i][j] = 0
                        }
                    }
                    return false
                }
            }
        }
        
        return true
    }
    
    solve()
    return count
}

这个函数用于检测数独是否有多个解。与标准的求解函数不同，这个函数不在找到第一个解时停止，而是继续搜索所有可能的解。使用一个计数器 count 来记录找到的解的个数。当找到一个完整的解时（即遍历完整个网格都没有找到空格），将 count 加 1。为了优化性能，当 count 超过 1 时（即找到了多个解），立即返回 true 停止搜索，因为我们只需要知道是否有多个解，而不需要计算确切的个数。这个函数可以用来验证生成的数独是否有唯一解，这是数独的一个重要特性。

扩展 4：添加求解步骤记录

data class Step(val row: Int, val col: Int, val num: Int)

fun solveWithSteps(): List<Step> {
    val steps = mutableListOf<Step>()
    
    fun solve(): Boolean {
        for (i in 0 until 9) {
            for (j in 0 until 9) {
                if (board[i][j] == 0) {
                    for (num in 1..9) {
                        if (isValid(i, j, num)) {
                            board[i][j] = num
                            steps.add(Step(i, j, num))
                            
                            if (solve()) return true
                            
                            board[i][j] = 0
                            steps.removeAt(steps.size - 1)
                        }
                    }
                    return false
                }
            }
        }
        
        return true
    }
    
    solve()
    return steps
}

这个函数实现了带步骤记录的数独求解功能。首先定义一个数据类 Step，用于记录每一步的操作（行、列、填入的数字）。然后在求解过程中，每当填入一个数字时，就将这一步记录到 steps 列表中。如果这一步最终导致了一个完整的解，就保留这一步；如果这一步需要回溯，就从 steps 列表中移除这一步（使用 removeAt(steps.size - 1) 移除最后一个元素）。最后返回所有的步骤列表。这个函数可以用来生成求解的完整过程，可以用于教学、可视化或调试目的。

---

最佳实践

1. 使用回溯算法

// ✅ 好：使用回溯
fun solve(): Boolean {
    for (i in 0 until 9) {
        for (j in 0 until 9) {
            if (board[i][j] == 0) {
                for (num in 1..9) {
                    if (isValid(i, j, num)) {
                        board[i][j] = num
                        if (solve()) return true
                        board[i][j] = 0
                    }
                }
                return false
            }
        }
    }
    return true
}

// ❌ 不好：蛮力搜索
for (i in 0 until 81) {
    for (num in 1..9) {
        // ...
    }
}

这个最佳实践强调了使用回溯算法的重要性。回溯算法通过约束检查进行剪枝，大大减少了搜索空间。好的做法是：对于每个空格，只尝试满足约束的数字，如果某个选择导致无解，立即回溯，而不是继续尝试。这样可以避免大量无效的搜索。蛮力搜索则没有任何剪枝，会尝试所有可能的组合，效率极低。对于 81 个格子和 9 个数字的组合，蛮力搜索的时间复杂度是 O(9^81)，而回溯算法通过约束检查可以将时间复杂度大大降低。

2. 提前验证初始状态

// ✅ 好：提前检查
if (!isValidInitial()) {
    return "错误: 初始数独无效"
}

// ❌ 不好：求解时才发现
val isSolvable = solve()

这个最佳实践强调了输入验证的重要性。提前检查初始数独的有效性可以避免浪费时间在无效的数独上。如果初始数独本身就违反了数独的约束（例如某行有重复数字），那么无论如何都无法求解。提前检查可以立即返回错误信息，而不是让求解算法徒劳地搜索。这样可以提高用户体验，并节省计算资源。

3. 使用集合检查重复

// ✅ 好：使用 Set
val rowSet = mutableSetOf<Int>()
if (board[i][j] in rowSet) return false
rowSet.add(board[i][j])

// ❌ 不好：线性搜索
for (k in 0 until j) {
    if (board[i][k] == board[i][j]) return false
}

这个最佳实践强调了选择合适数据结构的重要性。使用 Set 检查重复的时间复杂度是 O(1)（平均情况），而线性搜索的时间复杂度是 O(n)。在有效性检查中，需要多次检查重复，使用 Set 可以显著提高性能。此外，使用 in 操作符检查集合中是否存在某个元素比手动循环更简洁、更易读。

4. 分离关注点

// ✅ 好：分离验证和求解
fun isValid(row: Int, col: Int, num: Int): Boolean { ... }
fun solve(): Boolean { ... }

// ❌ 不好：混合在一起
fun solveAndValidate(): Boolean { ... }

这个最佳实践强调了代码的模块化和可维护性。将验证逻辑和求解逻辑分离成两个独立的函数，可以使代码更清晰、更易理解。每个函数只负责一个单一的职责，这样可以更容易地测试、调试和修改。此外，分离的函数可以被重复使用，例如 isValid 函数可以被用于验证初始数独、求解过程中的约束检查等多个地方。

---

常见问题

Q1: 数独求解的时间复杂度是多少？

A: 最坏情况下是 O(9^(nm))，其中 nm 是空格数。但通过约束检查和剪枝，实际性能要好得多。

Q2: 如何优化求解性能？

A:

• 使用约束传播减少搜索空间
• 选择最受限的变量（MRV 启发式）
• 使用前向检查（Forward Checking）

Q3: 如何检测数独是否有多个解？

A: 修改求解函数，不在找到第一个解时停止，而是继续计数。

Q4: 数独的输入格式是什么？

A: 81 个数字的字符串，其中 0 表示空格，1-9 表示已填充的数字。

Q5: 如何生成有效的数独？

A: 先生成一个完整的有效数独，然后随机移除数字，确保只有唯一解。

---

总结

关键要点

• ✅ 使用回溯算法求解数独
• ✅ 提前验证初始状态的合法性
• ✅ 使用约束检查减少搜索空间
• ✅ 分离验证和求解逻辑
• ✅ KMP 能无缝编译到 JavaScript

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net