# 如何用 BFS 算法秒杀各种智力题

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

773. Sliding Puzzle | 🔴 |

Prerequisites

Before reading this article, you need to learn:

Most of you have probably played the sliding puzzle game. Below is a 4x4 sliding puzzle:

There is one empty space in the puzzle, which you can use to move other numbers. Your goal is to rearrange the numbers to achieve a specific order, and you win when you do.

When I was a kid, I also played a puzzle game called "Huarongdao," which is quite similar to the sliding puzzle:

Actually, the sliding puzzle game is also known as the "Digital Huarongdao," and you can see they look quite similar.

So, how do you play these games? I remember there are some tricks, similar to the formulas for solving a Rubik's cube. However, we won't delve into those hair-pulling techniques today. **These puzzle games can all be solved using brute-force search algorithms. So, today we will apply what we've learned and use the BFS algorithm framework to conquer these games.**

### I. Problem Analysis

LeetCode Problem 773, "Sliding Puzzle," addresses this issue. The problem statement is as follows:

You are given a 2x3 sliding puzzle represented by a 2x3 array `board`

. The puzzle contains six numbers, 0 through 5, where **the number 0 represents the empty space**. You can move the numbers around, and you win the game when the `board`

configuration becomes `[[1,2,3],[4,5,0]]`

.

Your task is to write an algorithm to calculate the minimum number of moves required to win the game. If it's impossible to win, return -1.

For example, given the input 2D array `board = [[4,1,2],[5,0,3]]`

, the algorithm should return 5:

If the input is `board = [[1,2,3],[5,4,0]]`

, the algorithm should return -1, as it's impossible to win the game from this configuration.

### II. Thought Analysis

For problems involving finding the minimum number of steps, we should immediately think of the BFS (Breadth-First Search) algorithm.

Transforming this puzzle problem into a BFS problem requires some技巧 (skills). We face the following issues:

In typical BFS algorithms, we start from a point

`start`

and find a path to the`target`

. However, in this puzzle problem, we are not finding a path but continuously swapping numbers. How can we convert this into a BFS problem?Even if we can convert it into a BFS problem, how do we handle the

`start`

and`target`

points? They are both arrays. Putting arrays into a queue and applying the BFS framework seems complicated and inefficient.

First, let's address the first question. **BFS is not just a pathfinding algorithm; it is a brute-force search algorithm**. As long as the problem involves exhaustive enumeration, BFS can be used, and it can find the answer the fastest.

Think about how computers solve problems. There are no special tricks; essentially, they exhaustively enumerate all possible solutions and then find the optimal one among them.

Understanding this, our problem transforms into: **How to enumerate all possible states that can be derived from the current state of board**? This is simple: look at the position of the number 0 and swap it with the numbers above, below, to the left, and to the right:

This essentially becomes a BFS problem. Each time, we find the number 0, swap it with surrounding numbers to form new states, and add these states to the queue... When we first reach the `target`

, we get the minimum number of steps to win the game.

For the second question, our `board`

is just a 2x3 two-dimensional array, so it can be compressed into a one-dimensional string. **The tricky part here is that a two-dimensional array has concepts of 'up, down, left, right'. How do we determine the indices of these directions after compressing it into one dimension**?

For this problem, the input array size is always 2 x 3, so we can manually write out this mapping:

```
// Record the adjacent indices of one-dimensional strings
int[][] neighbor = new int[][]{
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2}
};
```

```
// Record the adjacent indices of one-dimensional strings
int neighbor[6][3] = {
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2}
};
```

```
# Record the adjacent indices of a one-dimensional string
neighbor = [
[1, 3],
[0, 4, 2],
[1, 5],
[0, 4],
[3, 1, 5],
[4, 2]
]
```

```
// Record adjacent indices of one-dimensional strings
neighbor := [][]int{
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2},
}
```

```
// Record the adjacent indices of one-dimensional strings
var neighbor = [
[1, 3],
[0, 4, 2],
[1, 5],
[0, 4],
[3, 1, 5],
[4, 2]
];
```

**This means that in a one-dimensional array, the index i has neighboring indices neighbor[i] in a two-dimensional array**:

So for an `m x n`

two-dimensional array, manually writing its one-dimensional index mapping is impractical. How can we generate this one-dimensional index mapping with code?

By observing the above image, you can see that if an element `e`

in the two-dimensional array has an index `i`

in the one-dimensional array, then the left and right neighboring elements of `e`

in the one-dimensional array have indices `i - 1`

and `i + 1`

, respectively. The upper and lower neighboring elements of `e`

have indices `i - n`

and `i + n`

, where `n`

is the number of columns in the two-dimensional array.

Thus, for an `m x n`

two-dimensional array, we can write a function to generate its `neighbor`

index mapping:

