如何求解4*4的数字华容道？

lhgzbxhz

如题，如何编程找出一个4*4数字华容道的最优解？如果求最优解有困难，求一个解即可
只需要给出设计思路、算法或伪代码即可，谢谢大家！

2020/8/3补充：
我考虑过用深搜、广搜或动态规划，但是它们从理论上的最坏情况考虑要走遍所有16!种排列
假设每一种排列占1字节，则最终会占用大约20000GB的内存空间
且不说它超过了64位程序的内存寻址上限，就算是硬盘恐怕也没有这么大
因此用搜索的方法应该是行不通的

weiter

你可以试一下穷举法……当然这不现实

baige

dfs深度优先搜索,当然我不会.
https://blog.csdn.net/yeluoxiang/article/details/102661569

Seawolf

Here is an 2*3 华容道.

1. 在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.
   
2. 
   
3. 一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
   
4. 
   
5. 最终当板board的结果是[[1,2,3],[4,5,0]]谜板被解开。
   
6. 
   
7. 给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
   
8. 
   
9. 示例：
   
10. 
    
11. 输入：board = [[1,2,3],[4,0,5]]
    
12. 输出：1
    
13. 解释：交换 0 和 5 ，1 步完成
    
14. 输入：board = [[1,2,3],[5,4,0]]
    
15. 输出：-1
    
16. 解释：没有办法完成谜板
    
17. 输入：board = [[4,1,2],[5,0,3]]
    
18. 输出：5
    
19. 解释：
    
20. 最少完成谜板的最少移动次数是 5 ，
    
21. 一种移动路径:
    
22. 尚未移动: [[4,1,2],[5,0,3]]
    
23. 移动 1 次: [[4,1,2],[0,5,3]]
    
24. 移动 2 次: [[0,1,2],[4,5,3]]
    
25. 移动 3 次: [[1,0,2],[4,5,3]]
    
26. 移动 4 次: [[1,2,0],[4,5,3]]
    
27. 移动 5 次: [[1,2,3],[4,5,0]]
    
28. 输入：board = [[3,2,4],[1,5,0]]
    
29. 输出：14
    
30. 提示：
    
31. 
    
32. board是一个如上所述的 2 x 3 的数组.
    
33. board[i][j]是一个[0, 1, 2, 3, 4, 5]的排列.

复制代码

1. It is easier for me to think about the board as a string (e.g. "123450" is the solution). I have a map that tells me positions I can move zero from the current one. I also keep track of the zero position, so I do not have to search for it every time.
   
2. 
   
3. DFS
   
4. I am running DFS with memo to store the string and the smallest number of moves to achieve this permutation. Also, I am pruning all searches that go deeper that the best solution found so far.
   
5. 
   
6. unordered_map<int, vector<int>> moves{{0,{1,3}},{1,{0,2,4}},{2,{1,5}},{3,{0,4}},{4,{3,5,1}},{5,{4,2}}};
   
7. void dfs(string s, unordered_map<string, int>& m, int cur_zero, int swap_zero, int cur_move, int& min_moves) {
   
8.   swap(s[cur_zero], s[swap_zero]);
   
9.   if (s == "123450") min_moves = min(min_moves, cur_move);
   
10.   if (cur_move < min_moves && (m[s] == 0 || m[s] > cur_move)) {
    
11.     m[s] = cur_move;
    
12.     for (auto new_zero : moves[swap_zero]) dfs(s, m, swap_zero, new_zero, cur_move + 1, min_moves);
    
13.   }
    
14. }
    
15. int slidingPuzzle(vector<vector<int>>& b, int min_moves = INT_MAX) {
    
16.   string s = to_string(b[0][0]) + to_string(b[0][1]) + to_string(b[0][2])
    
17.     + to_string(b[1][0]) + to_string(b[1][1]) + to_string(b[1][2]);
    
18.   
    
19.   dfs(s, unordered_map<string, int>() = {}, s.find('0'), s.find('0'), 0, min_moves);
    
20.   return min_moves == INT_MAX ? -1 : min_moves;
    
21. }
    
22. BFS
    
23. Even with the pruning, DFS solution is kind of slow for this problem. BFS is much faster, and below is the code using same ideas. Thanks @beetlecamera for good suggestions.
    
24. 
    
25. unordered_map<int, vector<int>> moves{{0,{1,3}},{1,{0,2,4}},{2,{1,5}},{3,{0,4}},{4,{3,5,1}},{5,{4,2}}};
    
26. int slidingPuzzle(vector<vector<int>>& b) {
    
27.   string s = to_string(b[0][0]) + to_string(b[0][1]) + to_string(b[0][2])
    
28.     + to_string(b[1][0]) + to_string(b[1][1]) + to_string(b[1][2]);
    
29. 
    
30.   unordered_map<string, int> m({{s, 0}});
    
31.   queue<pair<string, int>> q({{s, s.find('0')}});
    
32. 
    
33.   for (;!q.empty() && q.front().first != "123450";q.pop()) {
    
34.     for (auto new_zero : moves[q.front().second]) {
    
35.       auto str = q.front().first;
    
36.       swap(str[q.front().second], str[new_zero]);
    
37.       if (m.insert({str, m[q.front().first] + 1}).second) q.push({ str, new_zero });
    
38.     }   
    
39.   }
    
40.   return q.empty() ? -1 : m[q.front().first];
    
41. }
    
42. Follow-up tasks:
    
43. 
    
44. C++ does not have it, but in Java, we could use LinkedHashSet as both the hash and the queue (and get rid of stacks).
    
45. We could improve the performance by using integer instead of string (e.g. 123,450). Hash operations should be faster, but we will need to write our own swap function.
    
46. Use priority_queue to see if it boost the performance. Updated: tried this one. Looks like a hybrid between DFS and BFS. The performance is worse than DFS.

复制代码

lhgzbxhz

baige 发表于 2020-8-2 22:09
dfs深度优先搜索,当然我不会.
https://blog.csdn.net/yeluoxiang/article/details/102661569

4*4华容道理论上来说有16!种排列，深搜需要一个栈来实现递归，这样的话栈太深会导致程序崩溃（从理论上来说）

weiter

要不去查一下4*4华容道的公式然后用代码表示出来？

405794672

数字华容道？啥玩意？