Puzzle DE Programming

問題の説明

「カラーダイスパズル」は各面にそれぞれ赤、青、緑、黄のいずれかの色を塗った 4 つのサイコロを使ったパズルです。一般には「インスタント・インサニティ」と呼ばれています。それでは問題です。

上図の 4 つのサイコロを柱状に積み重ねて、どの側から見ても 4 つのサイコロの面が異なる色になるような積み方を考えてください。

●参考 URL

• パズル遊びへの招待・オンライン版 ３－１７．インスタント・インサニティ

●プログラムの作成

それではプログラムを作りましょう。プログラミング言語は Python3 (ver 3.8.10) を使うことにします。最初にサイコロの積み方が何通りあるか数えてみます。

サイコロは 6 つの面があります。上下の面を基準にすると、その置き方は 6 通り、上下を軸に回転して得られる置き方が 4 通りあるので、ひとつのサイコロの置き方は全部で 24 通りあります。サイコロは 4 つありますがその順番は関係ないので、サイコロの積み方は全部で 24 * 24 * 24 * 24 = 331776 通りになります。積み方の総数はそれほど多くないので、簡単な生成検定法でプログラムを作ることにします。

上下の面を基準にした 6 通りの置き方を下図に示します。

(A) を標準形とすると、1 の面が上になるよう縦に 90 度回転したものが (B)、2 の面が上になるように回転したものが (C) になります。そして、(A), (B), (C) を 180 度縦に回転 (上下を反転) したものが (D), (E), (F) になります。

色を数字 1 (赤), 2 (青), 3 (緑), 4 (黄) で表すと、サイコロと縦の回転パターンは次のように定義することができます。

リスト : サイコロと回転パターンの設定

# サイコロの設定
CUBE = [[2, 1, 3, 3, 4, 2], [2, 1, 2, 3, 4 ,1],
        [1, 1, 3, 4, 4 ,2], [3, 2, 3, 4, 3, 1]]

# 縦の回転パターン
PATTERN = [[0, 1, 2, 3, 4, 5], [5, 1, 4, 3, 2, 0], [1, 5, 2, 0, 4, 3],
           [3, 5, 4, 0, 2, 1], [2, 1, 5, 3, 0, 4], [4, 1, 0, 3, 5, 2]]

CUBE の要素を xs, PATTERN の要素を pat とすると、サイコロを回転するプログラムは関数 map() を使って簡単に記述することができます。

map(lambda x: xs[x], pat)

横の回転はサイコロを表す配列の 1, 2, 3, 4 番目の要素を回転させるだけです。たとえば、xs が [0, 1, 2, 3, 4, 5] の場合、xs を 90 度回転すると [0, 2, 3, 4, 1, 5] になります。プログラムは次のようになります。

リスト : 横の回転パターン

def rotate_dice(xs):
    ys = xs[:]
    y = ys[1]
    del ys[1]
    ys.insert(4, y)
    return ys

関数 rotate_dice() はサイコロを横に 90 度回転させます。引数 xs はサイコロを表す配列です。最初に xs をコピーして変数 ys にセットします。そして、1 番目の要素を取り出し、それをメソッド insert() で 4 番目に挿入します。最後に ys を return で返します。rotatice_dice() を 2 回呼び出せば、サイコロは 180 度回転し、3 回呼び出せば 270 度 (反回転で 90 度) 回転します。

パズルの解法プログラムは簡単です。次のリストを見てください。

リスト : カラーダイスパズルの解法

def solver(n, ds, a = []):
    if n == 4:
        if check(*a): print(a)
    else:
        xs = ds[n]
        for pat in PATTERN:
            ys = list(map(lambda x: xs[x], pat))
            for _ in range(4):
                a.append(ys)
                solver(n + 1, ds, a)
                a.pop()
                ys = rotate_dice(ys)

関数 solver() の引数 ds が 4 つのサイコロを格納した配列、a が積み上げたサイコロを格納する配列、n が ds から取り出すサイコロの位置です。n が 4 になったら関数 check() を呼び出して、横の 4 つの面に赤、青、緑、黄の 4 色があるかチェックします。

n が 4 未満の場合、ds[n] のサイコロ xs を積み上げます。PATTERN から縦の回転パターン pat を取り出し、map でサイコロ xs に pat を適用して、向きを変えたサイコロ ys を生成します。あとは ys を a に格納して solver() を呼び出し、そのあと rotate_dice() でサイコロを横に回転します。これで 24 通りの置き方を試すことができます。

あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト１ をお読みください。

