【解答】パズルのプログラミング【作成】
■ このスレッドは過去ログ倉庫に格納されています
パズルの問題をプログラムで解いたり
プログラムで面を作成したりする方法を話し合うスレ。 >>631
1から作れば移植する必要はないよ!やったね>>621! HashioKakero.Cざっと見たけど、HTMLとJavaScriptでよくね?
tableとonClickでやるどこかに似たようなGUIのやつあったべ。
あえてJava使ってそのうちAndroidアプリにしたいとかならあえて止めないけど 暫定的な修正版。別のページを参考にしたらあっさりできた(もちろん改良予定 >>634はミス。。。
暫定的な修正版。別のページを参考にしたらあっさりできた(もちろん改良予定)。背理法最強伝説
http://codepad.org/RYBb423Y
参考:http://infosys.sys.i.kyoto-u.ac.jp/~ken3/IL/index.html >>608 >>635
病院来るときは、DynabookAZです
Dynabook AZ (ARM Tegra250 1.0Ghz, Lubuntu13.04)
マイクロ秒は「us」と表記していいみたい
24,689,813usと書いていれば24秒と見えるようわかりやすく書きます
Ver.1(>>610), Ver.2(>>635)
121118B.mno 30x30 クリリン 2,005,498us, 6,549,043us
121118C.mno 30x30 ロイ・マスタング 218,733us, 1,364,396us
121118D.mno 30x30 スニフ 381,746us, 2,490,666us
121118E.mno 30x30 ねずみ男 1,637,525us, 6,814,192us
go46.mno 25x25 マジンガーZ ,を.に 813,404us, 3,088,609us
120718A.mno 40x35 トトロ 計測せず, 24,689,813us
110814A.mno 70x80 屋台 計測せず、計測せず、長くなる?
110818H.mno 50x50 犬はりこ 計測せず、計測せず、長くなる?
110529b.mno 40x45 オフロードバイク 計測せず、2033,137,185us(34分)
110614a.mno 20x20 イチゴのショートケーキ 125,230us, 353,486us
110612a.mno 40x40 あをによし奈良 10分放置、233,249,645us(4分)
>>635のソース見て、今までc++書いたことないけど、見よう見まねで
いじくってみようと思う >>635をちょっと改良しただけで大幅に速度アップ!
http://www2.ocn.ne.jp/~minui/illulogi/index.htmlを書いた
apostata氏(?)に差し入れしたいレベル。
http://codepad.org/qTPWXDa7
速度計測結果:
問題 サイズ マイクロ秒
121118B.mno. 30x30 13,000
121118C.mno. 30x30 7,000
121118D.mno. 30x30 10,000
121118E.mno 30x30 16,000
go46.mno. 25x25 29,001
120718A.mno. 40x35 21,001
110814A.mno. 70x80 555,031
110818H.mno. 50x50 587,033
110529b.mno 40x45 113,006
110614a.mno 20x20 2,000
110612a.mno 40x40 37,002 精神って単語と、クリリン・ねずみ男って単語で咄嗟に「ヤバイ」と信号が出た。
問題の絵の名前か・・・と思い至ったときホッっとした。 >>637 おおお〜、すげー
今からソース貰って試してみますわ。ありがとう! おお、今試したら120918A.mno(「イタリア・ゴンドラ.2490sec」、175x110)ですら
38,949,227[us]で解いたぞ……メモ化の威力が凄すぎる Dynabook AZ (ARM Tegra250 1.0Ghz, Lubuntu13.04)
70x180サイズに挑戦
>>637 さんの Ver.3
131313A.mno 39.48秒 スキューバ・ダイビング
131313B.mno 6.92秒 花火大会
131313C.mno 49.06秒 ガリバー旅行記
131313D.mno 82.31秒 ロミオとジュリエット
131313E.mno 82.75秒 赤毛のアン
131313F.mno 74.67秒 ハロウィン
131313G.mno 151.08秒 アダムの創造
僕のnekoppy3のmx46j(ARM)
131313A.mno 31.08秒 スキューバ・ダイビング
131313B.mno 19.02秒 花火大会
131313C.mno 27.96秒 ガリバー旅行記
131313D.mno 35.65秒 ロミオとジュリエット
131313E.mno 43.66秒 赤毛のアン
131313F.mno 44.82秒 ハロウィン
131313G.mno 41.53秒 アダムの創造
もう、ガブリ4つじゃん
Cacheに相当する変数、僕も入れているはずなんだけど
C++って速いんだな〜驚愕する よく見るHP
ttp://www.ic-net.or.jp/home/takaken/nt/logic/index.html
ここのは古い感じなの? >>641
>C++
まあC++使うのは趣味も半分ですけどねw
カプセル化とかに慣れれば(C言語よりは)良い言語ですよ……
>>642
そうでもないと思いますよ。ぶっちゃけググって上の方に出ていたページを
参考にしただけですからw
私が使ったアルゴリズムは普通に背理法で、
「列または行毎に、『あるマスが■だとして矛盾が出れば×。あるマスが×だとして
矛盾が出れば■。そうでない時は放置』として確定させる」というものです。
矛盾の判定は、「ヒント数字の置き方が1通りでも存在すればOK」といった感じなので、
そこだけより良いアルゴリズムに差し替えても構わない仕様になっています。
http://www2.ocn.ne.jp/~minui/illulogi/index.htmlの場合、その判定を
キャッシュ(メモ化)によって大幅に高速化しています。これがカラーイラストロジックに
使えるかまでは分かりませんが、スマートな発想だと言えます。 そう言えば、まだバックトラックは組み込んでなかったな……
(そうしないと超難問に対応できないと思われる) 更に人間が解くみたいに「更新があったマスを含む行列を優先的に見る」ということができればもっと速くなりそう >>645
>>更に人間が解くみたいに「更新があったマスを含む行列を優先的に見る」
それ必須と(出来れば、過去の行列の時間測定から速い順で行列を行う)
ある行が10こヒントデータがあるとして
1〜3番目と8〜10番目が既に確定している場合
4〜7番目のみ調べるようにする
僕のは実装してますけど608さんのは、まだまだ速くなりますよ 確定探索で、(sum数字0〜数字n)+(n-1)==問題幅or高さ。なら確定。
ってのは無駄な計算かな?
手作業で解くときはよく使うけど。 >>647 の言いたいことに追随して、
@:黒
x:白
_:未確定で
12345678901234567890
xx__@__xxxxxx
のときに3〜7まで4つ入るって分かってたら
12345678901234567890
xx_@@@_xxxxxx
なんてのを実装すれば速くなりますよ 「イラストロジック 演繹法」でググって
トップに出てくるサイトの
「Section 4 存在仮定法」っていうの僕のには実装していないから遅いのかも。
演繹法は、やっています。 ふと思ったんだが、背理法って演繹じゃないのだろうか……?
皆さんの意見も参考にして、とりあえず組み直してみますね。
ちなみに私、イラストロジックの問題ファイルを相互変換する
ソフトを作ったことがあったりしますw
http://www.vector.co.jp/soft/win95/game/se497399.html :::::::::::.: .:. . ∧_∧ . . . .: :::::::: ごめんなさい間違えました……
:::::::: :.: . . /彡ミ゛ヽ;)ヽ、. ::: : :: >>602で既に書いてあるのに宣伝がましくてごめんなさい
::::::: :.: . . / :::/:: ヽ、ヽ、i . .:: :.: ::: 言い訳ついでに書くと、アレを作った時はパズルを解く方がメイン
 ̄ ̄ ̄(_,ノ  ̄ ̄ヽ、_ノ ̄ でして、幾つかソフトがあるのに互換が効かないのに戸惑った
から作ったという経緯があります。一番面倒だったのはLogiNeko形式で、
目一杯容量を削った代償にチョー複雑なファイルフォーマットに四苦八苦しながら開発しました。
そのかいあって、画像インポート機能がないLogiNeko相手にも、こいつを噛ますことで擬似的に
画像インポートさせることができるんですよエッヘン、というのがささやかな自慢です。
まあ勝手に作ったソフトなので各ソフト作者からは連絡も何もありませんが、ちょっと寂しい気もしますね。 当面の目標。今の自分のコードじゃ完全には解けない強敵。つまりバックトラックしないと無理……
http://codepad.org/ZC3MxCc9 (注:mno形式)
注:元データは、昔某所に貼られていた問題をテキスト化したものです。
--------------------------------------------------------------------------------
【けいおん!】田井中律は目指せハッピー100%【ドラム】
http://changi.2ch.net/test/read.cgi/anichara2/1254827509/
38 :名無しさん@お腹いっぱい。:2009/10/06(火) 20:31:45 ID:2Pg/phyn
>>1乙
100スレ記念に作ったぜ
イラストロジック100×100
問題
ttp://nagamochi.info/src/up39860.jpg
解答
ttp://nagamochi.info/src/up39861.jpg
49 :名無しさん@お腹いっぱい。:2009/10/06(火) 20:37:07 ID:2Pg/phyn
>>42
プログラム作って唯一解であることを確認済みです
難易度は上級です(いわゆる上級テクニックが必要)
--------------------------------------------------------------------------------
http://www.syu-ta.com/blog/2009/10/07/015131.shtml
(http://web.archive.org/web/20130426174102/http://www.syu-ta.com/blog/2009/10/07/015131.shtml)
問題画像:http://i.imgur.com/KepEOB8.jpg
正解画像:http://i.imgur.com/IEIA0RH.jpg そう言えばこんなの見つけました。データは案の定biglogic_j140330a.zipに入ってましたが(grepして発見)
http://plaza.rakuten.co.jp/nekoppy3/diary/201208100000/ 組み合わせ爆発お姉さんを助けるアルゴリズム。とか
中学生がスパコンで魔方陣を解いたアルゴリズム。とか
中身を見ても居ないし想像もつかないけどワクワクするね。 >>652
それ作った本人参上
大まかに説明すると、解き方は大きく3段階に分けられて
まずは1段階だけで解き、完成しなかったら次の段階へ行く
3段階で解けなければ不成立か重解
どの段階まで使ったかを見れば難易度も分かる
GUIの部分が今の自分の環境では動かないから試せないけど、10秒程度で解けてた
あとカラーロジックにも対応している >>656
>それ作った本人
_人人人人人人人人人人人人人人_
> な なんだってー!! <
 ̄^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^ ̄
_,,.-‐-..,,_ _,,..--v--..,_
/ `''.v'ν Σ´ `、_,.-'""`´""ヽ
i' / ̄""''--i 7 | ,.イi,i,i,、 、,、 Σ ヽ
. !ヘ /‐- 、u. |' |ノ-、 ' ` `,_` | /i'i^iヘ、 ,、、 |
|'' !゙ i.oニ'ー'〈ュニ! iiヽ~oj.`'<_o.7 !'.__ ' ' ``_,,....、 .|
. ,`| u ..ゝ! ‖ .j (} 'o〉 `''o'ヽ |',`i
_,,..-<:::::\ (二> / ! _`-っ / | 7  ̄ u |i'/
. |、 \:::::\ '' / \ '' /〃.ヽ `''⊃ , 'v>、
!、\ \. , ̄ γ/| ̄ 〃 \二-‐' //`
……キャラ物作る時はとにかく目の部分がキツいんですがコツはありますかね?
最近作ったもの1:
http://i.imgur.com/11pOciw.jpg(元絵)
http://i.imgur.com/fhWpz5E.png(問題)
http://i.imgur.com/F71MutP.png(解答)
最近作ったもの2:
http://i.imgur.com/rMqisle.jpg(元絵)
http://i.imgur.com/eQRDIWB.png(問題)
http://i.imgur.com/vOp1hgq.png(解答) 存在仮定法、まだうまくいってない
理論をちゃんと理解してないのか
Dynabook AZ (ARM Tegra250 1.0Ghz, Lubuntu13.04)
田井中律 100x100 >>652 (>>608)
僕の mx46j 14.99秒 だけどお腹のあたりが未確定で解けない
>>608 さんのVer.3 5.30秒 だけどお腹のあたりが未確定で解けない
けいおん 60x100 120819E.mno
僕の mx46j 11.11秒
>>608 さんのVer.3 8.60秒
110x175サイズに挑戦(学研のロジックパラダイス・年末年始に解く問題)
僕のmx46j(2014年3月30日版)
120810A.mno 38.77秒 ナポレオンと馬
120918A.mno 81.29秒 イタリア・ゴンドラ(僕のは今82秒で解けます)
121227A.mno 82.99秒 スペイン
121228A.mno 106.26秒 カブキ・5人か?
131226P.mno 77.53秒 阿吽
131227A.mno 41.59秒 ドガのエトワール
>>608 さんの Ver.3
120810A.mno 100.19秒 ナポレオンと馬
120918A.mno 218.33秒 イタリア・ゴンドラ
121227A.mno 326.38秒 スペイン
121228A.mno 487.05秒 カブキ・5人か?
131226P.mno 292.37秒 阿吽
131227A.mno 42.51秒 ドガのエトワール
Ver.3 は背理法を白から始めているせいか
白っぽい絵は解くのが早いけど
黒っぽい絵は遅い傾向があるんじゃないかと思う やったー! 大幅な高速化に成功したよー!
http://codepad.org/4OeSJgsI
機種:ASUS K55VD-SX3210B
OS:Windows 7 Ultimate 64bit
その他:メモリは8GBまで増量
問題 旧版[us] 新板[us] 倍率
110529b.mno 98,005. 30,001. 3.3
110612a.mno 36,002. 15,000. 2.4
110614a.mno 4,000 1,000 4.0
110814A.mno. 494,028 136,007 3.6
110818H.mno. 581,033 122,007 4.8
120718A.mno. 24,001. 7,000 3.4
121118B.mno. 19,001. 8,000 2.4
121118C.mno. 8,000 3,000 2.7
121118D.mno. 8,000 4,000 2.0
121118E.mno 15,000. 7,000 2.1
go46.mno 26,001. 10,000. 2.6
131313A.mno. 4,943,282 775,044 6.4
131313B.mno. 810,046 152,008 5.3
131313C.mno. 6,265,358 962,055 6.5
131313D.mno. 10,597,606. 1,739,099 6.1
131313E.mno 10,404,595. 1,610,092 6.5
131313F.mno 9,552,546 1,377,078 6.9
131313G.mno. 18,595,063. 5,253,300 3.5
120810A.mno. 12,370,707. 1,945,111 6.4
120819E.mno 1,187,067 224,012 5.3
20091007k-on01.mno 662,037 167,009 4.0
20091007k-on02.mno 35,002. 17,001. 2.1
バックトラックはまだ実装できません……と言うより、組み込んだら遅すぎて使えませんでしたorz ちなみに、20091007k-on01.mnoは>>652で、20091007k-on02.mnoは次の問題です。
http://codepad.org/95H0X1Cb (注:mno形式)
注:元データは、昔某所に貼られていた問題をテキスト化したものです。
--------------------------------------------------------------------------------
けいおん!紅茶715杯目
http://changi.2ch.net/test/read.cgi/anime2/1264864946/
24 logic sage 2010/01/31(日) 00:39:52 ID:hFZ5c2QD
キャラスレが過疎ってるようなのでこっちにうp
イラストロジック
http://nagamochi.info/src/up58928.jpg (cache)
解答は23時間後に(覚えてたら)上げる
けいおん!紅茶716杯目
http://changi.2ch.net/test/read.cgi/anime2/1264935488/
410 logic sage 2010/01/31(日) 23:55:52 ID:hFZ5c2QD
問題
http://nagamochi.info/src/up58928.jpg
解答
http://nagamochi.info/src/up59052.jpg (cache)
--------------------------------------------------------------------------------
http://www.syu-ta.com/blog/2010/02/01/004724.shtml
(http://web.archive.org/web/20130426200910/http://www.syu-ta.com/blog/2010/02/01/004724.shtml)
問題画像:http://i.imgur.com/fd908c0.jpg
正解画像:http://i.imgur.com/uK23uxW.jpg Dynabook AZ (ARM Tegra250 1.0Ghz, Lubuntu13.04)
>>608 >>659 (Ver.4)
Ver.4のソース27行23番目
typedef uint16_t uint
uintはg++側で他に定義されているらしく
別の名を名乗れとエラーが出る
typedef uint16_t uintt
と定義し、以下uintをuinttに置き換え
これでコンパイルが通る
問題 [us]
110529b.mno 574,321
110612a.mno 287,072
110614a.mno 32,804
110814A.mno. 1,152,207
110818H.mno. 923,005
120718A.mno. 216,086
121118B.mno. 125,806
121118C.mno. 72,869
121118D.mno. 88,082
121118E.mno 182,625
go46.mno 281,405
ここから、単位は秒です
131313A.mno. 5.922秒
131313B.mno. 1.469秒
131313C.mno. 7.225秒
131313D.mno. 13.580秒
131313E.mno 12.565秒
131313F.mno 10.376秒
131313G.mno. 41.844秒
120810A.mno 14.975秒
120819E.mno 1.654秒
120918A.mno. 35.714秒
121227A.mno 33.163秒
121228A.mno 34.148秒
131226P.mno. 55.084秒
131227A.mno 7.047秒
ここから単位は[us]
20091007k-on01.mno 1,182,964[us] (未確定あり)
20091007k-on02.mno 298,231[us]
>>608 の言うバックトラックは、20091007k-on01.mno のような解けない問題に
Ver.4のソースの後にバックトラック・プログラムを追加すればいいと思う ソルバーは1秒を切らないと役に立たないってよく聞くよね。
高速化でよく聞くのは、1次元配列化・ビット演算。
何かすごい計算方法が眠って居るんだろうなぁ。
縦・横ときたらナナメ! 上下に分割して! 意味不明 >>662
ソースのコメントにも書いてますが、下手にCに近くすると(コードを最適化しすぎると)、
デバッグが大変になるので(まだ)やる気はありません。それにこのパズルの場合、
盤面をビット表現すると縦横が65マス以上になった際を考慮するのが面倒くさいということもあります。
また、アルゴリズムの良し悪し(オーダ)>コードの最適化具合(係数)なので、
C++でバッチリ決めた後にボトルネックを最適化しようかと思います。
(あるパズルで)
ところで、ソルバーは1秒云々のソースはどこにあるのでしょうか? >>659に小細工(既に解いた列・行は解かない)を施して微妙に高速化。
平均して2割ぐらいは速くなる、はず
http://codepad.org/N2UwGvhq バックトラック対応に行き詰まったので、現在は他形式にも対応できるように拡張中です。
とりあえず「イラロジヘルパー」(http://www6.ocn.ne.jp/~b-lab/txt_lib/)の「*.lgs」形式には対応させました。 ソルバーじゃないけど、将棋の対戦ソフトのアルゴリズムが凄かったな
パターン認識みたいなことをやってた バックトラック(縦横同時に考える上級テクニック)についてヒントを
あるマスが決定すると他のマスも次々に決定する時、「影響度が高い」と言う
この「影響度」を未決定の各マス毎に計算し、高い順に仮決定していく
影響度の計算式がカギ >>664に、拡張子「*.lgs(イラロジヘルパー)」「*.txt(ロジック・ピクチャー)」
「*.lgc(LogicLand)」への対応を追加し、更にバックトラックを試験的に導入しました。
その影響でコマンドライン引数が微妙に仕様変更されましたのでご了承下さい。
(ファイル名のみだとバックトラック無し、ファイル名の後に正数を書くとその段階までバックトラック)
http://codepad.org/byX1WiQJ
>>667
影響度ですか……実装を検討してみます。 2段階までバックトラックしないと解けない小さな問題があればいいのに…… あ、>>668には結構痛いバグが見つかりました(LogicLandのファイルを読み込む時のもの)。
修正版を上げておきます。
http://codepad.org/3PzprA51 存在仮定法を使ってC言語で書いたら、今まで作ったものより遅かった
美しいソースじゃないからなのかな〜?
それともC++には高速演算に向いているのか、僕にはわからない世界
でも今まで解けなかった問題が存在仮定法を使うと2問ほど解けた
(2つとも70x180位のサイズで) >>671
その2問の問題。「先生たち」と「ポケモン、ジオリジン」
ttp://logic777.web.fc2.com/i/140408a.zip >>672
相変わらず凄まじいコードだな……
書き方が違いすぎてまるで暗号だぜHAHAHA(別に悪い意味は無い)
さて、>>665のおまけとして、ファイルコンバータを上げておきます。
具体的には、*.mno・*.txt・*.lgc・*.lgsを相互変換できます。お試しあれ
(まあヒント数字以外の盤面情報はlgc形式しか保存できないんですけどね……)
http://codepad.org/mCPTln3E
ちなみに当方のプログラムはUnicodeを考慮していません……ご了承下さい ちなみに、>>673製作中、前回上げたファイルフォーマットに関するメモに
誤りがあることが発覚しました。謹んで訂正いたします。
修正版:http://codepad.org/cyziWoZX ・自PCでの測定結果
130226A.mno 131221C.mno
LogiNeko[s] 3.374 4.821 ※131221C.mnoは録画コマ送り測定
>>670[s] 2.878164 . 2.884165 . ※バックトラックは使用せず
ロジック・ピクチャー[s] 0.751 0.751 ※録画コマ送り測定
なお、時間計測機能が無いソフトでの測定方法は、
「AmaRecTVで録画(59.94fps)してコマ送り」という原始的なものです。
また、>>673で変換できない形式については、
拙作「イラロジ相互変換」で変換しています。
……なんでこんな時に「イラロジ相互変換」のバグに気づくんだよ畜生め!
自分の昔のコードを呪いたくなるんだぜorz
(訳:全然変換できないようわああん!) やったー!
画像から自動的にトレースして検算結果も出せるエディタできたよー!
http://i.imgur.com/l01KL4k.jpg
……手動編集機能はまだ付けてない。とりあえず試験的にうp
インターフェースが使いづらいだろうけど今は我慢してくだしあ
(エンターキーで出力画面を画像としてセーブ可能)
http://www1.axfc.net/u/3219410.zip >>608 さんの未解決問題
111105A.mno ジーニー
111213E.mno カウボーイ
120318D.mno 佐川急便
120319O.mno 怪物くん
120321G.mno コブラ
120321L.mno 救助犬?
120416T1.mno コンパス
120426D.mno ハガレン
121109A.mno ガンジー
608さんから教えてもらったHPに
京都大学の/~ken3/の図3.3論理積演繹法
あるいは、OCNの/~minui/さんのアルゴリズム解説にある
多項式時間で解く方法の解説の図を参考にして
普通の人が最初に思いつく演繹法を考えたらいいんじゃないかと思う
この演繹法を応用したのが存在仮定法でそこがいきなり出来たので
ぼくもあなたも戸惑ってるような気がする
存在仮定法を少しいじれば普通の演繹法が出来るはず
ぼくも頑張って608さんのプログラムいじって作ってみる
配置成功の時、
初めての場合、CacheX={(1)Unkown,(2)Black,(3)White}を置く
二番目以降は、CacheX={(1)Unkown,(2)BlackにBlack以外が上塗り->Unkown,
(3)WhiteにWhite以外が上塗り->Unknown}
だったと思う。間違えてたらごめん
普通の演繹法の内部で背理法が存在仮定法で
普通の演繹法の外部で背理法を行ったのが僕のやり方でなんとか解いた
(いきあたりばったりで滅茶苦茶だけど強引に解いた) 黒マスはヒントで与えられているけど、
白マスも幅・高さ・ヒントからある程度の推定が出来ますよね
白マスの推定ってのは強力な枝狩りにはなりえない?
縦の可能性・横の可能性から接点の可能性を絞るってのは無駄? >>679
X:白
@:黒
_:未確定で
3〜12の間に@が3つ入るって分かっていたら
この場合わかりやすいよう3つの後は30ことかで30こは3〜12
に入らないものとする
123456789012345
XX___@______XXX
123456789012345
XXx__@__xxxxXXX
小文字のxが新たに入る白マスってわかります
>>677
二番目以降は、CacheX={(1)Unkown,(2)BlackにWhiteの上塗り->Unknown,
(3)WhiteにBlackの上塗り->Unknown}
だったか。
演繹の終わりに、1回以上配置成功の場合
CellList=CacheX(ただし、Unknownはコピーせず、BlackとWhiteをコピー)
また間違ってたら、ここに書きこむわ >>680 うまくいかない。一部を書いておきます
C++初心者でわからん
celllist Check1(CellListSize);
celllist Check2(CellListSize);
HintListPosition[Index] = Position;
(省略)
//再帰
if (Position >= CellListSize) return false;
if (Cache[Index][Position] != 2) return Cache[Index][Position];
bool isPossible = false;
bool SameFlg = false;
bool flgflg = isPutPosition(CellList, HintList, Index, Position, CellListSize);
if(flgflg != false && Index == HintListSize){
for(uintt k = 0; k < CellListSize; ++k){
Check1[k] = Check2[k] = White;
}
for (uintt j = 0; j < HintListSize; ++j){
for(uintt k = HintListPosition[j]; k < HintListPosition[j] + HintList[j] - 1; ++k){
Check1[k] = Check2[k] = Black;
}
}
for(uintt k = 0; k < CellListSize; ++k){
if(CellList[k] == Black) Check1[k] = Black;
}
for(uintt k = 0; k < CellListSize; ++k){
if(Check1[k] != Check2[k]) SameFlg = true;
}
if(SameFlg == false){
if (FirstFlg == false){
FirstFlg = true;
for (uintt k = 0; k < CellListSize; ++k){
CacheX[k] = Check1[k];
}
}
else{
for (uintt k = 0; k < CellListSize; ++k){
if(CacheX[k] == Black && Check1[k] == White) CacheX[k]=Unknown;
if(CacheX[k] == White && Check1[k] == Black) CacheX[k]=Unknown;
}
}
Print3();
}
}
if (flgflg != false){
isPossible = isNormalAvailablePosition(CellList, HintList, Index + 1, Position + HintList[Index] + 1, CellListSize, HintListSize, Cache, Pass, FirstFlg, CacheX, HintListPosition);
}
(省略) 絵から数値データにするのは簡単なのに、数値から絵にするのは難しい。
いったい絵から数値に変換したときにどんな重要な要素が抜け落ちたんだろう。
あぁ白マスの数か・・・。 僕のプログラム、gccに-O2のスイッチ付けてなかった
つけると半分の時間で解けるようになった。
もっときれいに書き直そう。自分のやつ >>682
そりゃどう見たって情報量減ってるからなぁ……
>>683
>gccに-O2のスイッチ付けてなかった
!!!? >>684 誤解が生じたかもしれないけど、m246j.c(mx46j.c)の方ねそれは
gcc(g++)で-O2をつけるとSSE(x86),NEON(ARM)に最適化するらしい。
mx46j.c(ARM)は速くなったけどm246j.c(x86)は、さほど速くならなかったなあ >>686
横から申し訳。猫 7(2012)(←tegra3)Ubuntu13.04 で引数の場所を変更
$ gcc -O2 bmm.c -o bmm -lm
ARMLinuxだと高速化出来なかった
-O2付けても付けなくても「妖怪」が55sec程
ずっぱつVAIO(C2DT7250)RAM4GBで引数-O2無しで妖怪27sec
icc(インテルのコンパイラ)で18sec後半
gcc で-O2 (-O3は無くても良かった) の引数付け(18secちょい) コンパイルオプションは最後の手段ってばっちゃが言ってた。 >>688
え?リリースビルドって普通-O2にするもんじゃないの?
……まあ、コンパイラによってデフォでの最適化方向は違う(>>686)けどね >>687 中国電力さん、bmmはランチャーだってば。
メインプログラムがm246j(mx46j)ね。リア友じゃん >>690
やっぱバレたか
一応、irx86 と irarm とir の引数も変えてますがこれじゃ不味いすか?? >>688
僕は猫さんに怒られながらrenice でプロセス優先度を-20にする時があります
邪道と言われますw
つか、猫さんのあずにゃんで動かした>>608さんのぷろぐらむ見せて貰ったけど爆速吹いたす
猫さんに書いちゃダメて言われてたけど、約束破って書いちゃったす
木曜日に1人じゃねえとプログラム書けねえつーから早退したす
猫さんが2ちゃんねる書いて楽しそうにしてるからROMるの楽しいす
アンパンマン嫌いです >>687=>>691=>>692の言っていることが分からないっ……!
それはともかく、>>676の改良版が出来ました
http://i.imgur.com/tFXuP8b.jpg
http://i.imgur.com/qobsjHo.jpg
動作原理としては、自動トレース→盤面データをdllに送って解析→
結果を元に手動で修正、といったところ
2枚目のように、未確定部分は黄色で表示されるので楽に書けるのが(・∀・)イイネ!!
真面目にVectorに上げる予定なのでここにうpするのは難しいかな…… >>693
おはようございます
サムネ見たら凄すぎふいたす
$ ./irx86
or
$ ./irarm
の初期でbmm or armbmm のlauncherを作り、
その後、ir から必要な.cを沢山引数をつけつつ、ずらーっとコンパイルする仕様なのです
バリバリ猫さんの俺様仕様す
猫さん、プログラムやめるて言ってたけどあずにゃんを無理矢理買わせ。汗
無理矢理開発させている
のはボクです(爆)
>>猫さん
ずっぱ●いわく、SSEはインラインアセンブラで書いた方が速いらしいす >>693 Vectorに上がるの楽しみにしています
今日は、>>670 の70x180>一万ドット越えの問題
(biglogicに収録してあるのは60〜70問、未収録は他に10問くらい)
の時間計測したり、
>>677 の未解決問題をすんなり解く方法の模索をしようと思っています
>>692 中電さん、ウチワ受けする話が多すぎです
バッチファイルのirの中身いじるだけでいいんじゃね? Dynabook AZ (ARM Tegra250 1.0Ghz, Lubuntu13.04)
>>608 さんの >>670 (Ver.6)とmx46jl.c(ともにスイッチ-O2)
http://logic777.web.fc2.com/ にある、biglogic_j140330a.zip
に収録してある、1万ドット越えの問題の演算比較
時間単位は[s] mx46jl >>608 Ver.6
120810A 110x175 26.408 14.438 ナポレオン
120810B 70x180 28.593 5.420 盆踊り
120811A 70x180 28.572 11.918 オリンピック
120811B 180x70 19.285 4.263 スカイツリー
120818C 60x200 41.592 9.343 妖怪
120819D 60x200 29.156 3.347 キャラ8匹
120901A 70x180 25.040 4.170 平等院鳳凰堂
120915A 70x180 34.330 9.264 スイス
120917B 70x180 18.201 7.077 ロンドン
120918A 110x175 43.571 35.507 イタリア
120920A 70x150 20.575 7.544 ぷよぷよ
120922A 150x70 31.138 6.314 銀魂
120924A 70x150 20.409 6.649 ミッション・インポッシブル
120928A 70x150 15.253 8.087 フランス
121001D 60x200 33.268 9.511 海外ドラマ Dynabook AZ (ARM Tegra250 1.0Ghz, Lubuntu13.04)
>>608 さんの >>670 (Ver.6)とmx46jl.c(ともにスイッチ-O2)
ttp://logic777.web.fc2.com/ にある、biglogic_j140330a.zip
に収録してある、1万ドット越えの問題の演算比較
時間単位は[s] mx46jl >>608 Ver.6
121003A 70x150 25.639 8.557 スターウォーズ
121007B 70x150 17.590 7.042 牛若丸
121009A 150x70 30.794 5.087 ブレーメンの音楽隊
121011A 70x180 16.502 3.562 ゴールデンゲートブリッジ
121012A 70x180 51.737 11.966 電車
121013A 70x180 23.087 7.336 テキサス
121114F 180x70 29.901 24.537 ミュシャの椿姫
121116A 70x180 19.469 6.428 七五三
121116B 70x180 22.019 8.366 アンコールワット
121118A 70x150 17.008 8.353 赤ずきん
121120A 70x150 35.262 11.383 プリキュア
121120C 70x150 22.830 15.646 海猿
121122A 150x70 17.606 14.375 アメリカ
121122B 70x190 35.198 5.910 オーケストラ
121227A 175x110 43.992 32.652 スペイン
121228A 110x175 51.207 32.916 歌舞伎、5人か? >>633
昔貼られてたヤツのソースを見つけました。
Simon Tatham's Puzzle Collection
ttp://code.ohloh.net/project?pid=6dCunV7fspU&cid=ZJt1JK_7eXs&fp=299756&mp=&projSelected=true
js版もありましたがコードが2万行もある;; わけわかめ >>699
流石にjsで2万行とか頭おかしいとしか…… 変数が一文字とか連番なんで、
別の言語から自動変換して難読化とかしてあるんですかねw
ニコリのパズルの自動生成・自動解答への夢は遠い・・・ 自動解答はともかく、自動生成はパズルの良さを判定する必要があるからなー… >>677 未解決問題解決できました
>>652 20091007k-on01.mno(100x100,田井中律)攻略!
未解決の盤面に(X,Y)=Unknownを見つけ、n1=黒に仮置き背理法()&
n2=白に仮置き背理法()をする
n1,n2の戻り値は0=全部は解けないが矛盾せず、1=矛盾する、2全部解けた
n1=0&&n2=1の場合、黒ですすめる
n1=1&&n2=0の場合、白ですすめる
n1=0&&n2=0の場合、どちらか優先順位を決めて、黒優先のとき、黒を仮置き
して、後々矛盾した場合、白に仮置きする
n1=1&&n2=1の場合、明らかに矛盾、どっちでもよかった所まで戻って反転する
4つかどの背理法でどっちつかず(n1=n2=0)のとき、黒優先で黒から仮置き
4つかど以外の背理法でどっちつかずの(n1=n2=0)とき、白優先で白から仮置き 田井中律、背理法トレース
(X,Y)
01:100,100,四つ角、どっちつかず、黒から仮置き
02: 98,100,黒で決定
03: 98,97,白で決定
04: 99,97,どっちつかず、白で仮置き
05:96,95,黒で決定
06:96,100,黒で決定
07:83,100,黒で決定
08:81,100,黒で決定
09:78,100,黒で決定
10:75,100,黒で決定
この後矛盾(n1=n2=1)が生じ、前にどっちつかずだった04:まで戻る
04:99,97,黒で仮置き
05:96,100,白に決定
06:95,100,白に決定
07:94,100,黒に決定
このあと全部解けた
今段取り悪くて1500秒かかるんですけど
双方向リストにして各ノードに盤面コピーして高速化を図りたいと思います >>705
つまりバックトラックは2段階で十分ということか……
ちょっとプログラム見直してくる >>705 双方向リストにして各ノードに盤面コピーして高速化を図りたいと思います
作ってみた
>>677
111105A.mno ジーニー 6.655[s]
111213E.mno カウボーイ 18.279[s]
120318D.mno 佐川急便 10.383[s]
120319O.mno 怪物くん 20.571[s]
120321G.mno コブラ 5.730[s]
120321L.mno 救助犬? 29.608[s]
120416T1.mno コンパス 3.427[s]
120426D.mno ハガレン 7.964[s]
121109A.mno ガンジー 23.638[s]
田井中律 背理法・トレース
No. (X,Y)
00: 0,0,黒(これはダミー)
01:100,100,どっちでも、黒から
02:99,97,どっちでも、白から
03:96,95,白で決定
04:96,100,どちらも矛盾で02:に戻る
02: 99,97,黒にする
03:96,100,白に決定
04:95,100,白に決定
05:94,100,黒に決定
06:81,100,黒に決定
で解けた。時間は、216秒 >>699,701
昔というのは>483かな
そのページに書いてあるけど元がCで他はコンバートみたいよ
jsは見たら ttp://emscripten.org/ 使ってるみたい >>704
4つかどの背理法でどっちつかず(n1=n2=0)のとき、黒優先で黒から仮置き
4つかど以外の背理法でどっちつかずの(n1=n2=0)とき、白優先で白から仮置き
訂正
4つかど以外の背理法でどっちつかずの(n1=n2=0)ときも、黒優先で黒から仮置き
田井中律90度回転させて4つ作ったんだけど
全部解析パターンも違うし、解く時間も違う
オリジナル 118秒
左90度回転 266秒
180度回転 262秒
右90度回転 途中で異常になって解けなかった
遅いのを速くするのは、またアイデア絞ってみます
解けない謎を解明したい >>710 田井中律の90度回転の問題
ttp://logic777.web.fc2.com/i/muzu01.zip
難問データ集(mno)
101a.mno 田井中律オリジナル
101a.i オリジナル・イメージ
101b.mno 田井中律・左90度回転
101b.i イメージ
101c.mno 180度回転
101c.i
101d.mno 右90度回転
101d.i
rot.c イメージを左90度回転するプログラム $ ./rot 101a.i 101b.i
10a01.mno 矢口真里
10a02.mno ジーニー
10a03.mno カウボーイ
10a04.mno 佐川急便
10a05.mno 怪物くん
10a06.mno コブラ
10a07.mno 救助犬?
10a08.mno ミッキーマウス(背理法使わなくても解ける)
10a09.mno フラワー(スカンク)
10a10.mno コンパス
10a11.mno 鋼の錬金術師
10a12.mno ガンジー >>710
解けない理由(仮説)
誤った盤面(ノード)で(X,Y)=Unknownを見つけ出すから
仮置き背理法で、黒でも白でも大きな変化がない個所を
何回もつかまされると、リカバリーに苦労する
あらかじめ大きな変化があるところを探す
その場所とは、
(1)4つかど
(2)4つかど付近
(3)4つの辺
(4)2択・3択・4択
(5)その他 俺が悪かった。ソースを見ても意味が分からない。
初心者がまず手を付けるべきパズルって何ですかね・・・。 >>714
いや、何が悪いのやら……(hissiで見ても他にレスが見当たらない)
>初心者がまず手を付けるべきパズル
自分が解きたいパズルを選べばいいと思うけど、
数独は9×9サイズならゴリ押し(バックトラックのみ)でも解けるから楽といえば楽かな? まずはCUI数独ソルバー・・・やってみようか。
動くという成功体験が大事ですよね。 ナンバープレース(「数独」は登録商標)をバックトラックでやったら現実的な時間で解けないんじゃ?
ソルバーを作るならそのパズルが得意でないと手こずる
n国同盟とかX-wingとかが上級問題になると必要になってくる Cパズルプログラミング-再帰編
ttp://karetta.jp/book/cpuzzle-recursion
ここのナンバープレースをJAVAに移植し始めました。
第二段階の問題ファイルの読み込みでつまずいてますw
順番に理解していけば何とかなる・・・何とかなる。 >>719
ぶっちゃけ知ってるならC言語流に読むよりC++風に読むほうが簡単でミスもない気が……
と言うか9x9前提でコード書いてるなこの人w 再帰を説明することが目的だからな
ナンバープレースを解くことが目的なら
・サイズが9×9以外
・ブロックの形が正方形でない
・1〜9の数字が1つずつ入るマスの組が他にもある(対角線など)
がよくあるから、それに対応させないことにしても拡張しやすいように作る >>721
>ブロックの形が正方形でない
これを実現するために、ナンプレ自動生成エンジンでは
「マスの集合」を定義して認識する実装だと知った時は感心したものだ……
(つまり普通の数独では縦横ブロック合計27通りの集合、対角線も加えると29通り、
変形ブロックやカラー付きの場合はそれぞれに応じて定義可能) 「クロスワードギバー」の片山です。バグ混入申し訳ありませんでした。
新しいバージョンをお使い下さい。
http://katahiromz.web.fc2.com/xword/ 関数のインライン化、constexpr対応、右辺値対応、マルチコア対応…、これ以上の高速化は可能なのか
知恵を貸してくれ 話の横からごめんなさい
イラストロジックの話が興味深くて少し実験していましたが
行き詰まってきたので公開することにしました
ttps://gist.github.com/anonymous/11100710 >>608 さん、イラストロジックでサイズが100x100くらいで
もし難問・奇問があれば欲しいです。よろしければください
90度回転させてもバックトラック(あれでも、っていうのかなあ??)
して解けるようになりました
あとはバクが潜んでいるか徹底的に見つけたいところまできました >>725 ソース貰いました。今から見てみます。でもC++はよく知らないので
逆に勉強させてもらいます。
動かせたら、また感想なり述べさせていただきます >>725 さん。御見それいたしました。瞬殺でした。師匠と呼んでもよろしいですか?
僕なんか下っ端ですね レベルが高すぎて訳が分からんが、何でも聞いてくれ。
聞き流すから!!! >>725 まだソース貰って勉強してないんですが、高速化するのに
面白い方法があります
各ヒントデータに可動領域があって可動領域の開始位置と終了位置を
常に計算させます
長さが10でヒントデータが1,1,1のとき
1234567890
a_b_cd_e_f
1(a-f),1(b-e),1(c-d)が可動領域です
今ヒントデータが3,4で
__20という意味
1122222222223
8901234567890
xxxxx_@_xx___
今ヒントデータが3,4で、可動領域の開始位置が3が(15)
4が(23)となっていると(23)から(25)は3つしか入らないから
開始位置を計算し直して3(23)4(28)と改めます
あと、ヒントデータが3,3,7,3,3,2,2のときは3が4つ7が1つ
2が2つと数えていて、7が唯一で
______abcdefg___
___xxx@@@@@@@xxx___
盤面の真ん中で7こ確定されれば、可動領域の開始位置と終了位置は
狭められます
初期段階では可動領域の開始位置と終了位置は、たいてい
他のヒントデータの開始位置と終了位置はかぶっていますが
どこともかぶらなくなると開始位置と終了位置は一意になります
演繹をするルーチンに開始位置と終了位置を渡すだけでずっと速くなると思います 1234567890
a_b_cd_e_f
1(a-d),1(b-e),1(c-f)が可動領域です
の間違いですね
m246j.cで唯一の7を探すルーチンはuniqueing()
開始位置sst[]と終了位置eet[]を計算するルーチンは、qcheckt()です
汚いソースですいません。人に見られる前提で書けばよかったな〜 ■ このスレッドは過去ログ倉庫に格納されています