马踏棋盘的算法思考

马踏棋盘

将马随机放在国际象棋的8×8棋盘的某个方格中,马按走棋规则进行移动。 要求每个方格只进入一次,走遍棋盘上全部64个方格。

又是回溯?

这个做法和前面几个问题是差不多的(数独(sudoku)游戏),所以这里就不做太多解释了。 总体来说,就是可选的解空间是8个方向。回溯的代码就不多提了,需要说的是,这里简单的回溯 效率不好,需要跑很久才出结果。我们有什么方式可以优化一下!

贪心是否有效?

首先,我们可以对可供选择的方向进行过滤,对于它相连的8个方向所在的点, 在当前的局面下,假如存在两个点只有一条路可以到达,那么可以直接回溯, 因为无论走哪个方向都不能走完整个棋盘。假如存在一个点,它只有一条路可以到达, 那么下一步必须走这个方向。

但是,即使我们过滤了一些路径,效率还是没有非常大的提升。我们需要考虑一种贪心的思路: 在可选的方向中,优先选择出口最少的目标点。因为优先选择出口少的点, 就可以让出口少的点尽量少,使得最后剩下的点有比较多的入口,这样最终达到目的的概率就会大些。

虽然这个思路,我觉得不好直接证明,不过我修改了一些代码实现,的确效率得到非常大的提升。 就我那个机器,ruby代码,不到1s,64个点的情况就全部处理完了。

代码示例

def init
@arr = Array.new(8)
(0..7).each do |i| @arr[i] = Array.new(8, 0) end
@path = Array.new(64)
@ok = false
@poss = [[-2, 1], [2, 1], [1, 2], [-1, 2], [2, -1], [-2, -1], [-1, -2], [1, -2]]
end
# 判断[x,y]是否在棋盘内并未走过
def valid?(x,y)
x>=0 && x<8 && y>=0 && y<8 && @arr[x][y]==0
end

# 判断当前点有哪些方向可以走
def filter(mark)
posz, mustpos = {}, nil
a, b = @path[mark]
@poss.each do |pos|
axp, bxp = a+pos[0], b+pos[1]
if valid?(axp, bxp)
sz = 0
@poss.each do |ps|
ap, bp = axp+ps[0], bxp+ps[1]
sz+=1 if valid?(ap, bp) # 存在空点
end
if sz>0
posz[pos] = sz
else
mustpos.nil? ? (mustpos = pos) : (return [])
end
end
end
# 对目标点的方向多寡进行排序
mustpos.nil? ? posz.keys.sort {|a,b| posz[a]<=>posz[b]} : [mustpos]
end

def walk(mark)
if mark==63
@ok = true
return
end
a, b = @path[mark]
filter(mark).each do |pos|
rp = [a+pos[0], b+pos[1]]
@path[mark+1] = rp
@arr[rp[0]][rp[1]] = 1
walk(mark+1)
@ok ? return : (@arr[rp[0]][rp[1]] = 0)
end
end

(0..7).each do |i|
(0..7).each do |j|
init
@path[0] = [i,j]
@arr[i][j] = 1
walk(0)
if @ok
@path.each_with_index do |ps, idx|
@arr[ps[0]][ps[1]] = idx
end
@arr.each do |ar| p ar end
puts
else
"no solution"
end
end
end

数独(sudoku)游戏

数独游戏

在9×9格的大九宫格中有9个3×3格的小九宫格,并提供17个以上的数字。 根据这些数字,利用逻辑和推理,在其它的空格上填入1到9的数字。 每个数字在每个小九宫格内只能出现一次,每个数字在每行、每列也只能出现一次。

思路与数据结构

使用回溯法来不断尝试就可以了,可以用一个二维数组来arr[9][9]表示整个数独,其中还没有填上的用0表示。 我们还需要有个方法来判断能否在[i,j]这个格子上填入某个值。 同样还需要一个变量来表示是否已经找到解。另外,我使用了mark(0~80)作为每个格子的序号, 深度搜索的时候就从0开始处理,直到mark=80的时候出现一个解。

ruby代码示例

