Question

java 数字拼图 算法

就是简单的9格拼图，12345678排序就过关，说一下思想，最好是通解，就是4*4,5×5 都好的

Answer 1

要想得到最优的就需要使用广度优先搜索，九宫的所有排列有9！种，也就是362880种排法，数据量是非常大的，使用广度搜索，需要记住每一个结点的排列形式，要是用数组记录的话会占用很多的内存，可以把数据进行适当的压缩。使用DWORD形式保存，压缩形式是每个数字用3位表示，这样就是3×9＝27个字节，由于8的二进制表示形式1000，不能用3位表示，使用了一个小技巧就是将8表示为000，然后用多出来的5个字表示8所在的位置，就可以用DWORD表示了。用移位和或操作将数据逐个移入，比乘法速度要快点。定义了几个结果来存储遍历到了结果和搜索完成后保存最优路径。