数独

规则: 9x9 的矩阵，各行、各列、各组（区块）中，填入非重复的 0-9 数字

示例

$ ./sudoku
opts: [MODE] [INIT]
	[MODE]: solve mode combination of [CB][FSR][FA]
	[INIT]: the way to init sudoku puzzle(auto:num|fixed:seq)

$ ./sudoku BFA auto:40
sudoku:

  4  1  .    .  .  6    .  7  .
  2  5  7    .  .  9    .  1  .
  .  .  6    7  .  .    .  4  .

  1  .  2    .  6  5    4  .  .
  6  7  .    .  9  .    1  8  5
  .  .  5    .  .  .    2  .  3

  7  6  3    9  5  .    .  2  .
  .  .  1    .  7  .    9  .  6
  .  .  .    .  1  8    7  3  4

solution[1/2]:

  4  1  8    5  2  6    3  7  9
  2  5  7    4  3  9    6  1  8
  3  9  6    7  8  1    5  4  2

  1  3  2    8  6  5    4  9  7
  6  7  4    3  9  2    1  8  5
  9  8  5    1  4  7    2  6  3

  7  6  3    9  5  4    8  2  1
  8  4  1    2  7  3    9  5  6
  5  2  9    6  1  8    7  3  4

solution[2/2]:

  4  1  8    5  2  6    3  7  9
  2  5  7    4  3  9    6  1  8
  3  9  6    7  8  1    5  4  2

  1  3  2    8  6  5    4  9  7
  6  7  4    2  9  3    1  8  5
  9  8  5    1  4  7    2  6  3

  7  6  3    9  5  4    8  2  1
  8  4  1    3  7  2    9  5  6
  5  2  9    6  1  8    7  3  4

time takes: 0.28800000 ms

说明

程序求解模式开关设有三个选项，可自由组合
- 求解方式：暴力求解，逻辑排除
- 候选元素顺序：快速，顺序，随机
- 求解个数：首个，全部
基本求解思路
1. 构建一个节点状态数组，各节点记录各自的索引，候选数字和当前选项等状态信息
2. 对状态树进行深度优先遍历，直至所有位置填满得到一个解，或全部遍历后无解
关于求解模式开关
- 求解方式
  - 逻辑排除：每填充一处位置，扫描状态数组相关未填充位置，结合已填充信息进行候选排除
  - 暴力穷举：每填充一处位置，扫描对应行/列/组，若无冲突则继续，冲突则回溯尝试下一个候选项
- 候选元素排序
  1. 快速：默认排序，仅保证候选项位于候选列表前部（将空位后移，不改变原有顺序）
  2. 顺序：保证候选元素按确定顺序选中（求解顺序固化）
  3. 随机：候选元素随机排序（求解随机化）
- 求解个数
  1. 首个：得到第一个解后即退出
  2. 全部：得到解后继续求解（不超过预定义最大求解数量）

主要实现

数独相关

基本数据结构
1. unum ar[9][9] 数独
2. unum ar_pos_ct[9][9] 各位置候选元素计数
3. unum ar_pos_avail[9][9][9] 各位置候选元素列表
4. Pos_Node pos_state[9*9]: {id, ck, *p_ct, *p_ar, *avail} 状态数组
5. vector<unum (*)[9]> sols 数独求解结果
生成数独问题： gen_ar(unum ct)
1. 生成一个全零空数独
2. 使用 CRF 模式求解该数独获取一个合规的数独解
3. 对得到的解的随机位置元素清零（按指定个数），结果作为待求解的数独问题

状态相关

同步候选项信息： sync_pos_avail_and_ct(unum seq = 0)
1. 逐个扫描相关行/列/组生成各自候选元素数组 update_pos_avail_and_ct_at_idx(unum i, unum j)
2. 由生成的候选元素数组更新候选计数
初始化状态数组： init_pos_state()
1. 同步节点信息到状态结构体数组 pos_state
2. 对状态数组排序： pos_ct==1 在前，其它按 pos_ct 从小到大排序
3. 候选元素排序：按求解模式 mode.sort 处理

检查相关

求解有效性检查： check_ar(bool allow_zero = false)
1. 非重：逐行、逐列、逐组
2. 非零（如不指定）
检查填充： check_and_fill(unum seq)
- 暴力求解模式： fill_check_for_brute()
  1. 填充前检查待填充数是否与关联已填元素冲突