# 判断能否在[i,j]上填入val
def is_ok?(i,j,val)
(0..8).each do |m|
return false if @arr[i][m] == val && m!=j #判断行不重复
return false if @arr[m][j] == val && m!=i #判断列不重复
end
(i-i%3..i-i%3+2).each do |m|
(j-j%3..j-j%3+2).each do |n|
return false if @arr[m][n] == val && i!=m && j!=n #判断小九宫格不重复
end
end
true
end
# 用来输出数独
def print; (0..8).each { |m| p @arr[m] }; end

# 用来表示是否找到解
@ok = false
# 处理序号为mark开始的格子
def walk(mark)
m, n = mark/9, mark%9
val = @arr[m][n]
# 当前已经有初始值的情况
if val != 0
mark == 80 ? @ok = true : walk(mark+1)
return
end

# 没有初始值的情况
(1..9).each do |v|
if is_ok?(m, n, v)
@arr[m][n] = v
@ok = true and return if mark==80 # 找到一个解
walk(mark+1) #填好值之后,继续深度搜索
return if @ok
end
end
@arr[m][n]=0 # 都处理完,没有找到就恢复
end

walk(0)
@ok ? print : (p "no solution")

回溯法的基本步骤:

  1. a定义问题的解空间
  2. a确定易于搜索的解空间结构
  3. a以深度优先搜索的策略搜索解空间,并在搜索过程中用剪枝函数避免无效搜索

回溯法的基本结构

我们考虑递归的方式(比较容易理解),递推的以后再讨论。

# init
flag = false # 标记是否找到解
u = {} # 已知解, 并假设(x1,x2....xn)为可选的解空间

def backtrack(k)
(x1..xn).each do |x|
if is_ok?(x, k) # 过滤无效的解
u.add(x) # 把x加入已知解u
backtrack(k+1) if u.is_part? # 部分解的情况,继续处理
flag = true and exit if u.is_full? # 找到解并退出
# fail的时候有可能需要对u进行恢复
end
end
# fail的时候有可能需要对u进行恢复
end

backtrack(1) # 从1开始搜索
flag ? p u : "no solution"

简单的楼梯问题

问题描述

有个楼梯,一个人一次可以走1级或2级,那么走上一条100级的楼梯,有多少种不同的走法?

找到规律

先找到规律,从简单情况开始,设f(n)是n级楼梯的走法数量。那么就有:

  1. n=1,肯定只有一种走法,即f(1)=1
  2. n=2,可以一级级走或者一次两级,即f(2)=2
  3. 对于n>2的情况,如果第一次走1级,剩下的楼梯有f(n-1)种走法,如果走2级,剩下的楼梯有f(n-2)种走法。 那么总的走法是f(n)=f(n-1)+f(n-2)。

斐波纳契数列

说白了,这是个斐波纳契数列。计算的时候简单的动态规划即可。下面是简单的ruby源码:

a,b=1,2
98.times {b,a=a+b,b}
p b #=> 573147844013817084101

看,真的是一个天文数字来的。

一笔画游戏

在android上看过一个一笔画的小游戏,规则很简单,要连续一笔,不能重复。 当然,到后面比较难的时候还会限制方向,有些线路必须走多次等等。并不是觉得这有游戏做得多么的好,或者很有创意。 我只是从程序员的角度来看问题,用程序是怎么处理的。 我们只需要尝试所有可能的路径就可以了,这里用了回朔法,是一种优化过的穷举,

先来考虑一下数据结构。我们给所有的点加上编号1-n,所有的连线可以用二维数组表示a[n+1][n+1],值为0表示不可联通, 其他表示需要经过的次数(我实现的时候是采用类似稀疏矩阵的链表表示)。
至于给矩阵增加多一列,主要是考虑处理方便,还考虑到起始点不好确定,所以加个虚拟点,
同时增加虚拟点到其他n个点的连接,这样我们深度遍历的时候从虚拟点开始就可以了。
另外我们需要一个链表来存放走过的路径,还需要一个标记来表示找到路径,无需继续尝试。

初始化的伪代码如下,

(0..n).each do |k| a[0][k]=1 end #虚拟点
@path = [] # 走过的路径
@ok=false # 标记是否完成

接下去我们需要一个回溯算法(参考数独(sudoku)游戏),代码比较简单,这里就不展示代码示例了。

