1───2───3 4───1───3 4───3───6 │ │ │ │ │ │ │ │ │ │ A │ B │ │ A │ B │ │ A │ B │ │ │ │ │ │ │ │ │ │ 4───5───6 5───2───6 5───1───2 │ │ │ │ │ │ │ │ │ │ C │ D │ │ C │ D │ │ C │ D │ │ │ │ │ │ │ │ │ │ 7───8───9 7───8───9 7───8───9 (1) 初期状態 (2) Aを右回転 (3) Bを左回転 図 : 回転パズルの動作
1 から 9 までの数字が 4 つの正方形 (A, B, C, D) の頂点に配置にされています。回転パズルは 4 つの正方形を回転して数字の順番を並べ替えるパズルです。
(1) の状態で、正方形 A を右回転(時計回り)すると、数字 1, 2, 5, 4 が回転して (2) の状態になります。次に、正方形 B を左回転(反時計回り)すると、数字 1, 3, 6, 2 が回転して (3) の状態になります。このように、4 つの正方形を左回転または右回転して数字を並べ替えます。
それでは問題です。
9───8───7 1───2───3 │ │ │ │ │ │ │ A │ B │ │ A │ B │ │ │ │ │ │ │ 4───5───6 4───5───6 │ │ │ │ │ │ │ C │ D │ │ C │ D │ │ │ │ │ │ │ 3───2───1 7───8───9 START GOAL 図 : 問題
START から GOAL までの最短手数を求めてください。この問題では、正方形の右回転または左回転を 1 手と数えることにします。同じ正方形を 2 回続けて右回転する場合は 1 手ではなく 2 手となります。ご注意くださいませ。
「回転パズル」の解答です。
今回の規則では、この問題が最長手数の局面になります。最長手数の局面を幅優先探索で求めたところ、最長手数の局面は全部で 20 通りありました。今回の問題はそのひとつです。生成された局面の総数は 362880 (9!) 通りなので、このパズルは数字をランダムに配置しても解くことができます。
もちろん、規則を変更すると最長手数も変わります。たとえば、正方形は右回転だけに限定するとか、同じ正方形の連続回転を 1 手と数えるなど、興味のある方は試してみてください。
>>> solver_max() 手数 1, 個数 8 手数 2, 個数 52 手数 3, 個数 328 手数 4, 個数 1996 手数 5, 個数 11336 手数 6, 個数 51582 手数 7, 個数 130042 手数 8, 個数 125929 手数 9, 個数 39706 手数 10, 個数 1880 手数 11, 個数 20 最長手数 11, 個数 20 (8, 9, 7, 6, 5, 4, 3, 2, 1) (9, 7, 8, 6, 5, 4, 3, 2, 1) (7, 8, 9, 6, 5, 4, 3, 2, 1) (6, 8, 7, 9, 5, 4, 3, 2, 1) (9, 2, 7, 6, 5, 4, 3, 8, 1) (9, 5, 7, 6, 8, 4, 3, 2, 1) (9, 8, 7, 6, 5, 4, 1, 2, 3) (9, 8, 1, 6, 5, 4, 3, 2, 7) (9, 8, 4, 6, 5, 7, 3, 2, 1) (9, 6, 7, 2, 5, 8, 3, 4, 1) (9, 8, 7, 5, 6, 4, 3, 2, 1) (9, 8, 7, 3, 5, 4, 6, 2, 1) (9, 8, 7, 6, 5, 4, 3, 1, 2) (9, 8, 7, 6, 5, 4, 2, 3, 1) (9, 8, 7, 6, 4, 5, 3, 2, 1) (3, 8, 7, 6, 5, 4, 9, 2, 1) (9, 4, 7, 8, 5, 2, 3, 6, 1) (9, 8, 7, 6, 2, 4, 3, 5, 1) (9, 8, 7, 4, 5, 6, 3, 2, 1) (9, 8, 7, 6, 5, 1, 3, 2, 4) 状態の総数 362880
9 8 7 9 8 7 9 8 7 9 4 7 3 8 7 9 8 7 9 8 7 9 8 7 6 5 1 4 5 6 6 2 4 8 5 2 6 5 4 6 4 5 6 5 4 6 5 4 3 2 4 3 2 1 3 5 1 3 6 1 9 2 1 3 2 1 2 3 1 3 1 2 9 8 7 9 8 7 9 6 7 9 8 4 9 8 1 9 8 7 9 5 7 9 2 7 3 5 4 5 6 4 2 5 8 6 5 7 6 5 4 6 5 4 6 8 4 6 5 4 6 2 1 3 2 1 3 4 1 3 2 1 3 2 7 1 2 3 3 2 1 3 8 1 6 8 7 7 8 9 9 7 8 8 9 7 9 5 4 6 5 4 6 5 4 6 5 4 3 2 1 3 2 1 3 2 1 3 2 1
# # ccc.py : 回転パズル # # Copyright (C) 2022 Makoto Hiroi # from collections import deque # 盤面 # 0 1 2 # 3 4 5 # 6 7 8 # 回転 rotate_table = [ [0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7] ] def rotate_left(board, n): bd = list(board) rs = rotate_table[n] tmp = bd[rs[3]] bd[rs[3]] = bd[rs[2]] bd[rs[2]] = bd[rs[1]] bd[rs[1]] = bd[rs[0]] bd[rs[0]] = tmp return tuple(bd) def rotate_right(board, n): bd = list(board) rs = rotate_table[n] tmp = bd[rs[0]] bd[rs[0]] = bd[rs[1]] bd[rs[1]] = bd[rs[2]] bd[rs[2]] = bd[rs[3]] bd[rs[3]] = tmp return tuple(bd) # 手順の表示 def print_moves(b, table): if b: print_moves(table[b], table) print(b) # 幅優先探索 def bfs(start, goal): queue = deque() queue.append(start) check = {} check[start] = () while len(queue) > 0: b = queue.popleft() if b == goal: print_moves(b, check) return for i in range(8): if i % 2 == 0: newb = rotate_left(b, i // 2) else: newb = rotate_right(b, i // 2) if newb in check: continue queue.append(newb) check[newb] = b # 最長手数の局面 def solver_max(): start = (1,2,3,4,5,6,7,8,9) xs = [start] check = {} check[start] = True move = 0 while len(xs) > 0: ys = [] for b in xs: for i in range(8): if i % 2 == 0: newb = rotate_left(b, i // 2) else: newb = rotate_right(b, i // 2) if newb in check: continue ys.append(newb) check[newb] = True if not ys: break xs = ys move += 1 print(f'手数 {move}, 個数 {len(xs)}') print(f'最長手数 {move}, 個数 {len(xs)}') for b in xs: print(b) print(f'状態の総数 {len(check)}')
>>> bfs((9,8,7,4,5,6,3,2,1), (1,2,3,4,5,6,7,8,9)) (9, 8, 7, 4, 5, 6, 3, 2, 1) (4, 9, 7, 5, 8, 6, 3, 2, 1) (5, 4, 7, 8, 9, 6, 3, 2, 1) (5, 7, 6, 8, 4, 9, 3, 2, 1) (8, 5, 6, 4, 7, 9, 3, 2, 1) (8, 5, 6, 4, 9, 1, 3, 7, 2) (8, 5, 6, 3, 4, 1, 7, 9, 2) (3, 8, 6, 4, 5, 1, 7, 9, 2) (4, 3, 6, 5, 8, 1, 7, 9, 2) (4, 3, 6, 5, 1, 2, 7, 8, 9) (4, 1, 3, 5, 2, 6, 7, 8, 9) (1, 2, 3, 4, 5, 6, 7, 8, 9)
(0) 9 8 7 A B 4 5 6 C D R : 右回転 3 2 1 L : 左回転 (1) (2) (3) (4) (5) (6) A:R A:R B:L A:R D:L C:R 4 9 7 5 4 7 5 7 6 8 5 6 8 5 6 8 5 6 5 8 6 8 9 6 8 4 9 4 7 9 4 9 1 3 4 1 3 2 1 3 2 1 3 2 1 3 2 1 3 7 2 7 9 2 (7) (8) (9) (10) (11) A:R A:R D:L B:R A:L 3 8 6 4 3 6 4 3 6 4 1 3 1 2 3 4 5 1 5 8 1 5 1 2 5 2 6 4 5 6 7 9 2 7 9 2 7 8 9 7 8 9 7 8 9