生命不息，奋斗不止

发表于 更新于 本文字数： 2k 阅读时长 ≈ 2 分钟

数独求解 go语言版

源代码github地址：https://github.com/smilelc3/sudoku-solver

关于数独wiki介绍：https://zh.wikipedia.org/wiki/%E6%95%B8%E7%8D%A8

一个数独样例

1
2
3
4
5
6
7
8
9
10
11
12
13
+-----------------------------+
|       5 | 3       |         |
| 8       |         |    2    |
|    7    |    1    | 5       |
|---------+---------+---------|
| 4       |       5 | 3       |
|    1    |    7    |       6 |
|       3 | 2       |    8    |
|---------+---------+---------|
|    6    | 5       |       9 |
|       4 |         |    3    |
|         |       9 | 7       |
+-----------------------------+

规则

游戏一般由9个3×3个的九宫格组成。
每一列的数字均须包含 1～9，不能缺少，也不能重复。
每一行的数字均须包含 1～9，不能缺少，也不能重复。
每一宫(粗黑线围起来的区域，通常是 3*3 的九宫格)的数字均须包含 1～9，不能缺少，也不能重复。

算法介绍

实现了两种求数独的算法：

  1. 基于摈弃原则的深度优先搜索算法(dfs)
  2. 优化的舞蹈链算法(Dance Links X)

一、基于摈弃原则的深度优先搜索算法

说明

计算流程如下：

一般正常数独耗时<10ms，算法主要是深度优先搜索，但是做了几点优化：

  1. 优先填写唯一解的单元格
  2. 下一次搜索节点为全局可能性最小单元格（近似贪心）

补充

  • 其实可以做二进制编码优化，时间复杂度降低一个数量级。但主要是为了代码易读，并非为了极致时间效率；

二、优化的舞蹈链算法

主要优化有三点：

  1. 提前优先处理唯一单元格
  2. 优先标记最小可能舞蹈链列元素，极大降低了递归深度（近似贪心）
  3. 先把有数字的格子转换为舞蹈链行，插入到矩阵中，便于计算时优先选中，且仅插入规则合法行，以便减少迭代次数

测试与对比

test 文件夹中，含有各种测试样例，包含号称 最难数独 样例文件7hardest

测试结果基于400次重复求解用时均值，仅具有一定参考

样例文件 深度优先搜索算法 舞蹈链算法 备注
0finished 0 ms 0.557 ms 已完成的数独
1dream 3.027 ms 2.904 ms 全空
2easier 0.010 ms 0.567 ms 仅一个位置未填
3easy 0.750 ms 0.840 ms
4normal 12.16 ms 1.452 ms
5hard 0.829 ms 1.060 ms
6harder 3.871 ms 1.239 ms
7hardest 189.212 ms 18.623 ms 号称最难数独
  • 在某些特殊情况下，深度优先搜索深度低，在较为简单的数独上效率高；
  • 舞蹈链算法稳定高效，适用于精确覆盖类问题，用额外的空间开销与特殊的数据结构，在复杂数独上效果显著。

最难数独运行程序结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
+-----------------------------+
| 8       |         |         |
|       3 | 6       |         |
|    7    |    9    | 2       |
|---------+---------+---------|
|    5    |       7 |         |
|         |    4  5 | 7       |
|         | 1       |    3    |
|---------+---------+---------|
|       1 |         |    6  8 |
|       8 | 5       |    1    |
|    9    |         | 4       |
+-----------------------------+
已读取数独 test/7hardest
+-----------------------------+
| 8  1  2 | 7  5  3 | 6  4  9 |
| 9  4  3 | 6  8  2 | 1  7  5 |
| 6  7  5 | 4  9  1 | 2  8  3 |
|---------+---------+---------|
| 1  5  4 | 2  3  7 | 8  9  6 |
| 3  6  9 | 8  4  5 | 7  2  1 |
| 2  8  7 | 1  6  9 | 5  3  4 |
|---------+---------+---------|
| 5  2  1 | 9  7  4 | 3  6  8 |
| 4  3  8 | 5  2  6 | 9  1  7 |
| 7  9  6 | 3  1  8 | 4  5  2 |
+-----------------------------+
深度优先搜索法所用时间： 189.9914 ms
+-----------------------------+
| 8  1  2 | 7  5  3 | 6  4  9 |
| 9  4  3 | 6  8  2 | 1  7  5 |
| 6  7  5 | 4  9  1 | 2  8  3 |
|---------+---------+---------|
| 1  5  4 | 2  3  7 | 8  9  6 |
| 3  6  9 | 8  4  5 | 7  2  1 |
| 2  8  7 | 1  6  9 | 5  3  4 |
|---------+---------+---------|
| 5  2  1 | 9  7  4 | 3  6  8 |
| 4  3  8 | 5  2  6 | 9  1  7 |
| 7  9  6 | 3  1  8 | 4  5  2 |
+-----------------------------+
舞蹈链法所用时间： 20.0401 ms

