2015年4月14日より2015年5月19日まで開催した、paizaオンラインハッカソン Vol.5「俺の許嫁と幼なじみが修羅場すぎる」と「POH5+レナとミナミの国際プログラミング選手権」は全て解けましたでしょうか？ (プレゼント対象期間は終了しましたが、問題チャレンジは可能なので、未チャレンジの方は是非チャレンジください！)
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を動かさなければ行けない場合
なので 3, 4 同時に収まるまでは、3もランダムに動かすようにします。
同様に、、
7, 8
9, 13
10, 14
11,12,15
と同時に収まらないとどちらかが確定してしまうと上手くいかないパターンを処理します。色分けすると以下のようになります。
赤の部分、青の部分、紫の部分、黄色の部分、最後に灰色の部分がまとめて確定するまでランダムに動かしていきます。
白い部分はそれぞれ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に会員登録すると、下記の壁紙３種類がダウンロードできます！是非お気軽にご登録下さい！
paizaは、技術を追い続けることが仕事につながり、スキルのある人がきちんと評価される場を作ることで、日本のITエンジニアの地位向上を目指したいと考えています。
自分のスキルを磨いていきたいと考えている方におすすめなのが「paizaラーニング」。オンラインでプログラミングしながらスキルアップできる入門学習コンテンツです。初心者でも楽しくプログラミングの基本を学ぶことができます。
そして、paizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。
スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。
