滑块游戏

30 May 2013

想必大家小时候都玩过右边这个玩具，在一个 $ 3\times 3 $ 的盒子里面，移动 8 块方块，最终拼成一个图案。这个看似简单的问题，寻找最优解竟然是 NP 完全的，但是本文的目的不是寻找最优解，只是简单的寻找一个解而已。

是否所有排列都有解

假设我们把里面的 8 个小方块全部挖出来，然后再随机装回去，那么这样装回去肯定能够拼回原样么？答案是不能，下面解释一下为什么不能。

首先介绍一个概念，逆序数

設 $ A $ 為一個有 $ n $ 個數字的有序集 $ (n>1) $，其中所有數字各不相同。

如果存在正整數 $ i, j $ 使得 $ 1 \le i \lt j \le n $ 而且 $ A_{ i } \gt A_{ j } $，

則 $ \left< { A }_{ i },{ A }_{ j } \right> $ 這個有序對稱為 $ A $ 的一個逆序對

逆序数就是 $ A $ 中所有逆序对的数量

$ inv(A)=\# \left\{ \left< { A }_{ i },{ A }_{ j } \right> \mid i \lt j \ and \ { A }_{ i } \gt { A }_{ j } \right\} $

为了方便理解，这里举例说明一下：

$ \left\{ 1,2,3,4,5 \right\} $ 五个顺序的数，逆序数为0

$ \left\{ 1,2,4,3,5 \right\} $ 交换3-4，有一个逆序对 $ \left< 4, 3 \right> $，所以逆序数是1

$ \left\{ 1,2,5,4,3 \right\} $ 交换3-5，产生三个逆序对 $ \left< 5, 4 \right>,\left< 5, 3 \right>,\left< 4, 3 \right> $，所以逆序数是3

下面进入正题，首先我们给 8 个方块编号，然后定义其逆序数就是按照行列顺序组成数列的逆序数，例如：

$ inv(\begin{bmatrix} 5 & 8 & 1 \\ & 9 & 2 \\ 4 & 6 & 3 \end{bmatrix})=inv(\left\{ 5,8,1,9,2,4,6,3 \right\} ) $

我们考虑移动方块对其逆序数的影响，每次操作可以把空方块上下左右四个方向其中某个方向的方块移动到空方块的位置

明显左右移动不会影响其逆序数：

$ inv(\begin{bmatrix} 5 & 8 & 1 \\ & 9 & 2 \\ 4 & 6 & 3 \end{bmatrix})=inv(\begin{bmatrix} 5 & 8 & 1 \\ 9 & & 2 \\ 4 & 6 & 3 \end{bmatrix}) $

上下移动相当于把某数字往前移动 2 位，或者往后移动 2 位

$ inv(\begin{bmatrix} 5 & 8 & 1 \\ & 9 & 2 \\ 4 & 6 & 3 \end{bmatrix})=inv(\left\{ 5,8,1,9,2,4,6,3\right\} )\\ inv(\begin{bmatrix} 5 & 8 & 1 \\ 4 & 9 & 2 \\ & 6 & 3 \end{bmatrix})=inv(\left\{ 5,8,1,4,9,2,6,3\right\} ) $

这里只讨论向下移动对逆序数的影响，由于对称性，向上移动相同。向下移动就是把某个数在序列中往后移动两位，由于除了受影响的这三个数，其他数前后的顺序都没有变化，所以不会影响逆序数，我们把这三个数拿出来，分析逆序数的变化：

$ inv\left( \left\{ a,b,c \right\} \right) -inv\left( \left\{ b,c,a \right\} \right) =\begin{cases} -2 & \left\{ a \lt min\left( b,c \right) \right\} \\ 0 & \left\{ min\left( b,c \right) \lt a \lt max\left( b,c \right) \right\} \\ 2 & \left\{ a>max\left( b,c \right) \right\} \end{cases} $

可以看出所有移动都不会改变逆序数的奇偶性，由于最终目标的逆序数是 0，所以如果初始状态的逆序数的是奇数，那么将会出现无解的情况。

解法

首先，我们需要找到一个方法在不改变逆序数的情况下，随意移动空位，明显在同一行移动空位是非常简单的：

