Sliding Puzzle

if state == target:

Check if the current state matches the target state.

Detecting the target state allows immediate termination with the minimal move count.

seen = {start}

Initialize the visited set with the start state to avoid revisits.

Tracking visited states prevents infinite loops and redundant processing in BFS.

return moves

Return the number of moves taken to reach the target state.

Returning here ensures the shortest path length is reported as BFS guarantees minimal moves.

state_list[zero], state_list[nei] = state_list[nei], state_list[zero]

Swap zero with the neighbor tile to create a new state.

Swapping simulates sliding the tile into the empty space, producing a valid next configuration.

return -1

Return -1 if the target state is unreachable after exploring all states.

Exhausting the BFS queue without finding the target confirms no solution exists, so returning -1 signals failure.

start = "".join(str(num) for row in board for num in row)

Flatten the 2D board into a single string representing the start state.

Representing the board as a string creates a unique, hashable state that simplifies comparisons and storage in the visited set.

neighbors = {

Define a dictionary mapping zero tile indices to their valid neighbor indices.

Predefining neighbors enables constant-time lookup of valid moves for the zero tile, avoiding repeated computation during BFS.

q = deque([(start, 0)])

Initialize the BFS queue with the start state and zero moves.

Starting BFS with the initial state sets up the exploration frontier and move count tracking.

state, moves = q.popleft()

Dequeue the next state and its move count for processing.

FIFO ordering guarantees BFS explores states layer by layer, preserving shortest path properties.

for nei in neighbors[zero]:

Iterate over all valid neighbor indices for zero's position.

Exploring neighbors generates all possible next states reachable by one move.

if next_state not in seen:

Check if the next state has not been visited before.

Avoiding revisits prevents cycles and redundant BFS expansions.

seen.add(next_state)

Add the next state to the visited set.

Marking states as visited upon enqueueing ensures each state is processed only once.

q.append((next_state, moves + 1))

Enqueue the next state with incremented move count.

Adding new states to the BFS queue expands the search frontier in order of increasing moves.

target = "123450"

Define the target state string representing the solved puzzle.

Having a fixed target string allows quick equality checks to determine if the puzzle is solved.

while q:

Begin BFS loop to process states until queue is empty.

The loop ensures all reachable states are explored in order of increasing moves.

zero = state.index("0")

Find the index of zero in the current state string.

Locating zero is necessary to determine valid moves by swapping with neighbors.

state_list = list(state)

Convert the current state string into a list for swapping.

Strings are immutable in Python; converting to a list allows swapping tiles to generate new states.

next_state = "".join(state_list)

Convert the swapped list back into a string representing the next state.

Re-encoding the state as a string allows efficient hashing and membership checks.

0: [1,3],

List neighbors for zero at index 0.

Specifying neighbors for each zero position encodes the puzzle's movement constraints precisely.

1: [0,2,4],

List neighbors for zero at index 1.

Each neighbor list reflects the puzzle's adjacency rules, critical for generating valid next states.

2: [1,5],

List neighbors for zero at index 2.

Accurate neighbor mapping ensures BFS explores only valid moves.

3: [0,4],

List neighbors for zero at index 3.

Maintaining correct adjacency is essential to prevent invalid state transitions.

4: [1,3,5],

List neighbors for zero at index 4.

This mapping completes the adjacency graph for the zero tile positions.

5: [2,4]

List neighbors for zero at index 5.

Final neighbor list ensures all zero positions have correct adjacency information.

}

Close the neighbors dictionary.

Completes the data structure used for efficient neighbor lookup.