A: Water Puzzle
There are two ungraduated buckets, one can hold 9 liters of water, the other can hold 4 liters of water, how to use these two buckets to get 6 liters of water?
Water Puzzle is a classic Puzzle that I’m sure you’ve come across. Here are the steps to solve the problem:
- Fill a 9-liter bucket with water;
- Pour the water from the 9 liter bucket into the 4 liter bucket to fill the 4 liter bucket with water, leaving 5 liters of water left in the 9 liter bucket;
- Empty a 4-liter bucket of water;
- Pour all the water in the 9-liter bucket into the 4-liter bucket, at this point, there is 1 liter of water in the 9-liter bucket, and the 4-liter bucket is full of water;
- Empty a 4-liter bucket of water;
- Pour all the water in the 9-liter bucket into the 4-liter bucket. At this point, the 9-liter bucket is empty and the 4-liter bucket contains 1 liter of water.
- Fill a 9-liter bucket with water;
- Fill the 4l bucket with water by pouring the water from the 9l bucket onto the 4l bucket, leaving 6 liters of water left in the 9l bucket.
To give you a clear picture of the change in the amount of water in each bucket, I give the following table, with the amount of water in 9 liters on the left and the amount of water in 4 liters on the right:
| The capacity of 9 litre drums | The capacity of a 4-litre drum |
|---|---|
| 0 | 0 |
| 9 | 0 |
| 5 | 4 |
| 5 | 0 |
| 1 | 4 |
| 1 | 0 |
| 0 | 1 |
| 9 | 1 |
| 6 | 4 |
For such a problem, have you ever thought of using a program to solve it automatically?
In fact, this is perfectly feasible. Water Puzzle is a problem in the field of graph theory algorithms. In essence, it is a shortest path problem for solving undirected graphs.
The key is, how do we model this problem graphically?
My graph theory modeling method is as follows:
Where, X and Y respectively represent the water in the 9-liter bucket and the water in the 4-liter bucket. We take the current water states of the two buckets (X,Y) as one vertex of the graph, and the arrow pointing from one state to another state as one edge of the graph. And eventually, we’re going to go from 0,0 to 6,Y, or X,6.
There are several ways to change from one state (X,Y) to another:
- Fill 9 l drums to the full, or fill 4 l drums to the full, at which point the state (9,Y) or (X,4) is reached.
- Empty 9 litres of drums, or 4 litres of drums, at which point the state (0,Y) or (X,0) is reached.
- Pour a 9 liter bucket of water into a 4 liter bucket, or pour a 4 liter bucket of water into a 9 liter bucket
The Java code is as follows:
public class WaterPuzzle {
private int end = -1;
private boolean[] visited;
private int[] pre;
public WaterPuzzle(a) {
Queue<Integer> q = new LinkedList<>();
visited = new boolean[100];
pre = new int[100];
q.offer(0);
visited[0] = true;
pre[0] = 0;
while(! q.isEmpty()) {int cur = q.poll();
int x = cur / 10;
int y = cur % 10;
List<Integer> nexts = getNexts(x, y);
for (int next : nexts)
if(! visited[next]) { q.offer(next); visited[next] =true;
pre[next] = cur;
if (next / 10= =6 || next % 10= =6) {
end = next;
return; }}}}private List<Integer> getNexts(int x, int y) {
List<Integer> nexts = new ArrayList<>();
nexts.add(9 * 10 + y);
nexts.add(x * 10 + 4);
nexts.add(0 * 10 + y);
nexts.add(x * 10 + 0);
// x = 9 y = 2 -> x = 7 y = 4
// x = 1 y = 0 -> x = 0 y = 1
int x2y = Math.min(x, 4 - y);
nexts.add((x - x2y) * 10 + y + x2y);
// x = 8 y = 3 -> x = 9 y = 2
// x = 0 y = 3 -> x = 3 y = 0
int y2x = Math.min(9 - x, y);
nexts.add((x + y2x) * 10 + y - y2x);
return nexts;
}
public Iterable<Integer> result(a) {
List<Integer> res = new ArrayList<>();
if (end == -1) return res;
int cur = end;
while(cur ! =0) {
res.add(cur);
cur = pre[cur];
}
res.add(0);
Collections.reverse(res);
return res;
}
public static void main(String[] args) {
WaterPuzzle waterPuzzle = newWaterPuzzle(); System.out.println(waterPuzzle.result()); }}Copy the codeBecause the essence of this problem is to solve the shortest path of an undirected graph, I used BFS traversal.
For the representation of the vertices of the graph, I use the way of 10X + Y, because the maximum value of X is 9 and the maximum value of Y is 4. Therefore, I have created a space of 100 for both the Visited array and the Pre array.
This code runs as follows:
[0, 90, 54, 50, 14, 10, 1, 91, 64]
Copy the codeWe can compare them in the table above:
| The capacity of 9 litre drums | The capacity of a 4-litre drum |
|---|---|
| 0 | 0 |
| 9 | 0 |
| 5 | 4 |
| 5 | 0 |
| 1 | 4 |
| 1 | 0 |
| 0 | 1 |
| 9 | 1 |
| 6 | 4 |
The results are exactly the same.
Ii. River Crossing Puzzle
The River Crossing Puzzle is also a famous Puzzle.
The farmer had to transport the Wolf, sheep, vegetables and himself across the river. Only the farmer can row, and the boat can carry the farmer and one other thing. There is also the thorny problem that sheep will steal vegetables and wolves will eat sheep if the farmer is not watching. Please consider a way in which the farmer can safely arrange these things and himself across the river.
This problem is also a problem in the field of graph theory, and with the foreshadowing of the previous problem, we have made it clear that we should use state information to model this problem in graph theory.
We define a string of length 4 to represent the status of the opposite shore, from left to right, 0 for farmer, 1 for Wolf, 2 for sheep, and 3 for vegetables. The initial state is “0000”, the target state is “1111”, and we are solving the process from the initial state “0000” to the target state “1111”.
We know that wolves and sheep can’t be alone, and sheep and vegetables can’t be alone, so we can list all the impossible situations and define them in an array called deadends, which represents all the situations in which a Wolf eats sheep or a sheep eats vegetables. The array deadends looks like this:
{" 0111 ", "0110", "0011", "1000", "1001", "1100"}Copy the codeThe Java code is as follows:
The farmer needs to transport the Wolf, sheep, vegetables and himself to the other side of the River. * Only the farmer can row, and the boat can carry the farmer and one other thing. * Another tricky problem is that if the farmer is not watching, the sheep will steal the vegetables and the wolves will eat the sheep. * Please consider a way in which the farmer can safely arrange these things and himself across the river. * */
public class RiverCrossingPuzzle {
// We define a string of length 4 to represent the status of the opposite shore, where 0 is farmer, 1 is Wolf, 2 is sheep, and 3 is vegetable
// Find the shortest path from 0000 to 1111
private String initState = "0000";
private String finalState = "1111";
private String[] deadends = {"0111"."0110"."0011"."1000"."1001"."1100"};
// visited, key: indicates whether the state has been traversed, value: indicates the previous state of the key
private Map<String, String> visited;
public RiverCrossingPuzzle(a) {
visited = new HashMap<>();
HashSet<String> deadset = new HashSet<>();
for (String deadend : deadends)
deadset.add(deadend);
Queue<String> q = new LinkedList<>();
q.offer(initState);
visited.put(initState, initState);
while(! q.isEmpty()) { String cur = q.poll(); List<String> nexts = getNexts(cur);for (String next : nexts) {
if(! visited.containsKey(next) && ! deadset.contains(next)) { q.offer(next); visited.put(next, cur);if (next.equals(finalState))
return; }}}}private List<String> getNexts(String cur) {
List<String> res = new ArrayList<>();
char[] chars = cur.toCharArray();
// The farmer is on the left side of the bank. The farmer can cross the river with something else equal to 0, or he can cross the river himself
if (chars[0] = ='0') {
chars[0] = '1';
res.add(new String(chars));
chars[0] = '0';
for (int i = 1; i < chars.length; i++) {
if (chars[i] == '0') {
chars[i] = '1';
chars[0] = '1';
res.add(new String(chars));
chars[0] = '0';
chars[i] = '0'; }}}else {
// The farmer is on the right side of the bank. The farmer can cross the river with something else equal to 1, or cross the river by himself
chars[0] = '0';
res.add(new String(chars));
chars[0] = '1';
for (int i = 1; i < chars.length; i++) {
if (chars[i] == '1') {
chars[i] = '0';
chars[0] = '0';
res.add(new String(chars));
chars[0] = '1';
chars[i] = '1'; }}}return res;
}
public Iterable<String> result(a) {
List<String> res = new ArrayList<>();
String cur = finalState;
while(! cur.equals(initState)) { res.add(cur); cur = visited.get(cur); } res.add(initState); Collections.reverse(res);return res;
}
public static void main(String[] args) {
System.out.println(newRiverCrossingPuzzle().result()); }}Copy the codeThe result of this code execution is:
[0000, 1010, 0010, 1110, 0100, 1101, 0101, 1111]
Copy the codeThe meaning of this result is:
- In the initial state, the farmer, Wolf, sheep and vegetables are all on the left side of the river bank
- The farmer crossed the river with his sheep
- The farmer came back by himself
- The farmer led the Wolf across the river
- The farmer came back with the sheep
- The farmer crossed the river with the vegetables
- The farmer came back by himself
- The farmer took the sheep across the river, and all the goods and the farmer made it to the other side
Three: Sliding Puzzle
This problem is one of LeetCode’s hard-level problems: sliding puzzles
Given a 2 x 3 board, there are five tiles on the board, represented by numbers 1 to 5, and a vacancy represented by 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.
Given an initial state and the final state ([[1,2,3],[4,5,0]]), we can naturally think of using graph theory modeling to solve the problem from an initial state to the final state.
My modeling method is as follows:
The problem itself is not difficult, the complex part of the code is how to represent the information of the puzzle board, a two-dimensional array, as a state.
The state can be a number of type Integer or a String.
For example, if the board’s two-dimensional array information is: [[1,2,3],[4,0,5]], we can represent the corresponding state as the number 123405; Alternatively, we can represent the state as the string “123405”.
Regardless of the conversion method, the information and state of the puzzle board’s two-dimensional array should be consistent and correct.
In this case, I used an Integer number to represent the state of the puzzle board. If you are interested, you can try using a string to represent the state information.
The Java code is as follows:
class Solution {
private boolean[] visited;
private int[] pre;
private int[][] dirs = {{-1.0}, {0.1}, {1.0}, {0, -1}};
public int slidingPuzzle(int[][] board) {
visited = new boolean[550000];
pre = new int[550000];
Queue<Integer> q = new LinkedList<>();
int initState = board2num(board);
if (initState == 123450) return 0;
q.offer(initState);
visited[initState] = true;
pre[initState] = 0;
while(! q.isEmpty()) {int cur = q.poll();
List<Integer> nexts = getNexts(cur);
for (int next : nexts) {
if(! visited[next]) { q.offer(next); visited[next] =true;
pre[next] = pre[cur] + 1;
if (next == 123450)
returnpre[next]; }}}return -1;
}
private List<Integer> getNexts(int cur) {
List<Integer> res = new ArrayList<>();
int[][] board = num2board(cur);
int zeroX = -1;
int zeroY = -1;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 3; j++)
if (board[i][j] == 0) {
zeroX = i;
zeroY = j;
}
for (int d = 0; d < 4; d++) {
int nextX = zeroX + dirs[d][0];
int nextY = zeroY + dirs[d][1];
if(isValid(nextX, nextY)) { swap(board, zeroX, zeroY, nextX, nextY); res.add(board2num(board)); swap(board, zeroX, zeroY, nextX, nextY); }}return res;
}
private boolean isValid(int x, int y) {
return x >= 0 && x < 2 && y >= 0 && y < 3;
}
private void swap(int[][] board, int x1, int y1, int x2, int y2) {
int tmp = board[x1][y1];
board[x1][y1] = board[x2][y2];
board[x2][y2] = tmp;
}
private int[][] num2board(int num) {
int[][] res = new int[2] [3];
for (int i = 0; i < 2; i++)
for (int j = 0; j < 3; j++)
if (i == 0) {
res[i][j] = getDigit(num, i * 2 + j);
} else {
res[i][j] = getDigit(num, i * 2 + j + 1);
}
return res;
}
private int getDigit(int num, int index) {
String s = String.valueOf(num);
if (num > 100000) {
return s.charAt(index) - '0';
} else {
if (index == 0)
return 0;
return s.charAt(index - 1) - '0'; }}private int board2num(int[][] board) {
return board[0] [0] * 100000
+ board[0] [1] * 10000
+ board[0] [2] * 1000
+ board[1] [0] * 100
+ board[1] [1] * 10
+ board[1] [2] * 1; }}Copy the code