4x4 puzzle

def get_moves(status):
    pos, _ = status
    row, col = pos // 4, pos % 4
    if row > 0:  yield "U"
    if row < 3:  yield "D"
    if col > 0:  yield "L"
    if col < 3:  yield "R"
        
def copy_bit(v, b1, b2):
    if v & (1 << b1):
        v |= 1 << b2
    else:
        v &= ~(1 << b2)
    return v
        
def do_move(m, status):
    pos, bits = status
    row, col = pos // 4, pos % 4
    if m == "U":
        pos2 = (row-1)*4 + col
    elif m == "D":
        pos2 = (row+1)*4 + col
    elif m == "L":
        pos2 = row*4 + col - 1
    elif m == "R":
        pos2 = row*4 + col + 1
    return pos2, copy_bit(bits, pos2, pos) 
       
init_status = (0, int("0011001100110011", 2))
target_status = {(0, int("1010010110100101",2)), 
                 (0, int("1010010110100100",2))}

from collections import deque

def bfs(init, target, get_moves, do_move):
    todo = deque([(init, "")])
    visited = {init}
    
    while todo:
        status, route = todo.popleft()
        for m in get_moves(status):
            route2 = route + m
            status2 = do_move(m, status)
            if status2 in target:
                return route2
            if status2 not in visited:
                visited.add(status2)
                todo.append((status2, route2))
                
moves = bfs(init_status, target_status, get_moves, do_move)