# Sliding Puzzle

## # Solution

### # Layered BFS

``````DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
TARGET_STATE = "123450"
class Solution:
"""
@param board: the given board
@return:  the least number of moves required so that the state of the board is solved
"""
def slidingPuzzle(self, board):
start = self.matrixToString(board)
queue = [start]
vis = set()
res = 0

while queue:
for _ in range(len(queue)):
state = queue.pop(0)
if state == TARGET_STATE:
return res
for next_state in self.getNext(state):
if next_state not in vis:
queue.append(next_state)
res += 1
return -1

def matrixToString(self, state_mat):
state_str = ""
for i in range(2):
for j in range(3):
state_str += str(state_mat[i][j])
return state_str

def getNext(self, state):
pos = state.find('0')
x, y = pos // 3, pos % 3
next_states = []
for dx, dy in DIRECTIONS:
nx, ny = x + dx, y + dy
if 0<=nx<2 and 0<=ny<3:
npos = 3*nx + ny
mn, mx = min(pos, npos), max(pos, npos)
nstate = state[:mn] + state[mx] + state[mn+1:mx] + state[mn] + state[mx+1:]
next_states.append(nstate)
return next_states
``````
Last Updated: 7/19/2020, 3:45:14 PM