【解答】パズルのプログラミング【作成】

**名無しさん＠お腹いっぱい。** · 04/08/14 13:50

パズルの問題をプログラムで解いたり
プログラムで面を作成したりする方法を話し合うスレ。

**□７×７＝４□□** · 2014/04/02(水) 10:57:27.09

>>631
1から作れば移植する必要はないよ！やったね>>621！

**□７×７＝４□□** · 2014/04/02(水) 11:24:48.00

HashioKakero.Cざっと見たけど、HTMLとJavaScriptでよくね？
tableとonClickでやるどこかに似たようなGUIのやつあったべ。
あえてJava使ってそのうちAndroidアプリにしたいとかならあえて止めないけど

**□７×７＝４□□** · 2014/04/02(水) 13:27:36.05

暫定的な修正版。別のページを参考にしたらあっさりできた（もちろん改良予定

**608** · 2014/04/02(水) 13:28:56.40

>>634はミス。。。

暫定的な修正版。別のページを参考にしたらあっさりできた（もちろん改良予定)。背理法最強伝説
http://codepad.org/RYBb423Y

参考：http://infosys.sys.i.kyoto-u.ac.jp/~ken3/IL/index.html

**nekoppy3** · 2014/04/03(木) 13:01:59.39

>>608 >>635

病院来るときは、DynabookAZです
Dynabook AZ (ARM Tegra250 1.0Ghz, Lubuntu13.04)

マイクロ秒は「us」と表記していいみたい
24,689,813usと書いていれば２４秒と見えるようわかりやすく書きます

　　　　　　　　　　　　　　　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（３４分）
110614a.mno 20x20 イチゴのショートケーキ　125,230us, 353,486us
110612a.mno 40x40 あをによし奈良　１０分放置、233,249,645us（４分）

>>635のソース見て、今までc++書いたことないけど、見よう見まねで
いじくってみようと思う

**608** · 2014/04/03(木) 13:20:20.72

>>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

**□７×７＝４□□** · 2014/04/03(木) 13:29:30.38

精神って単語と、クリリン・ねずみ男って単語で咄嗟に「ヤバイ」と信号が出た。

問題の絵の名前か・・・と思い至ったときホッっとした。

**nekoppy3** · 2014/04/03(木) 13:31:34.26

>>637　おおお～、すげー
今からソース貰って試してみますわ。ありがとう！

**608** · 2014/04/03(木) 13:46:18.41

おお、今試したら120918A.mno（「イタリア・ゴンドラ.2490sec」、175x110）ですら
38,949,227[us]で解いたぞ……メモ化の威力が凄すぎる

**nekoppy3** · 2014/04/03(木) 14:47:33.15

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秒　アダムの創造

もう、ガブリ４つじゃん
Cacheに相当する変数、僕も入れているはずなんだけど
C++って速いんだな～驚愕する

**□７×７＝４□□** · 2014/04/03(木) 18:03:11.96

よく見るHP
ttp://www.ic-net.or.jp/home/takaken/nt/logic/index.html

ここのは古い感じなの？

**608** · 2014/04/03(木) 19:00:28.95

>>641
>C++
まあC++使うのは趣味も半分ですけどねｗ
カプセル化とかに慣れれば（C言語よりは）良い言語ですよ……
>>642
そうでもないと思いますよ。ぶっちゃけググって上の方に出ていたページを
参考にしただけですからｗ

　私が使ったアルゴリズムは普通に背理法で、
「列または行毎に、『あるマスが■だとして矛盾が出れば×。あるマスが×だとして
矛盾が出れば■。そうでない時は放置』として確定させる」というものです。
　矛盾の判定は、「ヒント数字の置き方が1通りでも存在すればOK」といった感じなので、
そこだけより良いアルゴリズムに差し替えても構わない仕様になっています。
　http://www2.ocn.ne.jp/~minui/illulogi/index.htmlの場合、その判定を
キャッシュ（メモ化）によって大幅に高速化しています。これがカラーイラストロジックに
使えるかまでは分かりませんが、スマートな発想だと言えます。

**608** · 2014/04/03(木) 19:02:04.56

そう言えば、まだバックトラックは組み込んでなかったな……
（そうしないと超難問に対応できないと思われる）

