Puzzle DE Programming

問題の説明

数字の並べ替え は おしどりの遊び のように数字をペアで空いている場所に動かして、数字を順番に並べるパズルです。今回の「続・数字の並べ替え」は、数字をペアではなく単独で動かして数字を順番に並べるパズルです。それでは問題です。

• 問題１ 続・数字の並べ替え (A)

数字をひとつ跳び越すことができるのは 蛙跳びゲーム と似ていますね。スタートの状態では、4 は隣が空き場所なので移動することができます。また、3 は隣に 4 がありますが、それを跳び越して空き場所へ移動することができます。ほかの数字は空き場所へ移動できません。

このパズルは、高木茂男氏の著書「パズル遊びへの招待」(PHP研究所 1994) の オンライン版 にある おしどりの遊びと入れ替え問題 を参考にさせていただきました。数字を逆順に並べることは同じですが、空き場所の位置が異なっているので少しだけ難しくなっていると思います。「パズル遊びへの招待・オンライン版」には興味深いパズルが多数紹介されています。パズル好きの方は要チェックです。

それから、もうひとつ数字の移動規則を少し変更したパズルを考えてみました。

• 問題２ 続・数字の並べ替え (B)

このパズルは数字をふたつ跳び越すことができます。スタートの状態では、4 は隣が空き場所なので移動することができます。また、2 は隣に 3 と 4 がありますが、それらを跳び越して空き場所へ移動することができます。ほかの数字は空き場所へ移動できません。

興味のある方は、数字の種類を増やしてみるといいでしょう。[1 2 3 4 5 0] や [1 2 3 4 5 6 0] を逆順に並べ替えることができるか、調べてみるのも面白いと思います。

• 問題１の解答
• 問題２の解答

●問題１の解答

それでは問題１の解答を示します。

>>> solver((1,2,3,4,0), (0,4,3,2,1))
(1, 2, 3, 4, 0)
(1, 2, 0, 4, 3)
(0, 2, 1, 4, 3)
(2, 0, 1, 4, 3)
(2, 1, 0, 4, 3)
(2, 1, 4, 0, 3)
(2, 0, 4, 1, 3)
(0, 2, 4, 1, 3)
(4, 2, 0, 1, 3)
(4, 2, 3, 1, 0)
(4, 2, 3, 0, 1)
(4, 0, 3, 2, 1)
(0, 4, 3, 2, 1)
120

最短手数は 12 手になります。数字の 0 が空き場所を表しています。実は、これが最長手数の局面なのです。ちなみに、[1 2 3 4 0] を [4 3 2 1 0] に並べ替える最短手数は 10 手にしかなりません。

>>> solver((1,2,3,4,0), (4,3,2,1,0))
(1, 2, 3, 4, 0)
(1, 2, 0, 4, 3)
(0, 2, 1, 4, 3)
(2, 0, 1, 4, 3)
(2, 4, 1, 0, 3)
(2, 4, 1, 3, 0)
(2, 4, 0, 3, 1)
(0, 4, 2, 3, 1)
(4, 0, 2, 3, 1)
(4, 3, 2, 0, 1)
(4, 3, 2, 1, 0)
113

そこで、数字の種類を増やして最長手数の局面を探索したところ、結果は次のようになりました。

>>> solver_max(4)
手数 = 12 局面数 = 1
(0, 4, 3, 2, 1)
状態の総数 = 120

>>> solver_max(5)
手数 = 17 局面数 = 2
(5, 4, 3, 2, 0, 1)
(0, 4, 5, 2, 3, 1)
状態の総数 = 720

>>> solver_max(6)
手数 = 25 局面数 = 1
(0, 6, 5, 4, 3, 2, 1)
状態の総数 = 5040

>>> solver_max(7)
手数 = 32 局面数 = 1
(7, 6, 5, 4, 3, 2, 0, 1)
状態の総数 = 40320

>>> solver_max(8)
手数 = 42 局面数 = 1
(0, 8, 7, 6, 5, 4, 3, 2, 1)
状態の総数 = 362880

空き場所 (0) を含めた数字の種類を N 個とすると、数字の並び方は全部で N! 通りになります。局面数を見ると、どの場合も N! 通りの局面を生成していますね。しがたって、このパズルは数字をランダムに配置しても必ず解くことができます。

• プログラムリスト

●問題２の解答

それでは問題２の解答を示します。

>>> solver((1,2,3,4,0), (0,4,3,2,1), make_move2)
(1, 2, 3, 4, 0)
(1, 0, 3, 4, 2)
(0, 1, 3, 4, 2)
(4, 1, 3, 0, 2)
(4, 1, 3, 2, 0)
(4, 0, 3, 2, 1)
(0, 4, 3, 2, 1)
30

