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

CodeIQ Blog

自分の実力を知りたいITエンジニア向けの、実務スキル評価サービス「CodeIQ(コードアイキュー)」の公式ブログです。

「アルゴリズム:【言語不問】最適解を目指せ!!(ナンプレ盤面問題)」解説会開催!解説資料の一部を公開します!! #ranking #ナンプレ #nanpure #numberplace

CodeIQの中の人、riyoppe です。


株式会社フィックスターズの田中 伸明@tomerunさんの出題問題、
アルゴリズム:【言語不問】最適解を目指せ!!(ナンプレ盤面問題)』に挑戦された方を対象に、解説会が開催されました。

ご参加いただいた方より、「解説に使った資料を公開してほしい」との声をいただきましたので、田中さんに公開していただきました!!

当日参加できなかった方も、ぜひ参考になさってください!

===============================


★☆★CodeIQ解答者限定 解説会を開催しました★☆★

CodeIQ”に掲載した問題に解答していただいた方を対象に、解説会を開催しました!
アルゴリズム:【言語不問】最適解を目指せ!!(ナンプレ盤面問題)※問題文はこちら』に挑戦したくださった方は46名にのぼり、そのうち11名の方に解説会にご参加いただくことができました。
お忙しい中お集まりいただき誠にありがとうございました。

f:id:codeiq:20130919190646j:plain
問題作成者をはじめ、上位解答者にも解答方法を紹介していただき、
大変充実した会となりました!
当日参加できなかった方のためにも、
当日発表された解説資料の一部を公開いたします。
ご興味のある方は是非目を通してみてください。



<解説資料>

■問題作成者:フィックスターズ 田中伸明
- 出題意図と典型解法について


- 解法の説明


■解答者第一位:machy 様


■解答者第二位:Mi_Sawa 様


■解答者第三位:foota 様 (フィックスターズ 二木紀行)



<問題文>はこうなっていました。

まずは問題に必要なファイルを以下からダウンロードしてください。
https://dl.dropboxusercontent.com/u/110505645/CodeIQ/201307/fixstars_trial_01.zip

■問題
500×500のマス目があり、その中の一部のマスに1〜9の数字が書き込まれています。

あなたは数字パズルが好きなので、まだ数字が書き込まれていないマスに1〜9の数字を書き込んで、
このマス目をナンプレの盤面に近づけようとしました。

「ナンプレの盤面に近い」を、次のように測定します。

・すべての横に隣り合った9マスについて、その9マスの中で数字1〜9がちょうど1回ずつ使われていれば+1点(500*(500-9+1)=246000箇所あります)
・すべての縦に隣り合った9マスについて、その9マスの中で数字1〜9がちょうど1回ずつ使われていれば+1点(同じく246000箇所あります)
・すべての3*3の正方形をなす9マスについて、その9マスの中で数字1〜9がちょうど1回ずつ使われていれば+1点((500-3+1)*(500-3+1)=248004箇所あります)

この合計スコアが高くなるような数字の書き込み方を探してください。


testcase.txt が問題のマス目です。
数字が書き込まれていないマスを0で表しています。

※この問題ファイルは次のようにして作成しました。
・各マス目について、5/6の確率で0にする
・残りの1/6の場合、1〜9の数字のどれかを等確率で選ぶ

■提出形式
提出するファイルの1〜500行目に、testcase.txtで0になっているところを1〜9のいずれかの数字で置き換えたものを記載してください。
はじめから0以外の数字だった部分はそのままです。
501行目は空行にして、502行目以降には工夫した点や感想、書いたプログラムなどを自由に記載してください。
文字コードや改行コードは(ある程度メジャーなものであれば)気にする必要はありません。

answer_sample.txt が提出するファイルの例です。

使用する言語・ツールに制限はありません。
純粋に高いスコアを狙うだけではなく、ひたすら処理の高速化を突き詰めたり、シンプルなコードにもかかわらずそれなりに高いスコアを取ることを目指したり、といったアプローチも歓迎します。

■サンプルコード
参考のために、C++11でのサンプルコードを付けました(g++4.8とVC2012で動作確認)。
解答にはこれらのコードの流用もOKです。

・benchmark1.cpp
 「0になっているところをランダムな数字で埋めてスコアを計算する」
 のを100回繰り返し、一番良かったものを出力するプログラムです。
 標準入力でtestcase.txtの内容を与えてください。

・benchmark2.cpp
 それぞれの0になっている位置について、同じ9マスの行・9マスの列・3*3の正方形に入っている
 ほかの数字と最も重複しないものを選んで決めていくプログラムです。
 標準入力でtestcase.txtの内容を与えてください。

・score.cpp
 スコアを計算するプログラムです。標準入力で入力を受け取ります。
 はじめから1〜9になっているマス目が正しくそのままかどうかまではチェックしていません。

===============================


いかがでしたでしょうか?

当日は大変盛り上がったようです!
こんな声もいただいています。

次回(あるのか?)もお楽しみに!