読者です 読者をやめる 読者になる 読者になる

paiza開発日誌

IT/Webエンジニア向け総合求人・学習サービス「paiza」(https://paiza.jp ギノ株式会社)の開発者が開発の事、プログラミングネタ、ITエンジニアの転職などについて書いています。

もし幼馴染と許嫁が15パズルの解法アルゴリズムを教えてくれるとしたら

f:id:paiza:20150603160136p:plain:left2015年4月14日より2015年5月19日まで開催した、paizaオンラインハッカソン Vol.5「俺の許嫁と幼なじみが修羅場すぎる」と「POH5+レナとミナミの国際プログラミング選手権」は全て解けましたでしょうか? (プレゼント対象期間は終了しましたが、問題チャレンジは可能なので、未チャレンジの方は是非チャレンジください!)

paiza.jp

POH5に出題される問題は解説するほどのむずかしさでもないので省きますが、POH5+の15パズル問題は多少工夫が必要なので、POH5+について今回もPOH恒例の「図解解説」をしてみたいと思います。

■問題文の再確認

まずは問題文を確認してみましょう。

15パズルとは、1~15の数字が書かれたタイルを4x4の合計16マスからなる枠の中でスライドさせ、並び替えるゲームです。 タイルのない空マスの四方に隣接するタイルを空マスへ移動することでゲームを進行します。
例えば、次の図のようにゲームを進行することができます。

タイルをスライドさせ、盤面を完成させるプログラムを作成してください。 ただし、最短の手数でパズルを完成させる必要はなく、盤面を完成させることができるならば、どのような順番でタイルをスライドしても構いません。
https://paiza.jp/poh/enshura-special

■乱択法

今回のパズルは探索になる為、幅優先探索深さ優先探索など色々なやり方がありますが、一番簡単で色々考えなくてもよい乱択法での解法について解説をしたいと思います。
基本方針はランダムに動かして、上手くパズルが組み上がったらランダムに動かした履歴を出力するというものです。完全にランダムにしたら流石に時間がかかるので、いくつか形が確定したら動かさないパズルのピースを決めていくという処理をしていきます。

基本的には1から順に15まで、所定の位置に確定したら動かさないと言う処理をしていきます。1が左上に移動したら1は動かさない、2が最上段、左から2マス目に移動したら動かない、と言う感じです。

ただし、例えば1、2、3、4を順に詰めていてしまうと3を動かさない事にしてしまうと4、が収まらない場合が起こりえます。下記のような場所に4が有った場合は3を動かさないと3,4が所定位置に納まりません。

◆3を動かさなければ行けない場合

f:id:paiza:20150603154440p:plain

f:id:paiza:20150603154451p:plain

f:id:paiza:20150603154459p:plain

f:id:paiza:20150603154514p:plain

f:id:paiza:20150603154520p:plain

なので 3, 4 同時に収まるまでは、3もランダムに動かすようにします。
同様に、、

7, 8
9, 13
10, 14
11,12,15

と同時に収まらないとどちらかが確定してしまうと上手くいかないパターンを処理します。色分けすると以下のようになります。

f:id:paiza:20150603155042p:plain

赤の部分、青の部分、紫の部分、黄色の部分、最後に灰色の部分がまとめて確定するまでランダムに動かしていきます。
白い部分はそれぞれ1つのパズルごとに確定させてく処理となっています。

この方針は運任せで動作しているのが大部分なので手数は運によって大きく変動します。何度も送信してもいいですが、実行時間ギリギリまで試行回数を伸ばすという処理もしています。

この解き方はパズルの動きを実装出来るならば複雑な探索をせずとも運に任せて回答を得ることが出来ます。手数を小さくしようとする場合は真面目に探索などをして回答を得るのが良いですが取り敢えず解くという解法がこの考え方になります。

pythonによる解法コード

#coding=utf-8
import random, time, copy

def check(board):
    for i, v in enumerate(reduce(lambda a,b: a+b, board)):
        if (i+1) != v:
            return False
    return True

def check_line(board):
    correct = [ \
                [ 1,  2,  3,  4],\
                [ 5,  6,  7,  8],\
                [ 9, 10, 11, 12],\
                [13, 14, 15, 16]\
            ]
    lines = []
    for i, v in enumerate(correct):
        if v == board[i]:
            lines.append(i)
    return lines

def find_mover(board, n):
    for i in xrange(len(board)):
        if n in board[i]:
            return i, board[i].index(n)

def random_walk(board, from_p, to_p, fixed=[]):
    moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    res = []
    mover = find_mover(board, 16)
    while len([v for i, v in enumerate(to_p) if board[v[0]][v[1]] == from_p[i] ]) != len(to_p):
        move = moves[random.randint(0,3)]
        moved = mover[0] + move[0], mover[1] + move[1]
        if moved in fixed:
            continue
        if 0 <= moved[0] < 4 and 0 <= moved[1] < 4:
            board[moved[0]][moved[1]], board[mover[0]][mover[1]]\
            = board[mover[0]][mover[1]], board[moved[0]][moved[1]]

            res.append(board[mover[0]][mover[1]])
            mover = mover[0] + move[0], mover[1] + move[1]
    return res, board

def solver(board):
    fixed = []
    to_list = [[(0, 0, 1)], [(0, 1, 2)], [(0, 2, 3), (0, 3, 4)],\
               [(1, 0, 5)], [(1, 1, 6)], [(1, 2, 7), (1, 3, 8)],\
               [(2, 0, 9), (3, 0, 13)], [(2, 1, 10), (3, 1, 14)],\
               [(2, 2, 11), (2, 3, 12), (3, 2, 15)]]
    ans = []
    for i in to_list:
        froms = [j[2] for j in i]
        tos = [(j[0], j[1]) for j in i]
        res, board = random_walk(board, froms, tos, fixed)
        ans += res
        fixed += tos
    return ans

def board_input():
    board = []
    for i in xrange(4):
        board.append(map(int, raw_input().replace('*','16').split()))
    return board

def board_output(board):
    for i in board:
        print i
    print "-----------"


if __name__ == "__main__":
    start = time.time()
    ans_len = 10000000
    res = []
    board = board_input()
    board_tmp = copy.deepcopy(board)
    while True:
        board = copy.deepcopy(board_tmp)
        ans = solver(board)
        if len(ans) < ans_len:
            res = ans
            ans_len = len(res)
        if time.time() - start > 7:
            break
    print '\n'.join([str(i) for i in res])

■もっとコードが見たいと言う場合

paiza.hatenablog.com

先週更新した上記記事で、各言語の最短手数クリアしてるコードを掲載していますので、更に色々な解法コードを見たいと言う方は是非ご覧下さい。

■壁紙プレゼントについて

paizaに会員登録すると、下記の壁紙3種類がダウンロードできます!是非お気軽にご登録下さい!
f:id:paiza:20150520153816j:plain
f:id:paiza:20150520153830j:plain
f:id:paiza:20150520153838j:plain





paizaではスキルのあるエンジニアがきちんと評価されるようにし、技術を追い続ける事が仕事につながるようにする事で、日本のITエンジニアの地位向上を図っていければと考えています。特にpaizaではWebサービス提供企業などでもとめられる、システム開発力や、テストケースを想定できるかの力(テストコードを書く力)などが問われる問題を出題しています。

テストの結果によりS・A・B・C・D・Eの6段階でランクが分かります。自分のプログラミングスキルを客観的に知りたいという方は是非チャレンジしてみてください。

http://paiza.jp

プログラミング入門講座|paizaラーニング

PHP入門編Ruby入門編Python入門編Java入門編JavaScript入門編C言語入門編C#入門編アルゴリズム入門編