ナンプレ（数独）問題作成プログラム その22 normalize

normalize

analyze の最初の版で目指していたのは、convertによって変わらない解法のリストを出力することであった。それとは別に、convertによって替わり得る問題、つまり実質的には同じ問題を違う問題として出力してしまうという危険性を避ける必要がある。それには何らかの基準で正規の形を決めてしまえば良い。
normalize は固定数字（初期数字）の位置が左上の方に多く集まるようにconvertで変換し、その後、ナンプレ盤面配列の順序でみて、最初から123というように数字が出るように数字を振り直すことによって正規形を得る。その過程でconvertの変換のすべての組み合わせを試すので、すべての組み合わせについて単純版analyzeを実行して、仮の評価値を計算し、評価値が最も低い解法の組み合わせを求める。これでだいたいやりたいことができる。
convertは対称性を崩さないようにしているので、組み合わせの数は多くないから計算時間はそんなにかからない。逆に、この正規化は真の意味での正規化ではない。しかし、まあいいことにする。
MSaito/NumPl · GitHub

次は generate

次はgenerateだが、またちょっと他のことをしなければならないので、少し間が開く。

読んでいる本

お薦めするって程でもないというか、現代のミステリファンからするとかなり物足りないのではないかと思われる。しかし、読める。読めるというのはどういうことかよく分からないが、読めない本もあるのだ。古い作品を読むときは、古さに合わせるということを読者の側でやって当然という気持ちで読むからだろうか。

思考機械の事件簿 1 (創元推理文庫 176-1 シャーロック・ホームズのライヴァルたち)

ナンプレ（数独）問題作成プログラム その21 xywing

analyze を単純化

analyze は無駄に複雑で重い割りに、目的を完全には達成していないので単純化することにしました。苦労してデバッグしたのに、機能をほとんど取ってしまいました。「泣いて馬謖を斬る」という感じでしょうか。いや、三国志は全然詳しくないです。どっかで聞いたような言葉なので使ってみました。

XY-Wing

XY-Wing という解法を追加しました。これでXY-Wingを使った問題も作成できるようになるはずです。問題点としては、XY-Wing のパターンって私には見つけられないんですよ。なのでandroidアプリにはまだ入れていないのです。何らかのサポート機能が必要だと思うんだが、面倒だな。売れてないし。

アニメが面白かった

デンキ街の本屋さん 1 (コミックフラッパー)

デンキ街の本屋さん (2) [Blu-ray]

androidアプリ「ミニナンプレ6×6」をリリースしました

android 用アプリ「ミニナンプレ6×6」をリリースしました。

ミニナンプレ6x6その0 - Google Play の Android アプリ無料
ミニナンプレ6x6その１ - Google Play の Android アプリ100円

先に入力するマスを指定して、その後数字を入力します。指定したマスはスワイプすることによって位置を修正できます。このため、スマフォのような比較的小さい画面でもミニナンプレをプレイすることが出来ると思います。ただし、入力数字の訂正機能はundoしかありません。（そして数字入力をミスするほどボタンが小さいならundo入力もミスする可能性があります）

パズルを解くと、ご褒美画像としてはてなハイクの戯壇さんによるイラストが見られます。

開発的には、ミニサイズでどの程度難しい問題を生成できるかという点に関心がありました。これには二つの相反する予想ができます。ひとつは、6×6というサイズの制限によって難しい問題は作れないのではないかという予想。もうひとつは、サイズが小さいことによって問題を作成しチェックする時間が短くなり、その結果として難しい問題も発見しやすくなるという予想です。

結果的には、まあまあというところ。例えばサイズの制限はHidden Triple を不可能にします。一行まるまる空いていても、Naked Triple になってしまうからです。従ってHidden Pair までしか生成できません。一方、X-Wing は問題なく生成できました。Sword Fish も生成できるけど、時間がかかります。

ミニナンプレということで、ユーザーも易しい問題を期待している気がしますので、とりあえずSword Fish は問題に入れないことにしました。

ナンプレ（数独）問題作成プログラム その20 analyze

酔っ払ってプログラムを書いた。

一度作った問題を convert によって変換して何度も使うようにするという考えであった。ところが、convert すると solve で求める解法が違ってしまうので、convertで変わらないような解法の情報を求めようとしていたのであった。つまり、どの解法を何回使って解けるかということについて、できるだけ難しい方法を使わない最低の解法を求めようとしていたのである。
だいたい思いついたのだが、解法プログラム全部について同じような変更を入れなければならず、そいつは面倒だったので手をつけないでいた。しかし、年末年始に酒を飲んでから、突然やる気を出してプログラムを書いたのであった。

酔っ払って書いたプログラムはバグだらけだった。

コンパイルを通すところまでは酔っ払っていても行けたのだが、実行すると終了しない。こりゃあかんわい、ということで醒めてから書き直し。再帰すりゃなんとかなるだろうと思っていたが、再帰しない方がよいとわかった。

局所最適解を求めていた。

動くようにはなったが、convert を掛けるとやはり解情報が変わってしまう。少し考えてみると、今回書いたプログラムではまだ局所最適解を求めているだけであり、このアルゴリズムでは大域最適解は求まらないようだ。この問題に限らず、大域最適解を求めることは、一般には難しい。局所最適解を求めるプログラムを多少修正しても大域最適解を求めるプログラムにはならないのだ。全件検索すればよいのだが、その場合計算時間の予測がつかない。なので、一度あきらめる。analyze という実行ファイルができるまでのところは、GitHubに挙げておく。名前をanalysis ではなく analyze にしたのは、動詞の方がよいと思ったから。

