解数独算法
1. 引言
数独是一种经典的数字游戏, 玩家需要在一个 9*9 的棋盘上填数字, 保证每一行, 每一列和每一个小九宫格里的数字都是 1-9 且没有重复. 通常盘面上会给出一些提示数让玩家推导.
通常数独的解是唯一的, 但随着提示数的减少, 数独也可以有多个解; 极端情况下, 没有提示数, 数独也是可以解的, 只不过解的数量会非常多. 本文讨论解数独的算法, 并且尝试求出一个数独的所有可行解.
2. 合法的数
我们来看数独的规则:
玩家需要在一个 9*9 的棋盘上填数字, 保证每一行, 每一列和每一个小九宫格里的数字都是 1-9 且没有重复.
首先我们需要根据任意一个给定的棋盘, 快速地得出任意一个空白格子上可填的数. 怎样做到这一点呢? 遍历这个格子所在的行, 列和...
详解寻路算法(2)-生成图
1. 引言
上篇文章 中主要讲解了 A* 算法. 然而 A* 算法只是一个图搜索算法, 我们在游戏中的地图通常是用一些不规则图形定义的一片行走区域, A* 算法并不能识别这样的地图.
因此我们要做的工作就是把一张这样的地图抽象成可用邻接矩阵或邻接链表表示的数学上的图 $G=(V,E)$. 本文介绍两种方法, 可视图(visibility graph) 法和 导航网络(Navigation Meshes)法.
2. 可视图(visibility graph)
对于大多数地图来说, 我们可以看成由一个无限大的行走区域和若干个障碍物组成; 为了简化问题, 障碍物通常都可以看做多边形. 如下图所示:
想象我们处于起始点, 要绕过障碍物到达目标点. 当我们绕过障碍物时, 最短的方式...
编辑距离
题目源自Leetcode: 编辑距离-leetcode
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
解法: 动态规划
这是一道很漂亮的动态规划问题. 我们这样想: 越长的单词求解就越困难, 越短的单词求解就越简单: 长度为1的单词只需比较字母是否相...
详解寻路算法(1)-图搜索
1. 引言
寻路算法广泛应用在各种游戏中. 寻路算法要解决的问题是, 给定一个 "地图"(定义可行走区域), 一个起点, 和一个目标点, 求起点到目标点的最短路径. 解决寻路问题是一个复杂的过程, 涉及到若干个算法. 大体可以分为两个步骤:
把 地图 抽象成 图. 这里的图指的是数学上的图 $G=(V,E)$;
对图进行搜索.
相比图搜索, 把地图抽象成图通常会比较复杂. 这篇文章先介绍介绍图搜索算法. 在下篇文章中, 我会介绍几种把地图抽象成图的方法.
图搜索算法有很多. 在寻路算法中, 主要用到 A* 算法. 这里我会先介绍 Dijkstra 算法, 然后引出 A* 算法. 稍后会看到, 这两种算法很相似: Dijkstra 算法总是搜索最近的, 适用于求解单源对所...
牛顿迭代法求平方根
1.先说结论
$\sqrt{a}$ 可这样求得: 令 $x_0$ 为任意实数, 执行以下迭代式:
$$
x_i = \frac{x_{i-1}+\frac{a}{x_{i-1}}}{2} \tag{1}
$$
迭代若干次, 当 $|x_i-x_{i-1}|$ 小于想要的精度时便可停止迭代. 最终的 $x_i$ 便可视为 $\sqrt{a}$. 根据 (1) 式我们可以很快写出求平方根的代码:
def sqrt(a):
x = 1.0
while True:
pre = x
x = (x + a / x) / 2
if abs(x - pre) < 1e-6:
break
ret...
在Lua中使用装饰器
引言
使用过 Python 的同学都会喜欢上 Python 的装饰器. 它提供一种语法, 对函数进行"声明":
def decorator(f):
def wrapper(x):
print 'call %s' % f.__name__
return "The 2nd power of {0} is {1}".format(x, f(x))
return wrapper
@decorator
def foo(x):
return x ** 2
装饰器本质上只是一种语法糖: 把目标函数作为参数传入装饰器. 巧妙地使用装饰器, 可以让程序变得简洁优雅. 比如说, 声明一个函数是事件, 声明一个函数是远程调用接口, 等等.
在...
调和级数的渐进表示
令 $H_n$ 为第 n 项调和数
$$
H_n=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}=\sum_{i=1}^{n}\frac{1}{i}
$$
证明 $H_n$ 是 $O(\log n)$ 的
证明 如下图所示:
$\sum_{i=1}^{n}\frac{1}{i}$可以看作图中蓝色阴影的面积; 而橙色部分的面积则可以看作函数 $y=\frac{1}{x}$ 的积分 $\int_{0}^{n}\frac{1}{x}\mathrm{d}x$. 因此有
$$
\sum_{i=2}^{n}\frac{1}{i}\lt \int_{0}^{n}\frac{1}{x}\mathrm{d}x=\ln n
$$
$$
\sum...
在Jekyll中使用LaTeX
我准备用 Jekyll + Github page 搭建自己的技术博客. 但是有个问题, 技术文章中不可避免地需要使用到数学公式, Jekyll 原生的 Markdown 解释器总是不能很好地使用 Latex. 通过查阅资料, 我最终解决了这个问题. 下面是我的做法:
禁用 Kramdown 自带的公式解释器:
在 _config.yml 中加入:
kramdown:
math_engine: null
导入 mathjax 的 javascript 代码:
在 _includes 下新建文件 latex.html, 粘贴上以下内容:
<script type="text/x-mathjax-config...
68 post articles, 9 pages.