- 逻辑排除优化： fill_check_for_calc()
  1. 每前进一次，更新未填充关联位置候选元素 ( trim_for_related_rcg(unum i, unum j) )
  2. 每次回退，重扫描关联位置候选项及部分清理 ( update_for_related_rcg(unum i, unum j) .. )

求解过程

// 初始化
sync_pos_avail_and_ct
seq_root = init_pos_state()

// 开始遍历
traverse_state(seq_root)
	for (i= seq_root; i< CT_D2; i++)
		if check_and_fill:
			move_forward
			if check_end:
				save_answer
		else:
			clean
			sel_next || move_backward
			if check_begin:
				end_loop

// 结束
show_answer

简单测试

对于预定义的 8 个数独，通过脚本简单统计求解时间，结果如下

$ ./test.sh
./sudoku BFA fixed:0 - 693.07460000000000000000 ms
./sudoku BRA fixed:0 - 767.43200000000000000000 ms
./sudoku CFA fixed:0 - 1142.88320000000000000000 ms
./sudoku CRA fixed:0 - 1210.75600000000000000000 ms
./sudoku BFA fixed:1 - 1524.42220000000000000000 ms
./sudoku BRA fixed:1 - 3392.64480000000000000000 ms
./sudoku CFA fixed:1 - 1327.57200000000000000000 ms
./sudoku CRA fixed:1 - 1360.46720000000000000000 ms
./sudoku BFA fixed:2 - 54.67980000000000000000 ms
./sudoku BRA fixed:2 - 53.40020000000000000000 ms
./sudoku CFA fixed:2 - 10.87440000000000000000 ms
./sudoku CRA fixed:2 - 11.21540000000000000000 ms
./sudoku BFA fixed:3 - .14140000000000000000 ms
./sudoku BRA fixed:3 - .19220000000000000000 ms
./sudoku CFA fixed:3 - .63620000000000000000 ms
./sudoku CRA fixed:3 - .61320000000000000000 ms
./sudoku BFA fixed:4 - 6.88740000000000000000 ms
./sudoku BRA fixed:4 - 6.82180000000000000000 ms
./sudoku CFA fixed:4 - 18.48160000000000000000 ms
./sudoku CRA fixed:4 - 24.55180000000000000000 ms
./sudoku BFA fixed:5 - .00840000000000000000 ms
./sudoku BRA fixed:5 - .00820000000000000000 ms
./sudoku CFA fixed:5 - .00800000000000000000 ms
./sudoku CRA fixed:5 - .00900000000000000000 ms
./sudoku BFA fixed:6 - .02900000000000000000 ms
./sudoku BRA fixed:6 - .04260000000000000000 ms
./sudoku CFA fixed:6 - .05720000000000000000 ms
./sudoku CRA fixed:6 - .07120000000000000000 ms
./sudoku BFA fixed:7 - .03940000000000000000 ms
./sudoku BRA fixed:7 - .09600000000000000000 ms
./sudoku CFA fixed:7 - .03880000000000000000 ms
./sudoku CRA fixed:7 - .09840000000000000000 ms

随机排序主要目的是随机化求解顺序，与快速排序相比，求解性能方面并不更好也不更差，结果有所体现。相对地快速排序求解顺序较为固定，一定情况下可能出现比较极端的性能差别。排序中，顺序与快速相比，主要是强化确定顺序，实际好像也并未有实质区别，此处便未予测试。

逻辑排除，这里使用的排除逻辑也较为简单，可以添加更多逻辑处理，以减少遍历组合，不过相应的计算量会大很多，综合下来很有可能还不如暴力求解（毕竟数独问题规模较小，且程序对节点求解顺序有过排序处理）。结果中逻辑排除与暴力求解两种方式在不同数独各有胜负，没有明显倾向。

理论上来说，因逻辑排除逐步填充时可利用已有确定信息减少之后的搜索组合，一般不容易出现搜索规模过大的情况，而暴力求解对于自由度较高的数独而言，就容易陷入较深的泥潭，导致极端差的表现，不如逻辑排除来的稳定。

实际测试时，求解高自由度数独时（如只有一个填充的数独： ./sudoku BRF auto:80 ），相比逻辑排除，暴力求解更容易陷入 10s 以上的求解困境，不过对于这种数独而言，确实应该考虑其它求解思路，比如在不直接相关的位置主动而保守地填入部分数字，再行求解（毕竟高自由度解的数量太多，就算全部求出来也没地方放…），如此状态数组的搜索组合可极大降低。

rtgiskard/sudoku

数独

示例

说明

主要实现

求解过程

简单测试