- 本工程是数独解决方案的库工程,包含 Demo 用例
- 支持 Debug/Release 编译模式
- 整个工程 PC 端编译构建采用 cmake 来管理,支持跨平台(可以在树莓派上正常 cmake+make)
- 移动端 iOS 直接给出 Xcode 工程,Android 则提供 Android.md 用于 ndk-build
- 提供 C#、Go、Java、Lua、NodeJS、PHP 和 Python 共 7 种语言调用数独 Native 动态库的 Demo 用例
- 本库提供求数独解的两种方法,以及求解精确覆盖问题的通用布尔矩阵
- 第一种解法是按照人们解题思路技巧,换用计算机实现,具体思路技巧参考琳琅在线
- 第二种解法为回溯遍历,根据数独规则将数独问题转化为布尔矩阵的精确覆盖问题,并使用 DancingLinks 算法高效求解,这种方式可以算出所有可能的解
- DancingLinks 算法的实现参考陈硕的 Github,此算法的作者是算法大师高德纳(Donald E. Knuth,《计算机程序设计艺术》丛书的作者),这是该算法原文链接,我给导出了pdf 版,原算法将数独问题的转换和求解耦合在一起,为了更加明确解法思路,我将其拆分为两部分,分别是数独问题转换成布尔矩阵和求解布尔矩阵
- 陈硕的CSDN 博客对数独有一个概括性的说明,如何将数独问题转化成布尔矩阵的精确覆盖问题可以参考这篇博客,DancingLinks 求解精确覆盖算法原理可以参考这篇博客
cd Sudoku/
mkdir buildXcode && cd buildXcode
cmake -DCMAKE_INSTALL_PREFIX=./install -G "Xcode" ..
# cmake -DCMAKE_INSTALL_PREFIX=/usr/local/zyk/sudoku -G "Xcode" ..
此时已经在 buildXcode 文件夹下生成了 Xcode 工程,直接打开并编译即可
cd Sudoku/
mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX=./install .. # default is Debug
# for Debug: cmake -DCMAKE_BUILD_TYPE=Debug ..
# for Release: cmake -DCMAKE_BUILD_TYPE=Release ..
# cmake -DCMAKE_INSTALL_PREFIX=/usr/local/zyk/sudoku -DCMAKE_BUILD_TYPE=Release ..
make
# for more details: make VERBOSE=1
make install
make 命令会自动编译好各个模块
cd Sudoku/
mkdir buildVS && cd buildVS
cmake -DCMAKE_INSTALL_PREFIX=./install -G "Visual Studio 15 2017 Win64" ..
# cmake -DCMAKE_INSTALL_PREFIX=D:/Applications/zyk/sudoku -G "Visual Studio 15 2017 Win64" ..
此时已经在 buildVS 文件夹下生成了 Visual Studio 工程,双击打开并编译即可
cd Sudoku/libsudoku/iOS
open sudoku.xcodeproj
编译该 iOS Xcode 工程即可得到 sudoku.a 库
cd Sudoku/libsudoku/Android/
ndk-build
ndk-build clean # clean project
ndk-build -B # rebuild project
编译之后便会有 Sudoku/libsudoku/Android/libs/${APP_ABI}/libsudoku.so 共享库 使用 ndk-build 命令需要先安装 AndroidStudio+AndroidSDK+NDK,然后将 ndk-bundle 路径加到系统 PATH 环境变量中
- data:存放用于测试的数独案例
- demo:用于测试的 Demo,包含多种编程语言
- for-c:C 语言用例(Mac/Linux/Windows)
- for-cs:C#语言用例(Mac/Linux/Windows)
- for-go:Go 语言用例(Mac/Linux)
- for-java:Java 语言用例(Mac/Linux/Windows)
- for-lua:Lua 语言用例(Mac/Linux/Windows)
- for-nodejs:NodeJS 语言用例(通过 FFI 调用布尔矩阵,Mac/Linux)
- for-php:PHP 语言用例(仅 Linux)
- for-python:Python 语言用例(通过 ctypes 调用布尔矩阵,Mac/Linux/Windows)
- libsudoku:数独库
- Android:用于编译 Android 动态库
- include:供外部调用的头文件
- iOS:iOS 静态库的 xcode 工程
- src:源码
- test:测试代码
- oldcode:旧代码,刚学 C++时写的,做个备份记录
- tools:工具脚本
- diff-sudoku:用于比较两个数独的区别
- format-sudoku:数独格式化工具
- SudokuTable.xlsx:辅助填充表,来自林健随笔
- CreateSudoku:创建数独对象,获取句柄用于后续操作,传入读函数、写函数和解题回调函数,读函数用于读取数独题目,写函数用于写出答案,解题回调函数在遇到某个推进解题的操作时会回调通知
- DestroySudoku:创建的反操作,销毁该对象
- VerifySudokuBoard:验证传入的 81 整数组成的数组是否是数独的有效解
- VerifySudoku:验证数独对象内部保存的内容是否为数独的有效解
- GetKnownCount:获取当前数独对象内部的内容中有多少个已知数
- MakeResultString:将数独对象内部记录的内容格式化成一个字符串
- CalculateSudokuAll:计算数独答案,dancing 用于指定是否采用舞蹈链算法来处理,cb 为找到一个可用解时的回调函数,data 为传递给回调函数的透传字段(舞蹈链算法其实是算布尔矩阵的精确覆盖问题,只是数独可以转化成一个布尔矩阵,因此可用此算法来遍历得到所有解)
- 当采用舞蹈链来算数独答案时,SudokuWriteData 回调函数的 type 字段固定为 None,因为此时并没有相关模式(该回调函数被调用顺序也就是解题过程的顺序)
- CreateBoolMatrix:创建一个布尔矩阵对象,传入参数分别为矩阵行数、矩阵列数、矩阵中值为 1 的节点个数
- DestroyBoolMatrix:释放布尔矩阵占用的内存空间
- SetMatrixRowData:设置布尔矩阵的每一行,注意这里需要按照布尔矩阵的行顺序进行设置,data 为一个整数数组,数组中的数字 n 表示这一行中第 n 列的节点值为 1,n 取值范围为[0, 列数-1],size 表示 data 数组的长度
- DancingLinks:触发舞蹈链算法,justOne 表示是否找到一个解就退出,data 为回调函数 cb 的透传字段