# Leetcode 787 Solution

https://leetcode.com/problems/sliding-puzzle

## Solution

``````class Solution:
def slidingPuzzle(self, board: List[List[int]]) -> int:
def get_key(board):
return ",".join([str(num) for row in board for num in row])

def is_target(board):
return board[0][0] == 1 and board[0][1] == 2 and board[0][2] == 3 and board[1][0] == 4 and board[1][1] == 5 and board[1][2] == 0

q = collections.deque()
visited = set()

q.append(board)

ans = 0
while q:
s = len(q)

for _ in range(s):
board = q.popleft()

if is_target(board):
return ans

for i, j in itertools.product([0, 1], [0, 1, 2]):
if board[i][j] == 0:
break

directions = [
(0, 1),
(0, -1),
(1, 0),
(-1, 0),
]

for di, dj in directions:
neigh_i = i + di
neigh_j = j + dj

if not (0 <= neigh_i < 2 and 0 <= neigh_j < 3):
continue

newboard = [list(row) for row in board]
newboard[i][j], newboard[neigh_i][neigh_j] = newboard[neigh_i][neigh_j], newboard[i][j]

newkey = get_key(newboard)
if newkey in visited:
continue

q.append(newboard)