convert のもう一つの懸案事項

convert によって問題数を増やせるのはよいのだが、一つ気になることがある。それは、自動生成した問題の中に convert によって変形できる問題があるのではないかということである。問題を10問作ってそれをconvertによって100問に増やしたつもりが、その100問の中に最初の10問と同じ問題があるかも知れない。これは嫌である。それを避けるには、何か正規の形というものを定めて、正規形になるようにconvertして、そこで同一性をチェックすればよい。解情報がconvertによって変わらないのであれば、それを使って少なくとも同一でないことが示せたのだが、それがダメになったので、正規形を考える必要性が高くなったということでもある。

ウィッチアクティビティ

なんでこの曲が頭の中で鳴っているかと考えたら、どうも android で Activity というクラスを使っているかららしい。

ウィッチ☆アクティビティ

• KMM団(倉石たんぽぽ(CV.井澤詩織)、飾鈴(CV.麻倉もも)、宇津木環那(CV.夏川椎菜)、目野輪冥(CV.飯田友子)、桂虎徹(CV.日岡なつみ))
• Anime
• ¥250
• 

• provided courtesy of iTunes

無関係なプロジェクトを閉じる

android 開発で、eclipse を起動する度にエラーが大量に出たり、たくさんあるソースのうち一個だけ java.lang.Object が見つからないとかでソースが全部エラーになったりと、わけのわからない状態になっていた。
泥沼の中で溺れるように試行錯誤していたのだが、起動時の動作が不安定ということは、起動時の処理が重すぎるということだろうと考えた。
プロジェクトを全部閉じてから、必要最小限だけ開くことにしたら、ずいぶん状況がすっきりしてきた。
android 以前のJava 開発時にはプロジェクト開きっぱなしで問題なかったんだけど、android では閉じた方がいいみたいだ。
パッケージエクスプローラーから、プロジェクトを右クリックして「無関係なプロジェクトを閉じる」ってやると、関係あるプロジェクトも含めて他のプロジェクトを全部閉じてくれるので、エラーになるけど、依存ライブラリのプロジェクトを開くとエラーが消える。

ナンプレ（数独）問題作成プログラム その19 analysis

バグではなくて仕様です

convert のバグと思われた事、convert すると使用する解法アルゴリズムが変わるという事は、バグというよりも仕様でした。前回の結果では、Locked Candidate の数が変わっていたわけですが、その原因はブロックの位置が変わることによって、最初にみつかる Locked Candidate が変わることにありました。
hidden singel アルゴリムによってそれ以上候補が消せなくなると、Locked Candidate アルゴリズムで消せる候補を探索します。その時、ブロックと行、列との組み合わせを見ていくわけですが、二つ以上Locked Candidateの形になっていると、見ていく順番によって消されることになるマスと数が異なります。そして消した後、また最初から naked single, hidden single というようにアルゴリズムを使って数を消していくのですが、この時に以前あったもうひとつのLocked Candidate の形が消えることがあるわけです。
順番に依存しないようにするのは面倒なので、これは「バグではなくて仕様です」

仕様でした

しかし、この問題作成プログラムが完成したら利用しようと手ぐすね引いて待ち構えている大勢のアプリ制作者がいると思うと、そうそう手を抜いた仕様で公開するわけにはいきません。
というわけで、これから仕様変更します。convertによって変わらないような形で、どのアルゴリズムを何回使用するかを表示するようにします。さっき風呂の中で考えていたら、大したことないという気がしてきたので。
ちなみに、本当にこの問題作成プログラムの完成を待って、数独のパズルゲームを作ろうと考えているとしたら、それはビジネスとして後手にまわっていますよ。完成など待たずに、「問題を売ってくれ」と言えばこっそり売りますから。そうすれば、完成を待っている呑気な競争相手を出し抜くことが出来るわけです。

analysis

以前に書いた solve や recursion_solve とは違うので、analysis という名前でプログラムを作ります。naked single は最初に使うのでそれは別にして、それ以後の解法である候補が消せたとしても、そこでリターンしないで再帰すればいいはずです。そして再帰の返却値が一番小さいものを採用すればよい。
となると、このナンプレ問題作成で最初に否定した難易度の定義が必要になります。しかし、それを今更やるのは癪なので、difficulty ではなくDと隠語で呼ぶことにします。昔から、口に出すことを憚るものをDと隠語で呼ぶ習わしがあるのです。
実際のプログラムはこの次。よくwebにいる天才プログラマじゃないんだから、そうそう簡単に書けるものか。

吸血鬼ハンター１　吸血鬼ハンター“D”

バンパイアハンターD(オリジナル日本語バージョン) [DVD]

バンパイアハンターD(劇場公開バージョン) [DVD]

ナンプレ練習お試し版にバグ

今度は、ナンプレ練習お試し版にバグがあった。しかも、スマートフォンの場合に起動しないという致命的なバグ。製品版が売れないと思っていたけど、お試し版にバグがあったら、そりゃあ製品版は売れないよなぁ。
クラッシュレポートをちゃんと見たらすぐに分かったという単純なバグ。というか、なんでコンパイルできたんだ？　なんでエミュレータはクラッシュしなかったんだ？　そっちの方がおかしいよ。
まあどのみち、スマートフォンでは画面が小さすぎてプレイに無理があるとは思っていたんだけど、タブレット使いが大量に買ってくれないかなぁ。学校とか。世にも珍しい（かどうかは知らないが）インストール権限不要アプリなんだけど。
こうやって書いていたら、製品版にも同じバグがあるような気がしてきたので、これから確認する。