This is the 26th day of my participation in Gwen Challenge
Topic describes
This is the 773. Slide puzzle on LeetCode. The difficulty is difficult.
Tag: “BFS”, “Minimum Steps”, “AStar algorithm”, “heuristic Search”
On a 2 x 3 board, there are five tiles, represented by numbers 1 to 5, and a vacancy represented by a 0.
A move is defined as choosing 0 to swap with an adjacent number (up, down, left, and right).
Finally when the board result is [[1,2,3],[4,5,0]] the puzzle board is solved.
Given the initial state of a puzzle board, return the minimum number of moves it can take to solve the puzzle board, or -1 if it cannot be solved.
Example:
Input: board = [[1,2,3],[4,0,5]] output: 1 explanation: swap 0 and 5, step 1 completeCopy the codeInput: board = [[1,2,3],[5,4,0]] output: -1 explanation: there is no way to complete the boardCopy the codeInput: board = [[4,1,2],[5,0,3]] output: 5 explanation: the minimum number of moves to complete the puzzle board is 5, one movement path: not moved: [[4,1,2],[5,0,3]] moved 1 time: ,5,3,1,2 [[4], [0]] move 2 times: [[0], [4,5,3]] move three times: [,0,2 [1], [4,5,3]] move four times: [[1 0], [4,5,3]] move 5 times: [[1, 2, 3], [4,5,0]]Copy the codeInput: board = [[3,2,4],[1,5,0]Copy the codeTip:
- A board is an array of 2 x 3 as described above.
- A board[I][j] is a permutation of [0, 1, 2, 3, 4, 5].
Fundamental analysis
This is a simplified version of the eight-digit problem: change 3∗33 * 33∗3 to 2∗32 * 32∗3, and change the “output path” to “find the minimum number of steps”.
Usually, such problems can be solved by “BFS”, “AStar algorithm” and “Convolution expansion”.
Since the problem is reduced to 2∗32 * 32∗3, we can use the first two solutions.
BFS
For convenience, the original two-dimensional matrix is converted into a string (one-dimensional matrix) for processing.
The benefits brought by this can be directly used as a hash Key, also can be very convenient for “two-dimensional coordinates” and “one-dimensional subscripts” conversion.
Since the lattice is fixed for 2∗32 * 32∗3, any legitimate two-dimensional coordinate (x,y)(x, y)(x,y) and the corresponding one-dimensional subscript IDxidxidx can be transformed as follows:
The rest is the normal BFS process.
Code:
class Solution {
class Node {
String str;
int x, y;
Node(String _str, int _x, int_y) { str = _str; x = _x; y = _y; }}int n = 2, m = 3;
String s, e;
int x, y;
public int slidingPuzzle(int[][] board) {
s = "";
e = "123450";
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
s += board[i][j];
if (board[i][j] == 0) { x = i; y = j; }}}int ans = bfs();
return ans;
}
int[][] dirs = new int[] [] {{1.0}, {-1.0}, {0.1}, {0, -1}};
int bfs(a) {
Deque<Node> d = new ArrayDeque<>();
Map<String, Integer> map = new HashMap<>();
Node root = new Node(s, x, y);
d.addLast(root);
map.put(s, 0);
while(! d.isEmpty()) { Node poll = d.pollFirst();int step = map.get(poll.str);
if (poll.str.equals(e)) return step;
int dx = poll.x, dy = poll.y;
for (int[] di : dirs) {
int nx = dx + di[0], ny = dy + di[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
String nStr = update(poll.str, dx, dy, nx, ny);
if (map.containsKey(nStr)) continue;
Node next = new Node(nStr, nx, ny);
d.addLast(next);
map.put(nStr, step + 1); }}return -1;
}
String update(String cur, int i, int j, int p, int q) {
char[] cs = cur.toCharArray();
char tmp = cs[i * m + j];
cs[i * m + j] = cs[p * m + q];
cs[p * m + q] = tmp;
returnString.valueOf(cs); }}Copy the codeA * algorithm
A heuristic function of A* can be designed directly according to the rules in this case.
For example, for two states A and B, the “theoretical minimum conversion times” can be directly calculated: the sum of the Manhattan distances of the “location” and the “target location” of the numerical values of all positions (i.e., the sum of the absolute values of the horizontal and vertical coordinates).
Note that we only need to calculate the Manhattan distance for the “non-space” position, because the position of the space is uniquely determined by what other digits take up.
A* To find the shortest correct problem: because we measure A statestrThe valuation is based on the target stringe=123450Is the benchmark, so we can only make sureeThe “shortest distance” when leaving the team cannot ensure the “shortest distance” when the middle node leaves the team. Therefore, we cannot decide whether to join the team simply based on whether a node has been in the team, but also based on whether the “minimum distance” of the current node has been updated.
This is critical and is reflected at the code level in the judgment of map.get(nStr) > step + 1.
We know that “heuristic search” is most valuable when A* has A solution, so it would be A huge improvement for A* if we could judge in advance the absence of A solution.
For universal N∗NN * NN∗N digital problems, a necessary and sufficient condition for determining the existence of solutions is that the number of “reverse pairs” is even. If not, there will be no solution and it is only necessary to directly return −1-1−1.
It is not at all difficult to prove the sufficiency and necessity of this conclusion, so it is recommended to remember this conclusion.
Code:
class Solution {
class Node {
String str;
int x, y;
int val;
Node(String _str, int _x, int _y, int_val) { str = _str; x = _x; y = _y; val = _val; }}int f(String str) {
int ans = 0;
char[] cs1 = str.toCharArray(), cs2 = e.toCharArray();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Skip "space" and calculate the Manhattan distance for the remaining values
if (cs1[i * m + j] == '0' || cs2[i * m + j] == '0') continue;
int cur = cs1[i * m + j], next = cs2[i * m + j];
int xd = Math.abs((cur - 1) / 3 - (next - 1) / 3);
int yd = Math.abs((cur - 1) % 3 - (next - 1) % 3); ans += (xd + yd); }}return ans;
}
int n = 2, m = 3;
String s, e;
int x, y;
public int slidingPuzzle(int[][] board) {
s = "";
e = "123450";
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
s += board[i][j];
if (board[i][j] == 0) { x = i; y = j; }}}// Determine in advance if there is no solution
if(! check(s))return -1;
int[][] dirs = new int[] [] {{1.0}, {-1.0}, {0.1}, {0, -1}};
Node root = new Node(s, x, y, f(s));
PriorityQueue<Node> q = new PriorityQueue<>((a,b)->a.val-b.val);
Map<String, Integer> map = new HashMap<>();
q.add(root);
map.put(s, 0);
while(! q.isEmpty()) { Node poll = q.poll();int step = map.get(poll.str);
if (poll.str.equals(e)) return step;
int dx = poll.x, dy = poll.y;
for (int[] di : dirs) {
int nx = dx + di[0], ny = dy + di[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
String nStr = update(poll.str, dx, dy, nx, ny);
if(! map.containsKey(nStr) || map.get(nStr) > step +1) {
Node next = new Node(nStr, nx, ny, step + 1 + f(nStr));
q.add(next);
map.put(nStr, step + 1); }}}return 0x3f3f3f3f; // never
}
String update(String cur, int i, int j, int p, int q) {
char[] cs = cur.toCharArray();
char tmp = cs[i * m + j];
cs[i * m + j] = cs[p * m + q];
cs[p * m + q] = tmp;
return String.valueOf(cs);
}
boolean check(String str) {
char[] cs = str.toCharArray();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n * m; i++) {
if(cs[i] ! ='0') list.add(cs[i] - '0');
}
int cnt = 0;
for (int i = 0; i < list.size(); i++) {
for (int j = i + 1; j < list.size(); j++) {
if(list.get(i) < list.get(j)) cnt++; }}return cnt % 2= =0; }}Copy the codeThe last
This is the No.773 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode as of the start date, some of which have locks, we will first finish all the topics without locks.
In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.
In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .
In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.