プログラミングパズルに関心のある人は雑談しましょう！
浅海さん、はじめまして。 すごいですね。またまた「N=17」問題を見つけたのですね。 浅海さんのプログラムは「閉所を探し数える」ということで 無作為に生成された解答図を評価し、本探索を実行させるかを フルイにかけているようですが「閉所」とは何なんでしょう。 その言葉だけでは判断しかねますが、私の想像の範囲では、 「下図のＡとＢは閉所の関係にある」という考え方とは違い ますか。 Ａ口Ｂ 口口口 口口口 口口口 口口口 口口口 口口口 口口口 口口口 Ｂ口Ａ 口口口 口口口 口口口 口口口 口口口 口口口 口口口 口口口 口口口 口口口 口口口 口口口 口口口 口口口 口口口 口口口 口口口 この想像は外しているかも知れませんが、もしよろしければ 閉所について、それが何なのか教えて頂けませんか。
初めまして。 自分のプログラムもヒント数１７の問題を発見しました。 1 - - - - - - - - - - 2 7 4 - - - - - - - 5 - - - - 4 - 3 - - - - - - - 7 5 - - - - - - - - - - - - 9 6 - - - 4 - - - 6 - - - - - - - - - - 7 1 - - - - - 1 - 3 - 196個目までの結果 ヒント数 [17]=1 [18]=31 [19]=164 [20]=0 [21]=0 [22]=0 最少ヒント数 = 17 生成解答図総数1283702 実行時間 5811593 [msec] 方法は、さして変わり映えしないものですが、 解答図の評価に「閉所を探し数える」方法を試しています。 評価でN=18の問題を見つけられる確立は上がってはいるものの、 閉所を探し数えるだけではN=17の特殊性は見出せないみたいです。
第２の「N=17」問題の発見はとても刺激的です。(遠方より拍手しています。) 欲しかったものがついに出ましたね。！！ 明らかに第１のものとは標準型変換に対してユニークなものになっています。 私が思っていたことはヒント数が究極に近づけば近づくほど何らかの共通的な 特性が出てくるのではないかということで第２第３の「N=17」問題を知りたかった ということなのですが、この解析はまた後にして、方法論的に例のサッカーくじで、 あらさんの色々のロジックが私にとっては発想の糸口になって、それを模倣してました。 結局は第２の「N=17」問題をあらさんが発見することになったということは、 乱数を上手に使うスキルが私として、あらさんにはまだまだ遠かったのでしょう。 それはともかく、今後の方針として、 1. ２つのN=17問題に何らかの共通的な特性を見い出す。 2. 第３第４のN=17問題を見つけてさらに共通特性を見つけやすくする。 3. N=16の問題を見つける。 といった感じで気長に進めようかなと。。。 ところで、究極のナンプレ問題における作図問題からのアプローチは、最終的な 証明としては必要とは思うのですが現実的にはどうなのでしょう。 稲葉さんがいいプログラムを作ったようですが。 # それにしても、あらさん。第２の「N=17」問題の発見、おめでとうございます。
ご無沙汰しています、あらです。 久しぶりにここに来てみたら、N=17問題の話が出ていたので、 思い出してちょっとやってみました。 そしたらなんとN=17の問題が出来てしまいました。 - - - - - - - - - 5 - 1 - - - - - - - - - - - 6 3 - - - 3 - - - - 9 - - - - - 1 5 - - - - - 6 - - 8 - - - - - - - 3 - 7 - 2 - 9 - - - - - - 5 8 - - - - - - - - 1 方法としては高橋さんのものと大体同じだと思います。 ただ、工程3で数字を戻すときに、１つずつではなくて いくつか同時に戻すようにしています。 半分くらい諦めていたので、 これが出てきたときには、かなり嬉しかったです。 次の目標はN=16？ ないと思いますが…。
いろいろとテーマの投げかけがあり嬉しく思っている処ですが、 プライベート時間を何に使うかはやはり限られてしまいます。 で、最近はまた倉庫番のソルバー作りに没頭しています。そして、 約３年間のブランクを克服してバージョン７を完成させました。 後はこのバージョンをどこまで性能アップしていけるかですが、 sokoban-MLが閉鎖されたので寂しいのですが、まあ、しばらくは 倉庫番づけになりそうです。 version 7.0: パーフェクト:215/306、リベンジ:180/306、xsokoban:78/90
はじめまして。こんにちわ。一連の話題と無関係でごめんなさい。 正十二面体の各面を５分割してできる擬似球面上のパズルゲームを作ってみました。 この多面体の各頂点を取り巻く面（３つまたは５つ）を回転移動させて ルービックキューブのように同色のブロックに塗り分けるパズルです。 ブロックのタイプによっていくつかのバリエーションを用意してみました。 同種の物は既にあるのかもしれませんが、全然別の問題で球面の分割について考えていたら ついでにできてしまったのでご紹介します。 JAVAアプレットとWindows用のEXEがあります。 アプレットのページの説明が日本語でなくて申し訳ありませんが使い方はいたって簡単です。 基本的な操作は以下の３つしかありません。 １．頂点をクリックして切面を回転させる。 ２．矢印をクリックして球を回転させる。 ３．UNDOボタンをクリックまたはバックスペースキーを押して直前の回転を取り消す。 正解（の１つ）を知りたい時はバックスペースキーを押しつづけて下さい。 最適解（最小手数）を求めるアルゴリズムは途轍もなく複雑になりそうです。 私自身は今はそんなことにはまっている場合ではないので遠慮しますが、 暇で物好きな方がいらしたら試してみるのも一興かと思います。 それでは。http://users.skynet.be/am254650/spherePuzzle/index.html
いろんな意味で、久々の書き込みです。 綺麗なパターンで問題を自動生成するプログラムを作ったので 興味のある方は見にきてください。
今回の挑戦では、せめてもう一つＮ＝１７の問題を見つける程度までには行きたいと考えて いましたが、どうもダメみたいです。そろそろ疲れてきました。ただ今回はＮ＝１８の問題 を多数見つけることが出来ました。(かなりの時間をかけましたが) 1. 解答図を乱数で作る。(とくしんさんの方法で優劣の判定をさせる機能あり) 2. シャッフルされた順番テーブルに従い消せるものは消して行く。 3. 再度シャッフルされた順番テーブルに従い消したものを一つずつ一旦戻して別の 場所で消せるものが複数無いかという改善を順に試みる。(改悪されれば元に戻す) 4. 行程３を何回か繰り返す。(改善ループ回数) 5. 消したものを総て元に戻し行程２から再度試みる。(再試行回数) 6. 以上の行程を無限に繰り返す。 いろいろなプログラムを試してみましたが結局一番最初に作ったこの方法が良かったみたいです。 とくしんさんの考案した判定法は確かにその効果を確認しているのですが、究極はどんな形で 潜んでいるのか謎なので標準設定は無いに等しいです。下図はその一例で解答図評価はわずか 24.5%です。 N=18 (解答図評価=24.5%) - - - - - - - - - - - - - - - 8 - 9 - 7 - 1 8 - - - - - - 4 - - - - 7 - - - - - 5 - 2 - - - - 1 - - - - - - - 2 - 9 - - - 1 - 9 8 - - - 2 - - - - - - - - 3 - - 4 引き続き面白いアイデアとか研究成果がありましたら是非とも投稿をお願いします。尚、今回 私が作ったプログラムを下に置きました。まあ、性能的にはとくしんさんのとあまり変わりま せん。設置フォルダへのファイル出力機能があるので必ずダウンロードしてから実行して下さい。 研究段階なのでソースの公開はご勘弁を。
こんばんは、高橋謙一郎さん。 僕の作ったN=17の逆算プログラムも平均10分ぐらいです。・・・と言うと聞こえは良いのですが、 P4-2G+WinXPという環境で動かしているので普通の環境ならその2〜3倍程は掛かっていると思います。 ヒント図の評価値についてですが、50％前後なら割と頻繁に出現し、65％程度まで存在するみたいです。 N=17の評価値が特別高いという訳では無さそうでした・・・ その60％程度の解答図のみを標的に探索してもN=18を見つけるのですら平均5時間ぐらい掛かってしまい、 N=17に至っては見つかるかどうか見当すら付きません。 解くのに使っているアルゴリズムはSbitとUbitのみですが、同じ条件でN=17の解答図から簡単に逆算できるので 矢張り何らかの特殊構造が存在していそうですね・・・ N=17が可能な解答図さえ見つかれば10分程度で問題図が得られる。 しかしその解答図には明確な特徴が存在しなく、（現状では）見つけ出す事が非常に困難。 と言う事はN=17の問題の解答図を徹底的に分析してその特殊構造を探し出す事が最重要課題ですね。 前回のプログラムが環境により動かなかった原因が判明した（恐らくCPU依存）ので 現在の最新のプログラムを公開します。ちょっと妥協してN=18を探すプログラムですが 最適化の方法は役に立つと思います。N=19が珍しい事を利用した探索法です 1.解答図作成：100回試行した時点で50％以下なら打ち切り、最終的に1000回まで50％を維持した解答図のみ採用 2.順序を乱数で作成して、1つずつ抜いていく。順番に抜いた時の限界をNとする。 3.1/2の確率で最後に解けなくなった数字と任意の数字、1/2で配置済みの数字と未配置の数字を入れ替える。 同じくNを調べ、同じか更新されれば交換成立。 4.最後にNが更新されてから1万回更新されなければ2へ。ただし、N=19が見つかれば更に6万回繰り返す 5.1つの解答図において、3回以内にN=19が見つからなければ1へ。N=19が見つかれば13回に延長 こんな感じで探索して、N=18が出来た時点で画面に出力して停止します。（Enter押すとすぐに消えるので注意）http://www.geocities.co.jp/Playtown-Darts/9133/Num2.lzh
単純に乱数を使ってナンプレ問題を作った場合、N=24 あたりが ピークになり、どうにかN=19が見つかるといった状況が私の実験 でも、以前に投稿された あらさん の実験でも得られています。 これに、順番テーブルを微調整して改善する等のループ処理を組み 込むと、N=20 あたりがピークになり、どうにかN=18が見つかると いう状況程度までには改善されるようです。 平均N=24 -> 平均N=20 の改善が一般的に成功するということなの ですが、究極を極めようとした場合、改善という工程ではかなり 厳しいのではないかと感じています。うまく説明するのも難しい のですが、少しずつ改善されてN=17とかN=16に到達するというより も「究極は突然に出現するもの」というイメージを感じています。 ですから、究極に達する解答図を見極めるには統計的にではなく、 法のアミの目をくぐり抜ける知能犯的な特殊構造があるのではないか と思うのです。何の根拠もない単なる直感なのですが。