15パズルの問題を作成するプログラム（Python）

1. 動機

15パズルの問題を解いていて，自分でも作問できるのではないかと思ったこと．

2. 15パズルについて

縦4マス、横4マスの盤に，1から15の番号が書かれた15枚のタイルを配置する．左上が1，右上が4，左下が13で，右下にはタイルを配置しない．空いているマスには，上下左右のいずれかで隣接しているマスのタイルを移動させることができ，この操作を繰り返した状態から始めて初期配置に戻すことが目的である．

3. 実装

15パズルの問題は，初期配置を崩していけば作ることができます．なお、実装を簡単にするため，初期配置はタイルを16枚並べた状態とします．配置を崩すには「16番タイルと隣接しているタイル」を取得する必要があるため，各タイルには番号と位置という二つの属性を持たせます．

class Tile:
    def __init__(self, number, location):
        self.number = number
        self.location = location  # locationは，各タイルが置かれる盤上の位置；左上が0，右上が3，左下が12，右下が15

各タイルについて16番タイルと隣接しているかどうかを調べ，該当するもののリストを取得します．

def check_moveable_tiles():
    for i in range(16):
        tiles[i].isup16 = 4 <= tiles[i].location == tiles[15].location + 4
        tiles[i].isdown16 = 11 >= tiles[i].location == tiles[15].location - 4
        tiles[i].isright16 = tiles[i].location % 4 != 3 and tiles[i].location == tiles[15].location - 1
        tiles[i].isleft16 = tiles[i].location % 4 != 0 and tiles[i].location == tiles[15].location + 1
        tiles[i].ismoveable = any([tiles[i].isup16, tiles[i].isdown16, tiles[i].isright16, tiles[i].isleft16])
    return [tiles[i].number for i in range(16) if tiles[i].ismoveable]

取得したリストから，16番タイルと入れ替えるタイルを無作為に選択し，16番タイルとの位置関係を反転します．

def replace_tiles():
    moveable_tiles = check_moveable_tiles()
    shuffle(moveable_tiles)
    rep_tile = moveable_tiles[0]  # 16番タイルと入れ替えるタイル
    # 上下の移動でタイルを入れ替える場合
    if tiles[rep_tile - 1].isup16 or tiles[rep_tile - 1].isdown16:
        tiles[rep_tile - 1].isup16, tiles[rep_tile - 1].isdown16 = tiles[rep_tile - 1].isdown16, tiles[rep_tile - 1].isup16
    # 左右の移動でタイルを入れ替える場合
    if tiles[rep_tile - 1].isright16 or tiles[rep_tile - 1].isleft16:
        tiles[rep_tile - 1].isright16, tiles[rep_tile - 1].isleft16 = tiles[rep_tile - 1].isleft16, tiles[rep_tile - 1].isright16
    tiles[rep_tile - 1].location, tiles[15].location = tiles[15].location, tiles[rep_tile - 1].location

この操作を充分な回数行った後で tiles[i].number と tiles[i].location を確認してみると，次のようになっています．

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]  # tiles[i].number
[1, 5, 3, 7, 4, 0, 11, 9, 13, 12, 6, 10, 8, 14, 15, 2]  # tiles[i].location

これは，1番タイルが1の位置に，2番タイルが5の位置に，……，16番タイルが2の位置にあるということを表しており，下図のようになっているという意味です．

 6  1 16  3
 5  2 11  4
13  8 12  7
10  9 14 15

このままでは分かりにくいので， tiles[i].location と tiles[i].number を zip 関数でまとめ， tiles[i].location が昇順になるよう並べ替えます．

_, shuffle_result = zip(*sorted((zip([tiles[i].location for i in range(16)], [tiles[i].number for i in range(16)]))))

すると次のようなタプルが返ってくるので，見やすく成形すれば完成です．

(6, 1, 16, 3, 5, 2, 11, 4, 13, 8, 12, 7, 10, 9, 14, 15)

4. コード

from random import shuffle


class Tile:
    def __init__(self, number, location):
        self.number = number
        self.location = location  # locationは，各タイルが置かれる盤上の位置；左上が0，右上が3，左下が12，右下が15


tiles = [Tile(i + 1, i) for i in range(16)]  # 各タイルを生成し，初期位置にセットする


def check_moveable_tiles():
    for i in range(16):
        tiles[i].isup16 = 4 <= tiles[i].location == tiles[15].location + 4
        tiles[i].isdown16 = 11 >= tiles[i].location == tiles[15].location - 4
        tiles[i].isright16 = tiles[i].location % 4 != 3 and tiles[i].location == tiles[15].location - 1
        tiles[i].isleft16 = tiles[i].location % 4 != 0 and tiles[i].location == tiles[15].location + 1
        tiles[i].ismoveable = any([tiles[i].isup16, tiles[i].isdown16, tiles[i].isright16, tiles[i].isleft16])
    return [tiles[i].number for i in range(16) if tiles[i].ismoveable]


def replace_tiles():
    moveable_tiles = check_moveable_tiles()
    shuffle(moveable_tiles)
    rep_tile = moveable_tiles[0]  # 16番タイルと入れ替えるタイル
    # 上下の移動でタイルを入れ替える場合
    if tiles[rep_tile - 1].isup16 or tiles[rep_tile - 1].isdown16:
        tiles[rep_tile - 1].isup16, tiles[rep_tile - 1].isdown16 = tiles[rep_tile - 1].isdown16, tiles[rep_tile - 1].isup16
    # 左右の移動でタイルを入れ替える場合
    if tiles[rep_tile - 1].isright16 or tiles[rep_tile - 1].isleft16:
        tiles[rep_tile - 1].isright16, tiles[rep_tile - 1].isleft16 = tiles[rep_tile - 1].isleft16, tiles[rep_tile - 1].isright16
    tiles[rep_tile - 1].location, tiles[15].location = tiles[15].location, tiles[rep_tile - 1].location


for _ in range(100):
    replace_tiles()

# tiles[i].locationとtiles[i].numberをzip関数でまとめ，tiles[i].locationが昇順になるよう並べ替えてから展開する
_, shuffle_result = zip(*sorted((zip([tiles[i].location for i in range(16)], [tiles[i].number for i in range(16)]))))

shuffle_result = [str(shuffle_result[i]).rjust(2) for i in range(16)]
shuffle_result[list(shuffle_result).index('16')] = '--'

for i in range(4):
    print(*shuffle_result[i * 4: i * 4 + 4])

5. 実行結果

 1  7  2  4
 9 10 13  8
 3  6 -- 15
 5 14 12 11

6. 終わりに

以外と早く書けたので，驚くとともに自分の成長を感じられて嬉しかったです．