小毛的胡思乱想

凡走过,必留痕迹.

数独(sudoku)游戏

| Comments

数独游戏

在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"

Comments