Problem

On an 2 x 3 board, there are five tiles labeled from 1 to 5, and an empty square represented by 0. A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.

The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].

Given the puzzle board board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.

Examples

Example 1:

$$ \begin{array}{|c|c|c|} \hline \colorbox{lightgray}{\textcolor{black}{1}} & \colorbox{lightblue}{\textcolor{black}{2}} & \colorbox{lightgreen}{\textcolor{black}{3}} \\ \hline \colorbox{YellowOrange}{\textcolor{black}{4}} & \colorbox{white}{\textcolor{black}{0}} & \colorbox{orchid}{\textcolor{black}{5}} \\ \hline \end{array} $$

1
2
3

Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Swap the 0 and the 5 in one move.

Example 2:

$$ \begin{array}{|c|c|c|} \hline \colorbox{lightgray}{\textcolor{black}{1}} & \colorbox{lightblue}{\textcolor{black}{2}} & \colorbox{lightgreen}{\textcolor{black}{3}} \\ \hline \colorbox{orchid}{\textcolor{black}{5}} & \colorbox{YellowOrange}{\textcolor{black}{4}} & \colorbox{white}{\textcolor{black}{0}} \\ \hline \end{array} $$

1
2
3

Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: No number of moves will make the board solved.

Example 3:

$$ \begin{array}{|c|c|c|} \hline \colorbox{YellowOrange}{\textcolor{black}{4}} & \colorbox{lightgrey}{\textcolor{black}{1}} & \colorbox{lightblue}{\textcolor{black}{2}} \\ \hline \colorbox{orchid}{\textcolor{black}{5}} & \colorbox{white}{\textcolor{black}{0}} & \colorbox{lightgreen}{\textcolor{black}{3}} \\ \hline \end{array} $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: board = [[4,1,2],[5,0,3]]
Output: 5
Explanation: 5 is the smallest number of moves that solves the board.
An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]

Solution

Method 1 - BFS

To solve this problem, we can use the Breadth-First Search (BFS) approach, which is suitable for finding the shortest path in an unweighted graph. Below are the steps:

  1. Convert Board to String: Transform the 2x3 board into a string to make it easier to handle states and transitions.
  2. Initialisations: Use a queue to perform BFS and a set to keep track of visited states.
  3. BFS Implementation:
    • Dequeue the current state and explore all possible moves by swapping the blank tile (0) with its 4-directionally adjacent tiles.
    • For each move, if the new state equals the goal state, return the depth (number of moves).
    • Otherwise, enqueue the new state if it hasn’t been visited.
  4. Goal Check: If the queue is empty and the goal state hasn’t been reached, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

class Solution {
    public int slidingPuzzle(int[][] board) {
        String goal = "123450";
        String start = boardToString(board);
        
        // Directions: down, up, right, left
        int[][] dirs = {{1, 3}, {-1, -3}, {3, 1}, {-3, -1}};
        
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        q.offer(start);
        visited.add(start);
        
        int moves = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String cur = q.poll();
                if (cur.equals(goal)) return moves;
                
                int zeroIdx = cur.indexOf('0');
                
                for (int[] dir : dirs) {
                    int newIndex = zeroIdx + dir[1];
                    if (newIndex < 0 || newIndex >= 6 || (zeroIdx % 3 == 2 && newIndex % 3 == 0)
                        || (zeroIdx % 3 == 0 && newIndex % 3 == 2)) {
                        continue;
                    }
                    String newBoard = swap(cur, zeroIdx, newIndex);
                    if (!visited.contains(newBoard)) {
                        visited.add(newBoard);
                        q.offer(newBoard);
                    }
                }
            }
            moves++;
        }
        return -1;
    }

    private String boardToString(int[][] board) {
        StringBuilder sb = new StringBuilder();
        for (int[] row : board) {
            for (int num : row) {
                sb.append(num);
            }
        }
        return sb.toString();
    }

    private String swap(String s, int i, int j) {
        char[] arr = s.toCharArray();
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return new String(arr);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

from collections import deque
from typing import List

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        goal: str = '123450'
        start: str = self.board_to_string(board)
        
        # Directions: down, up, right, left
        directions: List[tuple[int, int]] = [(1, 3), (-1, -3), (1, 3), (-3, -1)]
        
        queue: deque[str] = deque([start])
        visited: set[str] = set([start])
        
        moves: int = 0
        while queue:
            for _ in range(len(queue)):
                curr: str = queue.popleft()
                if curr == goal:
                    return moves
                
                zero_index: int = curr.index('0')
                
                for dir1, dir2 in directions:
                    new_index: int = zero_index + dir2
                    if new_index < 0 or new_index >= 6 or (zero_index % 3 == 2 and new_index % 3 == 0) or (zero_index % 3 == 0 and new_index % 3 == 2):
                        continue
                        
                    new_board: str = self.swap(curr, zero_index, new_index)
                    if new_board not in visited:
                        visited.add(new_board)
                        queue.append(new_board)
                        
            moves += 1
        
        return -1

    def board_to_string(self, board: List[List[int]]) -> str:
        return ''.join(map(str, [num for row in board for num in row]))

    def swap(self, s: str, i: int, j: int) -> str:
        lst: list[str] = list(s)
        lst[i], lst[j] = lst[j], lst[i]
        return ''.join(lst)

Complexity

  • ⏰ Time complexity: O((n*m)!) where n*m is the size of the board (2x3 in this case), due to the fact that this problem is equivalent to solving a permutation problem.
  • 🧺 Space complexity: O((n*m)!) for queue and set to store all possible states.