**□７×７＝４□□** · 2014/04/03(木) 22:03:56.34

更に人間が解くみたいに「更新があったマスを含む行列を優先的に見る」ということができればもっと速くなりそう

**nekoppy3** · 2014/04/04(金) 09:37:21.00

>>645

＞＞更に人間が解くみたいに「更新があったマスを含む行列を優先的に見る」
それ必須と（出来れば、過去の行列の時間測定から速い順で行列を行う）

ある行が１０こヒントデータがあるとして
１～３番目と８～１０番目が既に確定している場合
４～７番目のみ調べるようにする

僕のは実装してますけど６０８さんのは、まだまだ速くなりますよ

**□７×７＝４□□** · 2014/04/04(金) 12:23:03.83

確定探索で、（sum数字０～数字ｎ）＋（n-１）＝＝問題幅or高さ。なら確定。
ってのは無駄な計算かな？

手作業で解くときはよく使うけど。

**nekoppy3** · 2014/04/04(金) 12:38:01.27

>>647 の言いたいことに追随して、

＠：黒
ｘ：白
＿：未確定で

１２３４５６７８９０１２３４５６７８９０
ｘｘ＿＿＠＿＿ｘｘｘｘｘｘ

のときに３～７まで４つ入るって分かってたら

１２３４５６７８９０１２３４５６７８９０
ｘｘ＿＠＠＠＿ｘｘｘｘｘｘ

なんてのを実装すれば速くなりますよ

**nekoppy3** · 2014/04/04(金) 14:03:52.96

「イラストロジック　演繹法」でググって
トップに出てくるサイトの
「Section 4 存在仮定法」っていうの僕のには実装していないから遅いのかも。
演繹法は、やっています。

**608** · 2014/04/04(金) 19:45:47.96

ふと思ったんだが、背理法って演繹じゃないのだろうか……？

皆さんの意見も参考にして、とりあえず組み直してみますね。
ちなみに私、イラストロジックの問題ファイルを相互変換する
ソフトを作ったことがあったりしますｗ
http://www.vector.co.jp/soft/win95/game/se497399.html

**608** · 2014/04/04(金) 19:51:54.99

:::::::::::.:　.:. . ∧＿∧ . . . .: ::::::::　　ごめんなさい間違えました……
:::::::: :.: . .　/彡ミ゛ヽ;)ヽ、. ::: : ::　　>>602で既に書いてあるのに宣伝がましくてごめんなさい
::::::: :.: . . / :::/:: ヽ、ヽ、i . .:: :.: :::　言い訳ついでに書くと、アレを作った時はパズルを解く方がメイン
￣￣￣（_,ノ￣￣ヽ､_ノ￣　　　　でして、幾つかソフトがあるのに互換が効かないのに戸惑った
　　　　　　　　　　　　　　　　　　　から作ったという経緯があります。一番面倒だったのはLogiNeko形式で、
目一杯容量を削った代償にチョー複雑なファイルフォーマットに四苦八苦しながら開発しました。
そのかいあって、画像インポート機能がないLogiNeko相手にも、こいつを噛ますことで擬似的に
画像インポートさせることができるんですよｴｯﾍﾝ、というのがささやかな自慢です。
まあ勝手に作ったソフトなので各ソフト作者からは連絡も何もありませんが、ちょっと寂しい気もしますね。

**608** · 2014/04/05(土) 03:20:34.61

当面の目標。今の自分のコードじゃ完全には解けない強敵。つまりバックトラックしないと無理……
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

**608** · 2014/04/05(土) 03:25:02.79

そう言えばこんなの見つけました。データは案の定biglogic_j140330a.zipに入ってましたが(grepして発見)
http://plaza.rakuten.co.jp/nekoppy3/diary/201208100000/

**□７×７＝４□□** · 2014/04/05(土) 06:36:27.56

組み合わせ爆発お姉さんを助けるアルゴリズム。とか
中学生がスパコンで魔方陣を解いたアルゴリズム。とか

中身を見ても居ないし想像もつかないけどワクワクするね。

**□７×７＝４□□** · 2014/04/05(土) 11:42:17.81

>>654
>中身を見ても居ないし想像もつかない
いや見ろよ

