sudoku-go

一个用 Go 语言编写的高性能数独求解器，采用先进的算法和优化技术。

功能

• 🚀 高性能求解: 结合逻辑推理和智能回溯算法
• 🧠 高级推理引擎: 支持 Naked Pairs、Hidden Pairs、X-Wing、Swordfish 等技术
• ⚡ 智能搜索优化: MRV/LCV 启发式 + 并行回溯搜索
• 🔧 命令行工具: 支持 Verbose 模式输出求解过程

安装

确保你已经安装了 Go 1.24.2 或更高版本。

git clone https://github.com/gyyyy/sudoku-go.git
cd sudoku-go
go build -o sudoku main.go

使用

运行程序时，需要提供数独题目作为参数。数独题目是一个 81 个字符的字符串，用 | 分隔行，每行 9 个字符。空位用 # 或 0 或 . 表示，已填数字用 1-9 表示。

基本用法

./sudoku -s "6######52|3#1#2####|###9###3#|###5#19##|#7##3##8#|##62#9###|#8###7###|####5#2#8|56######4"

Verbose 模式

使用 -v 标志启用详细输出，显示求解过程：

./sudoku -s "6######52|3#1#2####|###9###3#|###5#19##|#7##3##8#|##62#9###|#8###7###|####5#2#8|56######4" -v

作为库使用

你也可以将 sudoku-go 作为 Go 包导入到你的项目中使用：

安装包

go get github.com/gyyyy/sudoku-go/sudoku

基本用法

package main

import (
    "fmt"
    "github.com/gyyyy/sudoku-go/sudoku"
)

func main() {
    // 从字符串创建数独题目
    puzzle := "6######52|3#1#2####|###9###3#|###5#19##|#7##3##8#|##62#9###|#8###7###|####5#2#8|56######4"
    sdk, err := sudoku.Create(puzzle)
    if err != nil {
        fmt.Printf("创建数独失败: %v\n", err)
        return
    }

    // 求解数独
    if solved := sudoku.Resolve(sdk); solved {
        fmt.Println("数独已解决！")
        fmt.Println(sdk.Print(false)) // 显示答案
    } else {
        fmt.Println("无法解决此数独")
    }
}

API 说明

创建数独

// 从字符串创建数独
sdk, err := sudoku.Create(puzzleString)

求解数独

// 求解数独，返回是否成功
solved := sudoku.Resolve(sudokuInstance)

检查状态

// 检查数独是否完成
completed := sdk.IsCompleted()

// 获取指定位置的宫
gong := sdk.Gong(row, col) // row, col: 1-3

// 获取指定宫内的单元格
cell := gong.Cell(x, y) // x, y: 1-3

// 获取单元格的值
value := cell.Value() // 返回当前值，0表示空

输出显示

// 显示题目
fmt.Println(sdk.String())

// 显示答案
fmt.Println(sdk.Print(false))

// 显示详细宫信息
fmt.Println(sdk.Detail())

测试

运行测试套件：

go test ./sudoku

运行性能基准测试：

go test -bench=. ./sudoku

性能

基准测试结果：

• 简单数独: ~19.4ms (60 次/秒)
• 困难数独: ~96μs (12,384 次/秒)
• 创建性能: ~16μs (72,164 次/秒)

算法详解

该求解器采用多层次优化策略：

1. 数据结构优化

• 位掩码存储: 使用 uint16 位掩码存储候选数，内存使用减少 50%
• 位运算加速: 候选数操作从哈希表查找优化到位级运算

2. 高级逻辑推理

• 基本推理: 唯一候选数检测
• Naked Pairs: 两单元格的相同候选数对排除
• Hidden Pairs: 隐藏的候选数对关系检测
• X-Wing: 两行两列的矩形模式消除
• Swordfish: 三行三列的复杂模式检测

3. 智能回溯搜索

• MRV 启发式: 优先选择候选数最少的单元格 (Minimum Remaining Values)
• LCV 启发式: 候选值排序，选择约束最小的值 (Least Constraining Value)
• 并行搜索: 多核 CPU 并行尝试分支，提高求解速度

4. 混合求解策略

1. 逻辑推理阶段: 应用所有推理技术尽可能减少候选数
2. 回溯搜索阶段: 当逻辑推理不足时，使用优化回溯算法
3. 并行加速: 困难题目自动启用并行搜索

许可证

MIT License - 详见 LICENSE 文件。