import random class SlideMover: def __init__(self, puzzle): self.puzzle = puzzle self.empty_pos = 0 for i, itm in enumerate(self.puzzle): if itm == 0: self.empty_pos = i break self.step = [] def shuffle(self, cnt): inc = 0 while inc < cnt: r_dir = random.randint(0, 3) if self.move('URDL'[r_dir]): inc += 1 def move(self, dir): delta = 0 if dir == 'U': if self.empty_pos in [0,1,2,3]: return False delta = -4 elif dir == 'R': if self.empty_pos in [3,7,11,15]: return False delta = 1 elif dir == 'D': if self.empty_pos in [12,13,14,15]: return False delta = 4 elif dir == 'L': if self.empty_pos in [0,4,8,12]: return False delta = -1 # swap tmp = self.puzzle[self.empty_pos] self.puzzle[self.empty_pos] = self.puzzle[self.empty_pos + delta] self.puzzle[self.empty_pos + delta] = tmp # update empty position self.empty_pos += delta # record step self.step.append(dir) return True # exception 래퍼 def emove(self, dir): if self.move(dir): pass else: raise Exception('cant move empty_pos:%d, dir:%s'%(self.empty_pos, dir) ) # 빈블록 수평이동 def move_col(self, col): while True: e_row, e_col = divmod(self.empty_pos, 4) c = col - e_col if c > 0: self.emove('R') elif c < 0: self.emove('L') else: break # 빈블록 수직이동 def move_row(self, row): while True: e_row, e_col = divmod(self.empty_pos, 4) r = row - e_row if r > 0: self.emove('D') elif r < 0: self.emove('U') else: break # 수평이동 -> 수직이동 def move_hv(self, dst_pos): if self.empty_pos == dst_pos: return d_row, d_col = divmod(dst_pos, 4) self.move_col(d_col) self.move_row(d_row) # 수직이동 -> 수평이동 def move_vh(self, dst_pos): if self.empty_pos == dst_pos: return d_row, d_col = divmod(dst_pos, 4) self.move_row(d_row) self.move_col(d_col) # 수직(벽을 고려 아래로)-> 수평이동 -> 수직이동 def move_hv_with_wall(self, dst_pos, wall_pos): if self.empty_pos == dst_pos: return e_row, e_col = divmod(self.empty_pos, 4) if wall_pos < 0: self.move_hv(dst_pos) else: w_row, w_col = divmod(wall_pos,4) min_row = w_row + 1 if e_row < min_row: self.move_row(min_row) self.move_hv(dst_pos) def print_puzzle(puzzle): for i, itm in enumerate(puzzle): print('{:>2}, '.format(itm), end='') if i in [3,7,11,15]: print(' ') # enter print('-'*16) # 무식한 풀이법 (휴리스틱) class MusicSolver: def __init__(self, puzzle, mover): self.puzzle = puzzle self.mover = mover # type: SlideMover def solve(self): self.normal_set_block(1, 0, True) self.normal_set_block(2, 1, True) self.normal_set_block(4, 2, True) self.row_set_block(0) self.normal_set_block(5, 4, True) self.normal_set_block(6, 5, True) self.normal_set_block(8, 6, True) self.row_set_block(1) self.normal_set_block(13, 8, True) self.col_set_block(0) self.normal_set_block(14, 9, True) self.col_set_block(1) self.rotate_block() # 원하는 숫자 위치 찾음 def find_num_pos(self, num): for i, itm in enumerate(self.puzzle): if itm == num: return i # 원하는 number를 원하는 위치 dst_pos 로 이동 def normal_set_block(self, num, dst_pos, left_wall): # 일단 목표지점에 빈블록을 갖다놓음 self.mover.move_hv(dst_pos) # 원하는 목표숫자의 위치를 찾음 num_pos = self.find_num_pos(num) # 빈블록을 목표숫자 주변으로 이동 (위, 왼쪽, 오른쪽) self.attach_empty_block(num_pos, left_wall) # 위쪽에 붙은 경우 일단 한번 위로 이동한다. if num_pos - self.mover.empty_pos == 4: self.mover.emove('D') num_pos -= 4 # column을 맞춘다. d_row, d_col = divmod(dst_pos, 4) while True: n_row, n_col = divmod(num_pos, 4) if d_col < n_col: self.move_target('L', num_pos) num_pos += -1 elif d_col > n_col: self.move_target('R', num_pos) num_pos += 1 else: break # row 를 맞춘다. while True: n_row, n_col = divmod(num_pos, 4) if d_row < n_row: self.move_target('U', num_pos) num_pos += -4 elif d_row > n_row: self.move_target('D', num_pos) num_pos += 4 else: break # 빈블록을 목표지점 주변에 붙인다. def attach_empty_block(self, num_pos, left_wall): o_row, o_col = divmod(self.mover.empty_pos, 4) t_row, t_col = divmod(num_pos,4) d_row = 0 d_col = 0 l_limit = 0 if left_wall: l_limit = 1 if o_col - t_col > 0: if t_row-l_limit > o_row: d_row = t_row-1 # UP d_col = t_col else: d_row = t_row #RIGHT d_col = t_col + 1 else: if t_row == o_row: d_row = t_row # LEFT d_col = t_col - 1 else: d_row = t_row-1 # UP d_col = t_col dst_pos = d_row*4 + d_col self.mover.move_vh(dst_pos) # 타겟 이동 (attach 이후) def move_target(self, dir, num_pos): # key : 타겟의 방향 # value-key : empty 가 붙어있는 위치 scripts = { 'U': {'U': 'D', 'R': 'ULD', 'D': 'RUULD', 'L': 'DRRUULD'}, 'L': {'U': 'RDDLLUR', 'R': 'DLLUR', 'D': 'LUR', 'L': 'R'}, 'R': {'U': 'LDDRRUL', 'R': 'L', 'D': 'RUL', 'L': 'DRRUL'}, } diff = num_pos - self.mover.empty_pos k = '' if diff == 4: # UP k = 'U' elif diff == 1: # LEFT k = 'L' elif diff == -1: #RIGHT k = 'R' elif diff == -4: #DOWN k = 'D' else: raise Exception('cant move target') script = scripts[dir][k] for d in script: self.mover.emove(d) # row 끝쪽 특수 패턴 체크 def check_row_pattern(self, row): dtec = False if row == 0: if self.puzzle[2] == 4 and self.puzzle[3] == 3: # detect pattern dtec = True if row == 1: if self.puzzle[6] == 8 and self.puzzle[7] == 7: # detect pattern dtec = True if dtec: for d in 'RULDRDLUURDLD': self.mover.emove(d) return dtec # row 0 인 경우 1,2,4 일단 맞추고 난뒤 # row 1 인 경우 5,6,8 맞추고 난뒤 # row 끝 부분 처리 def row_set_block(self, row): dst_pos = (row+1) * 4 + 2 # 일단 빈블록을 다음 ROW 3번쨰 칸에 위치 시킴 self.mover.move_hv_with_wall(dst_pos, dst_pos-4) # 특수 패턴 체크 if self.check_row_pattern(row): pass # 이동을 이미 시킴 else: self.normal_set_block(row*4 + 3, row*4 + 6, False) # 빈블록을 끝으로 이동 self.mover.move_hv_with_wall(row*4 + 3, row*4 + 6) # Row 맞춤 for d in 'LD': self.mover.emove(d) # row 끝쪽 특수 패턴 체크 def check_col_pattern(self, col): dtec = False if col == 0: if self.puzzle[8] == 13 and self.puzzle[12] == 9: # detect pattern dtec = True if col == 1: if self.puzzle[9] == 14 and self.puzzle[13] == 10: # detect pattern dtec = True if dtec: for d in 'DLURDRULLDRUR': self.mover.emove(d) return dtec def col_set_block(self, col): dst_pos = 9 + col self.mover.move_hv_with_wall(dst_pos, dst_pos-4) # 특수 패턴 체크 if self.check_col_pattern(col): pass # 이동을 이미 시킴 else: self.normal_set_block(dst_pos, dst_pos, True) # 빈블록을 끝으로 이동 self.mover.move_hv_with_wall(12 + col, dst_pos) # Row 맞춤 for d in 'UR': self.mover.emove(d) # 마지막 부분 회전 def rotate_block(self): for d in 'DRULDRULDRULDRUL': if self.puzzle[10] == 11 and self.puzzle[11] == 12 and self.puzzle[14] == 15: break self.mover.emove(d) if __name__ == '__main__': puzzle = list(range(1, 16)) + [0] mover = SlideMover(puzzle) mover.shuffle(80) mover.step = [] print_puzzle(puzzle) # solver = MusicSolver(puzzle, mover) solver.solve() print(len(mover.step), ''.join(mover.step)) print_puzzle(puzzle)