需要注意的是,找到一个可走的路径时(例如从i到j,a[i][j]>0),深度遍历的时候需要对这个值减1,回溯的时候加1就可以了。 而对于走过的路径path,是否需要回退呢? 其实我们关心的是把刚刚走过的路径加入路径的正确位置, 如果选择数组的话,在回溯的时候就不可以不回退了,而对于链表,回退则是必要的。

总体来说,这个游戏的实现是比较简单的,有兴趣的同学可以自己实现一下。

使用svn命令进行每日codediff

什么是codediff?

每日codediff是一项简单易用,行之有效的敏捷实践,可以保证项目进展,让项目中的新人得到学习的机会,让代码规范得到更有效贯彻。 具体做法是,每天早上站立晨会之后,几个人围在一起,使用版本控制工具的diff功能, 逐行浏览前一天提交的代码,提交者对修改的代码进行介绍,讲讲代码是什么功能,为什么要做这样的修改。 当然其他人可以提出异议,并且通常会记录评审意见,以便后续跟踪。

和每周的代码评审相比,每日codediff虽然局限于每个代码片段,但时效性更强,两者互补不足,都是保证代码质量的有效手段。

better svn, better codediff

在我们的项目团队里边,一直也是使用这种方式进行处理。 公司使用的是svn,不过由于环境的限制,svn性能并不是特别理想。 经常把大量时间用在svn log,diff的等待过程中,整个codediff也因此需要比较多时间,有时需要1个多小时。 长此以往,很多人对每日codediff不重视,参与度不高,对于我来说,评审问题也很不好跟踪。

后来我想找一专门为codediff服务的工具,考察了一些开源项目,但总觉得不是特别合适我们团队的需求。 我的要求也很简单,为svn服务,操作简单,便于跟踪,而不需要正规的评审流程。后来,我决定自己开发一个。

我的做法也很简单: 定时从svn上取出最新提交记录,并把相关文件记录到数据库中去。 再弄个网页展示出来,codediff和评审通过网页来进行,

原型一出来,就在团队中试用了一段时间,效果挺好的,通常只需要10来分钟就可以了,大大提高了效率。 现在几个同事还把这东西推广到其他项目中去,反应都还不错,让我着实感到非常有面子:)。

更多细节

后来,有些同事比较感兴趣提交记录是怎么弄出来的。 因为很多人平时只是使用海龟来操作,命令行基本没使用过,所以不清楚也不奇怪。所以解释一下是怎么做的,也是我写这篇博客的重要原因。

整个工程主要使用ruby on railstwitter bootstrap做页面. 通过jruby来跑,定时任务使用quartz-jruby来做,提交记录通过svn命令来获取,我这里主要说说svn命令。

当然首先需要安装svn命令行客户端,然后通过Runtime.exec()来获取输出信息,解析这些信息入库即可。

# 获取最新版本号,使用正则/Last Changed Rev: (\d+)/得到最新版本
svn info http://hustoj.googlecode.com/svn/trunk
# 获取svn log,这个解析比较麻烦,需要用正则分组
svn log -l 1 -v http://hustoj.googlecode.com/svn/trunk
# 获取diff文件,对于更新(M)的文件
svn diff -c 1659 http://hustoj.googlecode.com/svn/trunk/web/admin/contest_list.php
# 获取完整文件,对于增加(A)删除(D)的文件,需要直接取版本
svn cat http://hustoj.googlecode.com/svn/trunk/web/admin/contest_list.php@1655

不过在实际处理的时候,默认的diff取出来的上下文太少,所以我使用了外部diff工具:

svn diff -c 1659 --diff-cmd /usr/bin/diff -x "-U20" http://hustoj.googlecode.com/svn/trunk/web/admin/contest_list.php                    

不过通过程序执行命令获取数据时还存在一点问题:获取不到diff数据。 为了解决这个问题,我再封装了一个shell文件来调用。

#!/bin/bash
svn diff -c $1 --diff-cmd /usr/bin/diff -x "-U$2" $3

总的来说,实现的难度并不大,只是遇到了一些小问题,能够把一个想法化成现实,并且确实提高了效率,还是挺满意的。