前者のJavaコード付き解説：
http://d.hatena.ne.jp/nowokay/20120911
http://d.hatena.ne.jp/nowokay/20121015#1350267331
http://d.hatena.ne.jp/nowokay/20121016#1350351212
http://d.hatena.ne.jp/nowokay/20121017#1350435805
http://d.hatena.ne.jp/nowokay/20121018#1350528607
http://d.hatena.ne.jp/nowokay/20121019#1350607290

後者の解説：
http://pc.watch.impress.co.jp/docs/news/yajiuma/20140303_637771.html
http://www.ccs.tsukuba.ac.jp/pr/media/140228_press

**□７×７＝４□□** · 2014/04/05(土) 20:20:11.58

>>652
それ作った本人参上
大まかに説明すると、解き方は大きく3段階に分けられて
まずは1段階だけで解き、完成しなかったら次の段階へ行く
3段階で解けなければ不成立か重解
どの段階まで使ったかを見れば難易度も分かる

GUIの部分が今の自分の環境では動かないから試せないけど、10秒程度で解けてた
あとカラーロジックにも対応している

**□７×７＝４□□** · 2014/04/05(土) 20:58:35.23

>>656
>それ作った本人
　　　　　　＿人人人人人人人人人人人人人人＿
　　　　＞　　　　な　なんだってー！！　　　　＜
　　　　　￣^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^￣
　　　　 _,,.-‐-..,,_　　　　　　 _,,..--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（解答）

**nekoppy3** · 2014/04/06(日) 12:06:26.30

存在仮定法、まだうまくいってない
理論をちゃんと理解してないのか

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(２０１４年３月３０日版)

120810A.mno 38.77秒　ナポレオンと馬
120918A.mno 81.29秒　イタリア・ゴンドラ（僕のは今８２秒で解けます）
121227A.mno 82.99秒　スペイン
121228A.mno 106.26秒　カブキ・５人か？
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秒　カブキ・５人か？
131226P.mno 292.37秒　阿吽
131227A.mno 42.51秒　ドガのエトワール

Ver.3　は背理法を白から始めているせいか
白っぽい絵は解くのが早いけど
黒っぽい絵は遅い傾向があるんじゃないかと思う

**□７×７＝４□□** · 2014/04/07(月) 02:47:08.30

やったー！　大幅な高速化に成功したよー！
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

**608** · 2014/04/07(月) 02:54:48.78

ちなみに、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
　キャラスレが過疎ってるようなのでこっちにうｐ
　イラストロジック

　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

**nekoppy3** · 2014/04/07(月) 11:15:32.20

Dynabook AZ (ARM Tegra250 1.0Ghz, Lubuntu13.04)

>>608 >>659 (Ver.4)

Ver.4のソース２７行２３番目
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のソースの後にバックトラック・プログラムを追加すればいいと思う

**□７×７＝４□□** · 2014/04/07(月) 17:40:00.79

ソルバーは１秒を切らないと役に立たないってよく聞くよね。
高速化でよく聞くのは、１次元配列化・ビット演算。

何かすごい計算方法が眠って居るんだろうなぁ。
縦・横ときたらナナメ！　上下に分割して！　意味不明

**608** · 2014/04/07(月) 19:05:39.10

>>662
ソースのコメントにも書いてますが、下手にCに近くすると(コードを最適化しすぎると)、
デバッグが大変になるので(まだ)やる気はありません。それにこのパズルの場合、
盤面をビット表現すると縦横が65マス以上になった際を考慮するのが面倒くさいということもあります。
また、アルゴリズムの良し悪し(オーダ)＞コードの最適化具合(係数)なので、
C++でバッチリ決めた後にボトルネックを最適化しようかと思います。
(あるパズルで)

ところで、ソルバーは1秒云々のソースはどこにあるのでしょうか？

**608** · 2014/04/07(月) 21:05:01.88

>>659に小細工(既に解いた列・行は解かない)を施して微妙に高速化。
平均して2割ぐらいは速くなる、はず
http://codepad.org/N2UwGvhq

**608** · 2014/04/07(月) 23:05:43.87

