QT拼图还原程序（基于BFS算法-暴力破解）

前言

拼图： 一般是将一幅图像均匀分成NxN块后，去掉其中一块后,打乱其排序，然后再滑动图像进行还原。NxN大小的拼图一共有 $$(N\ast N-1)!$$ 种组合，但是并不是每一种组合都可以进行还原。

暴力破解方法理论上可以找出所有阶平图的最快的还原路径，但是当N增加时计算量会成指数级增加。 Demo实现了 3x3的拼图还原。

BFS

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

拼图算法

原理： 记录每一次进行一次滑动后的所有情况，然后持续迭代

转移参数

std::vector<std::vector<int>> neighbors = {{1, 3}, {0, 4, 2}, {1, 5}, {0, 4, 6}, {1, 3, 7, 5}, {2, 4, 8}, {3, 7}, {4, 6, 8}, {5, 7}};

核心算法

std::list<std::string> PuzzleBox::solvePuzzle() { steps.clear(); using namespace std; queue<pair<string, string>> q; unordered_map<string, string> visited; string start = getModel(); string target = "123456780"; // the garget order q.push({"", start}); visited[start] = ""; while (!q.empty()) { int sz = q.size(); for (int i = 0; i < sz; i++) { auto e = q.front(); string cur = e.second; q.pop(); // check if (target == cur) { // 找到目标，逆向遍历获得最短路径 steps.emplace_back(cur); auto parent = visited.find(e.first); do { if (parent == visited.end()) break; steps.emplace_back(parent->first); parent = visited.find(parent->second); } while (true); return steps; } // 找到数字 0 的索引 int idx = 0; for (; cur[idx] != '0'; idx++) ; // 将数字 0 和相邻的数字交换位置 for (int adj : neighbors[idx]) { string new_board = cur; swap(new_board[adj], new_board[idx]); // 避免进入循环路径 if (visited.find(new_board) == visited.end()) { q.push({cur, new_board}); visited[new_board] = cur; } } } } return {}; }

Demo

代码已经上传到Gitee

后记

加速方案： 采用多线程方式计算每一种可能（但当N 足够大时计算量急剧膨胀，导致无法计算）