How to Use BFS to Solve Puzzle Problems

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:

1. 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?

2. 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.