Process finished with exit code 0

发表于 更新于 本文字数： 1.2k 阅读时长 ≈ 1 分钟

Tmux 快捷键速查表

启动新会话：

1
tmux [new -s 会话名 -n 窗口名]

恢复会话：

1
tmux at [-t 会话名]

列出所有会话：

1
tmux ls

关闭会话：

1
tmux kill-session -t 会话名

关闭除指定会话外的所有会话：

1
tmux kill-session -a -t 会话名

销毁所有会话并停止Tmux：

1
tmux kill-server

在 Tmux 中，按下 Tmux 前缀 ctrl+b，然后

会话

1
2
3
:new<回车>   启动新会话
s           列出所有会话
$           重命名当前会话

窗口

1
2
3
4
5
6
7
8
c 创建新窗口
w 列出所有窗口
n 后一个窗口
p 前一个窗口
f 查找窗口
, 重命名当前窗口；这样便于识别
. 修改当前窗口编号；相当于窗口重新排序
& 关闭当前窗口

调整窗口排序

1
2
3
:swap-window -s 2 -t 0 交换2号和0号窗口
:swap-window -t 0  交换当前和0号窗口
:move-window -t 0  移动当前窗口到0号

窗格

1
2
3
4
5
6
7
8
9
10
%	垂直分割
"	水平分割
o	前一个窗格
;	后一个窗格
x	关闭窗格
sapce(空格键)	切换布局
q	显示每个窗格是第几个，当数字出现的时候按数字几就选中第几个窗格
{	与上一个窗格交换位置
}	与下一个窗格交换位置
z	切换窗格最大化/最小化

同步窗格

如果您将窗口划分为多个窗格，则可以使用synchronize-panes选项同时向每个窗格发送相同的键盘输入：

1
:setw synchronize-panes [on/off]

你可以指定开启on或停用off，否则重复执行命令会在两者间切换。 这个选项值针对当前个窗口有效，不会影响别的会话和窗口。 完事儿之后再次执行命令来关闭。

调整窗格尺寸

如果你不喜欢默认布局，可以重调窗格的尺寸。虽然这很容易实现，但一般不需要这么干。这几个命令用来调整窗格：

1
2
3
4
5
6
:resize-pane -D          当前窗格向下扩大 1 格
:resize-pane -U          当前窗格向上扩大 1 格
:resize-pane -L          当前窗格向左扩大 1 格
:resize-pane -R          当前窗格向右扩大 1 格
:resize-pane -D 20       当前窗格向下扩大 20 格
:resize-pane -t 2 -L 20  编号为 2 的窗格向左扩大 20 格

杂项

1
2
3
4
d  退出 tmux（tmux 仍在后台运行）
t  窗口中央显示一个数字时钟
?  列出所有快捷键
:  命令提示符

配置选项

1
2
3
4
5
6
7
8
9
10
11
12
# 鼠标支持 - 设置为 on 来启用鼠标
:set -g mouse on

# 设置默认终端模式为 256color
:set -g default-terminal "screen-256color"

# 启用活动警告
:setw -g monitor-activity on
:set -g visual-activity on

# 窗口名列表居中
:set -g status-justify centre

发表于 更新于 本文字数： 19k 阅读时长 ≈ 17 分钟

Natural Image Stitching with the Global Similarity Prior

论文原文

摘要： 本文提出了一种将多个图像拼接在一起的方法，使得拼接图像看起来尽可能自然。我们的方法采用局部扭曲模型，用网格引导每个图像的变形。目标函数用于指定扭曲的所需特征。除了良好的对齐和最小的局部失真之外，我们还在目标函数中添加了全局先验相似性。该先验约束每个图像的扭曲，使其类似于整体的相似变换。选择相似性变换对拼接的自然性至关重要。我们提出了为每个图像选择合适的比例和旋转的方法。所有图像的扭曲被一起解决，以最小化全局失真。综合评估表明，所提出的方法始终优于多种最先进的方法，包括AutoStitch，APAP，SPHP和ANNAP。

关键词： 图像拼接，全景图，图像扭曲

阅读全文 »

发表于 更新于 本文字数： 28k 阅读时长 ≈ 25 分钟

SIFT算法深入理解

SIFT（Scale Invariant Feature Transform），尺度不变特征变换匹配算法，是由David G. Lowe在1999年（《Object Recognition from Local Scale-Invariant Features》）提出的高效区域检测算法，在2004年（《Distinctive Image Features from Scale-Invariant Keypoints》）得以完善。

SIFT特征对旋转、尺度缩放、亮度变化等保持不变性，是非常稳定的局部特征，现在应用很广泛。SIFT算法是将Blob检测，特征矢量生成，特征匹配搜索等步骤结合在一起优化。

阅读全文 »
0%