バックトラック対応に行き詰まったので、現在は他形式にも対応できるように拡張中です。
とりあえず「イラロジヘルパー」(http://www6.ocn.ne.jp/~b-lab/txt_lib/)の「*.lgs」形式には対応させました。

**□７×７＝４□□** · 2014/04/07(月) 23:43:33.72

ソルバーじゃないけど、将棋の対戦ソフトのアルゴリズムが凄かったな
パターン認識みたいなことをやってた

**656** · 2014/04/08(火) 21:20:08.78

バックトラック（縦横同時に考える上級テクニック）についてヒントを

あるマスが決定すると他のマスも次々に決定する時、「影響度が高い」と言う
この「影響度」を未決定の各マス毎に計算し、高い順に仮決定していく
影響度の計算式がカギ

**608** · 2014/04/09(水) 00:59:55.04

>>664に、拡張子「*.lgs(イラロジヘルパー)」「*.txt(ロジック・ピクチャー)」
「*.lgc(LogicLand)」への対応を追加し、更にバックトラックを試験的に導入しました。
その影響でコマンドライン引数が微妙に仕様変更されましたのでご了承下さい。
(ファイル名のみだとバックトラック無し、ファイル名の後に正数を書くとその段階までバックトラック)
http://codepad.org/byX1WiQJ

>>667
影響度ですか……実装を検討してみます。

**608** · 2014/04/09(水) 01:00:45.60

2段階までバックトラックしないと解けない小さな問題があればいいのに……

**608** · 2014/04/09(水) 01:12:29.77

あ、>>668には結構痛いバグが見つかりました(LogicLandのファイルを読み込む時のもの)。
修正版を上げておきます。
http://codepad.org/3PzprA51

**nekoppy3** · 2014/04/09(水) 09:42:28.28

存在仮定法を使ってC言語で書いたら、今まで作ったものより遅かった
美しいソースじゃないからなのかな～？
それともC++には高速演算に向いているのか、僕にはわからない世界

でも今まで解けなかった問題が存在仮定法を使うと２問ほど解けた
（２つとも70x180位のサイズで)

**nekoppy3** · 2014/04/09(水) 09:52:26.99

>>671
その２問の問題。「先生たち」と「ポケモン、ジオリジン」

ttp://logic777.web.fc2.com/i/140408a.zip

**608** · 2014/04/09(水) 15:39:08.23

>>672
相変わらず凄まじいコードだな……
書き方が違いすぎてまるで暗号だぜHAHAHA(別に悪い意味は無い)

さて、>>665のおまけとして、ファイルコンバータを上げておきます。
具体的には、*.mno・*.txt・*.lgc・*.lgsを相互変換できます。お試しあれ
(まあヒント数字以外の盤面情報はlgc形式しか保存できないんですけどね……)
http://codepad.org/mCPTln3E

ちなみに当方のプログラムはUnicodeを考慮していません……ご了承下さい

**608** · 2014/04/09(水) 15:40:27.59

ちなみに、>>673製作中、前回上げたファイルフォーマットに関するメモに
誤りがあることが発覚しました。謹んで訂正いたします。
修正版：http://codepad.org/cyziWoZX

**608** · 2014/04/09(水) 16:47:26.31

・自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
(訳：全然変換できないようわああん！)

**608** · 2014/04/10(木) 02:37:35.43

やったー！
画像から自動的にトレースして検算結果も出せるエディタできたよー！
http://i.imgur.com/l01KL4k.jpg

……手動編集機能はまだ付けてない。とりあえず試験的にうｐ
インターフェースが使いづらいだろうけど今は我慢してくだしあ
(エンターキーで出力画面を画像としてセーブ可能)
http://www1.axfc.net/u/3219410.zip

**nekoppy3** · 2014/04/10(木) 11:07:41.68

>>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}

だったと思う。間違えてたらごめん

普通の演繹法の内部で背理法が存在仮定法で
普通の演繹法の外部で背理法を行ったのが僕のやり方でなんとか解いた
（いきあたりばったりで滅茶苦茶だけど強引に解いた）

**nekoppy3** · 2014/04/10(木) 11:11:12.63

Unknownの綴り間違えて恥ずかし

**□７×７＝４□□** · 2014/04/10(木) 12:05:20.24

黒マスはヒントで与えられているけど、
白マスも幅・高さ・ヒントからある程度の推定が出来ますよね
白マスの推定ってのは強力な枝狩りにはなりえない？

縦の可能性・横の可能性から接点の可能性を絞るってのは無駄？