```
int[][] generateNeighborMapping(int m, int n) {
int[][] neighbor = new int[m * n][];
for (int i = 0; i < m * n; i++) {
List<Integer> neighbors = new ArrayList<>();
// if it is not the first column, it has a left neighbor
if (i % n != 0) neighbors.add(i - 1);
// if it is not the last column, it has a right neighbor
if (i % n != n - 1) neighbors.add(i + 1);
// if it is not the first row, it has an upper neighbor
if (i - n >= 0) neighbors.add(i - n);
// if it is not the last row, it has a lower neighbor
if (i + n < m * n) neighbors.add(i + n);
// Java language feature, convert List type to int[] array
neighbor[i] = neighbors.stream().mapToInt(Integer::intValue).toArray();
}
return neighbor;
}
```

```
vector<vector<int>> generateNeighborMapping(int m, int n) {
vector<vector<int>> neighbor(m * n);
for (int i = 0; i < m * n; i++) {
vector<int> neighbors;
// if it's not the first column, it has a left neighbor
if (i % n != 0) neighbors.push_back(i - 1);
// if it's not the last column, it has a right neighbor
if (i % n != n - 1) neighbors.push_back(i + 1);
// if it's not the first row, it has an upper neighbor
if (i - n >= 0) neighbors.push_back(i - n);
// if it's not the last row, it has a lower neighbor
if (i + n < m * n) neighbors.push_back(i + n);
neighbor[i] = neighbors;
}
return neighbor;
}
```

```
def generateNeighborMapping(m: int, n: int) -> List[List[int]]:
neighbor = [[] for _ in range(m * n)]
for i in range(m * n):
neighbors = []
# if not the first column, it has a left neighbor
if i % n != 0: neighbors.append(i - 1)
# if not the last column, it has a right neighbor
if i % n != n - 1: neighbors.append(i + 1)
# if not the first row, it has an upper neighbor
if i - n >= 0: neighbors.append(i - n)
# if not the last row, it has a lower neighbor
if i + n < m * n: neighbors.append(i + n)
neighbor[i] = neighbors
return neighbor
```

```
func generateNeighborMapping(m, n int) [][]int {
neighbor := make([][]int, m*n)
for i := 0; i < m*n; i++ {
neighbors := make([]int, 0)
// if it's not the first column, it has a left neighbor
if i % n != 0 {
neighbors = append(neighbors, i-1)
}
// if it's not the last column, it has a right neighbor
if i % n != n-1 {
neighbors = append(neighbors, i+1)
}
// if it's not the first row, it has an upper neighbor
if i-n >= 0 {
neighbors = append(neighbors, i-n)
}
// if it's not the last row, it has a lower neighbor
if i+n < m*n {
neighbors = append(neighbors, i+n)
}
neighbor[i] = neighbors
}
return neighbor
}
```

```
function generateNeighborMapping(m, n) {
const neighbor = new Array(m * n).fill(0).map(() => []);
for (let i = 0; i < m * n; i++) {
const neighbors = [];
// if not in the first column, has a left neighbor
if (i % n !== 0) neighbors.push(i - 1);
// if not in the last column, has a right neighbor
if (i % n !== n - 1) neighbors.push(i + 1);
// if not in the first row, has an upper neighbor
if (i - n >= 0) neighbors.push(i - n);
// if not in the last row, has a lower neighbor
if (i + n < m * n) neighbors.push(i + n);
neighbor[i] = neighbors;
}
return neighbor;
}
```

At this point, we have completely transformed this problem into a standard BFS issue. With the help of the code framework from the previous article BFS Algorithm Framework, we can directly derive the solution code:

```
class Solution {
public int slidingPuzzle(int[][] board) {
int m = 2, n = 3;
StringBuilder sb = new StringBuilder();
String target = "123450";
// convert the 2x3 array to a string as the starting point of BFS
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sb.append(board[i][j]);
}
}
String start = sb.toString();
// record the adjacent indices of the one-dimensional string
int[][] neighbor = new int[][]{
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2}
};
// ***** BFS algorithm framework starts *****
Queue<String> q = new LinkedList<>();
HashSet<String> visited = new HashSet<>();
// start BFS search from the starting point
q.offer(start);
visited.add(start);
int step = 0;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
String cur = q.poll();
// determine if the target state is reached
if (target.equals(cur)) {
return step;
}
// find the index of number 0
int idx = 0;
for (; cur.charAt(idx) != '0'; idx++) ;
// swap number 0 with its adjacent numbers
for (int adj : neighbor[idx]) {
String new_board = swap(cur.toCharArray(), adj, idx);
// prevent from going back
if (!visited.contains(new_board)) {
q.offer(new_board);
visited.add(new_board);
}
}
}
step++;
}
// ***** BFS algorithm framework ends *****
return -1;
}
private String swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
return new String(chars);
}
}
```