●実行結果

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

[[2, 1, 3, 3, 4, 2], [1, 2, 4, 1, 2, 3], [4, 3, 2, 4, 1, 1], [3, 4, 1, 2, 3, 3]]
[[2, 3, 3, 4, 1, 2], [1, 4, 1, 2, 2, 3], [4, 2, 4, 1, 3, 1], [3, 1, 2, 3, 4, 3]]
[[2, 3, 4, 1, 3, 2], [1, 1, 2, 2, 4, 3], [4, 4, 1, 3, 2, 1], [3, 2, 3, 4, 1, 3]]
[[2, 4, 1, 3, 3, 2], [1, 2, 2, 4, 1, 3], [4, 1, 3, 2, 4, 1], [3, 3, 4, 1, 2, 3]]
[[2, 1, 4, 3, 3, 2], [3, 2, 2, 1, 4, 1], [1, 3, 1, 4, 2, 4], [3, 4, 3, 2, 1, 3]]
[[2, 4, 3, 3, 1, 2], [3, 2, 1, 4, 2, 1], [1, 1, 4, 2, 3, 4], [3, 3, 2, 1, 4, 3]]
[[2, 3, 3, 1, 4, 2], [3, 1, 4, 2, 2, 1], [1, 4, 2, 3, 1, 4], [3, 2, 1, 4, 3, 3]]
[[2, 3, 1, 4, 3, 2], [3, 4, 2, 2, 1, 1], [1, 2, 3, 1, 4, 4], [3, 1, 4, 3, 2, 3]]

先頭のサイコロを基準にすると、標準形 (A) を横に回転した 4 通りと、(A) を上下に反転した (D) を横に回転した 4 通り、合計で 8 通りの解が出力されました。

●重複解の排除

次は重複解を排除することを考えてみましょう。横に回転して得られる解は先頭のサイコロを横に回転しなければ排除することができますね。また、(A) の解において、すべてのサイコロを上下反転すると (D) の解と一致します。(B) と (D), (E) と (F) も同様です。したがって、先頭のサイコロは (A), (B), (C) のパターンだけを調べればよいことになります。

これをプログラムすると次のようになります。

リスト : 重複解の排除

PATTERN1 = [[0, 1, 2, 3, 4, 5], [1, 5, 2, 0, 4, 3], [2, 1, 5, 3, 0, 4]]

def solver1(ds, a = []):
    xs = ds[0]
    for pat in PATTERN1:
        zs = list(map(lambda x: xs[x], pat))
        a.append(zs)
        solver(1, ds, a)
        a.pop()

PATTERN1 に (A), (B), (C) の回転パターンをセットします。そして、関数 solver1() では先頭のサイコロを取り出して、それに PATTERN1 のパターン pat を適用したサイコロ zs を生成します。あとは zs を a にセットして関数 solver() を呼び出すだけです。これで先頭のサイコロの置き方を 3 通りに限定して重複解を排除することができます。

実行結果は次のようになります。

[[2, 1, 3, 3, 4, 2],
 [1, 2, 4, 1, 2, 3],
 [4, 3, 2, 4, 1, 1],
 [3, 4, 1, 2, 3, 3]]

重複解を排除すると、解は 1 通りになります。

●Appendix : サイコロを 5 つに増やす場合

ちなみに、5 色に塗り分けられたサイコロを 5 つ使って、どの側から見ても 5 つのサイコロの面が異なる色になるような積み方を考えることもできます。

上図の場合、3 通りの解があります。興味のある方は解答を見るまえに挑戦してみてください。

解答

●プログラムリスト１

#
# dice.py : カラーダイスパズル
#
#           Copyright (C) 2012-2022 Makoto Hiroi
#

# 座標
#   上
#   ０
# １２３４
#   ５
#   下
#
# 色 : r (red), b (blue), g (green), y (yellow)
#      1        2         3          4

# キューブの設定
CUBE = [[2, 1, 3, 3, 4, 2], [2, 1, 2, 3, 4 ,1],
        [1, 1, 3, 4, 4 ,2], [3, 2, 3, 4, 3, 1]]

# 縦の回転パターン
PATTERN = [[0, 1, 2, 3, 4, 5], [5, 1, 4, 3, 2, 0], [1, 5, 2, 0, 4, 3],
           [3, 5, 4, 0, 2, 1], [2, 1, 5, 3, 0, 4], [4, 1, 0, 3, 5, 2]]

PATTERN1 = [[0, 1, 2, 3, 4, 5], [1, 5, 2, 0, 4, 3], [2, 1, 5, 3, 0, 4]]

