Puzzle DE Programming

パズルの説明

1 から 9 までの数字が 4 つの正方形 (A, B, C, D) の頂点に配置にされています。回転パズルは 4 つの正方形を回転して数字の順番を並べ替えるパズルです。

(1) の状態で、正方形 A を右回転（時計回り）すると、数字 1, 2, 5, 4 が回転して (2) の状態になります。次に、正方形 B を左回転（反時計回り）すると、数字 1, 3, 6, 2 が回転して (3) の状態になります。このように、4 つの正方形を左回転または右回転して数字を並べ替えます。

それでは問題です。

START から GOAL までの最短手数を求めてください。この問題では、正方形の右回転または左回転を 1 手と数えることにします。同じ正方形を 2 回続けて右回転する場合は 1 手ではなく 2 手となります。ご注意くださいませ。

●解答

「回転パズル」の解答です。

• 最短手数 11 手

今回の規則では、この問題が最長手数の局面になります。最長手数の局面を幅優先探索で求めたところ、最長手数の局面は全部で 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