```
class Solution {
public:
int slidingPuzzle(vector<vector<int>>& board) {
int m = 2, n = 3;
string target = "123450";
string start = "";
// convert the 2x3 array to a string as the starting point of BFS
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
start += to_string(board[i][j]);
}
}
// record the adjacent indices of the one-dimensional string
vector<vector<int>> neighbor = {
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2}
};
// ***** BFS algorithm framework starts *****
queue<string> q;
unordered_set<string> visited;
// start BFS search from the starting point
q.push(start);
visited.insert(start);
int step = 0;
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
string cur = q.front();
q.pop();
// determine if the target state is reached
if (target == cur) {
return step;
}
// find the index of number 0
int idx = 0;
for (; cur[idx] != '0'; idx++);
// swap the position of number 0 with its adjacent numbers
for (int adj : neighbor[idx]) {
string new_board = swap(cur, adj, idx);
// prevent going back the same path
if (!visited.count(new_board)) {
q.push(new_board);
visited.insert(new_board);
}
}
}
step++;
}
// ***** BFS algorithm framework ends *****
return -1;
}
string swap(string s, int i, int j) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
return s;
}
};
```

```
class Solution:
def slidingPuzzle(self, board: List[List[int]]) -> int:
m, n = 2, 3
sb = ""
target = "123450"
# convert the 2x3 array to a string as the starting point of BFS
for i in range(m):
for j in range(n):
sb += str(board[i][j])
start = sb
# record the adjacent indices of the one-dimensional string
neighbor = [
[1, 3],
[0, 4, 2],
[1, 5],
[0, 4],
[3, 1, 5],
[4, 2]
]
# ********** BFS algorithm framework starts **********
q = [start]
visited = {start}
step = 0
while q:
sz = len(q)
for _ in range(sz):
cur = q.pop(0)
# determine if the target state is reached
if target == cur:
return step
# find the index of number 0
idx = 0
while cur[idx] != '0':
idx += 1
# swap the position of number 0 with its adjacent numbers
for adj in neighbor[idx]:
new_board = self.swap(list(cur), adj, idx)
# prevent going back the same path
if new_board not in visited:
q.append(new_board)
visited.add(new_board)
step += 1
# ********** BFS algorithm framework ends **********
return -1
def swap(self, chars, i, j):
chars[i], chars[j] = chars[j], chars[i]
return "".join(chars)
```

```
func slidingPuzzle(board [][]int) int {
m, n := 2, 3
sb := ""
target := "123450"
// convert the 2x3 array to a string as the starting point of BFS
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
sb += strconv.Itoa(board[i][j])
}
}
start := sb
// record the adjacent indices of the one-dimensional string
neighbor := [][]int{
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2},
}
// ******** BFS algorithm framework starts ********
q := []string{start}
visited := make(map[string]bool)
step := 0
for len(q) > 0 {
sz := len(q)
for i := 0; i < sz; i++ {
cur := q[0]
q = q[1:]
// determine if the target state is reached
if target == cur {
return step
}
// find the index of the number 0
idx := 0
for cur[idx] != '0' {
idx++
}
// swap the number 0 with its adjacent numbers
for _, adj := range neighbor[idx] {
new_board := swap(cur, adj, idx)
// prevent going back the same way
if !visited[new_board] {
q = append(q, new_board)
visited[new_board] = true
}
}
}
step++
}
// ******** BFS algorithm framework ends ********
return -1
}
func swap(s string, i, j int) string {
chars := []byte(s)
chars[i], chars[j] = chars[j], chars[i]
return string(chars)
}
```

```
var slidingPuzzle = function(board) {
let m = 2, n = 3;
let sb = "";
let target = "123450";
// convert the 2x3 array to a string as the starting point of BFS
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
sb += board[i][j];
}
}
let start = sb;
// record the adjacent indices of the one-dimensional string
let neighbor = [
[1, 3],
[0, 4, 2],
[1, 5],
[0, 4],
[3, 1, 5],
[4, 2]
];
// ******** BFS algorithm framework starts ********
let q = [start];
let visited = new Set();
let step = 0;
while (q.length) {
let sz = q.length;
for (let i = 0; i < sz; i++) {
let cur = q.shift();
// determine if the target state is reached
if (target === cur) {
return step;
}
// find the index of number 0
let idx = 0;
while (cur[idx] !== '0') {
idx++;
}
// swap the position of number 0 with its adjacent numbers
for (let adj of neighbor[idx]) {
let new_board = swap(cur, adj, idx);
// prevent going back
if (!visited.has(new_board)) {
q.push(new_board);
visited.add(new_board);
}
}
}
step++;
}
// ******** BFS algorithm framework ends ********
return -1;
};
function swap(s, i, j) {
let chars = s.split('');
[chars[i], chars[j]] = [chars[j], chars[i]];
return chars.join('');
}
```

With this, the problem is solved. In fact, the framework hasn't changed at all; the approach is the same. We just spent more time converting the sliding puzzle game into a BFS algorithm.

Many puzzle games are like this. Although they may seem particularly clever, they can't withstand brute-force enumeration. Commonly used algorithms for these games are backtracking or BFS algorithms.