Puzzle DE Programming

問題の説明

数字の並べ替えは おしどりの遊び のように数字をペアで空いている場所に動かして、数字を順番に並べるパズルです。

注意事項として、数字を動かすときはペアの順番を変えてはいけません。たとえば、上図の先頭にある 4, 3 を動かすときに、3, 4 というように数字を逆にすることは許されません。それでは問題です。

プログラムは おしどりの遊び で作成したものを修正するだけなので簡単です。

●解答

それでは実行結果を示します。

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

1. は 4 手、2. は 7 手で並べ替えることができますが、3. の並べ替えは不可能です。ついでに、次に示す数列の並べ替えも調べてみました。

4. [７ ６ ５ ４ ３ ２ １ ・ ・] --> [１ ２ ３ ４ ５ ６ ７ ・ ・]
5. [８ ７ ６ ５ ４ ３ ２ １ ・ ・] --> [１ ２ ３ ４ ５ ６ ７ ８ ・ ・]
6. [９ ８ ７ ６ ５ ４ ３ ２ １ ・ ・] --> [１ ２ ３ ４ ５ ６ ７ ８ ９ ・ ・]

>>> solver(7)
>>> solver(8)
(8, 7, 6, 5, 4, 3, 2, 1, 0, 0)
(8, 7, 0, 0, 4, 3, 2, 1, 6, 5)
(8, 7, 2, 1, 4, 3, 0, 0, 6, 5)
(8, 0, 0, 1, 4, 3, 7, 2, 6, 5)
(8, 4, 3, 1, 0, 0, 7, 2, 6, 5)
(8, 4, 3, 1, 2, 6, 7, 0, 0, 5)
(0, 0, 3, 1, 2, 6, 7, 8, 4, 5)
(1, 2, 3, 0, 0, 6, 7, 8, 4, 5)
(1, 2, 3, 4, 5, 6, 7, 8, 0, 0)
109202
>>> solver(9)
(9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0)
(0, 0, 7, 6, 5, 4, 3, 2, 1, 9, 8)
(4, 3, 7, 6, 5, 0, 0, 2, 1, 9, 8)
(4, 0, 0, 6, 5, 3, 7, 2, 1, 9, 8)
(4, 5, 3, 6, 0, 0, 7, 2, 1, 9, 8)
(4, 5, 3, 6, 1, 9, 7, 2, 0, 0, 8)
(4, 5, 3, 6, 1, 0, 0, 2, 9, 7, 8)
(4, 5, 3, 0, 0, 6, 1, 2, 9, 7, 8)
(0, 0, 3, 4, 5, 6, 1, 2, 9, 7, 8)
(1, 2, 3, 4, 5, 6, 0, 0, 9, 7, 8)
(1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0)
1717205

4. は並べ替え不可能ですが、5. は 8 手で、6. は 10 手で並べ替えることができました。実はこのパズル、15 パズルと同様の「偶奇性 (パリティ)」があり、これをチェックすることで並べ替えができないことは簡単に判断することができます。

●偶奇性

たとえば、数字の並びが [1 2 3 4] の場合を考えてみます。数字が順番に並んでいる場合、各数字の左側には自分より大きな数字はありませんね。これに対して [4 3 2 1] の場合、1 の左側には 3, 4, 5 があり、2 の左側には 3 と 4 があり、3 の左側には 4 があります。このように数字の順番が逆になっている個数を数え、その総数を仮に「転倒数」と名づけましょう。[1 2 3 4] は転倒数が 0 で、[4 3 2 1] は転倒数が 6 となります。

ここで、[1 2 3 4] と [4 3 2 1] の転倒数が偶数であることに注目してください。このような数字の並びを「偶順列」といい、転倒数が奇数の場合を「奇順列」といいます。たとえば、[2 1 3 4] は 1 と 2 が逆転しているだけなので、転倒数が 1 の奇順列になります。そして、数字をペアで動かす場合、「偶順列は偶順列のままで、奇順列は奇順列のままである」ことが 参考文献 10 で証明されています。

つまり、奇順列である [2 1 3 4] は、どうやっても偶順列 [1 2 3 4] に並べ替えることはできないのです。[6 5 4 3 2 1] と [7 6 5 4 3 2 1] の場合も転倒数が 15 と 21 の奇順列なので、並べ替えることができなかったわけです。

このように、パズルには奇数と偶数に場合分けができるものがあり、このような性質を「偶奇性 (パリティ)」といいます。15 パズルにも偶順列と奇順列があり、どのように駒を移動しても、偶順列は偶順列、奇順列は奇順列にしか移行できないそうです。15 パズルについては、参考文献 9 に詳細な説明があります。

●n 個の数字を逆順に並べる場合

