www.morihi-soc.net

セキュリティの話題を中心に取扱中

SECCON 2014 オンライン予選 Write-up 詰将棋(Unknown 100)

SECCON 2014 のオンライン大会の問題で詰将棋(問題の説明文より、つめしょうきと読むらしい)の問題があったので解いてみました。

詰将棋のおさらい

まずは詰将棋のルールのおさらいから
  • 先手(駒が上を向いている方で,先に駒を動かす。▲で表す)常に大手をかけ続けて、なおかつ最短の手順で詰みの状況まで状態遷移させる必要がある。
  • 後手(駒は下を向いていて,王がある方。△で表す)常に最長の手順で逃げ続けなければならない。
これが一般的な詰将棋のルールです。では CTF で出題された問題を見てましょう.

 

問題

SECCON2014 オンライン予選 詰将棋

 

見慣れない駒がありますね。現在の将棋では、王(玉)、飛車、角、金、銀、桂、香、歩の8種類の駒が使われます。
しかし今回は特、銅、平という3つの特殊な駒が、動き方の注釈とともに使われています。
推測ですが、既成品の詰将棋を解くプログラムの利用を回避するために導入したのでしょう。

 

ここで1つ重要なことがあります。各駒の通常の動き方は説明されていても、成った場合の動き方は説明されていません

 

通常の将棋のルールでは、相手の陣地に入った時に駒を裏返して成駒にすることができます。
この成駒は動き方が変わり、対局や詰将棋では考慮すべき重要事項です。
しかし成駒の動き方が説明されていないことは、成ることが想定されていないと言い換えることができます。
この気付きで考慮すべきパターンがかなり減りました。

 

解答

さて,それでは解答です.詰みまでの手順は下記のとおりです。なお手順は複数あるようですが、フラグが通ったこと確認した手順です。
※駒の位置については、出題図の番号を記載しています。

 

▲22銅△12王▲5特△同王▲10平△6王▲11平△同王▲4銀△16王▲15金△23王▲29金
まで十三手詰め

 

9手目▲4銀に対して、△16王▲15金の手順が相手の飛車の横効きを王で遮り、盤上の金を有効活用する点がポイントかと思います。

 

最終的な盤面はこちら。
SECCON2014 オンライン予選  詰将棋 最終盤面

 

フラグは駒が乗っているマスの番号をカンマ区切りで書いたものということで、「4,15,18,22,23,28,29」でした。
submit したら100ポインヨ ゲットだぜ!
以上です.

 

参考

SECCON 2014
http://2014.seccon.jp/
プログラミングして解いた方のプログラム
http://ideone.com/M7u29I

 

Written by morihisa

7月 20th, 2014 at 9:24 am

Posted in CTF,その他