**nekoppy3** · 2014/04/10(木) 13:02:13.22

>>679

X:白
@:黒
_:未確定で
３～１２の間に＠が３つ入るって分かっていたら
この場合わかりやすいよう３つの後は３０ことかで３０こは３～１２
に入らないものとする

123456789012345
XX___@______XXX

123456789012345
XXx__@__xxxxXXX

小文字のｘが新たに入る白マスってわかります

>>677

二番目以降は、CacheX={(1)Unkown,(2)BlackにWhiteの上塗り->Unknown,
(3)WhiteにBlackの上塗り->Unknown}

だったか。

演繹の終わりに、１回以上配置成功の場合
CellList=CacheX(ただし、Unknownはコピーせず、BlackとWhiteをコピー）

また間違ってたら、ここに書きこむわ

**nekoppy3** · 2014/04/11(金) 13:28:14.44

>>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);
}

（省略）

**□７×７＝４□□** · 2014/04/11(金) 13:37:15.55

絵から数値データにするのは簡単なのに、数値から絵にするのは難しい。
いったい絵から数値に変換したときにどんな重要な要素が抜け落ちたんだろう。

あぁ白マスの数か・・・。

**nekoppy3** · 2014/04/11(金) 16:13:44.15

僕のプログラム、gccに-O2のスイッチ付けてなかった
つけると半分の時間で解けるようになった。

もっときれいに書き直そう。自分のやつ

**608** · 2014/04/11(金) 19:36:06.35

>>682
そりゃどう見たって情報量減ってるからなぁ……
>>683
>gccに-O2のスイッチ付けてなかった
！！！？

**□７×７＝４□□** · 2014/04/13(日) 06:47:06.44

酸素が足りなくて息切れしてたんですね

**nekoppy3** · 2014/04/13(日) 09:10:17.70

>>684 誤解が生じたかもしれないけど、m246j.c(mx46j.c)の方ねそれは
gcc(g++)で-O2をつけるとSSE(x86),NEON(ARM)に最適化するらしい。
mx46j.c(ARM)は速くなったけどm246j.c(x86)は、さほど速くならなかったなあ

【中国電 76.7 %】 **川c ’∀´)** · 2014/04/13(日) 14:18:32.56

>>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ちょい)

**□７×７＝４□□** · 2014/04/13(日) 15:15:19.95

コンパイルオプションは最後の手段ってばっちゃが言ってた。

**608** · 2014/04/13(日) 15:22:21.75

>>688
え？リリースビルドって普通-O2にするもんじゃないの？
……まあ、コンパイラによってデフォでの最適化方向は違う(>>686)けどね

**nekoppy3** · 2014/04/13(日) 16:17:04.68

>>687 中国電力さん、bmmはランチャーだってば。
メインプログラムがm246j(mx46j)ね。リア友じゃん

【中国電 81.1 %】 · 2014/04/14(月) 08:08:51.08

>>690
やっぱバレたか
一応、irx86 と irarm とir の引数も変えてますがこれじゃ不味いすか？？

【中国電 83.6 %】 · 2014/04/14(月) 08:36:12.78

>>688
僕は猫さんに怒られながらrenice でプロセス優先度を-20にする時があります
邪道と言われますw
つか、猫さんのあずにゃんで動かした>>608さんのぷろぐらむ見せて貰ったけど爆速吹いたす
猫さんに書いちゃダメて言われてたけど、約束破って書いちゃったす

木曜日に１人じゃねえとプログラム書けねえつーから早退したす

猫さんが２ちゃんねる書いて楽しそうにしてるからROMるの楽しいす
アンパンマン嫌いです

**608** · 2014/04/14(月) 08:52:48.25

>>687=>>691=>>692の言っていることが分からないっ……！

それはともかく、>>676の改良版が出来ました
http://i.imgur.com/tFXuP8b.jpg
http://i.imgur.com/qobsjHo.jpg
動作原理としては、自動トレース→盤面データをdllに送って解析→
結果を元に手動で修正、といったところ
2枚目のように、未確定部分は黄色で表示されるので楽に書けるのが(・∀・)ｲｲﾈ!!
真面目にVectorに上げる予定なのでここにうｐするのは難しいかな……

【中国電 85.0 %】 · 2014/04/14(月) 09:13:11.51

