八数码游戏的Ruby实现

        八数码游戏就是通过移动空格把数字从给定的状态移动到目标状态，例如：

初始状态为        目标状态为
2 8 3                   1 2 3
1 6 4                   8    4
7    5                   7 6 5

        程序中用0表示空格，提供了两套状态。

EightNums.rb

---

class EightNums
  #常量定义
  UP    = 1
  DOWN  = -1
  LEFT  = 2
  RIGHT = -2
  ROW   = 0
  COL   = 1
 
  #初始化
  @@InitStat   = [[2,8,3], [1,6,4], [7,0,5]]  #初始状态
  @@TargetStat = [[1,2,3], [8,0,4], [7,6,5]]  #目标状态
  @@Stat       = [[2,8,3], [1,6,4], [7,0,5]]  #初始状态
  @@ZeroPos    = [2, 1]                       #0的位置

# @@InitStat   = [[2,0,3], [1,4,5], [6,7,8]]  #初始状态
# @@TargetStat = [[1,2,3], [4,0,5], [6,7,8]]  #目标状态
# @@Stat       = [[2,0,3], [1,4,5], [6,7,8]]  #初始状态
# @@ZeroPos    = [0, 1]                       #0的位置
   
  def run()
    puts "Initial status:"
    printStat(@@InitStat)
    min = getValue(@@Stat)
    puts "Target status:"
    printStat(@@TargetStat)  
    puts "Initial value: #{min}",' '
    steps = 0
    lastmove = -1       #记录上次移动方向,避免反复
    while steps < 10 do
      flag = false      #是否找到比min小的值
     
      #寻找最小值，确定移动方向
      direction = UP
      [UP, DOWN, LEFT, RIGHT].each do
        |i|
        val = tryMoving(i)
        if val != -1
          if val < min && i != -lastmove then
            min = val
            flag = true
            direction = i
          end
        end
      end
     
      #移动
      moveZero(direction)
      lastmove = direction
      printStat(@@Stat)
      puts "Current value: #{getValue(@@Stat)}"
      if !flag
        min = getValue(@@Stat)
      end
      steps += 1
      break if getValue(@@Stat) == 0
    end
  end
 
private
  def getValue(status)
    value = 0
    for row in 0..2 do
      for col in 0..2 do
        if status[row][col] != @@TargetStat[row][col]
          value += 1
        end
      end
    end
    return value
  end

  #移动0
  def moveZero(direction)
    case direction
      when UP   #上移
        if @@ZeroPos[ROW] != 0
          @@Stat[@@ZeroPos[ROW]][@@ZeroPos[COL]] = @@Stat[@@ZeroPos[ROW] - 1][@@ZeroPos[COL]]
          @@Stat[@@ZeroPos[ROW] - 1][@@ZeroPos[COL]] = 0
          @@ZeroPos[ROW] -= 1
        else
          return -1
        end
      when DOWN #下移
        if @@ZeroPos[ROW] != 2
          @@Stat[@@ZeroPos[ROW]][@@ZeroPos[COL]] = @@Stat[@@ZeroPos[ROW] + 1][@@ZeroPos[COL]]
          @@Stat[@@ZeroPos[ROW] + 1][@@ZeroPos[COL]] = 0
          @@ZeroPos[ROW] += 1
        else
          return -1
        end
      when LEFT #左移
        if @@ZeroPos[COL] != 0
          @@Stat[@@ZeroPos[ROW]][@@ZeroPos[COL]] = @@Stat[@@ZeroPos[ROW]][@@ZeroPos[COL] - 1]
          @@Stat[@@ZeroPos[ROW]][@@ZeroPos[COL] - 1] = 0
          @@ZeroPos[COL] -= 1
        else
          return -1
        end
      when RIGHT  #右移
        if @@ZeroPos[COL] != 2
          @@Stat[@@ZeroPos[ROW]][@@ZeroPos[COL]] = @@Stat[@@ZeroPos[ROW]][@@ZeroPos[COL] + 1]
          @@Stat[@@ZeroPos[ROW]][@@ZeroPos[COL] + 1] = 0
          @@ZeroPos[COL] += 1
        else
          return -1
        end
    end
    return 0
  end
 
  #打印状态
  def printStat(status)
    3.times {|i| print status[i][0], ' ', status[i][1], ' ', status[i][2], "\n"}
  end
 
  #尝试移动，移动不成功则返回-1
  def tryMoving(direction)
    success = moveZero(direction)
    if success == 0
      value = getValue(@@Stat)
      moveZero(-direction)
      return value
    else
      return -1
    end
  end
end

Num = EightNums.new
Num.run()