# 横の回転パターン
def rotate_dice(xs):
    ys = xs[:]
    y = ys[1]
    del ys[1]
    ys.insert(4, y)
    return ys

# 色のチェック
def check(xs1, xs2, xs3, xs4):
    for x in range(1, 5):
        c = 1 << (xs1[x] - 1)
        c |= 1 << (xs2[x] - 1)
        c |= 1 << (xs3[x] - 1)
        c |= 1 << (xs4[x] - 1)
        if c != 0x0f: return False
    return True

# 解法
def solver(n, ds, a = []):
    if n == 4:
        if check(*a): print(a)
    else:
        xs = ds[n]
        for pat in PATTERN:
            ys = list(map(lambda x: xs[x], pat))
            for _ in range(4):
                a.append(ys)
                solver(n + 1, ds, a)
                a.pop()
                ys = rotate_dice(ys)

# 重複解の排除
def solver1(ds, a = []):
    xs = ds[0]
    for pat in PATTERN1:
        zs = list(map(lambda x: xs[x], pat))
        a.append(zs)
        solver(1, ds, a)
        a.pop()

# 実行
solver(0, CUBE)
print('-----')
solver1(CUBE)

●Appendix : 解答

red (1), blue (2), green (3), yellow (4), cyan (5) とします。重複解を除くと 3 通りの解があります。

[[2, 2, 4, 5, 3, 1],
 [2, 3, 5, 1, 4, 3],
 [3, 4, 1, 2, 5, 4],
 [4, 5, 2, 3, 1, 5],
 [5, 1, 3, 4, 2, 1]]

[[2, 1, 4, 2, 3, 5],
 [1, 2, 5, 3, 4, 3],
 [2, 3, 1, 4, 5, 4],
 [3, 4, 2, 5, 1, 5],
 [4, 5, 3, 1, 2, 1]]

[[4, 2, 1, 5, 2, 3],
 [4, 3, 2, 1, 3, 5],
 [5, 4, 3, 2, 4, 1],
 [1, 5, 4, 3, 5, 2],
 [2, 1, 5, 4, 1, 3]]

ご参考までに Python3 のプログラムを示します。

#
# dice1.py : カラーダイスパズル
#
#           Copyright (C) 2012-2022 Makoto Hiroi
#

# 座標
#   上
#   ０
# １２３４
#   ５
#   下
#
# 色 : r (red), b (blue), g (green), y (yellow), c (cyan)
#      1        2         3          4           5

# キューブの設定
CUBE = [
    [2, 2, 4, 5, 3, 1],
    [3, 3, 4, 1, 5, 2],
    [4, 4, 5, 2, 1, 3],
    [5, 5, 1, 3, 2, 4],
    [1, 1, 2, 4, 3, 5]
]

# 縦の回転パターン
PATTERN = [[0, 1, 2, 3, 4, 5], [5, 1, 4, 3, 2, 0], [1, 5, 2, 0, 4, 3],
           [3, 5, 4, 0, 2, 1], [2, 1, 5, 3, 0, 4], [4, 1, 0, 3, 5, 2]]

PATTERN1 = [[0, 1, 2, 3, 4, 5], [1, 5, 2, 0, 4, 3], [2, 1, 5, 3, 0, 4]]

# 横の回転パターン
def rotate_dice(xs):
    ys = xs[:]
    y = ys[1]
    del ys[1]
    ys.insert(4, y)
    return ys

# 色のチェック
def check(xs1, xs2, xs3, xs4, xs5):
    for x in range(1, 5):
        c = 1 << (xs1[x] - 1)
        c |= 1 << (xs2[x] - 1)
        c |= 1 << (xs3[x] - 1)
        c |= 1 << (xs4[x] - 1)
        c |= 1 << (xs5[x] - 1)
        if c != 0x1f: return False
    return True

# 解法
def solver(n, ds, a = []):
    if n == 5:
        if check(*a): print(a)
    else:
        xs = ds[n]
        for pat in PATTERN:
            ys = list(map(lambda x: xs[x], pat))
            for _ in range(4):
                a.append(ys)
                solver(n + 1, ds, a)
                a.pop()
                ys = rotate_dice(ys)

# 重複解の排除
def solver1(ds, a = []):
    xs = ds[0]
    for pat in PATTERN1:
        zs = list(map(lambda x: xs[x], pat))
        a.append(zs)
        solver(1, ds, a)
        a.pop()

# 実行
solver(0, CUBE)
print('-----')
solver1(CUBE)