最短手数は 6 手になります。数字の 0 が空き場所を表しています。ちなみに、最長手数を調べたところ 8 手になりました。

>>> solver_max(4, make_move2)
手数 = 8 局面数 = 9
(3, 4, 1, 2, 0)
(0, 2, 1, 4, 3)
(4, 2, 0, 1, 3)
(0, 3, 2, 4, 1)
(4, 3, 2, 1, 0)
(0, 2, 4, 3, 1)
(3, 2, 0, 4, 1)
(2, 1, 0, 4, 3)
(2, 1, 4, 3, 0)
状態の総数 = 60

最長手数の局面は 9 個あって、その中のひとつが [4 3 2 1 0] です。

次は、数字の種類を増やしてみましょう。[1 2 3 4 5 0] は [0 5 4 3 2 1] へ並び替えることができます。

>>> solver((1,2,3,4,5,0), (0,5,4,3,2,1), make_move2)
(1, 2, 3, 4, 5, 0)
(1, 2, 0, 4, 5, 3)
(1, 0, 2, 4, 5, 3)
(0, 1, 2, 4, 5, 3)
(4, 1, 2, 0, 5, 3)
(4, 1, 2, 5, 0, 3)
(4, 0, 2, 5, 1, 3)
(0, 4, 2, 5, 1, 3)
(5, 4, 2, 0, 1, 3)
(5, 4, 0, 2, 1, 3)
(5, 4, 3, 2, 1, 0)
(5, 4, 3, 2, 0, 1)
(5, 4, 3, 0, 2, 1)
(5, 4, 0, 3, 2, 1)
(5, 0, 4, 3, 2, 1)
(0, 5, 4, 3, 2, 1)
360

最短手数は 15 手、これが最長手数の局面になります。ところが [1 2 3 4 5 6 0] の場合、[0 6 5 4 3 2 1] へ並び替えることはできません。

>>> solver((1,2,3,4,5,6,0), (0,6,5,4,3,2,1), make_move2)
>>>

並び替えが不可能なことは、「転倒数の偶奇性」で説明することができます。転倒数と偶奇性については 数字の並べ替え：偶奇性 をお読みくださいませ。

数字の並びは左から右へと定義し、空き場所は無視します。転倒数が偶数の並びを「偶順列」といい、転倒数が奇数の並びを「奇順列」といいます。たとえば、[1 2 3 4 5 6 0] は順番に並んでいるので転倒数は 0 となり、偶順列であることがわかります。これに対し、逆順 [0 6 5 4 3 2 1] の転倒数は 15 になるので奇順列になります。

このパズルでは、数字を隣の空き場所へ移動しても転倒数に変化はありません。数字を 2 つ跳び越す場合、自分よりも大きな数字と小さな数字、大きな数字 2 つ、小さな数字 2 つという 3 通りのパターンがありますが、どのパターンも転倒数の変化は偶数個にしかなりません。したがって、奇順列から偶順列へは移行できない、並び替えは不可能というわけです。転倒数の変化は 15 パズルの偶奇性 で詳しく説明しているので参考にしてください。

今度は、数字を N 個に増やして、それを逆順に並べ替えることを考えてみます。これは 数字の並べ替え と同じ結果になります。詳しい説明は n 個の数字を逆順に並べる場合 をお読みくださいませ。結果だけ書くと、数字の個数が 4m + 2, 4m + 3 (m = 1, 2, 3 ... ) の場合、逆順の並びが奇順列になるため並べ替えは不可能です。逆に、4m, 4m + 1 (m = 1, 2, 3 ... ) 個の場合は偶順列になりますが、これだけでは不十分で、偶順列ならば並べ替え可能であることを証明する必要があります。

●並べ替えできることの証明

それでは、並べ替えできることを証明してみましょう。なお、この証明は花谷さんから教えてもらいました。花谷さん、どうもありがとうございます。

花谷さんの証明は、N 個の数字の並びを 3 つの数字の並びに帰着させる方法です。説明の都合上、花谷さんの方法を少し変更していますが、基本的な考え方は同じです。今、数字が N 個ある並びを、左から順番に 1 から N - 3 まで並べることを考えます。いちばん小さな数字を見つけて、それを左端まで移動させればいいわけです。

移動させる数字を m としましょう。m の左側に空き場所がある場合は、m をひとつ左へ移動させることができます。これは自明ですね。そして、空き場所は m の右側へ移ります。m の右側に空き場所がある場合は、m の左隣にある数字を空き場所へ移動すればいいわけです。m の右隣が空き場所で、それが右端にある場合、m の左隣の数字は移動できません。この場合は、2 つ隣の数字を空き場所へ移動すればいいでしょう。