$ \begin{bmatrix} 1 & 2 & 3 \\ & 4 & 5 \\ 6 & 7 & 8 \end{bmatrix}\leftrightarrow \begin{bmatrix} 1 & 2 & 3 \\ 4 & & 5 \\ 6 & 7 & 8 \end{bmatrix}\leftrightarrow \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & \\ 6 & 7 & 8 \end{bmatrix} $

下面是在不同行移动空位的方法，经过 12 步移动，我们可以把空位在上下行之间移动：

$ \begin{bmatrix} 1 & 2 & 3 \\ & 4 & 5 \\ 6 & 7 & 8 \end{bmatrix}\leftrightarrow \begin{bmatrix} & 2 & 3 \\ 1 & 4 & 5 \\ 6 & 7 & 8 \end{bmatrix}\leftrightarrow \begin{bmatrix} 2 & & 3 \\ 1 & 4 & 5 \\ 6 & 7 & 8 \end{bmatrix}\\ \leftrightarrow \begin{bmatrix} 2 & 3 & \\ 1 & 4 & 5 \\ 6 & 7 & 8 \end{bmatrix}\leftrightarrow \begin{bmatrix} 2 & 3 & 5 \\ 1 & 4 & \\ 6 & 7 & 8 \end{bmatrix}\leftrightarrow \begin{bmatrix} 2 & 3 & 5 \\ 1 & & 4 \\ 6 & 7 & 8 \end{bmatrix}\\ \leftrightarrow \begin{bmatrix} 2 & & 5 \\ 1 & 3 & 4 \\ 6 & 7 & 8 \end{bmatrix}\leftrightarrow \begin{bmatrix} & 2 & 5 \\ 1 & 3 & 4 \\ 6 & 7 & 8 \end{bmatrix}\leftrightarrow \begin{bmatrix} 1 & 2 & 5 \\ & 3 & 4 \\ 6 & 7 & 8 \end{bmatrix}\\ \leftrightarrow \begin{bmatrix} 1 & 2 & 5 \\ 3 & & 4 \\ 6 & 7 & 8 \end{bmatrix}\leftrightarrow \begin{bmatrix} 1 & 2 & 5 \\ 3 & 4 & \\ 6 & 7 & 8 \end{bmatrix}\leftrightarrow \begin{bmatrix} 1 & 2 & \\ 3 & 4 & 5 \\ 6 & 7 & 8 \end{bmatrix} $

结合使用这里两种方法，我们可以在保证数列不变的情况下，随意调整空位的位置，那么剩下的思路就相当清晰了，我们通过调整空位的位置，使上下移动能够减少逆序数，然后不断减少整个数列的逆序数，最后使得其逆序数为 0，然后把空位调整到要求位置就可以了。

实现

根据上面的思路，实现起来相当简单：

case class Puzzle(val m: Array[Int]) {
  val space = m.indexOf(0)

  def swap(i: Int, j: Int) = {
    println(this)
    Puzzle(m.slice(0,i)++Array(m(j))++m.slice(i+1,j)++Array(m(i))++m.slice(j+1,9))
  }

  def u = swap(space, space+3)
  def d = swap(space-3, space)
  def l = swap(space, space+1)
  def r = swap(space-1, space)

  def moveSpace(i: Int): Puzzle = {
    if (i == space) {
      this
    } else{
      (if (i > space) {
        if (space % 3 == 2) u.r.r.d.l.u.l.d.r.r.u else l
      } else {
        if (space % 3 == 0) d.l.l.u.r.d.r.u.l.l.d else r
      }).moveSpace(i)
    }
  }

  def solve: Puzzle = {
    val seq = m.filter(_ != 0)
    for (i <- 0 until 6) {
      if (seq(i) > seq(i+1))
        return moveSpace(i+3).d.solve
    }
    moveSpace(0)
  }

  override def toString =
    (for(i <- 0 until 3) yield m.slice(i*3, i*3+3).mkString(",")).mkString("\n") + "\n"
}

测试一下：

Puzzle(Array(0,1,2,3,4,5,8,6,7)).solve

结果太长，这里就不贴了，有兴趣可以自己跑一下

math 4