Broad First Search

Sliding Puzzle (Leetcode 773)

We can think of this problem as a graph traversal problem, where each state is a configuration of the puzzle, and the neighbors of a state are the configurations that can be reached by sliding a tile.

from collections import deque

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        # Decompose the 2D list into 1D string

        start_state = "".join(str(x) for row in board for x in row)
        target = "123450"

        neighbor_map = {
            0: [1, 3],
            1: [0, 2, 4],
            2: [1, 5],
            3: [0, 4],
            4: [1, 3, 5],
            5: [2, 4]
        }

        queue = deque()
        queue.append((start_state, 0))
        visited = set()
        visited.add(start_state)

        while queue:
            state, step = queue.popleft()

            if state == target:
                return step

            # Let us find the zero index
            zero_idx = state.index('0')

            for neighbor_idx in neighbor_map[zero_idx]:
                state_list = list(state)

                state_list[zero_idx], state_list[neighbor_idx] = state_list[neighbor_idx], state_list[zero_idx]

                new_state = "".join(state_list)

                if new_state not in visited:
                    visited.add(new_state)

                    queue.append((new_state, step+1))

        return -1

Open the Lock (Leetcode 752)

from collections import deque
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        start = '0000'

        if target == start:
            return 0

        def getNeighbors(state):
            res = []
            for i in range(4):
                x = int(state[i])
                for d in (-1, 1):
                    y = (x + d) % 10 
                    new_state = state[:i] + str(y) + state[i+1:]
                    res.append(new_state)
            return res

        visited = set(deadends)
        queue = deque()

        if start in visited:
            return -1



        queue.append(('0000', 0))
        visited.add('0000')


        while queue:
            state, step = queue.popleft()

            if state == target:
                return step

            for neighbor in getNeighbors(state):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, step + 1))

        return -1