この手順を繰り返すことで、m を左端へ移動することができます。そして、今度は N - 1 個の数字の中で、いちばん小さな数字を m の右隣へ移動させればいいわけです。あとは、同じ手順を繰り返すだけです。簡単な例を示しましょう。

 (1) ４ ３ ２ １ ０
 (2) ４ ０ ２ １ ３  空き場所を１の左側へ移動
 (3) ４ ２ ０ １ ３  空き場所を１の手前に移動
 (4) ４ ２ １ ０ ３  １をひとつ左へ動かす
 (5) ４ ２ １ ３ ０  空き場所を右へ移動
 (6) ４ ０ １ ３ ２  １の左隣の２を空き場所へ移動
 (7) ４ １ ０ ３ ２  １をひとつ左へ動かす
 (8) ４ １ ３ ０ ２  空き場所を右へ移動
 (9) ０ １ ３ ４ ２  ４を空き場所へ移動
(10) １ ０ ３ ４ ２  １を左へ動かす

(1) の [4 3 2 1 0] の中で、1 を左端へ動かします。(2) で 3 を空き場所へ移動しました。これで、(3), (4) のように 1 を左へひとつ動かすことができます。次は、(5), (6) のように、空き場所を右へひとつ動かし、1 の左隣の数字 2 を移動させれば、(7) のように 1 を左へ動かすことできます。これを繰り返すことで、(10) のように 1 を左端へ動かすことができます。

このように、N 個の数字の並びを 1 から N - 3 まで順番に並べることができます。ここで、最初の並びが偶順列だったとしましょう。この移動により偶奇性は変化しないので、全体の並びは偶順列のままです。ここで、1 から N - 3 までの並びに注目してください。数字は左から順番に並んでいるので、転倒数は 0 になります。全体の並びは偶順列のままですから、残り 3 つの数字 N - 2, N - 1, N の転倒数は偶数になるはずです。したがって、残りの数字の並びは偶順列であることがわかります。

数字 3 つの並びは、全部で 6 通りあります。

(1) N-2, N-1, N      転倒数 0 偶順列
(2) N-2, N,   N-1    転倒数 1
(3) N-1, N-2, N      転倒数 1
(4) N-1, N,   N-2    転倒数 2 偶順列
(5) N,   N-2, N-1    転倒数 2 偶順列
(6) N,   N-1, N-2    転倒数 1

偶順列は 3 通りあります。数字が 3 つの場合、図に示すように移動経路は巡路になります。

数字は経路にそってグルグル回るだけなので、(4) と (5) は (1) へ並べ替えることができますが、奇順列は (1) へ並べ替えることはできません。残り 3 つの数字は偶順列ですから、数字が N 個の偶順列は 1, 2, .... N （正順）に並べ替えることができます。

どの偶順列でも正順に並べ替えることができるのですから、逆に正順からどの偶順列へも並べ替えが可能です。したがって、どの偶順列からでもほかの偶順列へ並べ替えることができる、というわけです。

●プログラムリスト

#
# chgnum1.py : 続・数字の並べ替え
#
#              Copyright (C) 2022 Makoto Hiroi
#
import time
from collections import deque

#
# 最短手順を求める
#

# 指し手の生成
# 問題１
def make_move1(b, s):
    move = []
    size = len(b)
    for dx in [-2, -1, 1, 2]:
        p = s + dx
        if 0 <= p < size: move.append(p)
    return move

# 問題２
def make_move2(b, s):
    move = []
    size = len(b)
    for dx in [-3, -1, 1, 3]:
        p = s + dx
        if 0 <= p < size: move.append(p)
    return move

# 手順の表示
def print_answer(b, table):
    prev = table[b]
    if prev:
        print_answer(prev, table)
    print(b)

# 幅優先探索
def solver(start, goal, move_maker = make_move1):
    queue = deque()
    queue.append((start, start.index(0)))
    check = {}
    check[start] = []
    while len(queue) > 0:
        b, s = queue.popleft()
        for i in move_maker(b, s):
            a = list(b)
            a[s] = a[i]
            a[i] = 0
            newb = tuple(a)
            if newb in check: continue
            queue.append((newb, i))
            check[newb] = b
            if newb == goal:
                print_answer(newb, check)
                print(len(check))
                return

def solver_max(n, move_maker = make_move1):
    start = tuple(range(1, n + 1)) + (0,)
    check = {}
    check[start] = True
    xs = [(start, start.index(0))]
    move = 0
    total = 1
    while True:
        ys = []
        for b, s in xs:
            for i in move_maker(b, s):
                a = list(b)
                a[s] = a[i]
                a[i] = 0
                newb = tuple(a)
                if newb in check: continue
                ys.append((newb, i))
                check[newb] = True
        if not ys: break
        move += 1
        total += len(ys)
        xs = ys
    print('手数 =', move, '局面数 =', len(xs))
    for b in xs[:10]: print(b[0])
    print('状態の総数 =', total)