八数码实现

闲来无事，把八数码实现一下：BFS,DFS,A*

原理也没什么好说的，记录一下写代码遇到的问题。

• 状态的判重 我的八数码Status类中包含一个String code—也就是当前状态的情况，如“123456780” ->
  1 2 3
  4 5 6
  7 8
  主要是标识出每个状态的 唯一性，第一次写的时候，判重的代码写错了，没有裁剪状态，直接 out of memory，运行只能求出最多15步的复原，而且花了很长时间。
  之后 我意识到了判重，先后采用了 string的hashcode直接生成一个int型的标识，或者直接将这个string来进行判断也可以。完成判重后基本可以在500ms内得到解决。A*的话100ms左右。
  听说还有个康托方法？？？
  八数码的八重境界
• 八数码是否可解
  求逆序数。
  1. 如何求逆序数
     3756412的逆序数
     在3后面比它小的有2个，逆序数为2
     在7后面比它小的有5个，逆序数为5
     在5后面比它小的有3个，逆序数为3
     在6后面比它小的有3个，逆序数为3
     在4后面比它小的有2个，逆序数为2
     在1后面比它小的有0个，逆序数为0
     所以序列的逆序数有2+5+3+3+2=15
  2. 在八数码中 我的目标状态为 [1,2,3,4,5,6,7,8,0]
     1 2 3
     4 5 6
     7 8
     将这个0去掉，它代表这空格。得到他的逆序数为0，是偶数，那么对于任意一个序列，如[5,1,7,4,3,0,8,6,2]
     将其中的0去掉，得到[5,1,7,4,3,8,6,2]可以算得他的逆序数为14，是偶数，所以能够转化到目标状态。