【解答】パズルのプログラミング【作成】
- : 名無しさん@お腹いっぱい。 [] 04/08/14 13:50:7ki1y5sx
-
パズルの問題をプログラムで解いたり
プログラムで面を作成したりする方法を話し合うスレ。 - : 608 [sage] 2014/04/09(水) 01:12:29.77:m3a9/KQB
- あ、には結構痛いバグが見つかりました(LogicLandのファイルを読み込む時のもの)。
修正版を上げておきます。
ttp://http://codepad.org/3PzprA51 - : nekoppy3 [] 2014/04/09(水) 09:42:28.28:IBSI3Ewd
- 存在仮定法を使ってC言語で書いたら、今まで作ったものより遅かった
美しいソースじゃないからなのかな〜?
それともC++には高速演算に向いているのか、僕にはわからない世界
でも今まで解けなかった問題が存在仮定法を使うと2問ほど解けた
(2つとも70x180位のサイズで) - : nekoppy3 [] 2014/04/09(水) 09:52:26.99:IBSI3Ewd
-
その2問の問題。「先生たち」と「ポケモン、ジオリジン」
ttp://logic777.web.fc2.com/i/140408a.zip - : 608 [sage] 2014/04/09(水) 15:39:08.23:m3a9/KQB
-
相変わらず凄まじいコードだな……
書き方が違いすぎてまるで暗号だぜHAHAHA(別に悪い意味は無い)
さて、のおまけとして、ファイルコンバータを上げておきます。
具体的には、*.mno・*.txt・*.lgc・*.lgsを相互変換できます。お試しあれ
(まあヒント数字以外の盤面情報はlgc形式しか保存できないんですけどね……)
ttp://http://codepad.org/mCPTln3E
ちなみに当方のプログラムはUnicodeを考慮していません……ご了承下さい - : 608 [sage] 2014/04/09(水) 15:40:27.59:m3a9/KQB
- ちなみに、製作中、前回上げたファイルフォーマットに関するメモに
誤りがあることが発覚しました。謹んで訂正いたします。
修正版:ttp://http://codepad.org/cyziWoZX - : 608 [sage] 2014/04/09(水) 16:47:26.31:m3a9/KQB
- ・自PCでの測定結果
130226A.mno 131221C.mno
LogiNeko[s] 3.374 4.821 ※131221C.mnoは録画コマ送り測定
[s] 2.878164 . 2.884165 . ※バックトラックは使用せず
ロジック・ピクチャー[s] 0.751 0.751 ※録画コマ送り測定
なお、時間計測機能が無いソフトでの測定方法は、
「AmaRecTVで録画(59.94fps)してコマ送り」という原始的なものです。
また、で変換できない形式については、
拙作「イラロジ相互変換」で変換しています。
……なんでこんな時に「イラロジ相互変換」のバグに気づくんだよ畜生め!
自分の昔のコードを呪いたくなるんだぜorz
(訳:全然変換できないようわああん!) - : 608 [sage] 2014/04/10(木) 02:37:35.43:WB1fGxr1
- やったー!
画像から自動的にトレースして検算結果も出せるエディタできたよー!
ttp://i.imgur.com/l01KL4k.jpg
……手動編集機能はまだ付けてない。とりあえず試験的にうp
インターフェースが使いづらいだろうけど今は我慢してくだしあ
(エンターキーで出力画面を画像としてセーブ可能)
ttp://http://www1.axfc.net/u/3219410.zip - : nekoppy3 [] 2014/04/10(木) 11:07:41.68:7fl4Jdci
- さんの未解決問題
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}
だったと思う。間違えてたらごめん
普通の演繹法の内部で背理法が存在仮定法で
普通の演繹法の外部で背理法を行ったのが僕のやり方でなんとか解いた
(いきあたりばったりで滅茶苦茶だけど強引に解いた) - : nekoppy3 [] 2014/04/10(木) 11:11:12.63:7fl4Jdci
- Unknownの綴り間違えて恥ずかし
- : □7×7=4□□ [sage] 2014/04/10(木) 12:05:20.24:TfTOr8Vs
- 黒マスはヒントで与えられているけど、
白マスも幅・高さ・ヒントからある程度の推定が出来ますよね
白マスの推定ってのは強力な枝狩りにはなりえない?
縦の可能性・横の可能性から接点の可能性を絞るってのは無駄? - : nekoppy3 [] 2014/04/10(木) 13:02:13.22:7fl4Jdci
-
X:白
@:黒
_:未確定で
3〜12の間に@が3つ入るって分かっていたら
この場合わかりやすいよう3つの後は30ことかで30こは3〜12
に入らないものとする
123456789012345
XX___@______XXX
123456789012345
XXx__@__xxxxXXX
小文字のxが新たに入る白マスってわかります
二番目以降は、CacheX={(1)Unkown,(2)BlackにWhiteの上塗り->Unknown,
(3)WhiteにBlackの上塗り->Unknown}
だったか。
演繹の終わりに、1回以上配置成功の場合
CellList=CacheX(ただし、Unknownはコピーせず、BlackとWhiteをコピー)
また間違ってたら、ここに書きこむわ - : nekoppy3 [] 2014/04/11(金) 13:28:14.44:XMVD1Svh
- うまくいかない。一部を書いておきます
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);
}
(省略) - : □7×7=4□□ [sage] 2014/04/11(金) 13:37:15.55:Mx+5Rbr5
- 絵から数値データにするのは簡単なのに、数値から絵にするのは難しい。
いったい絵から数値に変換したときにどんな重要な要素が抜け落ちたんだろう。
あぁ白マスの数か・・・。 - : nekoppy3 [] 2014/04/11(金) 16:13:44.15:XMVD1Svh
- 僕のプログラム、gccに-O2のスイッチ付けてなかった
つけると半分の時間で解けるようになった。
もっときれいに書き直そう。自分のやつ - : 608 [sage] 2014/04/11(金) 19:36:06.35:YRY+QOFm
-
そりゃどう見たって情報量減ってるからなぁ……
>gccに-O2のスイッチ付けてなかった
!!!? - : □7×7=4□□ [sage] 2014/04/13(日) 06:47:06.44:6N8GvIsn
- 酸素が足りなくて息切れしてたんですね
- : nekoppy3 [] 2014/04/13(日) 09:10:17.70:SVRq3Rq1
- 誤解が生じたかもしれないけど、m246j.c(mx46j.c)の方ねそれは
gcc(g++)で-O2をつけるとSSE(x86),NEON(ARM)に最適化するらしい。
mx46j.c(ARM)は速くなったけどm246j.c(x86)は、さほど速くならなかったなあ - : 【中国電 76.7 %】 川c ’∀´) [sage] 2014/04/13(日) 14:18:32.56:03ZWkzXk
-
横から申し訳。猫 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ちょい) - : □7×7=4□□ [sage] 2014/04/13(日) 15:15:19.95:fRQEwya2
- コンパイルオプションは最後の手段ってばっちゃが言ってた。
- : 608 [sage] 2014/04/13(日) 15:22:21.75:FKEdmCCc
-
え?リリースビルドって普通-O2にするもんじゃないの?
……まあ、コンパイラによってデフォでの最適化方向は違う()けどね - : nekoppy3 [] 2014/04/13(日) 16:17:04.68:SVRq3Rq1
- 中国電力さん、bmmはランチャーだってば。
メインプログラムがm246j(mx46j)ね。リア友じゃん - : 【中国電 81.1 %】 [sage] 2014/04/14(月) 08:08:51.08:miyzVE5m
-
やっぱバレたか
一応、irx86 と irarm とir の引数も変えてますがこれじゃ不味いすか?? - : 【中国電 83.6 %】 [sage] 2014/04/14(月) 08:36:12.78:miyzVE5m
-
僕は猫さんに怒られながらrenice でプロセス優先度を-20にする時があります
邪道と言われますw
つか、猫さんのあずにゃんで動かしたさんのぷろぐらむ見せて貰ったけど爆速吹いたす
猫さんに書いちゃダメて言われてたけど、約束破って書いちゃったす
木曜日に1人じゃねえとプログラム書けねえつーから早退したす
猫さんが2ちゃんねる書いて楽しそうにしてるからROMるの楽しいす
アンパンマン嫌いです - : 608 [sage] 2014/04/14(月) 08:52:48.25:vjM+0EfD
- ==の言っていることが分からないっ……!
それはともかく、の改良版が出来ました
ttp://i.imgur.com/tFXuP8b.jpg
ttp://i.imgur.com/qobsjHo.jpg
動作原理としては、自動トレース→盤面データをdllに送って解析→
結果を元に手動で修正、といったところ
2枚目のように、未確定部分は黄色で表示されるので楽に書けるのが(・∀・)イイネ!!
真面目にVectorに上げる予定なのでここにうpするのは難しいかな…… - : 【中国電 85.0 %】 [sage] 2014/04/14(月) 09:13:11.51:miyzVE5m
-
おはようございます
サムネ見たら凄すぎふいたす
$ ./irx86
or
$ ./irarm
の初期でbmm or armbmm のlauncherを作り、
その後、ir から必要な.cを沢山引数をつけつつ、ずらーっとコンパイルする仕様なのです
バリバリ猫さんの俺様仕様す
猫さん、プログラムやめるて言ってたけどあずにゃんを無理矢理買わせ。汗
無理矢理開発させている
のはボクです(爆)
>>猫さん
ずっぱ●いわく、SSEはインラインアセンブラで書いた方が速いらしいす - : nekoppy3 [] 2014/04/14(月) 09:19:29.91:2cyJDrLQ
- Vectorに上がるの楽しみにしています
今日は、 の70x180>一万ドット越えの問題
(biglogicに収録してあるのは60〜70問、未収録は他に10問くらい)
の時間計測したり、
の未解決問題をすんなり解く方法の模索をしようと思っています
中電さん、ウチワ受けする話が多すぎです
バッチファイルのirの中身いじるだけでいいんじゃね? - : nekoppy3 [] 2014/04/14(月) 13:44:33.51:2cyJDrLQ
- Dynabook AZ (ARM Tegra250 1.0Ghz, Lubuntu13.04)
さんの (Ver.6)とmx46jl.c(ともにスイッチ-O2)
ttp://http://logic777.web.fc2.com/ にある、biglogic_j140330a.zip
に収録してある、1万ドット越えの問題の演算比較
時間単位は[s] mx46jl 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 海外ドラマ - : nekoppy3 [] 2014/04/14(月) 13:59:44.77:2cyJDrLQ
- Dynabook AZ (ARM Tegra250 1.0Ghz, Lubuntu13.04)
さんの (Ver.6)とmx46jl.c(ともにスイッチ-O2)
ttp://logic777.web.fc2.com/ にある、biglogic_j140330a.zip
に収録してある、1万ドット越えの問題の演算比較
時間単位は[s] mx46jl 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人か? - : nekoppy3 [] 2014/04/14(月) 14:35:45.97:2cyJDrLQ
- 書きこめない?もう書かない方がいいかも?
- : □7×7=4□□ [sage] 2014/04/14(月) 22:24:38.85:IBypCLJs
-
昔貼られてたヤツのソースを見つけました。
Simon Tatham's Puzzle Collection
ttp://code.ohloh.net/project?pid=6dCunV7fspU&cid=ZJt1JK_7eXs&fp=299756&mp=&projSelected=true
js版もありましたがコードが2万行もある;; わけわかめ - : 608 [sage] 2014/04/14(月) 22:31:39.74:vjM+0EfD
-
流石にjsで2万行とか頭おかしいとしか…… - : □7×7=4□□ [sage] 2014/04/15(火) 13:54:50.30:qOocNSff
- 変数が一文字とか連番なんで、
別の言語から自動変換して難読化とかしてあるんですかねw
ニコリのパズルの自動生成・自動解答への夢は遠い・・・ - : □7×7=4□□ [sage] 2014/04/15(火) 19:25:12.25:eqZg8GQE
- 自動解答はともかく、自動生成はパズルの良さを判定する必要があるからなー…
- : □7×7=4□□ [sage] 2014/04/15(火) 22:39:50.67:e/MxJsxa
- 自動ボツ
- : nekoppy3 [] 2014/04/16(水) 09:41:16.68:yagBLouI
- 未解決問題解決できました
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)とき、白優先で白から仮置き - : nekoppy3 [] 2014/04/16(水) 09:52:47.39:yagBLouI
- 田井中律、背理法トレース
(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秒かかるんですけど
双方向リストにして各ノードに盤面コピーして高速化を図りたいと思います - : 608 [sage] 2014/04/16(水) 09:58:02.28:OO0C8syb
-
つまりバックトラックは2段階で十分ということか……
ちょっとプログラム見直してくる - : nekoppy3 [] 2014/04/16(水) 14:31:26.38:yagBLouI
- 双方向リストにして各ノードに盤面コピーして高速化を図りたいと思います
作ってみた
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秒 - : □7×7=4□□ [sage] 2014/04/16(水) 19:59:23.98:yRagSnAL
- 次は10秒目指そうぜ
- : □7×7=4□□ [sage] 2014/04/17(木) 02:56:43.05:tszemOhm
- ,701
昔というのは>483かな
そのページに書いてあるけど元がCで他はコンバートみたいよ
jsは見たら ttp://emscripten.org/ 使ってるみたい - : nekoppy3 [] 2014/04/17(木) 14:38:37.32:Tepn1/DQ
-
4つかどの背理法でどっちつかず(n1=n2=0)のとき、黒優先で黒から仮置き
4つかど以外の背理法でどっちつかずの(n1=n2=0)とき、白優先で白から仮置き
訂正
4つかど以外の背理法でどっちつかずの(n1=n2=0)ときも、黒優先で黒から仮置き
田井中律90度回転させて4つ作ったんだけど
全部解析パターンも違うし、解く時間も違う
オリジナル 118秒
左90度回転 266秒
180度回転 262秒
右90度回転 途中で異常になって解けなかった
遅いのを速くするのは、またアイデア絞ってみます
解けない謎を解明したい - : 名無し [] 2014/04/17(木) 20:17:28.70:AWYKCBFs
- 柴山万里子は糞先生。氏ね。
- : nekoppy3 [] 2014/04/18(金) 09:18:09.06:nnU9xAbl
- 田井中律の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 ガンジー - : nekoppy3 [] 2014/04/18(金) 09:25:47.28:nnU9xAbl
-
解けない理由(仮説)
誤った盤面(ノード)で(X,Y)=Unknownを見つけ出すから
仮置き背理法で、黒でも白でも大きな変化がない個所を
何回もつかまされると、リカバリーに苦労する
あらかじめ大きな変化があるところを探す
その場所とは、
(1)4つかど
(2)4つかど付近
(3)4つの辺
(4)2択・3択・4択
(5)その他 - : □7×7=4□□ [sage] 2014/04/18(金) 14:02:34.24:+EYWIPhx
- 俺が悪かった。ソースを見ても意味が分からない。
初心者がまず手を付けるべきパズルって何ですかね・・・。 - : 608 [sage] 2014/04/18(金) 14:11:36.86:PXHNyPAp
-
いや、何が悪いのやら……(hissiで見ても他にレスが見当たらない)
>初心者がまず手を付けるべきパズル
自分が解きたいパズルを選べばいいと思うけど、
数独は9×9サイズならゴリ押し(バックトラックのみ)でも解けるから楽といえば楽かな? - : □7×7=4□□ [sage] 2014/04/18(金) 14:27:13.90:+EYWIPhx
- まずはCUI数独ソルバー・・・やってみようか。
動くという成功体験が大事ですよね。 - : □7×7=4□□ [sage] 2014/04/18(金) 21:08:24.75:Jyp8Lj+/
- ナンバープレース(「数独」は登録商標)をバックトラックでやったら現実的な時間で解けないんじゃ?
ソルバーを作るならそのパズルが得意でないと手こずる
n国同盟とかX-wingとかが上級問題になると必要になってくる - : 608 [sage] 2014/04/18(金) 21:42:19.50:hDtYtLi5
-
いや、9x9なら普通に解けるよ。証拠にソースを上げておく(拙いものだが)↓
ttp://http://codepad.org/0sqgRLH3
それより大きくなると手筋必須。ttp://http://www2.tokai.or.jp/deepgreen/shortnotes/numberplace/algorithm.htm
に載ってたEnclosure関数を実装してみた結果がこちら↓
ttp://http://codepad.org/qThGei4K - : □7×7=4□□ [sage] 2014/04/19(土) 13:31:45.21:fI34Rd1n
- Cパズルプログラミング-再帰編
ttp://karetta.jp/book/cpuzzle-recursion
ここのナンバープレースをJAVAに移植し始めました。
第二段階の問題ファイルの読み込みでつまずいてますw
順番に理解していけば何とかなる・・・何とかなる。 - : 608 [sage] 2014/04/19(土) 13:36:59.58:/NBCQyQ2
-
ぶっちゃけ知ってるならC言語流に読むよりC++風に読むほうが簡単でミスもない気が……
と言うか9x9前提でコード書いてるなこの人w - : □7×7=4□□ [sage] 2014/04/19(土) 19:09:17.98:EyU0dVVm
- 再帰を説明することが目的だからな
ナンバープレースを解くことが目的なら
・サイズが9×9以外
・ブロックの形が正方形でない
・1〜9の数字が1つずつ入るマスの組が他にもある(対角線など)
がよくあるから、それに対応させないことにしても拡張しやすいように作る - : 608 [sage] 2014/04/19(土) 20:43:31.24:/NBCQyQ2
-
>ブロックの形が正方形でない
これを実現するために、ナンプレ自動生成エンジンでは
「マスの集合」を定義して認識する実装だと知った時は感心したものだ……
(つまり普通の数独では縦横ブロック合計27通りの集合、対角線も加えると29通り、
変形ブロックやカラー付きの場合はそれぞれに応じて定義可能) - : 片山博文MZ ◆T6xkBnTXz7B0 [] 2014/04/20(日) 00:30:56.65:RevNx0tL
- 「クロスワードギバー」の片山です。バグ混入申し訳ありませんでした。
新しいバージョンをお使い下さい。
ttp://http://katahiromz.web.fc2.com/xword/ - : 片山博文MZ ◆T6xkBnTXz7B0 [] 2014/04/20(日) 00:49:45.37:RevNx0tL
- 関数のインライン化、constexpr対応、右辺値対応、マルチコア対応…、これ以上の高速化は可能なのか
知恵を貸してくれ - : □7×7=4□□ [sage] 2014/04/20(日) 08:35:38.51:ZOT2sJOz
- 話の横からごめんなさい
イラストロジックの話が興味深くて少し実験していましたが
行き詰まってきたので公開することにしました
ttps://gist.github.com/anonymous/11100710 - : nekoppy3 [] 2014/04/20(日) 09:14:54.73:IKgqueXq
- さん、イラストロジックでサイズが100x100くらいで
もし難問・奇問があれば欲しいです。よろしければください
90度回転させてもバックトラック(あれでも、っていうのかなあ??)
して解けるようになりました
あとはバクが潜んでいるか徹底的に見つけたいところまできました - : nekoppy3 [] 2014/04/20(日) 13:26:00.53:IKgqueXq
- ソース貰いました。今から見てみます。でもC++はよく知らないので
逆に勉強させてもらいます。
動かせたら、また感想なり述べさせていただきます - : nekoppy3 [] 2014/04/20(日) 14:19:22.77:IKgqueXq
- さん。御見それいたしました。瞬殺でした。師匠と呼んでもよろしいですか?
僕なんか下っ端ですね - : □7×7=4□□ [sage] 2014/04/20(日) 14:57:02.94:7bG/3gud
- レベルが高すぎて訳が分からんが、何でも聞いてくれ。
聞き流すから!!! - : □7×7=4□□ [sage] 2014/04/20(日) 19:21:26.07:hbYbM0Mc
- 流すんかい!
- : nekoppy3 [] 2014/04/21(月) 09:50:30.69:KjuEzmp/
- まだソース貰って勉強してないんですが、高速化するのに
面白い方法があります
各ヒントデータに可動領域があって可動領域の開始位置と終了位置を
常に計算させます
長さが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こ確定されれば、可動領域の開始位置と終了位置は
狭められます
初期段階では可動領域の開始位置と終了位置は、たいてい
他のヒントデータの開始位置と終了位置はかぶっていますが
どこともかぶらなくなると開始位置と終了位置は一意になります
演繹をするルーチンに開始位置と終了位置を渡すだけでずっと速くなると思います - : nekoppy3 [] 2014/04/21(月) 10:10:22.66:KjuEzmp/
- 1234567890
a_b_cd_e_f
1(a-d),1(b-e),1(c-f)が可動領域です
の間違いですね
m246j.cで唯一の7を探すルーチンはuniqueing()
開始位置sst[]と終了位置eet[]を計算するルーチンは、qcheckt()です
汚いソースですいません。人に見られる前提で書けばよかったな〜 - : nekoppy3 [] 2014/04/21(月) 11:49:20.59:A6cZqWAn
- uniqueing()じゃなくて、uniqt(),uniqy()だった。
念の為、確認してみた - : □7×7=4□□ [sage] 2014/04/21(月) 18:41:21.50:2FaE1dv4
- 方程式に出来たりするんですかね?
マス=??????????
有限で一意なら出来るんでしょうね。意味ないだろうけど - : □7×7=4□□ [sage] 2014/04/21(月) 23:11:12.55:HhyGC33B
- 何の言語が向いてるんだろう
LISPとか良さそうな気がするんだが - : 725 [sage] 2014/04/22(火) 19:45:45.73:LQvwnui8
-
いずれは公開するつもりだったのですが
テスト用に問題を回転させるアイデアに驚いて早めました
テスト問題ですがランダムなドット絵を使い始めました
安定的に1秒程度で判別できるのは50×50黒6割で
黒が減ったり問題が大きくなると極端に遅くなります
100×100を10秒以内はまだまだ先のようです
ところでとても速いものをみつけました
ttp://sourceforge.net/projects/jsolver/
ソースが読みづらく説明もなくてアルゴリズムがわからないのが残念です - : 【中国電 77.3 %】 [sage] 2014/04/22(火) 22:23:07.30:HN2HK1hp
-
さん
120818C.mno が確か一番時間の掛かる問題であったかと思います
しかし5年前の C2D で1秒切ってますよ
ARM(Nexus 7(2012)) だと3秒ほどで爆速過ぎます - : nekoppy3 [] 2014/04/23(水) 12:47:41.73:qTz728eI
- ランダムなドット絵、そのアイデアいただきます!
僕もランダムな絵の問題作ってみます
100x100は僕の力では100秒かかります。この辺が限界ですわ、C言語で
C言語よりC++の方が向いてると思います。こういうの - : nekoppy3 [] 2014/04/24(木) 09:14:40.23:IGWrBaRM
-
ランダムなドット絵、裁縫のパッチワークをイメージした
元絵(131313A.mno〜131313N.mno,サイズ180x70)のイメージから
ランダムに20x20の布切れを切り取り、100x100のサイズに貼り合わせる
というもの。布切れはランダムに90度、180度回転している
昨晩、作っていた。問題がほぼ無限に作れます - : nekoppy3 [] 2014/04/24(木) 09:26:34.37:IGWrBaRM
- 100x100のサイズのパッチワーク風の問題のある場所
ttp://logic777.web.fc2.com/i/paw_mno140424a.zip
00001.mnoは1000秒かかりました
00002.mnoはまだ解けていません
n1=n2=0(黒と白の仮置き、どちらでもOKのとき増え方がどちらも
200ドット以下の時、リスト構造を枝刈りしてもうまくいかないです
500ドット以下の時、枝刈りにしてみます - : □7×7=4□□ [sage] 2014/04/24(木) 12:33:42.80:2Fm6dbfU
- 100*100サイズ固定で問題データの復元用の数値って作れないのかな?
データの受け渡しに便利ですよね。 - : 608 [sage] 2014/04/24(木) 14:12:17.67:KtiK3nHw
- 最近忙しくてコードに手をつけていません……
理屈から言えば、長さがnある部分のヒント数字は
最大n/2個(nが奇数なら(n+1)/2個)必要なので、
100x100固定なら50×100×2=10000個の数字枠が必要になります
charでも10KBは必要ですね - : nekoppy3 [] 2014/04/25(金) 10:49:52.66:ziNlGwWg
- さんの教えてくれた jsolverで の内容物
00001.mnoから00010.mnoをtxtにコンバートして動かしてみた
$ ./js1 00005 // mno->txt converting, original program
$ ./jsolver -n 2 00005.txt
どれも2秒もかからない - : nekoppy3 [] 2014/04/25(金) 11:01:02.97:ziNlGwWg
- js1.c のある場所:
ttp://logic777.web.fc2.com/i/js1.zip - : nekoppy3 [] 2014/04/25(金) 13:00:46.71:ziNlGwWg
- 00001.mno トレース
No. (X, Y)
1 1 1 両方OK黒から 黒863ドット白0ドットの増加分
2 1 100 両方OK黒から 黒1669白1514
3 98 63 両方OK黒から 黒1634白1629
3は黒でこのまま続けるが、実際はここは白が正解
4 83 100 白のみ 黒65白2
5 82 100 黒のみ 黒120白164
6 79 100 黒のみ 黒164白2
7 78 100 白のみ 黒69白0
8 77 100 白のみ 黒47白1
9 76 100 白のみ 黒41白1
10 75 100 白のみ 黒1220白0
11 74 100 白のみ 黒33白0
Noはこの後11から19まで進むんだけど、No10で疑問に思わなければ
(プログラム的に)1万ドットのうち黒1220ドットも動いているのに
なんで白に決めるんかと。このへんを改良できれば速くなるような気がする - : nekoppy3 [] 2014/04/27(日) 10:46:46.95:kJK5Dpla
- さんの意見、心に留めておきましょう。今いろいろ忙しいです。
ちょっとゆっくりやってみます - : □7×7=4□□ [sage] 2014/04/27(日) 21:55:20.71:mubuiqy6
- Cパズルプログラミング-再帰編 > ペントミノ > 盤面の1次元配列化 をJAVAに移植中。
ポインタの++使われるときついわぁw
変換じゃなくて元から1次元配列のデータを持たせた方が楽かな。
動かんけどw - : □7×7=4□□ [sage] 2014/04/27(日) 23:38:20.47:ARwYB3LB
- Javaなら、Cのポインタ演算をエミュレートするクラスを作っておいて
その中で一次元配列なりなんなり使って実装すればいいんじゃね - : 608 [sage] 2014/04/28(月) 00:04:30.45:bgeglmxX
-
本当なら当該言語(今回はJava)に合わせたコードに
書き直せればいいんだけどなぁ……>ポインタの移植云々
俺?Javaはまだ勉強中で…… - : □7×7=4□□ [] 2014/04/28(月) 09:54:58.52:1coyLXtd
- さんの意見で作ってみた
ttp://logic777.web.fc2.com/i/paw_mnx140427.zip
ファイルの中は、mnoファイルと拡張子が.1と.2のファイル
mnxファイル、そしてmnofix.cとmnoprint.cが入っていると思います
.1と.2はイメージファイルで、.1と.2が存在して.3のファイルが存在しない時
.2を読み込みます。このファイルの実装は解析時間が578秒だったとき
578/100+1=6で拡張子が「.6」100秒置きに100秒目で「.1」、200秒目で
「.2」、300秒目で「.3」の拡張子の中断ファイルを作っていた経緯からです。
イメージファイルの書式は、盤面のデータが未確定のとき「_」、
黒は「Q」、白は「x」です。ファイルの中身はその3つと改行とEOFの5つしかありません
mnofix.cはmnoファイルとイメージファイルを読み込んで、
さん用の復元用の数値のファイル.mnxを出力します
mnoファイルで
*Y10
*y001 5
で、イメージファイルが
___QQQQQxx
(未確定が3つ、黒が5つ、白が2つのとき)
mnxファイルでは
*y001 _3,5,x2
というように、数値の前に「_」や「x」が、つきます
例外的に
mnoファイルで
*Y10
*y001 0
のとき、イメージファイルは
xxxxxxxxxx (白が10こ)になりますが、
mnxファイルでは
*y001 0
となる(?こういう仕様にしたはず、ちょっと自信がない)
いずれにしても、mnxファイルからmnoに、いつでも戻せるように
したかったです
mnoprint.cはmnxを読み込んで、実際に絵が出るかCUIで表示
*yのデータは盤面data[]に
*tのデータは盤面data2[]に
data[]とdata2[]に異常がなければ、未確定は「_」黒は「Q」白は「x」
異常があれば「E」を表示します - : □7×7=4□□ [sage] 2014/04/29(火) 00:23:10.46:SKT6Qn4J
- >Cのポインタ演算をエミュレートするクラスを作って
なんぞそれw
再帰の引数にポインタ+1しやがって・・・・・・。どうしろとw - : □7×7=4□□ [sage] 2014/04/29(火) 13:12:47.54:w7oxn/VC
-
今更だが自己解決
って2009年かよ!書いたのw
検索すれば出てくるんでリンクはしない… - : □7×7=4□□ [sage] 2014/04/30(水) 19:17:50.37:M1dqXkiH
-
考え方だけ参考にしてプログラムはJavaで書いてあるものを読んでみたら
例えば ttp://oku.edu.mie-u.ac.jp/~okumura/java-algo/ の Tetromino.java - : 【中国電 74.6 %】 [sage] 2014/05/01(木) 06:23:59.03:cuUObW46
- おくぬら先生じゃないか
わろたw - : □7×7=4□□ [sage] 2014/05/03(土) 12:38:57.17:FdF1eVCj
- リスト構造と検索再帰が理解できれば・・・・。
- : □7×7=4□□ [sage] 2014/05/18(日) 21:07:39.73:sMCfOBJf
- ___
/| |
||. 彡⌒ミ|
||. (・ω・`| 誰かいる?
||oと. U|
|| |(__)J|
||/彡 ̄ ガチャ
彡 ⌒ ミ ♪
(( (・ω・` )
♪ / ⊂ ) )) ♪
((( ヽつ 〈
(_)^ヽ__)
♪ 彡⌒ ミ
(´・ω・彡⌒ ミ
彡⌒ ミつ(´・ω・`) )) ♪
(( (´・ω・`) ( つ )
( つ ヽ とノ ♪
〉 とノ )^(_)
(__ノ⌒(_)
___
/| |
|| .彡⌒ ミ
||. ( )|
||oと. |
|| |(__)J|
||/彡 ̄ ガチャ - : □7×7=4□□ [] 2014/05/30(金) 09:16:18.37:4WfnTzis
- ある知り合いから、virtual host に接続していると書きこめない
(実際書きこめなかった)Jimのやつめ・・・
ミラー:ttp://hello.2ch.net/test/read.cgi/puzzle/1092459010/l50
ここなら書きこめるかテスト - : □7×7=4□□ [] 2014/05/30(金) 10:12:17.70:4WfnTzis
- githubに貼り付けてみました
内容は、m246k.cで、biglogic_k140430a.zip と変わりませんが一応
ttps://gist.github.com/nekoppy3 - : □7×7=4□□ [] 2014/08/22(金) 22:28:36.54:ZN257wEY
- おながいします
ttp://i.imgur.com/Wv1Fx2u.jpg
1〜16までの数字を一個ずつ入れて
各線上の4つの合計が
いずれも34になるように - : □7×7=4□□ [sage] 2014/08/23(土) 01:17:42.20:GVLSUtl/
- 13
1 2 3 4
12 5
14 15
11 6
10 9 8 7
16
[1,3,14,16,2,7,9,4,8,13,5,15,6,10,12,11] - : □7×7=4□□ [] 2014/08/23(土) 14:57:27.93:+rB8LlQn
- au予報言氷雨デモなぜ末端ディレクター戦争指名タイ米粉ステーキ万国ニューヨークブカ牛肉直輸出制限業者議論病院雇用市議しょうゆダシマクッロスさむらいエバコラア山雪光金ガンダム風ミックドラ社員あかうんとパズ豚骨のり野菜炒めラーメン
au予報言氷雨デモなぜ末端ディレクター戦争指名タイ米粉ステーキ万国ニューヨークブカ牛肉直輸出制限業者議論病院雇用市議しょうゆダシマクッロスさむらいエバコラア山雪光金ガンダム風ミックドラ社員あかうんとパズ豚骨のり野菜炒めラーメン
au予報言氷雨デモなぜ末端ディレクター戦争指名タイ米粉ステーキ万国ニューヨークブカ牛肉直輸出制限業者議論病院雇用市議しょうゆダシマクッロスさむらいエバコラア山雪光金ガンダム風ミックドラ社員あかうんとパズ豚骨のり野菜炒めラーメン
ニンニクヤーフォー低原価スマ金土地酒気帯びNHK公的私的支出トウデン教授嘘芸人横浜名古屋遅延電池切れ福岡損保新規駐車近代ゲームシェア回収フジ政権転職提案たれ巫女ラーメン
abk公式審判漏洩安保険王なにあげてんだよ?「わー!ふーう?」↓↓★★↓↓★↓★▼★宿題通調印鑑カウントダウンたまらんだけ労災募金額休日接待ゴルフ議員国会アイスブルームハンバーグ歌舞伎派大学生 - : 片山博文MZ ◆T6xkBnTXz7B0 [] 2014/10/08(水) 13:19:25.58:LjbFvpMJ
- Windows用フリーソフト「クロスワード ギバー」
ヒント直接編集機能が付いたよ!!!
ttp://http://katahiromz.web.fc2.com/xword/ - : 片山博文MZ ◆T6xkBnTXz7B0 [] 2014/10/09(木) 15:17:20.90:nfoI1BGW
- バグ修正しました。
- : 片山博文MZ ◆T6xkBnTXz7B0 [] 2014/10/18(土) 17:21:02.56:9V3xWvL8
- Windows用フリーソフト「クロスワード ギバー」
ver.2.2にバージョンアップしたよ!!!
ttp://http://katahiromz.web.fc2.com/xword/ - : 片山博文MZ次期CEO ◆T6xkBnTXz7B0 [] 2014/11/30(日) 16:43:56.91:RLHclfWA
- Windows用ソフト「クロスワード ギバー」
ver.2.4にバージョンアップしたよ!!!
漢字・英語クロスワードも作れるよ!!!
ttp://http://katahiromz.web.fc2.com/xword/ - : □7×7=4□□ [sage] 2014/12/01(月) 03:54:19.08:q0k/WMwV
- ___
/| |
|| .彡⌒ ミ
||. ( )|
||oと. |
|| |(__)J|
||/彡 ̄ ガチャ - : □7×7=4□□ [sage] 2015/04/25(土) 23:51:32.95:AFsw2VHO
- ブラウザでペンシルパズルに毛の生えた程度のゲームを作ろうとする。
JAVAアプレット・フラッシュ・html5・・・・
色々選択肢があるのだろうが、無難なのはどれなんだろう。 - : アホ私大 [] 2016/11/11(金) 10:17:43.00:kBBzMlLV
- スケルトンを自動生成するプログラムのヒントをください。
迷路作成アルゴリズムで迷路の直線長さを制限するとよいように思うがうまくゆかない。 - : □7×7=4□□ [] 2016/11/29(火) 17:41:22.51:ctNNl3EY
- 29日午前3時半ごろ、
逆走した軽乗用車が大型トラックと衝突。
計3人が死傷した。
認知症の過程は放射能汚染によって加速します。
注意欠陥障害(ADD)多動性障害(ADHD)、
若年性アルツハイマー病の原因となっており、
人々は肺炎やインフルエンザ、慢性疲労、癌、
HIV/エイズなどに抵抗できなくなっています。
免疫システムの崩壊の結果がアレルギーです。
死者の数は、他のいかなる原因よりも多いです。
河川の汚染は犯罪と見られなければなりません。
問題は、日本政府が何も認めないことです。
多くの人々が放射能の影響で死んでいるのに、
彼らは幻想の中に生きています。
日本の近海の食料は安全ではありません。
健康上のリスクは福島に近づくほど高まります。
福島の子供達は癌をもたらす被爆をしています。
福島県民は廃炉後1、2年で戻れるでしょう。
マイト レーヤは原発の閉鎖を助言されます。
マイト レーヤによれば、飛行機など
原子のパターンが妨害されると墜落します。
彼はいかなる人間よりも危険をよくご存じです。
マイト レーヤの唇からますます厳しい
警告と重みが発せられることを覚悟しなさい。
凡例:
レス番
100 (赤) → 2つ以上レスが付いている
100 (紫) → 1つ以上レスが付いている
名前
名無しさん (青) → sage のレス
名無しさん (緑) → age のレス
ID
ID:xxxxxxx (赤) → 発言が3つ以上のID
ID:xxxxxxx (青) → 発言が2つ以上のID
このページは2ch勢いランキングが作成したキャッシュです。元のページはこちら。削除についてはこちら。