>>693
おはようございます
サムネ見たら凄すぎふいたす

$ ./irx86
or
$ ./irarm
の初期でbmm or armbmm のlauncherを作り、
その後、ir から必要な.cを沢山引数をつけつつ、ずらーっとコンパイルする仕様なのです

バリバリ猫さんの俺様仕様す
猫さん、プログラムやめるて言ってたけどあずにゃんを無理矢理買わせ。汗

無理矢理開発させている
のはボクです(爆)

>>猫さん
ずっぱ●いわく、SSEはインラインアセンブラで書いた方が速いらしいす

**nekoppy3** · 2014/04/14(月) 09:19:29.91

>>693 Vectorに上がるの楽しみにしています

今日は、>>670 の70x180>一万ドット越えの問題
(biglogicに収録してあるのは６０～７０問、未収録は他に１０問くらい）
の時間計測したり、
>>677 の未解決問題をすんなり解く方法の模索をしようと思っています

>>692 中電さん、ウチワ受けする話が多すぎです
バッチファイルのirの中身いじるだけでいいんじゃね？

**nekoppy3** · 2014/04/14(月) 13:44:33.51

Dynabook AZ (ARM Tegra250 1.0Ghz, Lubuntu13.04)

>>608 さんの >>670 (Ver.6)とmx46jl.c(ともにスイッチ-O2)

http://logic777.web.fc2.com/ にある、biglogic_j140330a.zip
に収録してある、１万ドット越えの問題の演算比較

時間単位は[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　　　キャラ８匹

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

Dynabook AZ (ARM Tegra250 1.0Ghz, Lubuntu13.04)

>>608 さんの >>670 (Ver.6)とmx46jl.c(ともにスイッチ-O2)

ttp://logic777.web.fc2.com/ にある、biglogic_j140330a.zip
に収録してある、１万ドット越えの問題の演算比較

時間単位は[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　　　歌舞伎、５人か？

**nekoppy3** · 2014/04/14(月) 14:35:45.97

書きこめない？もう書かない方がいいかも？

**□７×７＝４□□** · 2014/04/14(月) 22:24:38.85

>>633
昔貼られてたヤツのソースを見つけました。
Simon Tatham's Puzzle Collection
ttp://code.ohloh.net/project?pid=6dCunV7fspU&cid=ZJt1JK_7eXs&fp=299756&mp=&projSelected=true

js版もありましたがコードが２万行もある；；　わけわかめ

**608** · 2014/04/14(月) 22:31:39.74

>>699
流石にjsで2万行とか頭おかしいとしか……

**□７×７＝４□□** · 2014/04/15(火) 13:54:50.30

変数が一文字とか連番なんで、
別の言語から自動変換して難読化とかしてあるんですかねｗ

ニコリのパズルの自動生成・自動解答への夢は遠い・・・

**□７×７＝４□□** · 2014/04/15(火) 19:25:12.25

自動解答はともかく、自動生成はパズルの良さを判定する必要があるからなー…

**□７×７＝４□□** · 2014/04/15(火) 22:39:50.67

自動ボツ

**nekoppy3** · 2014/04/16(水) 09:41:16.68

>>677 未解決問題解決できました
>>652 20091007k-on01.mno(100x100,田井中律）攻略！

未解決の盤面に(X,Y)=Unknownを見つけ、n1=黒に仮置き背理法()＆
n2=白に仮置き背理法()をする

n1,n2の戻り値は０＝全部は解けないが矛盾せず、１＝矛盾する、２全部解けた

n1=0&&n2=1の場合、黒ですすめる
n1=1&&n2=0の場合、白ですすめる
n1=0&&n2=0の場合、どちらか優先順位を決めて、黒優先のとき、黒を仮置き
して、後々矛盾した場合、白に仮置きする
n1=1&&n2=1の場合、明らかに矛盾、どっちでもよかった所まで戻って反転する

４つかどの背理法でどっちつかず(n1=n2=0)のとき、黒優先で黒から仮置き
４つかど以外の背理法でどっちつかずの(n1=n2=0)とき、白優先で白から仮置き

**nekoppy3** · 2014/04/16(水) 09:52:47.39

田井中律、背理法トレース

(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,黒に決定

このあと全部解けた

今段取り悪くて１５００秒かかるんですけど

双方向リストにして各ノードに盤面コピーして高速化を図りたいと思います

**608** · 2014/04/16(水) 09:58:02.28

>>705
つまりバックトラックは2段階で十分ということか……
ちょっとプログラム見直してくる

**nekoppy3** · 2014/04/16(水) 14:31:26.38

>>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秒

**□７×７＝４□□** · 2014/04/16(水) 19:59:23.98

次は１０秒目指そうぜ

**□７×７＝４□□** · 2014/04/17(木) 02:56:43.05

>>699,701
昔というのは>483かな
そのページに書いてあるけど元がCで他はコンバートみたいよ
jsは見たら ttp://emscripten.org/ 使ってるみたい

**nekoppy3** · 2014/04/17(木) 14:38:37.32

>>704

４つかどの背理法でどっちつかず(n1=n2=0)のとき、黒優先で黒から仮置き
４つかど以外の背理法でどっちつかずの(n1=n2=0)とき、白優先で白から仮置き

訂正

４つかど以外の背理法でどっちつかずの(n1=n2=0)ときも、黒優先で黒から仮置き

田井中律９０度回転させて４つ作ったんだけど
全部解析パターンも違うし、解く時間も違う

オリジナル　　　１１８秒
左９０度回転　　２６６秒
１８０度回転　　２６２秒
右９０度回転　　途中で異常になって解けなかった

遅いのを速くするのは、またアイデア絞ってみます

解けない謎を解明したい

**名無し** · 2014/04/17(木) 20:17:28.70

柴山万里子は糞先生。氏ね。

**nekoppy3** · 2014/04/18(金) 09:18:09.06

>>710 田井中律の90度回転の問題

ttp://logic777.web.fc2.com/i/muzu01.zip

難問データ集(mno)

101a.mno 田井中律オリジナル
101a.i オリジナル・イメージ
101b.mno 田井中律・左９０度回転
101b.i イメージ
101c.mno １８０度回転
101c.i
101d.mno 右９０度回転
101d.i

rot.c イメージを左９０度回転するプログラム $ ./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

>>710

解けない理由（仮説）

誤った盤面（ノード）で(X,Y)=Unknownを見つけ出すから

仮置き背理法で、黒でも白でも大きな変化がない個所を
何回もつかまされると、リカバリーに苦労する

あらかじめ大きな変化があるところを探す

その場所とは、

（１）４つかど

（２）４つかど付近

（３）４つの辺

（４）２択・３択・４択

（５）その他

**□７×７＝４□□** · 2014/04/18(金) 14:02:34.24

俺が悪かった。ソースを見ても意味が分からない。

初心者がまず手を付けるべきパズルって何ですかね・・・。

**608** · 2014/04/18(金) 14:11:36.86

>>714
いや、何が悪いのやら……(hissiで見ても他にレスが見当たらない)
>初心者がまず手を付けるべきパズル
自分が解きたいパズルを選べばいいと思うけど、
数独は9×9サイズならゴリ押し(バックトラックのみ)でも解けるから楽といえば楽かな？

**□７×７＝４□□** · 2014/04/18(金) 14:27:13.90

まずはCUI数独ソルバー・・・やってみようか。
動くという成功体験が大事ですよね。

**□７×７＝４□□** · 2014/04/18(金) 21:08:24.75

ナンバープレース（「数独」は登録商標）をバックトラックでやったら現実的な時間で解けないんじゃ？
ソルバーを作るならそのパズルが得意でないと手こずる
n国同盟とかX-wingとかが上級問題になると必要になってくる

**608** · 2014/04/18(金) 21:42:19.50

>>717
いや、9x9なら普通に解けるよ。証拠にソースを上げておく(拙いものだが)↓
http://codepad.org/0sqgRLH3
それより大きくなると手筋必須。http://www2.tokai.or.jp/deepgreen/shortnotes/numberplace/algorithm.htm
に載ってたEnclosure関数を実装してみた結果がこちら↓
http://codepad.org/qThGei4K

**□７×７＝４□□** · 2014/04/19(土) 13:31:45.21

Cパズルプログラミング-再帰編
ttp://karetta.jp/book/cpuzzle-recursion

ここのナンバープレースをＪＡＶＡに移植し始めました。
第二段階の問題ファイルの読み込みでつまずいてますｗ
順番に理解していけば何とかなる・・・何とかなる。

**608** · 2014/04/19(土) 13:36:59.58

>>719
ぶっちゃけ知ってるならC言語流に読むよりC++風に読むほうが簡単でミスもない気が……
と言うか9ｘ9前提でコード書いてるなこの人ｗ

**□７×７＝４□□** · 2014/04/19(土) 19:09:17.98

再帰を説明することが目的だからな
ナンバープレースを解くことが目的なら
・サイズが9×9以外
・ブロックの形が正方形でない
・1～9の数字が1つずつ入るマスの組が他にもある（対角線など）
がよくあるから、それに対応させないことにしても拡張しやすいように作る

**608** · 2014/04/19(土) 20:43:31.24

>>721
>ブロックの形が正方形でない
これを実現するために、ナンプレ自動生成エンジンでは
「マスの集合」を定義して認識する実装だと知った時は感心したものだ……
(つまり普通の数独では縦横ブロック合計27通りの集合、対角線も加えると29通り、
変形ブロックやカラー付きの場合はそれぞれに応じて定義可能)

**片山博文MZ** ◆T6xkBnTXz7B0 · 2014/04/20(日) 00:30:56.65

「クロスワードギバー」の片山です。バグ混入申し訳ありませんでした。
新しいバージョンをお使い下さい。
http://katahiromz.web.fc2.com/xword/

**片山博文MZ** ◆T6xkBnTXz7B0 · 2014/04/20(日) 00:49:45.37

関数のインライン化、constexpr対応、右辺値対応、マルチコア対応…、これ以上の高速化は可能なのか

知恵を貸してくれ

**□７×７＝４□□** · 2014/04/20(日) 08:35:38.51

話の横からごめんなさい
イラストロジックの話が興味深くて少し実験していましたが
行き詰まってきたので公開することにしました
ttps://gist.github.com/anonymous/11100710

**nekoppy3** · 2014/04/20(日) 09:14:54.73

>>608 さん、イラストロジックでサイズが１００ｘ１００くらいで
もし難問・奇問があれば欲しいです。よろしければください
９０度回転させてもバックトラック（あれでも、っていうのかなあ？？）
して解けるようになりました

あとはバクが潜んでいるか徹底的に見つけたいところまできました

**nekoppy3** · 2014/04/20(日) 13:26:00.53

>>725 ソース貰いました。今から見てみます。でもC++はよく知らないので
逆に勉強させてもらいます。

動かせたら、また感想なり述べさせていただきます

**nekoppy3** · 2014/04/20(日) 14:19:22.77

>>725 さん。御見それいたしました。瞬殺でした。師匠と呼んでもよろしいですか？
僕なんか下っ端ですね

**□７×７＝４□□** · 2014/04/20(日) 14:57:02.94

レベルが高すぎて訳が分からんが、何でも聞いてくれ。
聞き流すから！！！

**□７×７＝４□□** · 2014/04/20(日) 19:21:26.07

流すんかい！

**nekoppy3** · 2014/04/21(月) 09:50:30.69

>>725 まだソース貰って勉強してないんですが、高速化するのに
面白い方法があります

各ヒントデータに可動領域があって可動領域の開始位置と終了位置を
常に計算させます

長さが１０でヒントデータが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,3,7,3,3,2,2のときは３が４つ７が１つ
２が２つと数えていて、７が唯一で

______abcdefg___
___xxx@@@@@@@xxx___

盤面の真ん中で７こ確定されれば、可動領域の開始位置と終了位置は
狭められます

初期段階では可動領域の開始位置と終了位置は、たいてい
他のヒントデータの開始位置と終了位置はかぶっていますが

どこともかぶらなくなると開始位置と終了位置は一意になります

演繹をするルーチンに開始位置と終了位置を渡すだけでずっと速くなると思います

**nekoppy3** · 2014/04/21(月) 10:10:22.66

1234567890
a_b_cd_e_f

1(a-d),1(b-e),1(c-f)が可動領域です

の間違いですね

m246j.cで唯一の７を探すルーチンはuniqueing()

開始位置sst[]と終了位置eet[]を計算するルーチンは、qcheckt()です
汚いソースですいません。人に見られる前提で書けばよかったな～