数独游戏
在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")
回溯法的基本步骤：
- a定义问题的解空间
- a确定易于搜索的解空间结构
- 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"
