fork download 
  1. import random
  2.  
  3.  
  4. class SlideMover:
  5.     def __init__(self, puzzle):
  6.         self.puzzle = puzzle
  7.         self.empty_pos = 0
  8.         for i, itm in enumerate(self.puzzle):
  9.             if itm == 0:
  10.                 self.empty_pos = i
  11.                 break
  12.         self.step = []
  13.  
  14.     def shuffle(self, cnt):
  15.         inc = 0
  16.         while inc < cnt:
  17.             r_dir = random.randint(0, 3)
  18.             if self.move('URDL'[r_dir]):
  19.                 inc += 1
  20.  
  21.     def move(self, dir):
  22.         delta = 0
  23.         if dir == 'U':
  24.             if self.empty_pos in [0,1,2,3]:
  25.                 return False
  26.             delta = -4
  27.         elif dir == 'R':
  28.             if self.empty_pos in [3,7,11,15]:
  29.                 return False
  30.             delta = 1
  31.         elif dir == 'D':
  32.             if self.empty_pos in [12,13,14,15]:
  33.                 return False
  34.             delta = 4
  35.         elif dir == 'L':
  36.             if self.empty_pos in [0,4,8,12]:
  37.                 return False
  38.             delta = -1
  39.  
  40.         # swap
  41.         tmp = self.puzzle[self.empty_pos]
  42.         self.puzzle[self.empty_pos] = self.puzzle[self.empty_pos + delta]
  43.         self.puzzle[self.empty_pos + delta] = tmp
  44.  
  45.         # update empty position
  46.         self.empty_pos += delta
  47.  
  48.         # record step
  49.         self.step.append(dir)
  50.  
  51.         return True
  52.  
  53.     # exception 래퍼
  54.     def emove(self, dir):
  55.         if self.move(dir):
  56.             pass
  57.         else:
  58.             raise Exception('cant move empty_pos:%d, dir:%s'%(self.empty_pos, dir)  )
  59.  
  60.     # 빈블록 수평이동
  61.     def move_col(self, col):
  62.         while True:
  63.             e_row, e_col = divmod(self.empty_pos, 4)
  64.             c = col - e_col
  65.             if c > 0:
  66.                 self.emove('R')
  67.             elif c < 0:
  68.                 self.emove('L')
  69.             else:
  70.                 break
  71.     # 빈블록 수직이동
  72.     def move_row(self, row):
  73.         while True:
  74.             e_row, e_col = divmod(self.empty_pos, 4)
  75.             r = row - e_row
  76.             if r > 0:
  77.                 self.emove('D')
  78.             elif r < 0:
  79.                 self.emove('U')
  80.             else:
  81.                 break
  82.     # 수평이동 -> 수직이동
  83.     def move_hv(self, dst_pos):
  84.         if self.empty_pos == dst_pos:
  85.             return
  86.         d_row, d_col = divmod(dst_pos, 4)
  87.         self.move_col(d_col)
  88.         self.move_row(d_row)
  89.     # 수직이동 -> 수평이동
  90.     def move_vh(self, dst_pos):
  91.         if self.empty_pos == dst_pos:
  92.             return
  93.         d_row, d_col = divmod(dst_pos, 4)
  94.         self.move_row(d_row)
  95.         self.move_col(d_col)
  96.  
  97.     #  수직(벽을 고려 아래로)-> 수평이동 -> 수직이동
  98.     def move_hv_with_wall(self, dst_pos, wall_pos):
  99.         if self.empty_pos == dst_pos:
  100.             return
  101.         e_row, e_col = divmod(self.empty_pos, 4)
  102.         if wall_pos < 0:
  103.             self.move_hv(dst_pos)
  104.         else:
  105.             w_row, w_col = divmod(wall_pos,4)
  106.             min_row = w_row + 1
  107.             if e_row < min_row:
  108.                 self.move_row(min_row)
  109.             self.move_hv(dst_pos)
  110.  
  111.  
  112. def print_puzzle(puzzle):
  113.     for i, itm in enumerate(puzzle):
  114.         print('{:>2}, '.format(itm), end='')
  115.         if i in [3,7,11,15]:
  116.             print(' ') # enter
  117.     print('-'*16)
  118.  
  119.  
  120.  
  121. # 무식한 풀이법 (휴리스틱)
  122. class MusicSolver:
  123.     def __init__(self, puzzle, mover):
  124.         self.puzzle = puzzle
  125.         self.mover = mover # type: SlideMover
  126.  
  127.     def solve(self):
  128.         self.normal_set_block(1, 0, True)
  129.         self.normal_set_block(2, 1, True)
  130.         self.normal_set_block(4, 2, True)
  131.         self.row_set_block(0)
  132.         self.normal_set_block(5, 4, True)
  133.         self.normal_set_block(6, 5, True)
  134.         self.normal_set_block(8, 6, True)
  135.         self.row_set_block(1)
  136.         self.normal_set_block(13, 8, True)
  137.         self.col_set_block(0)
  138.         self.normal_set_block(14, 9, True)
  139.         self.col_set_block(1)
  140.         self.rotate_block()
  141.  
  142.  
  143.     # 원하는 숫자 위치 찾음
  144.     def find_num_pos(self, num):
  145.         for i, itm in enumerate(self.puzzle):
  146.             if itm == num:
  147.                 return i
  148.  
  149.     # 원하는 number를 원하는 위치 dst_pos 로 이동
  150.     def normal_set_block(self, num, dst_pos, left_wall):
  151.         # 일단 목표지점에 빈블록을 갖다놓음
  152.         self.mover.move_hv(dst_pos)
  153.  
  154.         # 원하는 목표숫자의 위치를 찾음
  155.         num_pos = self.find_num_pos(num)
  156.  
  157.         # 빈블록을 목표숫자 주변으로 이동 (위, 왼쪽, 오른쪽)
  158.         self.attach_empty_block(num_pos, left_wall)
  159.  
  160.         # 위쪽에 붙은 경우 일단  한번 위로 이동한다.
  161.         if num_pos - self.mover.empty_pos == 4:
  162.             self.mover.emove('D')
  163.             num_pos -= 4
  164.  
  165.         # column을 맞춘다.
  166.         d_row, d_col = divmod(dst_pos, 4)
  167.         while True:
  168.             n_row, n_col = divmod(num_pos, 4)
  169.             if d_col < n_col:
  170.                 self.move_target('L', num_pos)
  171.                 num_pos += -1
  172.             elif d_col > n_col:
  173.                 self.move_target('R', num_pos)
  174.                 num_pos += 1
  175.             else:
  176.                 break
  177.         # row 를 맞춘다.
  178.         while True:
  179.             n_row, n_col = divmod(num_pos, 4)
  180.             if d_row < n_row:
  181.                 self.move_target('U', num_pos)
  182.                 num_pos += -4
  183.             elif d_row > n_row:
  184.                 self.move_target('D', num_pos)
  185.                 num_pos += 4
  186.             else:
  187.                 break
  188.  
  189.  
  190.     # 빈블록을 목표지점 주변에 붙인다.
  191.     def attach_empty_block(self, num_pos, left_wall):
  192.         o_row, o_col = divmod(self.mover.empty_pos, 4)
  193.         t_row, t_col = divmod(num_pos,4)
  194.         d_row = 0
  195.         d_col = 0
  196.         l_limit = 0
  197.         if left_wall:
  198.             l_limit = 1
  199.         if o_col - t_col > 0:
  200.             if t_row-l_limit > o_row:
  201.                 d_row = t_row-1 # UP
  202.                 d_col = t_col
  203.             else:
  204.                 d_row = t_row #RIGHT
  205.                 d_col = t_col + 1
  206.         else:
  207.             if t_row == o_row:
  208.                 d_row = t_row  # LEFT
  209.                 d_col = t_col - 1
  210.             else:
  211.                 d_row = t_row-1 # UP
  212.                 d_col = t_col
  213.  
  214.         dst_pos = d_row*4 + d_col
  215.         self.mover.move_vh(dst_pos)
  216.  
  217.     # 타겟 이동 (attach 이후)
  218.     def move_target(self, dir, num_pos):
  219.         # key : 타겟의 방향
  220.         # value-key : empty 가 붙어있는 위치
  221.         scripts = {
  222.             'U': {'U': 'D', 'R': 'ULD', 'D': 'RUULD', 'L': 'DRRUULD'},
  223.             'L': {'U': 'RDDLLUR', 'R': 'DLLUR', 'D': 'LUR', 'L': 'R'},
  224.             'R': {'U': 'LDDRRUL', 'R': 'L', 'D': 'RUL', 'L': 'DRRUL'},
  225.         }
  226.         diff = num_pos - self.mover.empty_pos
  227.         k = ''
  228.         if diff == 4: # UP
  229.             k = 'U'
  230.         elif diff == 1: # LEFT
  231.             k = 'L'
  232.         elif diff == -1: #RIGHT
  233.             k = 'R'
  234.         elif diff == -4: #DOWN
  235.             k = 'D'
  236.         else:
  237.             raise Exception('cant move target')
  238.         script = scripts[dir][k]
  239.         for d in script:
  240.             self.mover.emove(d)
  241.  
  242.     # row 끝쪽 특수 패턴 체크
  243.     def check_row_pattern(self, row):
  244.         dtec = False
  245.         if row == 0:
  246.             if self.puzzle[2] == 4 and self.puzzle[3] == 3:
  247.                 # detect pattern
  248.                 dtec = True
  249.         if row == 1:
  250.             if self.puzzle[6] == 8 and self.puzzle[7] == 7:
  251.                 # detect pattern
  252.                 dtec = True
  253.         if dtec:
  254.             for d in 'RULDRDLUURDLD':
  255.                 self.mover.emove(d)
  256.         return dtec
  257.  
  258.     # row 0 인 경우 1,2,4 일단 맞추고 난뒤
  259.     # row 1 인 경우 5,6,8 맞추고 난뒤
  260.     # row 끝 부분 처리
  261.     def row_set_block(self, row):
  262.         dst_pos = (row+1) * 4 + 2
  263.         # 일단 빈블록을 다음 ROW 3번쨰 칸에 위치 시킴
  264.         self.mover.move_hv_with_wall(dst_pos, dst_pos-4)
  265.  
  266.         # 특수 패턴 체크
  267.         if self.check_row_pattern(row):
  268.             pass # 이동을 이미 시킴
  269.         else:
  270.             self.normal_set_block(row*4 + 3, row*4 + 6, False)
  271.  
  272.         # 빈블록을 끝으로 이동
  273.         self.mover.move_hv_with_wall(row*4 + 3, row*4 + 6)
  274.  
  275.         # Row 맞춤
  276.         for d in 'LD':
  277.             self.mover.emove(d)
  278.  
  279.     # row 끝쪽 특수 패턴 체크
  280.     def check_col_pattern(self, col):
  281.         dtec = False
  282.         if col == 0:
  283.             if self.puzzle[8] == 13 and self.puzzle[12] == 9:
  284.                 # detect pattern
  285.                 dtec = True
  286.         if col == 1:
  287.             if self.puzzle[9] == 14 and self.puzzle[13] == 10:
  288.                 # detect pattern
  289.                 dtec = True
  290.         if dtec:
  291.             for d in 'DLURDRULLDRUR':
  292.                 self.mover.emove(d)
  293.         return dtec
  294.  
  295.     def col_set_block(self, col):
  296.         dst_pos = 9 + col
  297.         self.mover.move_hv_with_wall(dst_pos, dst_pos-4)
  298.  
  299.         # 특수 패턴 체크
  300.         if self.check_col_pattern(col):
  301.             pass  # 이동을 이미 시킴
  302.         else:
  303.             self.normal_set_block(dst_pos, dst_pos, True)
  304.  
  305.         # 빈블록을 끝으로 이동
  306.         self.mover.move_hv_with_wall(12 + col, dst_pos)
  307.  
  308.         # Row 맞춤
  309.         for d in 'UR':
  310.             self.mover.emove(d)
  311.  
  312.  
  313.     # 마지막 부분 회전
  314.     def rotate_block(self):
  315.         for d in 'DRULDRULDRULDRUL':
  316.             if self.puzzle[10] == 11 and self.puzzle[11] == 12 and self.puzzle[14] == 15:
  317.                 break
  318.             self.mover.emove(d)
  319.  
  320.  
  321.  
  322. if __name__ == '__main__':
  323.     puzzle = list(range(1, 16)) + [0]
  324.     mover = SlideMover(puzzle)
  325.     mover.shuffle(80)
  326.     mover.step = []
  327.  
  328.     print_puzzle(puzzle)
  329.  
  330.     #
  331.     solver = MusicSolver(puzzle, mover)
  332.     solver.solve()
  333.  
  334.     print(len(mover.step), ''.join(mover.step))
  335.     print_puzzle(puzzle)
  336.  
  337.  
Success #stdin #stdout 0.02s 11596KB
comments (?)
stdin 
Standard input is empty
stdout 
 3, 10,  6,  4,  
 1,  0,  2,  7,  
 5,  9, 11,  8,  
13, 14, 15, 12,  
----------------
66 LURDLURRDLURRDLRDUULDLLDRURRDLURDLRDUULDLLDRUDLURDRUDLURDRULDRULDR
 1,  2,  3,  4,  
 5,  6,  7,  8,  
 9, 10, 11, 12,  
13, 14, 15,  0,  
----------------
https://ideone.com/0WNDrZ
language:
Python 3 (python  3.12)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!