15-puzzle

问题描述

滑块拼图游戏，共 15 个滑块，一个空位，滑块不能取下来，只能通过移动滑块到空位来改变位置，直到滑块按 1-15 、空位结束。

board

题目要求

随机生成 15-PUZZLE 数码棋盘。
检查问题是不是有解。如果无解，输出无解。
如果有解，输出一个 .txt 文件。文件把解路径上的每张棋盘都按顺序输出。
或者，写一个带可视化界面的程序，在界面上动态展示解路径。

问题求解

15 数码状态空间有16!，采用无信息搜索需要耗费大量时间， A* 算法需要维护 open 表和 close 表，以及排序选择最小代价的结点内存空间消耗过多，采用 IDA* 既节约时间，又减少空间占用（不用判重）。

生成棋盘采用 Fisher–Yates shuffle 随机洗牌算法
判断是否可解: 判断逆序数与原来是否相等
调整状态使其可解原理: 任意交换两个不为零的数，改变排列逆序数
求解时启发函数采用 4*曼哈顿距离/3
后台编程语言为 golang，求解逻辑编写，提供接口及命令行模式
前端采用 js + html + css，负责将结果以动画形式呈现

使用方式

首先需要本地搭建go环境，拉取代码

git clone https://github.com/imyhui/15puzzle.git

或者

go get -v github.com/imyhui/15puzzle

编译
```
cd 15puzzle
go build
```

运行

命令行模式

./15puzzle 
正在求解...,详情见solve.txt

等待运行结束，查看 solve.txt

cat solve.txt
------------
|12| 3|14| 0|
| 9| 8| 4|10|
| 2|11| 5|13|
| 7| 6|15| 1|
-------------
[12 3 14 0 9 8 4 10 2 11 5 13 7 6 15 1]
该 puzzle 有解
解为: DLLLDRRRDLUUULLDRURRDDLULDLDRRUUULDRRDLLLDRRULURDLLURULDRDRDR
cost=[2.430521923s]
------------
|12| 3|14|10|
| 9| 8| 4| 0|
| 2|11| 5|13|
| 7| 6|15| 1|
-------------
------------
|12| 3|14|10|
| 9| 8| 0| 4|
| 2|11| 5|13|
| 7| 6|15| 1|
-------------
...
------------
| 1| 2| 3| 4|
| 5| 6| 7| 8|
| 9|10|11|12|
|13|14|15| 0|
-------------

服务模式
```
./15puzzle server
```
访问 localhost:8080

点击随机生成局面，等待局面完成

点击获取结果
- 若局面不可解，弹窗提醒是否调整, 调整后重新点击获取结果即可
- 也可直接随机生成新局面, 重新求解
  - 查看结果展示动画

线上体验

线上地址

example

参考资料

Authored by @imyhui. Maintained by @imyhui