今度は、「n 個の数字を逆順に並べる」場合を考えてみましょう。この場合、並べ替えができないこと (解が無いこと) だけならば、簡単に調べることができます。次の表を見てください。

n 個の数字の並びに数字をひとつ追加すると、各数字に逆順の数字がひとつずつ増えるため、転倒数が n 増えることがわかります。つまり、n 個の数字を逆順に並べた場合、転倒数は 1 から n - 1 までの総和になるのです。したがって、転倒数は次の式で求めることができます。

求めた転倒数が奇数であれば並べ替えることはできません。

表をよく見てみると、転倒数は「偶数、偶数、奇数、奇数、・・・・」と順番に並んでいますね。これも数式から求めることができます。数字の個数を \(4m, 4m + 1, 4m + 2, 4m + 3 \ (m = 1, 2, 3, \ldots)\) で表すことにすると、転倒数は次のようになります。

1. \(4m\) の場合
   \(4m(4m - 1) / 2 = 2m(4m - 1)\) --- 偶数
2. \(4m + 1\) の場合
   \((4m + 1)4m / 2 = 2m(4m + 1)\) --- 偶数
3. \(4m + 2\) の場合
   \((4m + 2)(4m + 1) / 2 = 2m(4m + 3) + 1\) --- 奇数
4. \(4m + 3\) の場合
   \((4m + 3)(4m + 2) / 2 = 2m(4m + 5) + 3\) --- 奇数

整数に偶数を掛け算すると、その結果は偶数になります。1. と 2. の転倒数は必ず偶数になるので、並べ替えることができるかもしれません。それから、偶数に奇数を足し算すると、その結果は奇数になりますね。よって、3. と 4. の転倒数は必ず奇数になるので、並べ替えることはできません。

●最長手数を求める

次は、最長手数となる並び、つまり、一番難しい数字の並びを求めてみましょう。このような場合、すべての並べ方について最小手数をチェックしていたのでは、時間がとてもかかってしまいます。そこで、完成形から始めていちばん長い手数の局面を生成することにします。

まず、完成形から数字を動かして 1 手で到達する局面をすべて作ります。次に、これらの局面から数字を動かして新しい局面を作れば、完成形から 2 手で到達する局面となります。このように、手数を 1 手ずつ延ばしていき、新しい局面が生成できなくなった時点での手数が求める最長手数となります。この処理は幅優先探索を使えばぴったりです。

さて、生成されるパターンの総数ですが、ふたつの空き場所はひとつの数字にみなすことができるので、数字が n 種類のパターンは (n + 1)! / 2 通りになります。たとえば、数字が 8 種類の場合は 9! / 2 = 181440 通りとなります。これは「8 パズル」と同じ総数ですね。とりあえず、4 - 8 種類の最長手数を求めることにします。

プログラムは簡単なので説明は割愛させていただきます。詳細は プログラムリスト をお読みください。

それでは実行結果を示します。

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

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

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

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

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

思っていたよりも最長手数は短いですね。パズルとして楽しむ場合、5, 6 種類くらいで十分なのかもしれません。

それから、4 種類の場合は 5! / 2 = 60 通りのパターンがあるはずですが、20 通りのパターンしか生成していません。ということは、「数字の並びが偶順列でも解けない場合がある」ということです。たとえば、[1 3 4 2 0 0] は偶順列ですが、実際に試してみると解くことはできません。つまり、偶奇性を満たしているからといって、解けるとは限らないのです。逆に、偶奇性を満たしていないと絶対に解けません。

ところが、数字が 5 - 8 種類の場合はすべてのパターンを生成していますね。この場合、数字の並びが偶順列であれば必ず数字を昇順に並べ替えることができます。もしかすると 4 種類の場合だけが特別で、数字が 5 種類以上の場合、偶奇性を満たせば解くことができるのかもしれません。数学的に証明できればいいのですが、M.Hiroi はお手上げです。何か良いアイデアがありましたら、ぜひ教えてくださいませ。

●プログラムリスト

#
# chgnum.py : 数次の並べ替え
#
#             Copyright (C) 2022 Makoto Hiroi
#
from collections import deque
import time

# 空き場所
S = 0

def print_answer(b, table):
    prev = table[b]
    if prev:
        print_answer(prev, table)
    print(b)

def bfs(start, goal):
    queue = deque()
    queue.append((start, start.index(0)))
    check = {}
    check[start] = []
    while len(queue) > 0:
        b, s = queue.popleft()
        for i in range(len(start) - 1):
            if b[i] == S or b[i + 1] == S: continue
            a = list(b)
            a[s], a[s + 1] = a[i], a[i + 1]
            a[i] = a[i + 1] = S
            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(n):
    goal  = tuple(range(1, n + 1)) + (0, 0)
    start = tuple(range(n, 0, -1)) + (0, 0)
    bfs(start, goal)

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