お気づきの点や感想要望などなんでもＯＫ！
としひでさん、全クリアーおでとうございます。 そして、解説のＨＰも拝見させていただきました。まだ理解しきれていませんが とても興味深いアプローチだと思います。ところで、最適解等についてと言うこと ですが最適解を得る確信を得たのでしょうか。 以下、deepgreenさんへ (1) おそらく 719面 だと思います。 口口口口口口口口口口口口口 口 口 口 口 口 口 口 口 口口口 口口口 口口口 口口口 口口★ 口口口 口 口 口口口 口口口 口口口 口口口 口口口 口口口 口 口 口 口 口 口 口 口 口口口口口口口口口口口口口 STEP=107 Auther=KOICHI (2) 37step です。 特に(1)の質問はスルドイ質問です。ついでに全1000問の特徴も書いておきます。 Ａ）ボードサイズは、１５×１０の固定です。 Ｂ）全問とも交差点と道だけです。(２×２などの広場はありません) Ｃ）初期状態は、始点の１箇所だけ塗られているパターンだけです。
最適解等について書いてみました。
高橋さん、ありがとうございます。 面白い話にはついつい引き込まれてしまいます。仕事が忙しいので 見るだけにしようと思っていたのですが、。。。 解が存在することはわかりました。あとは最短経路を求める問題が 私の関心事ですが、こちらは難問そうですね。 甘えついでにもう少し教えてください。 （１）ＸＯＲの１０００面の問題で最大の面のスケール(交叉点の 数と線の数）はどの程度でしょうか？ （２）以下の問題を高橋さんのＳｏｌｖｅｒで解くと何ステップに なりますか？（この問題の交叉点の数＝２，線の数＝４） □□□★□□□ ★：始点 □ □ □ □□□ □ □ □ □ □ □□□□□□□ □ □ □ □ □□□ よろしくお願いします。
deepgreenさん、こんばんは。 deepgreenさんに投稿して頂けると、なんだかとても嬉しくなります。 ご質問の件ですが、 XORは歩数を意識しなければ、どんな問題でも必ず解けるはずです。 行ったり来たりのチドリ足で確実に塗りつぶしていくことが出来ます。 XORはいかに無駄なチドリ足を無くしてどれだけ歩数を短縮出来るかと いうパズルのようです。 以下、独り言です。 ところで、私のソルバーは全1000問解けましたが、重大な欠点に気付き ました。初期状態で道のあちこちが既に塗りつぶしてある場合には間違 った結果を出す場合があります。下図なら 9step と答えが返ってきます。 ★はスタート位置 ※※※※※※※ ※●●●●口※ ※口※※※口※ ※口※※※口※ ※●●●●★※ ※※※※※※※ 3(本線) + 6(穴埋め) = 9step もちろん、9step で塗りつぶすことは出来ません。1000問中にこの ような問題が無かっただけのことです。(愕然)
ずっとご無沙汰のdeepgreenです。 ＸＯＲはなかなか面白いですね。 ところで、ＸＯＲはどのような面の問題でも解が存在するのでしょうか？
ご指摘のとおりです。書き込み直後に解けない問題が出てきて焦りましたが、 どうやら三叉路以上で五回訪問しなければならないますが存在するようです。
やっぱり toshihideさんは、としひでさん でしたか。(変な文章) それにしても正統派のアプローチをされているのですね。 私の方法と全く異なるようなので、としひでさんの概要説明では としひでさんの方法が良く理解出来ていませんが、 「各マス間の移動回数を求めた後に経路を探索する。」 これは思い付けませんでした。どうやってプログラムを書いたら いいのか想像も付きません。私の方法よりかなりスマートになって いるような気がします。検討してみます。 ところで、「一つのマスに3回以上訪れることがない」というのは、 ちょっと気になります。下図の問題は解けるでしょうか。 ※※※※※※※※※※※※※※※ ※※※※※●口口口口口口口口※ ※※※※※口※※※※※※※口※ ※口口口※口※口口口※※※口※ ※口※口口口口口※口※※※口※ ※口口口※口※口口口※※※口※ ※※※※口口口※※※※口口口※ ※※※※口※口※※※※口※口※ ※※※※口口口※※※※口口口※ ※※※※※※※※※※※※※※※ STEP 72 takaken 「4差路の場合は理論的に5回必要」な場合があると思うのです。 ただし、あくまでも理論上であって全1000問中にそのような事例が あったかというと、無かったような気もしますが。
ようやく500面達成！ 歩数制限がシビアだなあと思っていたら、解答者によって更新されるのですね！ 本線＋袋小路は私も考えたのですが、本線に経路の重複を認めるというところまで 思考が及ばず、結局構想じまいに終わってしまいました。 今使っているソルバの概略は、 各ます間の移動回数を求めた後に、経路を探索するというものです。 一つのますに3回以上訪れることがないことと、 任意の隣り合うますの移動回数は4本以内である（証明はしてません）という 制約条件の元で幅優先的（通路は深さ優先的）に求めています。（通路：隣接ますが2ます以下） 実行時間ですが、詳しいプロファイルをとってるわけではないですが、 高橋さんのものよりもやや遅い気がします。 1秒以内のものもありますが、ものによっては30分くらいかかってますので。 改良前のものは、15時間とかもありました。（汗）
自己レスです。 ついに「buzzstyle」が、恐怖の1000面パズルXORを全問制覇したので、 私の作ったソルバープログラムの概要を公開させていただきました。 今は、第２弾の「RingMyBell」という名で再度1000問に挑戦していま すが、これはより良い解答(制限歩数をどれだけ下回れるか)の実証を 目的にしています。 toshihideさん(としひでさん?かな)と競り合っているような形になって ますが、それが結構、楽しめたりして飽きずに２回目をやっています。 実を言いますと、解説ページにも書きましたが、私のプログラムには 理論的なゴマカシがあって気持ち悪いのです。もっとスマートな解き方 がないのか、気になっています。 そのうち気が向いたら、詳しくこの場でても語ってみたいなぁ。
見ていただいて、ありがとうございました。 さすがに我流の(?)解き方では底が知れていますね。 ゼロから組みなおすつもりで精進したいと思います（いつのことになるやら…）。 ではでは。