パズルの問題をプログラムで解いたり
プログラムで面を作成したりする方法を話し合うスレ。
ttp://www.ic-net.or.jp/home/takaken/ ttp://bach.istc.kobe-u.ac.jp/puzzle/ ttp://rogiken.org/puzz/program/index.html ttp://www.alpha-net.ne.jp/users2/cult/java/ ttp://be__.at.infoseek.co.jp/java/nps/ 15*15でも即答できるようになったが、問題は別解探索。
数字が通らないマスもあるのを前提にすると、10*10でも解けなくなる。
関西解探索ありの限度は、今は7*7ぐらいだ。
計算順序でのものなので１から作り直します。
関西チェックは10*10なら30分ぐらいで発見できるレベル。まだまだだな。
面積は倍以上になるんだな。７×７で４９だけど１０×１０は１００マス。
どうりでここらへんから急に遅くなるはずだ。探索数から考えると５０マス増えたとして
２の５０乗倍に増えるということになるし。こりゃやっかいなＮＰ問題に手を出したかも。
はなにで作ってる？
ちょっと勉強してみることにするよ。
今日は眠いから明日にでものんびりいくとするよ。
大変だなぁDelphiなんて。
学生だったらマイクロソフトがたまにやるイベントとかで
.net配ったりするからそれをもらったほうがいいかもね。
その.ＮＥＴはＣです？ＪＡＶＡです？ＶＢです？
言語選ぶ時にどれにしようか色々悩んだけどね。
２ＣＨやその他で色々調べた結果これになったよ。
>16
ガンガレー。Ｃより楽だしＶＢみたいに外部ＤＬＬがいらないから
ちょっとしたものを作って配布するのに便利だぞ。
解けるものと解けないものがあるのには驚いたな。
現在、10*10で短絡解ありをチェックして平均１分半で見つけるように。
ようやく進歩が見えてきた感がある。
だが、10*10の短絡が無い盤面を短絡チェックしようとすると
無いと判明するまで６分３０秒。2.4Ｇｈｚでこれではまだまだっす。
>19 トポロジーというやつですな。
問題自動作成と最低限の機能を持ったものが3時間ほどで完成ヽ(´ー｀)ノ
ちょっと慣れたからそろそろ解答プログラム作りに入る予定。
にないものを作ろうと思案中。
でも出てないやつって難しいんだろうか・・・_|￣|○
ペントミノ詰・数独・カックロ・四角に切れ・ひとりにしてくれ・美術館・橋かけ
ttp://http://www.pro.or.jp/~fuji/puzzlestudy/index.html 黒どこ
ttp://http://f24.aaacafe.ne.jp/~nikolist/puzzle/kurodoko.html シンクローン
ttp://http://f24.aaacafe.ne.jp/~nikolist/puzzle/synchro.html ｻﾝｸｽ!
なんか難しそうだけどよく読んで勉強するよ。
とりあえず初期段階の１の四方を黒にするのは成功。
ifの入れ子でエラーだしまくったよ････_|￣|○
あと意外とぬりかべは面倒なので注意。
とりあえずその程度の腕だときついんじゃないかなあと思った。
ネタがかぶってもいいので簡単なパズルを練習に作ってみるのがよいかと。
ってことで見た感じ一番スタンダードな数独をやってる。
とりあえず順調にいってる予感。
高速解答の順序もなんとなくやりかたをつかめ始めた気がする。
基本として、枝狩りの時は初期の枝を重視すべし、だな。
やや時間がかかってもいいから、良くあるありえないパターンは
先にはじいておいた方が、大きな面が速く解ける。
ところで、ペントミノなんかの敷き詰め問題の解き方が
どうしても想像つかんのだが。
ペントミノなら藤原氏のところにプログラムがあるよ。
左上から順に置けるところにピースを置いていくだけで、
今の計算機なら数秒で前階が出る。
けっこう難しいな･････
とりあえずじっくりいくか･･･
なぜそんなやりかたでいいのか？という理由がわからんのですよ。
とてもいいかげんそうで穴があるように見えてしまう。
でも解けるらしい。なんで？
置けるパターンを全部試しているのだからあのやりかたで漏れているパターンはないはず。
盤面のプリント関数が用意してあるから、あちこち挿んで実行してみると動きがわかっていいよ。
氏の「再帰のお勉強」に割と詳しめの解説があります。
サンクス。やっと感覚的に理解できたよ。
再帰はわかってたけど、それをどう応用するのかがわからんかった。
パズル解答のプログラミングって、再帰は重要だよな。
初心者はまず、でこぼこのマス目を塗りつぶせるようなプログラムを作るべしと思う。
これでニコリのいろんな面を確かめられる。
今までテキストのコピペでやりくりしてたから楽になるぜ。
高速化も実行。チェックスピードは遅くなったものの全体的な解析力は向上。
10*10の全短絡解析を数秒～11分で。数字が少ないと一気に長くなるな。
あと、物は試しに11*11の面をチェックしてみたら・・・１時間近くかかったよ＿|￣|○
これまで色々ブレイクスルーな方法で時間短縮してきたけど
もう一皮向けないとダメってことか。厳しいな。
ペンシルパズルはオープンソースモデルが向いているだろう。
10*10の短絡チェックを多くても２分以内で解析できるように。
11*11も３分程度で完了。でも15*15までにはまだまだ。
そろそろ遅くなってきたから、計算そのものの高速チューニングを検討してみる。
数字同士を繋げている線でなく、線が通過していない壁に注目しました。
ラインが通っているマスは上下左右のうち、２方がライン、２方が壁になります。
ある一つのマスがあるとして、その上と左を調べます。
上と左の壁数が
２つの場合、右と下は壁は０です。
１つの場合は、右か下どちらか一つが壁です。
０の場合は、右と下は両方とも壁です。
数字の入っているマスの場合は１方がラインで、残り三方は壁です。そして
上と左の壁数が
２つの場合は、右か下どちらか一つが壁です。
１つの場合は、右と下は両方とも壁です。
０の場合はありえません。
これを、左上から右に向けて１マスずつ壁を置いていき
ありえない状態になったら前に戻って別のパターンを調べます。（どちらかが壁の部分での分岐）
矛盾なく最後まで全部埋まったら同じ数字同士が繋がっているかチェック。
違う数字が繋がっていたらまた前に戻って別パターンを調べます。
これが基本的なやりかたです。
早く解析できるのですが、それでも時間がかかるので途中で色々なチェックを入れて
解析スピードを上げています。
例１：
→↓
←←
のようにコの字型にラインが曲がるのはありえないので
壁がこういう状態になったら戻ってやり直し。
例２：数字マスの壁を決定する時、上か左が開いていたら
その時点で繋がっている先の数字を調べてダメならやり直す。
などなどです。
ナンリンソルバーとはすごいね
ところで、そのプログラムって、
すべてのマス目を線が通る解を全て出力する
もんと思っていい？
その通りです。
そして、プログラムをちょっと追加してやれば短絡解のチェックもできます。
数字の入ってないマスで上と左の壁数が
２の場合、右と下の壁は０か２。
としてやれば線の通っていないマス目がある場合も探し出せます。
ただし、これをやると一気に計算時間が増えます。それを減らすのが現在の課題。
空白のマス目全部を線が通る解を求めるなら、
例えば、盤面の隅なんかは線の通り方がかなり限定されるから
探索はある程度速いと思うけど、
短絡解だと限定できないから膨大な時間かからない？
自分は、短絡解まで出力するソルバーを、昔作ろうとして挫折したんだけどさw
計算時間が一気に増えるってのは、その状況で壁数０としたときに矛盾（既にどうやってもつなぐことができない）
していることを判定できていないから、じゃないかな。
例えば
ttp://pc5.2ch.net/test/read.cgi/gamedev/1088809456/67 この左上で０を入れたときとか。それがさらに複雑になったものとか。
結果、後になって（それも相当に分岐して）から矛盾に気づく、と。
ありがとう
そっちのリンク先読ませてもらった。
短絡解ありの問題は時間かかるけど、
解がユニークな問題は １０×１０ くらいまではかなり速く解けるんだ。
いや、それにしてもすごいわ
短絡解を探さないなら15*15でも即答だ。
短絡解チェックありでも10*10なら最大30秒に。
短絡解チェックありで15*15だと３０分以上かかるからまだまだだけどな。
ttp://www8.plala.or.jp/ara3/puz/ac/1209.gif これで短絡解も調べてどれくらいですか?
12*12は、６番で１２分１３秒かかった以外は多くても４分ってとこだった。
そろそろスピードアップ方法が煮詰まってきた感じ。
今日はこれまで。おやすみ～。
二個ある同じ数字を区別して無かったのでチェックのスルーが発生した。
今から組みなおします。
ところで勘違いされないように書いておくけど、短絡解チェックの場合に時間がかかるのは
短絡の解答が見つかるまでに時間がかかるという理由以外に。
短絡解が無い場合は、最後まで全部チェックしきらなくてはいけない
からという理由があったりします。全部チェックして、これは短絡解の無い正当な面ですよと
証明できなくちゃいけないからなぁ。
しかも原因取り除いたらなぜか>45のが１分16秒に早まったよ。
ま、結果オーライｗ
お話してくれ
肝ったってどこが肝なのかいまいちわからんので概略から。
１マスの情報は右壁の有無と下壁の有無を01で持っています。
上の壁と左の壁は隣のマスの情報からもらいます。
上と左の壁情報から右と下の壁を決めます。やり方は上の通り。
□□□□ →１ それを一番上の左端から右へ向かって決定していき
□□□□ →２ 一行埋まったら一つ下の行の左端から繰り返します。
□□□□ →３ パターンが合わなかったら分岐のあるところまで戻ってやり直し。
□□□□ →４ 右下まで埋めきったら数字の繋がりをチェック。
いかにしてありえないパターンを排除して短縮させるかってとこ。
最初に加えたのはコの字の禁止。上に書いたように
→↓
←←
となるパターンは右上と右下で壁がカタカナのコの形になって
線を引く時にはありえない。これを上下左右の向きそれぞれにチェック。
壁が ＿| の形に決まったら上のマスと左のマスを調べて |＿＿| になってたり
￣|
＿| になってたらＮＧで戻ります。￣| では左マスで |￣￣| を調べ、|＿では上マスの
|￣
|＿ を調べます。
塗りつぶしプログラムの要領で先端を調べて違う数字と繋がっていたらＮＧ。
ただ、検索範囲外まで調べてはいけないので下図の□から出た場合は
数字不明として仮にＯＫとしておきます。
□□□□
□□３
ここまで加えたチェックでも、短絡を探さないなら15*15で即答できます。
でも、壁マスあり条件の短絡を探すとなると7*7程度が限界です。
時間短縮することにしてみました。
例えば
４３２１
５ ９10
６７８
のようにラインが回る場合はダメなので、壁の向こうにすでに通った跡があればＮＧです。
１２
■３
５４ のように壁越しの無駄な遠回りもＮＧなので、壁マスの向こうもチェックします。
このＮＧチェックを数字が書かれて無いマスにも適用し、上か左が開いていたら
調べるようにさせたところかなりの時間短縮ができました。
違う数字同士がむすばれていたらＮＧ。
続いて壁が ＿| の状態で、上を調べていったら左にたどり着くような
空ループになった状態もＮＧとしました。
このせいで探索回数の数字の伸びは遅くなったものの
より短い時間で解答を得ることができました。
無駄なチェックが多いのを発見。
１ □□■ 例えばこの盤面で１の先が右端の下から出るパターンは数通りあります。
■■□■ でも上がどんなパターンでも、下の出口は同じです。１が右下から出るパターンは
■■□□ 一回チェックしてＮＧが出れば、後はどんなパターンでもＮＧ確定です。
↓
これはいくらなんでも無駄なので、マスを改行する時に下の壁のパターン＆壁が無い場合の
行き着く先の数字を調べて記憶し、前と同じパターンが出てきたらＮＧとします。
上の例なら最下段の改行で0001と記憶しておき、ＮＧで戻ってきて上のパターンを変え、
再度改行する時に、また同じ0001が出たら下を調べるまでもなくＮＧです。
あまり記憶数を増やすと逆にそれを調べるのに遅くなるので、500パターン程度の記憶にして
試したところ、劇的に速度が向上しました。これで10*10の探索が30秒以内に。
とまぁ、とりあえず入れてるチェックはこんなとこです。
ですが、15*15全チェックだと2時間やってもまだ序盤なので、もっと他にいい方法が無いか研究中。
今日はこんなとこでまた。
現実的な時間で、複数解チェックのできるプログラムがないと思う。
応用が効くのに
あっちも力任せの世界
局所的に短絡がないことを示すとか、いろんなアプローチがあると思う。
逆にＡ～Ｅ同士を繋ぐ線の距離と曲げ回数を同じにしろ
っていうパズルはどうだろうと前向きに考えたりして。
あ～時間縮まんねぇ。もう一度ざっぱり組みなおしてみよう。
今度は子プロセスの超入れ子構造無しでチャレンジ。
うっかりではできちゃうけど、作ろうと思って作れるもんじゃないからなぁ。
過去のニコリさばくりまくっちゃったよ。
あと、チェッカは稠密解がなくてもいいなら適当に数字を一個減らせば別解の山。
考えてみれば普通に解けるかどうかだけは即チェックできるんだから
数字をちょっとずつ移動させながらチェックしていけばいいんだな。サンクス。
あと、昨日思いついたんだけど、２方向だけ決まっている状態だと、残り二方向は
まだ壁不確定な時があるけど、三方向決まっていれば残り一方向は絶対確定なんだよな。
つまり、壁を確定させるのを二行目からやっていけば、一番上の行は確定されるんだよな。
□□□□ これでＡを仮決定させる、上のマスは必ず確定。これを右へ伸ばしていく。
Ａ.□□□ 仮の状態は２から３に増えるけど、仮定で進めていく行は半分になる。
10*10ならマス100。今までの一行２択方式で考えると最下段は自動決定として
2＾90なので、約1.2*10＾27通り。ゼロが27個つく。
この２行３択方式で考えると、3＾50で約7.2*10＾23。ゼロが23個。
超大雑把に見積もっても1000倍の差があるな。
15*15なら1.6*10＾63と、1.3*10＾50でゼロが13個分の差。
１から組みなおしが必要だから時間がかかるけどやってみる価値はあるかも。
└─┘└──┘ 間に初期配置の数字がなければ無駄。
間が3以上の└…┘は調べる場所が広くて少し大変。
落としどころは└──┘くらいかなあ。
斜めに埋めていくような探索も考えたけど、どう考えても逆に遅くなるしなぁ。
└─┘└──┘ のチェックは
□□□□ の１の先をチェックする時の帰りに、壁向こうに通った番号が無いかを
□■■□ 入れ子構造でチェックしているので、壁で直線ショートカットできる
□■■１ パターンは全部チェックしてますです。
今日は子プロセスの超入れ子構造無しで１から組み立ててみたけど
逆に5％ほど遅くなっちゃったよ(´・ω・`)ｼｮﾎﾞｰﾝ
今度は２段三方向での方式にチャレンジしてみる。
試したところ、のが51秒に。
１ □■■ やり方は、例えば左の図で３をチェックしてNG判定した時に戻る場合は
■□■■ 一度左に戻って、さらに改行して戻って右端につき、さらに左へとなりますが
■３ この時、途中で分岐できる部分があったら、その分岐から再度進み始めます。
分岐部分で形を変え、また３の位置に進んでも、３での繋がりは同じなので結局NGです。
そこで、こういう場合には３の一つ上の場所まで無条件でバックするようにしてやれば
余計な探索を減らすことができます。このおかげで探索時間が大幅に減らせるように。
もう無理かと思ってたけど、まだまだ縮められるようです。
もう少し詳しく説明して頂けるとありがたい。
ttp://gamdev.org/up/img/1120.lzh マウスで１から数字を置いて実行させるだけ。置いた数字は移動もできます。
......1............6
.2..........3.......
....................
..........6......5..
...7................
......5.4......9....
..1................2
.....9....8.........
.3................7.
.......4.....8......
線じゃなくて壁でわけると、盤面がフィルオミノっぽくて面白いですねえ。
２
１ の順でマスを決定させるのって、上下を入れ換えてもパターン数同じじゃないか。
さらには、横に１２と並べるのとも同じじゃないか。ぐはぁ、無駄だったぁ！
発展させて考えると、短絡解探索の全検索は、マスの決定順序をどう変えても
パターン数は変わらないということになるな。途中チェックでなるべく速くダメパターンを消せるか？
のほうが重要だということになる。ダメパターンのチェックがしやすいような順番ならＯＫ
ということにもなるけど、今のところ今の一列ごとに改行方法が一番早そうだし。
はいそうです。テキストだけ見るとちょっと驚くと思います。
でも、１～99の数字を使えるようにするための処置ですんで。
例えば、
+++12345+
+++++++++
+++++++++
となってるとすると、
+++12345+
++++234++
+++++3+++
と決まります。
順番に探索するより早く矛盾を導ける可能性があります。
右から左端へ順々に決めて改行していき、３の部分まで決めてこうなった場合。
┼─┼─┼─┼
│１ │２ │ │
┼┃┼┃┼─┼ 一度戻ってやり直すのですが、この場合、２の下にある分岐から
│┃│┗━┓│ 再度やり直すことになります。
┼┃┼─┼┃┼
│３ │
┼─┼
┼─┼─┼─┼ そうすると◎の所がこう変化してまた前進することになり
│１ │２ │ │ １と３の関係は変わらないので無駄な探索になります。
┼┃┼┃┼─┼
│┃│◎│
┼ ┼┃┼ ┼
│３ │
┼─┼
┼─┼─┼─┼ なので、探索時につけた番号を記憶しておき
│１ｆ│２ │ │ その番号のマスがでるまで何があろうと
┼┃┼┃┼─┼ ひたすらバックするというのがクイックバック方式です。
│ ｆ│┗━┓│
┼┃┼─┼┃┼
│３ｆ│
┼─┼
│１ｆ│２ │ │ ３の上のマスまで戻り、余計な探索を減らせることになります。
┼┃┼─┼─┼
│┗━ │ │
┼ ┼─┼─┼ ちょっとわかりにくい例図ですいません。
│３ｆ│
┼─┼
一回チェックするごとに500回ほどループが入り、非常に遅くなるので撤去。
変わりに 複数ありえるパターンの場合には最後のパターン以外は却下に
１ ■■■ 例えば>55にあったパターンなら、一番初めに調べる配置はこうで
□■■■
□□□□
１ □□□ 一番最後に調べる配置はこうなります。これを利用して
■■■□
■■■□
□■ 盤面に、この形が出るようなパターンはＮＧとしました。
□□ そうすれば上の場合なら一番最後のパターン以外はＮＧです。
□□ そして右上から左下へ伸びる場合も考慮し、このパターンもＮＧに
□■
このおかげで、>45のが８秒875にまで短縮しました。（ペン４の2.4Ｇhz）
なんだか目標の15*15の短絡チェックにだいぶ近づいてきた気がします。
助言サンクス。でも、ナンバーリンクの場合そういう類の配置のパターンが出てくる頻度は
かなり低いのであまり有効ではないかと。でも、ぬりかべならかなり効果のありそうな方法だ。
「最後のパターン以外はNG」なのを「最初のパターン以外はNG」に。これで少し短くなった。
そして、この最初パターン限定方式を追加したことにより、>53の遠回りパターンが
２ １
３ ■ に類似した状態にしか、ほとんどありえなくなったので
４ ５ 壁越しﾁｪｯｸは上下方向のみに。しかも上から調べれるのと下から調べるのは
同じだというのに気がついたので、上方向のみのチェックにして更に短縮。
これで>45が６秒625に。
その労力を短縮につぎ込んだ方が効率がいいだろうしなぁ、と思ってしまう。
目標は15*15の短絡なしチェックを１時間以内に、だから
そこまで完成したらプロジェクトX風に解説してみたいねｗ
あれからの進歩。上と左の先端の変な繋がりチェックを＿|のマス目のみにした。
右と下のみに進む繋がりは記憶しておいてすぐチェックできるように。
その他細かくIF文の数を減らしたりバグを取ったり。
これで>45が04.391に。>77の頃から見ると半分以下になったな。
それでも15*15は手に負えないよ。単純に考えるとマス目が10個増えると
2の10乗で1024倍時間が増える。約1000倍としたら20個で約1000000倍。
12*12から15*15はマスが111個増えるんだよね…
ttp://gamdev.org/up/img/1180.lzh 今、古いニコリひっくり返して入力してチェックしてるけど
一番時間がかかった面で３０分。あとは数分といった程度で確認終了できるようになった。
今回はロジックではなく、休憩のさせかたを変更。
これまでのは一回探索するごとにほんのちょっぴり休み（sleep(0)）を入れていたんだが
それを5000回に一回しっかり休ませる（sleep(1)）ようにしたら、劇的に速く＆CPU負荷が減った。
今日の成果と例の>45の履歴を確認してみる。
8/23 ２分１４秒
8/23 １分１６秒
8/29 ５１秒
9/04 ８秒875
9/05 ６秒625
9/06 ４秒391
9/08 ２秒046 ＊今回
なんつーか自分で言うのもなんだけどすげぇ。最初の遅さがもう何年も前のようだ。
ただ、5000回固定だと遅いCPUには高負荷になってしまうので、使う側で指定できるようにします。
それに関数呼び出しコストもばかにならないし。usleep 使うてのはどうでしょう。
これだけ速くなったら 15x15 もいけるんでないの?
手元のソルバでも 45 のが 5 秒くらいですが、
15x15 が(ものによっては)数十分から一時間くらいで解けますよ。
15*15が最大３０分、通常数分です。
ちなみにCPU100%でぶん回すとさらに時間が短くなります。
usleepは帰ってから調べてみます。サンクス。
...............
.......1.......
.....2...3.....
...4...5...6...
.....7...8.....
.......7.......
.....6...2.....
.9.5.......3.8.
.....b...a.....
.......9.......
.....c...d.....
...a...b...c...
.....1...d.....
.......4.......
...............
470519069ノード、607.86秒 @ P4 2.8GHz でした。
それでもめげずにぅぉりゃっ！更に高速化＆便利に！
ttp://www.interq.or.jp/moonstone/person/NLsolv05.lzh テキスト読込機能を付けました。コピー＆ペーストで>87のような面が読み込めます。
オプション機能を付けました。探索何回ごとに表示させるか指定できます。
コ・マ・オ・ク・リ・モ・デ・キ・マ・ス・ヨ
シャア専用モードをつけましたw 通常の約３倍で探索します。CPUの発熱に注意。
↓の本にも載っているみたいだけど、これはどうなん？
ttp://www.pro.or.jp/~fuji/computerbooks/algorithm/nanopico.bit.html 発売が十年前か。手に入れるのは厳しいな･･･
後はその場所に総当りで数字を入れて、短絡無しの唯一解が出る面だけを
抽出するソフトはどうだろうか？と。でも、しばらくしてから自己否定。
そんなソフトを作ったら、ソフトを持ってる人が優遇されすぎる。
配置が綺麗なだけの味気ない面ばかりが増えそうだ。
っていうより、それはナンバーリンクの熱的な死ではないか？
まぁ考えすぎっちゃ考えすぎだってのは判ってるけどね。
どっちにしろ今は作るのは止めときます。
半分は自分のため、もう半分はニコリのために作ったんだから
必要なのは短絡解の判定ができるソルバー機能のみでよし。
ぅぉ、チェックしてみます。
１ ２
■→ ←■
３↓ ↓４
５↑ ↑６
■→ ←■
７ ８
こういう風に四隅二方向から、１２３４５６７８…の順で１つずつサーチ
したらどうだろう？
もしくは１４８５の四隅一方向からとか、１８の二方向はさみうちとか。
1+++++++++
++++++++++
+++4++++++
++++++++++
++++++++++
++++1+++++
++++++++++
++++++++++
+24+++++++
+++++32++3
設置数最少設定。しかも短絡なし。でも目で解けそうだ。
>94 自分も色々考えてみたけど、古い決定部分がいつまでも表に出ていると効率悪いみたい。
ぐるーっと回って、などのやり方は、１の次の段で失敗がわかった時に
同じように、またぐるーっと手を戻さないといけないし。
なるべく表面積を少なくする＝仮決定部分がすぐ埋まる＝失敗した時にすぐ判明、ってことかな？
「このまま進めたら破綻」ってのを極力早期に発見できないかな、と。
＜多方向から探索
...............
.....a...2.....
..b....7....3..
......8........
...34.....5....
........b......
.a...........1.
...9.......5...
.c...........6.
......4........
....8.....76...
........1......
..9....2....c..
.....d...d.....
...............
30.58 sec.
>96
うん、俺もいかにして「このまま進めたら破綻」を速めにできるか考えたけど
ばらさないでまとめた方が良いみたいなんだよね。
例えば四隅の簡易版として上下２分割で上下交互に進めていくとした場合
下で破綻が出たら上もついでに戻らないといけないようになるし。
だったら探索をまとめて中央付近を速く埋めた方が破綻が少なくてすむ。
線の重要度は真ん中が高い。真ん中が決まらんと相手番号が未定のケースが増えるし。
+++++++++++++++
++++++++++++25+
++++++++++++3++
+++4+++++++1+++
++++7++++++++++
+++++++++++++++
+++++++++++++++
2++++++++++++++
+++6+++++++++4+
+++++++++++++++
++++++++++++++6
+++++++++++5+++
++++++++++37+++
++++++1++++++++
+++++++++++++++
ttp://www.interq.or.jp/moonstone/person/numlink/index.html ---------------
-3-------------
--7---------5--
------------4--
-------2-------
-------8-----1-
-------6-----2-
---------------
---------------
---------------
-----4---------
---1-----3-5---
--------67-----
--------8------
---------------
8.15 sec.
探索の順序を上下左右に振るのはよくないかもしれないけど、
初めに盤面を見てやりやすそうな方向を決めるというのは有効。
上下左右を反転させるだけで10倍くらい計算量が変わることも。
---------------
-3-------------
--7---------5--
------------4--
---------------
------6------1-
-------------2-
---------------
---------------
---------------
-----4---------
---1-----3-5---
--------27-----
--------6------
---------------
9.55 sec.
昔VBで数独のソルバー作ったけど、あと一歩で完成ってとこでやめちゃったな。
このｽﾚで、いろんな人で同じパズルのｿﾙﾊﾞｰ作って、
処理の早さを競うのも楽しそうだ。
とりあえず、ナンバーリンクってどんなんだったか思い出さないと…。
まずは人が少ないのをなんとかしないとなぁ。
まだﾊﾟｽﾞﾙ板の知名度自体低いだろうし（俺おととい知った）、
ム板・ゲ製作技術でウザがられない程度に宣伝するしか。
ちなみにム板で「ﾊﾟｽﾞﾙ」で検索ヒットするスレなし。
ゲ製作技術で検索したら
思考型パズルでも作ってみる(21)
ttp://pc5.2ch.net/test/read.cgi/gamedev/1088756216/ 最終書き込みが7/8で廃墟。
でもう一個が
【作る】倉庫番パズルの自動プログラム 【解く】
ttp://pc5.2ch.net/test/read.cgi/gamedev/1088809456/ 最終…って、こっちが先だったんですか、進可さん。
お絵かきロジックあたりが簡単そうかな？
数独も、解くために、とある思考が必要…でない問題解くまでなら簡単なんだけど。
ナンリンはナンリンで、平行してればいいだろうし。
人が増えてきたら、ナンリンだけ独立スレたてればよろし。
あいあい、そっちでやってる最中にパズル板ができたんで移りますた。
>109-110
いや別にナンリンにこだわらなくても。ナンリンは自分では一段落したし。
個々で思い思いに違うパズルで作ったりアイデア出したりでいいんじゃないかな？
でもこれはあまりパズルを解くのに向いてない感じ。
遺伝子式は「探しつくせない組み合わせの中から一番効果の高いパターンを見つける」だけど
パズルの場合「全ての組み合わせの中から正しいパターンを見つける」だし。
特に、「全パターン中、正しい答えが一つだけなのを確認する」場合に向いてない。
遺伝子式のやり方に向いているのは、ニコリで言うと「スケルトンコンテスト」が最適だろうな。
GAによるスケルトンコンテストだったりする
応募はしなくても、人間のトップを破れるのか試してみたい
もちろん、作っても応募しないけど。
ところで、速さを競うとしたら同じ言語で作らないと不公平だよな。
俺は多分、C（コンソール）でアルゴリズム固めてから、
本気で公開するならC（windows）にするだろうな。
まあ、それは本当に速さを競うことになったとき考えればいいか。
表示された盤面を見て( д ) ﾟ ﾟってことになるのか、
それともスケコン上位陣はやっぱり凄いという結論が出るのか。
何か試行錯誤の回数をカウントして、それを指標にするのがいいと思う
落として全部自分のところで実行すればOK。
人が多いほど、いろんな環境での結果が見れて良い。
嘘報告しないでね。
( д ) ﾟ ﾟ
着手する元気がないんだよねー…。
はい、そういうことです。見た目が一見違うだけでまんまナンバーリンクなもので。
速度勝負は
・GCCかG++でコンパイルできること。
・標準入出力のみ使うこと。
って条件でソースうｐするようにすればいいんじゃないかな？
GCCならどんなプラットフォームにもあるし、profileでCPU時間確認もできるし。
試行錯誤カウントはカウントする場所でもめそうな気がする。
…とはいえ、どれかに統一する必要があるなら、Cがいいだろうな。
使える人は多いだろうし、フリーでコンパイラあるし。
俺も個人的にはCがいい。
ソースうｐじゃなくてexeでいいでしょ。
速さを競ってるんだから、ソース見られちゃまずいわけで。
どうせ人少なそうだし、言語とか実行環境に制限を加えなくてもいいかと。
実行速度だけじゃなくて、行数とか開発速度とか、そういう点も見てみたい。
速度はCが有利だし、
行数と開発速度ならVBが有利かな。
言語の壁を越えて、プログラムを競うってのは難しいね。
速度なんか競わなくていい
競うのも、結局人が増えなきゃ無理な話か。
もともとの趣向どおり、好きなものを好きなように作って、
偶然同じものを同じ言語で作ってる人がいて、
両者が競ってみようか、って言ったらそのときやればいいのかな。
同じCでもコンパイラで変わっちゃうし。
たかがパズルで公開の弊害どうこうってのもどうかと。
どうせすでにWEBにけっこう存在するんだし。
勝負するなら締切日をきめてそれにあわせてうpすればいい。
今日Cマガ買って来ちゃったよ。
俺パズラー出身だからアルコネと呼んでいるのだが、ナンリンてあれか。
Cマガのは、線が通らないところがあってもよい、ってところがアルコネと違う。
遺伝的～は確かにスケコンに向いてそうとは思うが、
どの状態とどの状態が、隣接する要素なのかとかしっかり考えないといけないな。
なんかスケコンでいつの間にかどんどん話が進んでるぞ。
ところでよ、スケコンで発表すべき一番重要なものは『答え』ではないのか？
最適解(近似解)を一つ示せばそれでいいし。
２．いかに早く出せるか。
だな。あとは保守性とかもあるけど。
とりあえずスケコンやるなら、とにかく１だけ考えて作ればいいんでない？
それだけで大変そうだし。
GAとかIAとかやると大変だし、ランダムサーチ→山登りくらいで十分かな、と思う。
でもせっかくだからIAでやれば勉強にはなるんだよなぁ。
大きな四角形の中に無駄なく配置する問題のGA的解決
たしか、LSIのフロアープランに使うんだったかな
遺伝子としては、配置する順番だけを情報として持っていて、
ある程度賢い配置アルゴリズムが、与えられた四角を
現状の配置に対して、できるだけ下へ、できるだけ左へ、というような
基本方針で一意に配置場所が決まる方法で配置する
で、遺伝子の交配は順序情報をスワップするんだったか
切り取って後ろに付けるんだったか、そんな感じの単純なの
本来はここらへんが一番肝なんだろうけど
それと似たアプローチでスケコンが解けないかなと構想中
っていうか、とりあえず解いて答えを出力してみせるところまでは
すぐに作れる筈
ttp://http://www.geocities.co.jp/Berkeley-Labo/6317/seqsqr.htm これの隙間を埋めるのも面白そうだ。
スケコンの性質上、「子供を作る」ということができない。まったく思いつかない。
ちょっとじっくり考えて見たけど、
しらみつぶし的なアルゴリズムしか思いつかなかった。
それでもいいから作ってみようかな…。
マスという細胞壁の中に、単語が入ってきてランダムに今までの単語と繋がったり
字数/ポイントで効率が低いのが出て行ったりするのを想像した。
で、中身が詰まっててポイントの高いのが分裂したり
中身が詰まってる割りにポイントの低いのが死んだりしてるような
原始の海みたいな光景を想像した。
いや、いけるんじゃない？
一つの盤面から他の盤面に過渡できるように、
その中間に生じる不正な盤面を許容すれば。
たとえば、盤面の表現方法として、各ワードについての
「何行目／何列目の何マス目から入っているか（または不使用か）」
という情報を持つことで盤面を表現したとして、
混血の仕方を、各ワードの位置情報を両親のそれぞれどちらか一方から引継ぐ
ことによって実現したとすると、
その結果生じる子は多くの場合適正な盤面とはならないわけだけど、
それもアリ、ただしその不正さに応じて評価関数の減点対象、ということにすれば。
多分、漏れが聞きかじってる遺伝的アルゴリズムは、その
「スワップする」ってやつだと思うんだよね。
で、がそのスワップではないかと。
うーん、いまいちイメージが湧かない、というよりは
先が見えない。
それで交配すると、ほとんどの子は親より低い点数（不当なための減点）になり、
あっという間に淘汰されてしまわないだろうか。
仮に評価の高い子ができたところで、
最終的にはそれを不正じゃない状態にしなきゃならないわけだが、
そうやって交配してできた状態を、正当な状態にもっていけるもんだろうか。
もっていけたとしても、持っていく間に盤面の状態はかなり変わってしまい、
評価が下がらないだろうか。
「だろうか」ばっかりで、やってみなきゃわからないけどね。
お絵かきロジックは多重背理が必要なのもあるのでその点留意。
ま、確定しなきゃ再帰処理かけりゃいいだけなんだけども。
多色問題になると難度が格段にうｐするようなので、手応えも上がるかも。
人間のトップは十分に破る余地があると聞いた記憶がある。
むしろこのスレでソースもアルゴリズムも公開しまくって情報交換しつつ
切磋琢磨する方がいいんじゃないか？
スケコンは、全体が一繋がりでないといけない。
つまり、登場する単語は必ず他の単語と交わることになる。
で、単語と単語は必ず縦と横に一点で交わる。つまり、
「交わる単語はどれか」
「自分の何文字目が交わるか」
「相手の何文字目と交わるか」
この３つが判明すれば、二単語の位置関係は一意に定まるわけだ。
（厳密には縦横交換した二通りになるけども）
（交わる単語の番号）（自分の何文字目か）（相手の何文字目か）
のセットを１単位として、単語の数だけ並べてみてはどうだろ。
登場しない単語については、（交わる単語の番号）を０にでもすればいい。
この遺伝子情報をもとにスケルトンを組み立てれば、全ての単語の位置
関係が、一意に定まることになる。
この表現ならば交叉や突然変異も、比較的簡単に行えるはず。
このままじゃ致死遺伝子（文字同士の衝突など）の発生率は高いけどね。
そこをどう防いでいくかは今後の課題ってことで。
それ良案っぽいね。
どうせ、各ワードに対して、それと交われるワード（及び位置）
なんて、百とかせいぜい二百くらいしか無いんだから、
それをあらかじめ全部調べて付番しておくこともできるかと。
変な物ばかりできないためには、の案を取り入れて
「交わっているワード同士は行動をともにする傾向をもつ」
とかにすればいいのかも。
つまり遺伝子は交点中心に考える、ということか。うまい案だな。
の交差位置情報は「交差可能な文字のうち何番目」の方が死ににくくなっていいかも。
「単語番号１：単語番号２：単語番号1の、2と交差可能な文字のうちの何番目か：単語番号2の、1と交差可能な文字のうちの何番目か：」
を全通りリストにして並べて、その交差があるかないかの01をランダムに決めてしまえばよいのか。
これなら盤面も(縦横の入れ替えはあるけど)遺伝子で一意に決まるのでは？
スケコンは40単語だし、実際の可能な交差を考えれば、
問題によってはカナなので交差が少なければ1000通りもないかも。
適正な盤面とは限らないけど、一意に決まることは確かだよね。
盤面の評価（広さとか、正当性とか）に手間がかかりそう、というのが
交点中心のアプローチの難点、なのかなあ？
いや、意外とそんなに手間はかからない。多分。
詳細はまたのちほど。
イツテヨシ オマエモナ キモイヨー
交点に付番してその交点で交わるか否かでコーディングすると
1. [イ]ツテヨシ と キモ[イ]ヨー で
0 : 交差しない
1 : 交差する （以下同様）
2. イッテ[ヨ]シ と キモイ[ヨ]ー で…
3. オマエ[モ]ナ と キ[モ]イヨー で…
この３ビットのオンオフになるが、このうち 1 ビット目 と 2 ビット目が
同時にオンになると（110, 111）、当然ながら致死遺伝子となってしまう。
1. イッテヨシ と キモイヨー は
0 : 交差しない
1 : [イ]ツテヨシ と キモ[イ]ヨー で 交差
2 : イッテ[ヨ]シ と キモイ[ヨ]ー で 交差
2. オマエモナ と キモイヨー は
0 : 交差しない
1 : オマエ[モ]ナ と キ[モ]イヨー で 交差
「21」だったら下のようになるわけだな。
オ イ
マ ツ
エ テ
キモイ.ヨー
ナ シ
致死にしないで、どちらか一方だけが発現するように両方のタイプを計算させればよいのではなかろうか。
みたいにすれば、片方だけを発現させるような処理が不要になる。
だと
101 011
を交叉させるときに
1|01 0|11
で一点交叉させると
110 001
明らかな致死遺伝子が発生する。
の方法だったら
10 21
1|0 2|1
11 20
明らかな致死遺伝子の発生は抑制できるし、交差位置の交換もスムーズに行える。
キ
イチゴ
ヨウキ
ウ
みたいに２×２のカタマリが出来るのはセーフだったっけ？
ge_num[] = {3, 2}
i = rand() % 2;
gene[i] = rand() % ge_num[i];
みたいにすればいいのかな？
誤）,153
正）,154
問題ないはず。過去に何度か見た覚えがあるし、ルールにも引っかかってない。
ＯＫなのだけど、それを考慮に入れ始めると盤面の不正性の検討が
ややこしくなる気がするんだよね。
だから、「隣り同士の行／列に言葉が入る時は、必ずズレて入るようにする」
というつもりでやった方がいいのかもしれないって漏れは思う。
統一的に簡単な方法でチェックできる筈だけど
作者側が解答として想定した盤面(数字のみ)を入力して、
その盤面がルール2を満たしているかどうかを調べる、みたいなの。
このスレの優秀な頭脳さんにぜひお願いしたいです。
作成途中にリアルタイムでチェックしたいとか、そういうのかな
やっぱ漏れだけじゃなかったのね、そういうの欲しかったの。
つー訳でExcelに入力してチェックするためのマクロ、既に作ってあります。
左上から１文字ずつ見て回るという芸のないマクロですが、
そんなんでよかったらご提供申し上げます。
ファイルそのままどこかにうpするか、マクロだけテキストでここに書き込むか、
そういう経験のない文系の漏れなので、ご意見をいただきたいと。
あ、そーそー。
実は、Mac版Excelでしか動作確認してないけど、大丈夫だよね、きっと。
遺伝子表現はってことでOK？
そのままだと、２単語の交差パターンが多ければ多いほど「交差なし」が
選択される可能性が下がってしまうので、確率の調整は必要かも。
たとえば、必ず半分の確率で「交差なし」を選択させるとか。
gene[i] = (rand() % 2 == 1)? 0 : rand() % (ge_num[i] - 1) + 1
そうか、㌧クス。
盤面に単語を全部埋めたあとにも、再度妥当性のチェックが必要になるな。
（２×２のブロックが不可なら、単語一つ埋めるたびのチェックだけで十分なはず）
ファイルを圧縮して流れにくいとこにうｐ、ってのが無難じゃないかと。
もしくはどっか無料のレン鯖借りるとか。
誰かが拾ってgeocitiesあたりにサイトを立てて保管すればいい
㌧クス。
GAはここで初めて知ったもんで(という言葉は言い訳にもならんが)その辺の考慮ができんかったとです。
>>All
これもゲームといえばゲームだしアプロダはこれ使っていいんじゃない？
ttp://http://gamdev.org/up/ そこいいね。
そんなに頻繁にうｐがあるわけじゃないだろうし、
ちょうどよさそう。
「解く」までのチェックはいらないんですの。
波及効果作りでいちばんきついのが、ルール2の矛盾がないかどうか
盤面見渡して調べる作業なんですが、要はそれさえできればじゅうぶん、ってことで。
ひとりにしてくれの余計な数字埋めプログラムがありがたいのと同じような感じ？
ttp://http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/readres.cgi?bo=lounge&vi=1064150088&res=236 こんなんでどう？簡略化しまくったけど。
違反する数字をマスに書いた瞬間に
音が鳴る、みたいなのがいいのかな
波及効果ってコンピュータには扱いやすそう。分断禁とか無いし。
数字のチェックだけなら簡単なのだけど。
どうかな。
へやわけの部屋に比べて確かに自由度が高いから、
人の入力操作は若干面倒になるだろうけど、
コンピュータの方としては大差ないんじゃないかな。
部屋の壁を何回またぐか、とか数える必要もないし。
その「人間側が面倒臭い」ってことが言いたいんだと思うけど…
人が扱うのに適した上手いテキストデータの形式が思い浮かばない
チェックするだけなら数字だけですむけど、清書用に使うためには部屋の情報も欲しいしね
そのようなエディタができたら、テキストデータの形式とかは不要になるんじゃない？
エディタ上で入力して、データはそのエディタの形式で持っていればいいんだから。
とりあえず、うpしてみました。
ttp://gamdev.org/up/img/1481.lzh 一応、職場のWinで動作確認＆ウィルスチェックは済ませてあります。
使える人は使ってみてやってください。
まぁそうなんですけどね
出来ることならあまりエディタに依存させたくないのよ
例えば、各マスに左と上の壁の有無と中の数字の情報を持たせるとか
ある程度のチェック機能とかつけるんだったら、たとえば
各ブロックに「ブロック番号」みたいなものを与えて、各マスに
自分のブロックの番号を持たせるとかの方が扱いやすそうかな？
問題を作成・表示するためだけのツールだったら
そういう形の方が簡単になるだろうけどね。
入出力用のテキストデータには要らない
さっそく使ってみました。便利！
まことに感謝感激でございます。
あーテキストファイルで入出力するの？ GUIじゃなくて？
なんかこう、盤面をマウスとかで操作して入力するようなものを想像してた。
GUIで操作して、結果はテキストに吐き出す感じ
データの規格さえ合わせれば、そのデータを他のツールに
読ませたり、テキスト処理で加工したりできる
いや、たぶん言いたいことは分かるんだけど。
でもそのテキストに出力ってのは、もうそのままニコリに郵送できるみたいな
整形された盤面を出力すればいいんじゃないかな？
データの規格を合わせればって話は、内部で扱うデータ形式を
そのまま書き出したようなものでもいいって思うし。
windowsとmacとunixと、どれが一番優れてるかみたいな話
上段は部屋の分割。同じ文字を使っていても、縦横で接していない場合は違う部屋。
下段は数字の位置。 '-' は白マス。
上段と下段の間は１行以上あける。
チェックツールの入力として使う場合には数字をすべて入れた形で入力すればよいかと。
例）
abaa
bbaa
aabb
aabb
----
--2-
---4
2---
やっぱその形に落ち着くわな
テキスト打ち込むときに四色問題としても楽しめる特典付き
新しく解答支援ツールページみつけたので紹介。たぶん初出だと思う。
ttp://homepage2.nifty.com/lonelyperzoo/ ナンプレ、ぬりかべ、美術館、ましゅ など。
>169 を読んで納得。確かにチェックが一番しんどそうだし
入力は、数字打ってリターン、数字打ってリターンだけにすれば単純作業の分、早いよな。
数字も大体１～６程度だし。
データー形式としては188がかなりいいと思う。
ただ、パソで処理するなら違う部屋は必ず違う英字にした方がいい。
入力はそれでよしとして、内部で清書するってパターンもありだけど。
大文字を使えばいい。なんておもったんだけど、
実際数えてみたら、１０×１０でも部屋数は26を越えて、
ジャイアントでは100オーバーするのでダメ。
この分だとスーパージャイアントの部屋数は256を軽く越えそうですよ。
波及効果の部屋数は多いですね。ちょっと意外。
数字の10以上対策を考えていなかったことに気がつきました。
１０以上の数字に対してはアルファベットで入力させるという案を出しておきます。
あまりないとおもわれるので、対応だけできればいいと思うんだけど、
これはどこかで上限を決めないといけない話。
個人的には大文字、小文字の使い分けはしたくないのですが、使い分けて61まで対応。
35もあれば足りるとは思っているけど、一応。
例）
a=10,b=11,...,ｚ=35,A=36,B=37,...,Z=61
どうしても色塗り分けが面倒なら、10進でスペース区切りにすれば上限など気にする必要なし。
もともとテキスト形式が欲しいのって単に保存しておくのに便利だからでしょ。
入力は使いやすいGUIを作って、出力でいくつかの形式を選べるようにしておけばいいかと。
高くなくていいけどね
プログラムでやるなら、ぬりわけのアルゴリズムが気になる。
適当にやっても多くて６色ぐらいで収まりそうだけど、
確実にN色以下に塗り分ける簡単な仕組みってあるかな？
Nは４じゃなくて５でも６でもいいんだけど。
喜んで貰えてなによりです。
そして、もし感謝していただけるなら、
漏れの分のノルマ、持ってきやがれぇ( ・∀・)つ●ﾄﾞｿﾞｰ
遅ればせながら使わせていただきました。
作りながらの途中確認がとてもラクだった。
ありがとう。
四色問題？
そんなにアルゴリズムに凝らなくても大丈夫だと思うよ。
みんながスケコンの遺伝子について話あうさなか、
（と言っても、話は既に波及効果に移っているようですが）
遺伝子情報なんて考えず、しらみつぶし法で
とりあえず１つの解にたどり着くのができました。
２つめ以降の解を探しにいくところは作ってる最中だけど、
既に仕様は頭の中で固まってます。
全ての解を巡回してくれるはず。
問題はどんだけ時間かかるか…。
ttp://news16.2ch.net/test/read.cgi/scienceplus/1097156523/l50 ttp://http://www.slis.tsukuba.ac.jp/school/lecture/sotsuron/H13/13000090.pdf とりあえず貼ってみる
壁を作るのやらを統合的にまとめられないかなぁ？
あと、スケコンやってみようとしたけど、まだ俺には難しすぎるようだ。
まだまだ実装しなきゃならんことがいっぱい。
でも着実に完成に近づきつつあります。
やはり全ての解を探索するのは時間がかかりすぎるようですね。
まぁ、とりあえず完成してから考えよう。
40の候補から組むべき26個選ぶだけで、2.3E10ある
全ての部屋の中から隣接する部屋の数が5以下の部屋を全て取り除く。
この部屋は回りの部屋全てが違う色だったとしても残りの色で塗れば良い
「その部屋を取り除いた状態で」隣接する部屋の数が5以下の部屋を全て取り除く。
このようにすれば全ての部屋が無くなるので取り除いたのと逆の順に塗っていけば良い
「途中で６以上の部屋ばかりになってしまい、操作が続けられなくなる」という
状況が生じないというのは…、漏れはすぐには分からないんだけど、そうなん？
これは正6角形を敷き詰めた状態（もしくはレンガを積み上げた状態）だが、
6を維持するためには無限平面にする必要がある。
波及効果の問題は当然有限平面なので淵に（とは限らないが）5以下の部屋は必ず発生する
WindowsXPは行間が空いて、目に優しいなあ！
＆＃１７９
＆＃１８
を小文字にしたもの。ＩＥの表示に悪さをし、行間を一行空けさせる。
ttp://gorogoro.cis.ibaraki.ac.jp/web/html/sotsuron.html の平成六年度参照
遺伝的アルゴリズム(北野宏明)という本にも軽く触れられていて、
(上の論文と関係あるのか知らん)
その中ではコンテストの第一位よりもさらに良い解が得られたと書かれています。
ただしのパターンは現れないので、もうちょっと改良が必要。
で、実行してみたわけですが、全然進まない。
およそ全体の4000分の1に相当する処理が、10分たっても終わらない。
仮に10分で終わったところで、１ヶ月流さないと終わらないことに…。
とりあえずこれを基盤として、ここから「点数が高くならなそうなパターン」の
枝切りとか、GAへの応用とかを考えてみます。
…と書き込んでいたら、既にやった人がいるんですね。
いったん凍結して他のでも作ろうかな。
形自由な部屋が全てＮ個以上の他の部屋に接しているとして
そのＮの最大値は幾つなのだろう？
３つまでは簡単にできるんだが
四色問題の結果を定理として認めるなら、三つが最大
1111
2342
2432
1111
私もで納得できているわけではないけど、
（６以上を実現するためにはハチノスにならんといけない理由がわからん、でもそれ以外が無理っぽい気はする）
211 を否定するためには有限平面で６の例を実現しないといけないわけで。
でも、５はいけそうだ。がんばる。
そのときにオイラーの定理 v - e + f = 2 と極大平面グラフで 2e = 3f から
e <= 3v - 6
平均次数 d = 2e / v <= 6
より次数 5 の頂点が存在する
11111111
23322442
21443312
21334412
24422332
11111111
ここまでくると４色塗りわけも難しくなってきて楽しいかも。
最小部屋数、最小面積が気になってきたけど、どんなプログラムを組めばよいかわからん。
上記のは結構いい線いってると思うんだけど。
（ Д ）
1111111
1433223
1424413
2423313
2411443
2222222
接する国の数が全て6以上の地図が有限平面では不可能な証明は
正多面体が5種類しかない事の証明と同じで良い筈なのだが。
ところで、ここの書き込みを参考に自分でナンバーリンクソルバーを作ってみたのだが、
の問題の短絡チェックは3秒で終わったぞ。
で、G16の2番を調べたら9分で終わったので4番を調べたのだが・・・
丸2日経っても終わらなかったorz
なるほど、わかってきた。オイラーの多面体定理より
すべての部屋が接する部屋の数は２以上で、
部屋数 >= 12 / (6 - すべての部屋が接する部屋の数)
が求まるのか。
確かに５の最小部屋数は１２で、６は不可能だ。
４の最小部屋数は６で、正６面体を平面に展開したものか。
220は8部屋……
正六面体をっていうことは、こういうことかね。
11111
12231
13131
13221
11111
でもこれは三色で塗り分け可能だよ。
11113
14223
24113
22223
（
ttp://images.google.com/images?q=10%E9%9D%A2%E3%82%B5%E3%82%A4%E3%82%B3%E3%83%AD） で、それを八面にしたのがで、六面にしたのがと。
３色でいけるよ！
11113
13223
23113
22223
１０面サイコロの形は６ｎ面の場合、３色、それ以外は４色になるのかな？
正多面体についてまとめてみた。
正４面体：４色
正６面体：３色
正８面体：２色
正１２面体：４色
正２０面体：３色
正２０面体が３色であることがすぐにわからなかった自分は大馬鹿だと思いました。
あーうん、漏れもそのあと考えて気がついたんだけど、話題がそれてるって思って。
(2n)面サイコロについてもその通りって思うよ。
リアルタイムでエラーチェックができる。
ttp://gr.vxx.jp/haky.html 個人サイトだけど。
いいなぁ、こんなの作りたいなぁ。おみくじﾜﾛﾀ。
できれば人間っぽく解いていくようなの作ってみたい。
法則なんかを自分で見つけて上達していくようなAIがあればいいけど
さすがにそこまでは難しすぎるよなぁ。
そこまでは勝手に解いてくれる、とかにすると作るのが楽になりそう
VB6はマイナーかもしれないけど、
VB6持っててEXEは不安であればソースからどうぞ。
☆ビジュアル美術館β
VisualBasic6.0用ソースパック(使用した画像も同梱)
ttp://nun.nu/fhdic.fbox.info/VisualBijutsuSrc.lzh WindowsEXE実行ファイル
ttp://nun.nu/fhdic.fbox.info/VisualBijutsuEXE.lzh よさげですね。
点対象に配置とか、漏れは（へやわけで）やろうと思って投げたけど、
やっぱあると便利ですね。
ところで、三つあるモードは統合できるのでは？
当初はモード統合していましたが、ミスで勝手に盤面が崩れていくのが
ちょっと(Undoすればいいのだけど)使いにくいなぁと思い、普段作る
順番どおりにやってみました。今は○を置くと上下左右に×を打つ機能
しかありませんが、今後は中級問題まではサクサク作れるぐらいの
問題を解くプログラム(理詰め型)を搭載しようと思っています。
もっと便利なものをと考えてもなかなか案がでてこないもので、、、
初級手筋(単純発生、単純否定、孤立、救出)と
中級手筋(斜めとび)を搭載しています。
慣れれば美術館を3分以内で作れます。
ちなみに私は運がよければ90秒で作れます。
☆ビジュアル美術館
VisualBasic6.0用ソースパック(使用した画像も同梱)
ttp://nun.nu/fhdic.fbox.info/VisualBijutsuSrc.lzh WindowsEXE実行ファイル(高速化版)
ttp://nun.nu/fhdic.fbox.info/VisualBijutsuEXE.lzh WindowsEXE実行ファイル(デバッグ)
ttp://nun.nu/fhdic.fbox.info/VisualBijutsuSafe.lzh 現在、私が使う上ではエラーは発生していませんが
エラーが発生するようでしたらデバッグで同じ作業をし
そのエラー内容と状況を伝えていただけると幸いです。
・盤面の管理方法がずさんだった
・盤面解析が異様に低速
・数字の点対称表現がなっていない
などなど。
現在が何モードかわからないのはちと辛いね。
"解き味の良い"美術館って具体的にいうとどういう物なんでしょう。
例えば、「連鎖が出る」とか「ある程度光が伸びる(4つぐらい)」とか
そんなもんなんでしょうかねぇ。
自動生成プログラムを作って出来た盤面を180度逆向きにして解いてみれば良いじゃないか。
完全な問題として検出された盤面に短絡解が発見されたら短絡チェックのミス。
いつもお世話になっているﾅﾝﾘﾝｿﾙﾊﾞｰ、
15x15の趣向作を入力したら瞬殺されました＿|￣|○
0分0秒032ですって。
すげー
短絡解発見時に答えが表示されるとして、
その答えが違う数字を結んだり途中断線があったりしたらバグありってこと？
元の盤面で短絡解になり得るパターンを枝刈りで見落とした事になる。
このチェック方法はナンバーリンクの解答図として有り得ない解を出さなくなった上で
枝刈りが正常に行われているかのチェックに使える。。。かも。
高速化を考えると結構無茶な枝刈りをやらざるを得なくなるので
短絡解の見落としが無いかチェックする方法は結構重要になってくる。
短絡解のある盤面を片っ端から探して突っ込むだけでは限界があるんで。
同じ短絡あり面で８通りの短絡チェックができるな。
そしてどれか一つでも短絡無しと判断すれば
そのチェックはどこかで見落としがある、という訳か。
ずいぶん昔にやってみたんだけど せいぜい平均賞どまりだった。
一方、語彙制限付き しりとりにGAつかったら きれいにのって
あっさり 最適解に到達。
試行ごとに収束する解が違っておもしろかった。
GAするときは問題解析を結構がんばらないときれいに収まらない印象。
昔書いたプログラムをちょっと弄って101号のを解かせてみたのだが
平均6918、トップは7737なのに最高6817までしか出ない・・・
面の色のデータベースはどう定義するのがエッセンシャルでしょうか？
おそらく面(0-5)xX(0-2)xY(0-2)の３次元配列になると思います。
面の中の座標軸をどう定義すると数学的にきれいなんでしょう？
回し方を返してくれるというものにはしたくないと思います。
そういうものはたくさんあるんで。
今回の目標は「一般解を導き出すアルゴリズム」です。
メタ・ソルバーというのか、ソルバー・メーカーというのか、
とりあえず「ルール」を入力として、「ソルバー」を出力するというのが目標です。
コンピュータにルービックキューブを「揃えて」もらうのではなくて、
ルービックキューブの揃え方を教えてもらう*のです。
ということは出力として出てくるものはアルゴリズムです。
プログラムのような、「ここが赤で反対が青だったら右を回す」という
条件分岐を含む記述になります。これを綺麗に出すために面の定義を綺麗にしておきたいのです。
とりあえず展開図で面番号を
４
３５０２
１
と定義してこの展開図の左右をx軸-+，
上下をy軸-+とした３次元配列cube[面][X][Y]として
動くルービックキューブを作ってみました。
xy軸がすごく納得行かず不満です。
(*)一般解とはいうものの、３＾３ルービックキューブを渡して
Optimal Solverが出てくるのを待つ、というのは難しすぎるので、
まずは部分的なゴールから。１面完成なんかがいいでしょう。
Optimalでなくてもいいです。
6面完成までの手順の数って、10いくつとか、そんなんだったような
それを割り出すべし
入力は画面、出力はキー操作と言うことで。
ttp://http://robots.engadget.com/entry/2116781701378779/ やっぱりmindstormか…
エミュでできるやつを探してたのに。すごいなこれ。解けるんだろうか？
mindstorm でコントローラを操作しようとしてるのね。
賢いというべきか、頭悪いというべきか・・・
000400000000000000030000000000
000000000000000000000005000000
000000000100000000000000000000
000003000000000006000007000000
000000000000000000000000000000
000000000000000000000800000000
000000000800000009000000000000
000007000000000000000000000000
000000000000000000000000000000
001000000400000000001100000000
000000000000000010000000000000
000200000000000000000006000000
010000110000000000000000000000
050000000000000000000000090002
進可さんのプログラムでこれ解いたらPen4-2GHzで
109億7517万3926ステップ、2時間1分48秒319かかったぞ。
とある表出11個対称形の問題をプログラムで解きにくいように
少し改造したらこの問題になって、試しに全検索したら2時間かかった。
・・・多分逆から解けば10分切るけど
回転や反転で面探索を短くする方法も考えたけど、なんかそれは
「反転させたら負けかなっと思っている」ような気がしてやらなかった。
ちなみに、２ｃｈに面をうｐする場合は、問題を入力してから
上のバーにあるファイル＞テキストで表示させると
↓のような感じで出てきます。ここからテキストからの入力もできるんで
２ｃｈでのやりとりは、こっちのが使いやすいです。
+++++++++++++++
+4+++++++3+++++
+++++++++++5+++
++++1++++++++++
++3+++++6++7+++
+++++++++++++++
++++++++++8++++
++++8+++9++++++
++7++++++++++++
+++++++++++++++
+a++4+++++b++++
++++++++a++++++
+2+++++++++6+++
1++b+++++++++++
5+++++++++++9+2
検証ご苦労様でした。
5+++++++++++9+2
1++b+++++++++++
+2+++++++++6+++
++++++++a++++++
+a++4+++++b++++
+++++++++++++++
++7++++++++++++
++++8+++9++++++
++++++++++8++++
+++++++++++++++
++3+++++6++7+++
++++1++++++++++
+++++++++++5+++
+4+++++++3+++++
+++++++++++++++
10112215回探索 ０分５秒157
５秒？・・・何、この差＿|￣|○
いままでROMしていたけど、ちょっと自作プログラムを
走らせてみた。上から順に時計回りに問題を回転させ
ている。（ミラー処理はコーディングしてない）
00:04:01.9489695 探索ステップ 870413965
00:00:02.8998330 探索ステップ 11450820
00:00:00.2962195 探索ステップ 1097793
00:00:32.2099730 探索ステップ 125931282
基本的には進可さんのプログラムと同じ考え方。簡単
にコーディングするにはこのやり方しかないと思う。
初代は進可さんのと同じぐらいのスピードだったが
内部データの持ち方と枝狩りアルゴリズムの見直し
でコツコツとスピードアップしていった。仕事が忙しく
なったので中断中だけど、まだまだいけるはず。
こういう問題は並列ソルバにすれば安定しますね。
４並列ソルバでを解くと0.3秒*4＋α=1.2秒＋αの時間で解けることになりますね。
アルゴリズムの改良だけでもっと探索時間が減って、
回転に対して探索時間が安定するようになれば並列化はいらないかもしれません。
そういう意味で並列化は今の時点では後でもいいかもと思います。
＃現在私は領域分割の観点から大きくバックトラックできないかと思考中。
でないので汎用性はあまり高くないかもしれません。実は回転に
よる問題の計算量を前もって知ることができれば、一番コストが
低いものだけ計算すればよいのではないかと考えていたのですが、
計算量の予測が数値化できず断念した経験があります。
領域分割も検討中。いくつかの方法が考えられるが、単純に分割
するとメモリの使用量が爆発するので駄目。今考えているのは
ある程度まで解いた段階で分割領域のミニ探索を行う方法ですけど
プログラムの構造を大幅に変更する必要があるので躊躇してます。
0.17/25274
0.84/130956
58.77/15888737
12.54/2743254
ことがなかったです。
確かに だと重心で判断できますね。問題は回転によって重心が
移動しない対称形のやつですね。このタイプも回転させると 10 倍以上
差が出る場合があります。ただ何もしないよりはよいので、試して見る
価値はありそうですね。
並列計算かぁ、そこまでしっかりやるなら反転もありかも。
重心っていうのは探索の早い位置に数字が多いかどうか？って考えでいいのかな？
探索開始位置に数字が多いと速く解けるのが多いだろうし。
ほかの重みとしては、端に数字が多いと速く解けるっていうのも感覚的にあるな。
あと、対象形で速さに差が出るのは、同じ番号の距離があやしいと思う。
確定の早いパターンが探索開始位置に近いほど、解き易いから。
（の「ありえない状態になったら」の部分）は
どういうタイミングで発動するのでしょうか？
-「壁あり」を割り当てて整合性チェック
- if(整合の場合){次の壁の割り当てルーチンへ}
- if(不整合、または残りの割り当てで矛盾が出てバックトラックした場合){
-- 「壁なし」を割り当てて整合性チェック
--- if(整合の場合){次の壁の割り当てルーチンへ}
--- if(不整合、または残りの割り当てで矛盾が出てバックトラックした場合){バックトラック}
-- 現在の割り当てルーチン終わり
と言う感じで合ってますか？
いまのところスレを読むと
基本チェック
・数字マスからもう一方の数字マスまでたどり着けるかのチェック（推測）
枝刈り用チェック
・コの字型枝刈り()
・遠回りチェック()
・部分閉空間の枝刈り()→廃止→のように小規模化
これでいいでしょうか。言っていい範囲で教えてください。
あとの話ですが、この場合１の下のマスと２の下のマスの間の壁を決定した時点で
１と３が短絡されてるのでバックトラックできそうなもんですが、
１の下のマスと２の下のマスの間の壁の割り当てのときにはこれは検出されないのでしょか？
面倒なので元の向きと上下逆のみ。
元の向き：3分59秒063、394431038 step
逆の向き：0分00秒370、621326 step
枝刈りのアイデアはまだまだあるのだが15x15で効果が出るかは謎・・・
最終的には25x25を現実的な時間（大体1週間ぐらい）で解ける事を目標に高速化しています
ただ、このサイズになると問題によって探索空間が4桁ぐらいは平気で変わるので
どの問題でも安定して解ける、というのは厳しそう。
最適な探索方向については、同じ数字同士を繋いだ線の重心で調べれば良いと思う。
あと、枝刈りの方法によって最適な値は異なるけど縦向き、横向きも考慮するとより良い結果になりそう
だいたいそんな感じ。詳しくはここにあり。
ttp://www.interq.or.jp/moonstone/person/numlink/nl01.html ttp://www.interq.or.jp/moonstone/person/numlink/nl02.html >274 現在の整合性チェック項目
同じく上のnl01とnl02のhtmlに書いてあります。
ただし、壁向こうチェックは片方だけとか、微調整してたと思った。
図の場合、１と３が結ばれるのが確定するのは、１の真下のマスが縦直線に決まった時。
２の真下へチェックが移る前に決まる。だから、チェックするなら１の真下の時。
だが、実際にプログラムしてみると、うまくいかなかった。逆に時間がかかってしまう。
理由は、全てのマスに対し、「下に伸びるならそこに数字があるか？」を一々チェックするのは手間だから。
そしてその手間に対し、下に数字のあるケースはとても少ない。
なぜなら、空白マスの数＞＞（越えられない壁）＞＞数字マスの数 だから。
チェック回数に対し、NGになる状況が少なすぎる探索は、逆に時間がかかるので効果的ではない。
という結論に達したので無しにしました。
2GHz のマシンでですか？速いですね。ステップ数の数え方はプログラムに
よって違いがあるので正確には比較できないが、元の向きを見る限り私の
よりも大幅に枝刈りをしているようです。時間ができたら私ももう少し
考えて見よう。今以上の枝刈りをするには相当慎重にやらないとバグって
しまうのが怖いですが。
私の目標はとあるところで見かけた 25x42 の問題ですが、現実的には
25x25 ぐらいでしょうね。
重心はいろいろと調べて見ると面白いでしょうね。こちらも今後の課題です。
> チェック回数に対し、NGになる状況が少なすぎる探索は、逆に時間がかかるので効果的ではない。
この点は同意しますが、下方向の先読みを行わずにできる枝刈りは限られ
ているので、なんとしてでも組み込みたい機能です。条件としては「パスが
数字につながっている」、「下に数字がある」、「パスの値と下の数字の値
が異なる」の 3 つだけですから、これをいかに効率的にチェックできるか
を追い求めれば必ずクリアできます。これができれば 2 行以上下の数字も
活用できるようになります。
(上から探索したときの下側)の影響があるので、
上半分、右半分、下半分、左半分に分けて、そこの重心を使っていたりします。
これだと対称形で扁平な数字配置のときにも少しは対処できます。
上下左右対称のときにはどういう指標がいいんだろう…
# 15x15 と 25x25 の間のサイズで手頃な問題集がないかなあ。
解くチェックが遅いのと1箇所でも短絡していると駄目なので厳しそう。
15x15が自動生成出来る限界なのかなぁ？それでも条件を厳しく設定すると
1問2時間とか平気で掛かったりするけど
20x20とかで
15から18に上がっただけでここまで変わるのか・・・15なら今と同じ程度の縛りを入れた問題でも大体数分で解くのに
但し、線が繋がった時に両端の数字が一致しているかのチェックは行わない。
全部埋まったらペアになっている数字を対応付けて短絡チェックをすればOK
結構乱暴な方法だけどこの方法でも案外まともな問題を作ってくれるのが不思議
+1++++++++++++++++
++++++++2+++++++++
++++++3++++4++5+++
++++++++++++++++++
++6+++++++++++++1+
+++++++++++++7++++
+++++++7+++++++8+9
a++4+++++++3++++++
++++++b+++++++c++9
d+e+++++++8+++++++
++++b+++++++++++++
+c+++++++++++++2++
++++++++++++++++++
+++6++d++++e++++++
+++++++++a++++++++
++++++++++++++++5+
++++++++++++++++++
18x18で妥協したら何とか1問完成・・・
このサイズの問題を量産しても使い道が無いので多分もう作りません
15xと25xの中間のサイズの問題が欲しいのならナンバーリンク2のパート3（14x24）が良いんじゃないかと思いました。
長方形なので微妙ですが逆に正方形の問題では使えないような解き方が見つかるかも？
解くんじゃなくて問題作るのって結構みんなやるのかな。どこかに投稿したり？
唯一の解をもつというのは決まりなんでしょうか。
「角の定理」っていうのがキーワードみたいだけど、
googleっても内容はでてこなかったです。考えてみよう。
ただ、この方法で自動生成するには高速なソルバーが必要で、
しかも良問が出来る可能性はかなり低い。
場合によってはコンピュータが出した問題から選別する時間があれば
最初から1問作れるぐらいだったりもするのであまり実用的じゃないかも。
出てくる問題は少なくともナンバーリンクのルールで解く事が出来て短絡解の無い問題ではあるのだが。
重心とか考えるのが面倒だったので短絡なしで先に全パターン検索し
一番効率的なやつだけ解かしてみました。それでも 30 分かかりますね。
解いたパターンは右 90 度回転の左右反転です。
短絡なしは一瞬で終わるので下手に重心を考えずに 8 パターン分
なしで計算し、一番ステップ数が少ないのをありで解かせるのも
いいのかもしれません。
はるか昔にナンリンソルバーは作ったことがあるんだが、
証明できない定理（つーか仮定）を使ってたんで、完璧かどうかは
なんとも言えなかった。ただし当時（90年代半ばぐらいだったかな）でも
10x10は普通に解けてた。
ちなみにその仮定と言うのが
「完全解があるものに関西解がある場合、
関西解のうち１つは、必ずすべての曲がり角の内側を
ななめにたどったところに数字がある」というもの。
これの反例が見つかったことが無いんだが、誰か証明してくんね？
こんな感じで示せないかな？
線の引き方に余裕度（名称はなんでもいいけど）とかいうものを、
‐余裕度は常に 0 以上の整数。
‐「すべての曲がり角の内側をたどったところに数字がある」という条件を
みたしているとき、余裕度は 0 になる。
‐その条件をみたしていないときは、引き方を変えることで、もっと小さな
余裕度を持った引き方にすることができる。
とかいうふうになるように、うまく定義するんだわ。
具体的には、たとえばこんな感じかな。
まず、各白マス（線の通ってないマス）に対して、そのマスから盤面の外へ
「白マスまたは『曲がり角の内側』をなしてるマス」だけを通って出るときの
線をまたぐ回数（出方が多数あるときはその合計）を考える。
そして、盤面の全白マスに対するその値を合計したものを、余裕度とする。
これだと、上の三条件をたしかにみたしてる。
というのも、まず 1 個目は明らか、2 個目はその時外へ出る道が無いから、
3 個目は曲がり角をくぼませればよいから。
よって、仮説は証明された。
と思う。
○────┐□□□
□□○○┐│○─┐
□□│□││□□│
○─┘□││□□│
○─┐□│└─○│
□□│ a.└──○│
□○┘□□□□○│
○──────┘○
○────○□□□
たとえば上図で a のマスは、上から右上に抜ける 2 と、右下の 1 とで、
合わせて 3 と数えるわけです。
？？┐
？a1？ a1が空白なら
a2？？
？？□
？└？という別解が存在する
a2？？
aが空白でなく、数字でもないなら、
？？┐
？┐？
a2？？となっているはず。
a2に対してa1と同じ議論が生じる。
という数学的帰納法でも証明できますね
> 曲がり角をくぼませればよいから
ってのが、それのことね。
１ □□□
□□２ □
□１ □□
□□□２
色々な引き方があるけどどうやって引いても
┌ このような位置関係のマスは発生する。
□
完全解とか短絡解とか関西解と稠密解とかいまいち分類が分からないんだけど
誰か解説してくれる？
どうかな。「内側」の定義の問題になると思うのだけど。
○┐□□
□│○┐
□○ a.│
□□□○
たとえば、上の a のマスは、「角の内側」と言っていいものかどうか。
○○○○□□□
││││□□□
││││ b.□□
○○○└──○
○─────○
○─────○
○─────○
上の b ならどうか。とか、さ。
つーか漏れ（）も「内側」の定義は気になってたんだけど、
外に直接つながってる白マスに面するのは内側じゃない、とかする
必要がありそうですかね。
短絡解＝関西解＝通らないマスがあり自明な他の解がある解（を含む問題）
別 解＝（自明な他の解を持たない場合も含み）作意解以外の解（を含む問題）
完全解＝短絡解を含まない（別解は含んでも良い？）問題の解
唯一解＝完全解が1つある問題
で良いのかな？
あまり意識せずに使ってたけど人によって解釈が違ったりするので
きちんと定義した方が良さそうですね。
そんなエピソードでそう呼ばれてるのでしょうか
１ □１ □□□□８ □８
２ □２ □６ ７ □９ □９
３ □□□□□□□□３
４ □４ □６ ７ □10□10
５ □５ □□□□11□11
関西解の定義を
線の通らないマスがあり、ある空白マス群に隣接する線のうち同じ数字に属する物が２箇所以上にある解
とすればこれも関西解に含まれる事になるのだが
┌┐
┘└
とか
┌─
│□
とかのパターンが存在するという条件だと関西解ではなくなってしまう・・・
角の定理を封印する目的で淵に□□１□２□□というようなパターンを作って
──１□２──と引かせる等といった問題も作れるので。
完全解と全てのマスを通らない解1つが存在する問題（あればの話だけど）も関西解と呼べるのか微妙なラインです
僕が考える関西解の定義は「自明な別解を持つ全てのマスを通らない解」で、
何を持って自明とするかの線引きで悩んでいるといった感じです。
ナンリンソルバーのバージョンアップしました。
>264でチェック。パソは同じ。
10112215回探索 ０分５秒157
↓
3865353回探索 ０分２秒093
ほぼ半分以下の短縮です。
メールで教えてもらった法則を追加したんだけど、よく見たら>292あたりでやってるのと同じ理論っぽい。
いただきました。
手持ちの15×15を2つほど解かせてみたところ、
正確な時間は忘れましたが、
・9秒→7秒
・約11分→3分40秒
と、それなりに大きな短縮を見せておりました。
盤面反転ボタンとかあると嬉しい、と言ってみたりして。
ttp://www.interq.or.jp/moonstone/person/numlink/index.html 片方だけ枝狩りしていたのを両方で枝狩りに。
>264でチェック。パソは同じ。
10112215回探索 ０分５秒157 （初期）
↓
3865353回探索 ０分２秒093 （前回）
↓
1332705回探索 ０分０秒828 （今回）
時間のかかる>263だと
1308783250回探索 １３分１秒156
でした。これだけできればほぼ１時間切ると言えるかな？
（片方だけ枝狩りだと30分かかってました）
>308 オプションから反転を選択できるようにしました。
いや、最初の時点でつけるか止めようか悩んだんだけどね。
悪意があれば、既出の問題を反転回転の数字変更で捏造新規が可能だし。
でも最近は大型の面は対象形が多くて、捏造してもバレやすいってことに
気がついたんで機能追加させることにしました。
│ 1││
││││
││ 2│
│└─┘
この手の無駄な経路を検出できるいい方法はないかなあ
ジャイアント１７号の４の関西解を見つけた。
ペコンとして編集部にメールしますた。
サイト上に書かれてない＆メール載せてないんで
ぶっちゃけここで聞いちゃうけど、進可タソのサイトってリンク可？
無差別広告メールが嫌なのでサイトにはメルアドを載せてませぬ。
ありが㌧
みんなを唸らせられるようなナンリンをがんがって作ってみるよ。
サムラインを簡単に作るツール(VB6ソース付)
ttp://www.geocities.jp/jyokun_geo/ むー、適当なあぷろだが見つからなかった。
しょうがないので塩のアカウントとっちゃったよ。
AIっていうことは、定石・手筋はあまり前もって教えずに
ひたすら対戦しゅみれーと（←なｚ）して、
勝ちパターンデータベースを作る、っていう方向？
ルールを変更して既存の定石は役にたたなくするつもりだから
定石を教えるようなことは、どっちみちさせないつもりです。
変更内容はマス目ごとに点数が違う所。+3点のマスや-1点のマスがあったりする。
例えば、カドだけが-9点だとしたら、取るべきか取らざるべきか難しくなるよね？
ttp://www.geocities.jp/m_hiroi/puzzle/index.html これを縦型探索に変更したらどんなプログラムになるんだろう・・・
数独解析アプレット
ttp://www.geocities.jp/jyokun_geo/sudoku/index.html 数独を解くプログラムはネット上に山ほどおちてますが、
今更晒す理由（ウリ）は
「人が解く場合の手順を示してくれる」
ってとこです。
まあ、数独の場合人によって解く手順が分かれるんで、
「俺の解き方と全然違う」ということもあると思いますが。
数独が流行ってるようだけど、解析まで手を出してる人が少ないのは
こってり頭を使うのが流行らないからなんだろうなぁ。
プログラミングの基本的な例題として有名だし
使えるアルゴリズムとかデータ構造とか。
引っ張り出して、1GHzのノートで実行してみた。
15x15がチェッカーモード (関西解探索) で 11分ぐらい、
ソルバーモードで0.01秒ぐらい。
俺、なかなかやるな。いまさらどっかにあげてみようか。
っていうか、関西解がある問題でチェッカはしらせたら、
1時間かかったっす。だめだこりゃ。
基本方針としては進可さんのと同じなので、入れてる heuristicsの差だな。
アルゴリズムとかパラメータを人間の勘とか経験で適当に決める方法をヒューリスティック、と言う。
heuristics
【名】ヒューリスティックス◆経験則
だよな。
翻訳の方でも「発見的教授法」とか出たりでサッパリだったもんで。
ただし複数個敷き詰めで同じのが隣り合わせにならないルール。
でかいと解答遅いので高速化方法を思考中。
一本棒を一番最初に入れちゃうと多分それが一番遅い探索になると思う。
なるべく複雑な形のピースから入れてくと速い。
探索の速い段階で（探索の枝の根元の方で）
孤立した小さい穴が出来たりして（それ以上やっても無駄なのが明らか）
早い段階でその探索枝を断ち切れるから。
また、大きくても孤立した穴のサイズが4の倍数でなければ探索を打ち切れる。）
例：左上にS字のピースを置いたらサイズ1の穴が出来るのでこれ以上探索の必要なし。
＿■■
■■
配置していったほうが速いんじゃないかな。
テトロミノに限れば、この方法で埋めてけば、孤立した島が出来てもサイズ1の
島しか出来ないから(多分)、枝刈りも楽かもしれない。
盤面をビットフィールドで実装していれば、大きさ1の島が出来ているかどうかは
board != board & ((board >> 1) | (board << 1) | (board >> width) | (board << width))
で判定できそうだし、きっと速い。
> 孤立した島が出来てもサイズ1の島しか出来ないから
いや、残念ながら
■■■■■■
■■■
■■
■■
↓
■■■■■■
■■■□□□
■■ □
■■
↓
■■■■■■
■■■■■■
■■□ ■
■■□□□
↓
■■■■■■
■■■■■■
■■■ ■
■■■■■
そっか(´･ω･｀)ｼｮﾎﾞｰﾝ
サイズ3の島が出来るときは、右側に島が出来るケースしかないと思うので
次のピースを配置するときに必ず失敗するから妥協するとして
サイズ2の島があるかどうかの判定を書き下してみたんだが、
b!=b&((b shl 1)&((b shr 1)|(b shl (+w))|(b shr (-w))|(b shl 2)|(b shl (1+w))|(b shr (-1-w)))|(b shr 1)&((b
shl (+w))|(b shr (-w))|(b shr 2)|(b shl (-1+w))|(b shr (1-w)))|(b shl (+w))&((b shr (-w))|(b shl (1+w))
|(b shl (-1+w))|(b shl (+2*w)))|(b shr (-w))&((b shr (-1-w))|(b shr (1-w))|(b shr (-2*w))))
とでてきた。全然速そうな気がしないな。
サイズ3に至っては、条件式だけで1kbyte超えた。
いっそヒューリスティックで乗り切るほうが早そうな気もする
というか、サイズ１の島ができる場合のことも含めて、たとえば
「最も左上の空きマス」を左上とする５×３くらいの領域の
現時点までに埋まっているマスの配置模様（たぶん１Ｇ通りくらい）
に応じた「可能な次の手一覧」を作成するっていう方針はどうかな
なるほど。良さそうだ。
左上であわせるよりも、6x3の領域を作って
↓「最も左上の空きマス」
■■□□□□
□□□□□□
□□□□□□
みたいにしたほうが、チェックの効率がよくなるかな。
高々 2^(3*6-3)通りだから10Mもメモリがあれば足りるかな。
1234
5678
だったのか。自分は
15
26
37
48
でやってるから、何事かと思ったよ。
■■□□□□
□□□□□◆
◆□□□◆◆
◆の位置は影響ないからもっと少なくすむんじゃない？
チェック位置本体も開いてるはずだから、実質2^11で2048通りかな？
まぁ今やってるのは、はるかにそれ以前の段階だけど（汗
ttp://karetta.jp/book-node/cpuzzle-recursion/001628 全部２個ずつ使って7*8に敷き詰めたら509通り。
奇数なのは左右対称ぶんのせいだろう。
全数探索に１２秒ぐらいかかってるから、これをなんとか
縮めないといかんけど、盆休み終わる方が先だなorz
「最も左上の空きマス」より左方へ来ることもあるんだな
いや、その◆の位置は確かに「既存のピースと重なるか」には
関係ないんだけど、「シマを作らずにすむか」には関係してくるよ
たとえば左下の◆が埋まっていると、
■
■
■■
この形のピースは置けない（シマができてしまう）
本当に影響ないのは一番右下の◆◆だけじゃないかな
結局この範囲を見ることになるかと思う
単純計算なら2の13乗で8K通りか
■■◎□□□
□□□□□□
□□□□
■■◎□□□
□□□□□□
□□□□□
これくらい必要な気がしてきた。
■■■■◇□□□□□
□□□□□□□□□◆
◆□□□□□□◆◆◆
＃もちろん、長方形でないような盤面でやるなら話は別だけど
■■■■●□□□□ ■■■■●□□□□
■□□□●□□□□ ■□□□●□□□□
■■■●●□□□□ ■□■●●□□□□
たしかに上の左図で黒丸のピースを置くと破綻するのに対し
右図では置いても破綻しないから区別が必要なように思える
でも実は右図のような状況はありえないから考慮しなくていい
■■■■○□□□□
■□□□□□□□□
■□★□□□□□□
上は黒丸のピースを置く前の状況だけど、星で書いたマスが
もしすでにピースで埋まっているのだとすれば
そのピースは、○のマスを埋める前に置かれた
つまり、○のマスが空いているという状況下で、他の、○より
優先順位の高いマスにピースを置こうとしてその結果埋められた
としか考えられないわけだ
■◎■■○□□□□ ■★■■○□□□□
■□□□□□□□□ → ■★□□□□□□□
■□□□□□□□□ ■★★□□□□□□
つまり★のマスは絶対に上辺の黒マスと繋がってる
■■■■●□□□□
？？？□●□□□□
？？★●●□□□□
だから上みたいな状況で？がわからなくても、★がすでに埋まってて
そこへ●を置いたとしたら、それだけで破綻ってわかるわけ
■■◎●●□■
□□□□●■■
□□□□□
角が接しているパターン等を考え出すと最初に一覧を作るのは無理があるぞ。
それに、すべての分断パターンを網羅した一覧表を作るのも現実的じゃない。
■■●●●１
９ ●６ ●２
８ ７ ５ ４ ３
1234565789の順でブロックの有無を調べて
ブロックが無い領域が2箇所に分断されていたら
分断されていると判定するのが楽。
ただし、テトロミノの場合でも残念ながら4の倍数チェックは必要
■■●□□□□■
□□●●●■■■
■■■●●●１
９ ●６ ●２
８ ７ ５ ４ ３
よく見たら上の4マス空き図間違ってる・・・4マスの島はありえないのか。
ただ、壁際では矢張り4の倍数チェックが必要になる。
それと、テトロミノである事が前提の枝刈を入れすぎると
ペントミノ等に応用しようとした時に苦労するからやめた方が吉。
テトロミノの敷き詰めプログラムを限界までチューンナップする必要があるとも思えないし。
肝心なところは、「左上から順に配置していく」っていうところで
これによって「既存のピース」の配置状況がだいぶ狭められる
新たに置いたピースと既存のピースとによって島ができるとすると
その既存のピースというのは、当然のことだけど
「新たに置いたピース」より前に置かれたピースなわけだ
ここで、「左上から順に配置していく」という制約というのは
すべてのマスに左上からの優先順位がついていて
現時点で空きマスであるマスのうち最も優先順位が高いマスを
埋めるようにピースを置くということ
「既存のピース」は、「新たに置いたピース」より早く置いたのだから
「新たに置いたピース」が埋めたかった空きマスよりも
優先順位の高いマスをそのピースは含んでいるということ
たとえば、
■■■■■■■■
■■■■■■■■
■■■○？？？？
？？？？？？？？
？？？？？？？？
○のマスが現時点で一番優先順位の高い空きマスだとする
？の部分はとりあえず不明ということで
このとき、新たに置くピースは○を含むように置くわけだ
じゃあ？の部分について、こういう状況はありうるか
■■■■■■■■
■■■■■■■■
■■■○□□□□
□□□□□□■□
□□□□■■■□
これはありえない
なぜなら、右下のピースは既存のピースではありえないから
「こんなとこに置いてる暇があったら、もっと優先順位の高い
○のマスとかを埋めるように置いてるだろ」というわけだ
つまり、既存のピースというのはすべて
■■■■■■■■
■■■■■■■■
■■■○？？？？
？？？？？？？？
？？？？？？？？
この図で言う■のマスを少なくとも１マス含むように置かれている
それが「島は３マスまで」の根拠であり、「１３マス調べればいい」の
根拠でもあるのですわ
簡単に言えば今から埋めようとしている○のマスの右下方向というのは
ほとんど埋まってるマスが無いので、「実は遠くでつながってる」的な
可能性というのは考えなくてよくなるっていう感じかと
あーレスが前後したごめ
壁際については、左右どっちが壁の場合も大丈夫だと思うんだけど
> それと、テトロミノである事が前提の枝刈を入れすぎると
> ペントミノ等に応用しようとした時に苦労するからやめた方が吉。
これは確かになあ。言われてみればもっともだ
まだ盤面が余っているのに置けるパーツがなくなったらハタン、で十分な速度出たよ。
高速化はどうしても必要になるよ。
今の自分は枝狩り以前の構造的な高速化してる段階だけど。
なんかいいアイディアないかな。
ちなみに、途中で同色のピースが1個しかなくなったら
探索中止という枝刈しか入れてません。
どうせ手順前後で同じになることはかなり多いと思う
あとは盤面を分割してそれぞれで考えて後で合併するとか
盤面の分割は結構いけるかも。
やってみる。
最も得点が高くなる手順を発見するプログラムを書きたいのなら・・・
まぁ頑張れ。
＊先に消しにくい両端を消し、全体を山形にする。
＊横繋がりがあるのを優先（下が消えるとズレる）
＊孤立しそうなコマに注意する
コマ消しに優先順位をつければ多少は解きやすくなるかも。
消した後に形が悪くなったり、孤立するコマが増える手は
探索の評価を低くしたほうがいいだろうね。
例えば０と１になる確立が５０％ずつの状態を、０＝５０と１＝５０のような要素にして計算する感じ。
敷き詰めパズルでは、それぞれのマスでどのピースの一部が置かれるかを
確率的な数値要素にしておいて、隣との相互干渉で、確率を上下させる。
矛盾が無い置き方に収束していけば、そのうち答えが出てくるのでは？と思っている。
ただしこのやり方は、解があるか？の判断はできるが
何通りあるかの計算はできないし、答えが収束しないからといって
解が無いと判断することもできないのがネックだ。
むぅ、単なる山登り式の方が効率いいかも。
話は変わるけどナンリンソルバー。久々に見直したら
色々短縮できるところが見つかって、数パーセント速くなったよ。
まだまだなんかできそうだ。
929828回探索 ０分０秒578
>309の
>1332705回探索 ０分０秒828
と比べると、数パーセントどころか30％近く短縮できてた。
ナンプレの解説などは
ttp://hobby8.2ch.net/test/read.cgi/puzzle/1158485888/l50 いまのところEXCELのVBAです。
さて、下記のような盤面の場合、下の可能性リストが得られます。
A B C D E F G H I
┏━┯━┯━┳━┯━┯━┳━┯━┯━┓
１┃ │ │ ６┃ │ │ １┃ │ ３│ ５┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
２┃ ９│ ３│ ┃ ７│ │ ┃ │ ８│ １┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
３┃ │ │ ┃ ８│ ３│ ┃ │ ９│ ４┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
４┃ ７│ ５│ ┃ ６│ │ ┃ １│ ２│ ９┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
５┃ │ ２│ ８┃ │ │ ┃ ４│ │ ７┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
６┃ │ ９│ １┃ │ ７│ ２┃ ３│ │ ８┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
７┃ ５│ │ ┃ │ ６│ ７┃ │ ４│ ２┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
８┃ │ ６│ ┃ │ │ ４┃ │ ７│ ３┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
９┃ │ ４│ ７┃ ２│ │ ┃ ５│ １│ ６┃
┗━┷━┷━┻━┷━┷━┻━┷━┷━┛
このF列に56のペアがありますが、これを２国同盟と呼んでいて、同様に３国、４国などあります。
３国の例 12 23 13
２国はプログラム化する事もそれほど難しくないと思いますが、３国以上、何か妙案はありますか。
A B C D E F G H I
┏━━━━┯━━━━┯━━━━┳━━━━┯━━━━┯━━━━┳━━━━┯━━━━┯━━━━┓
１┃248 . . . . .│78 . . . . . .│ . . . . . . . .┃49 . . . . . .│249 . . . . .│ . . . . . . . .┃27 . . . . . .│ . . . . . . . .│ . . . . . . . .┃
┠────┼────┼────╂────┼────┼────╂────┼────┼────┨
２┃ . . . . . . . .│ . . . . . . . .│245 . . . . .┃ . . . . . . . .│245 . . . . .│56 . . . . . .┃26 . . . . . .│ . . . . . . . .│ . . . . . . . .┃
┠────┼────┼────╂────┼────┼────╂────┼────┼────┨
３┃12 . . . . . .│17 . . . . . .│25 . . . . . .┃ . . . . . . . .│ . . . . . . . .│56 . . . . . .┃267 . . . . .│ . . . . . . . .│ . . . . . . . .┃
┣━━━━┿━━━━┿━━━━╋━━━━┿━━━━┿━━━━╋━━━━┿━━━━┿━━━━┫
４┃ . . . . . . . .│ . . . . . . . .│34 . . . . . .┃ . . . . . . . .│48 . . . . . .│38 . . . . . .┃ . . . . . . . .│ . . . . . . . .│ . . . . . . . .┃
┠────┼────┼────╂────┼────┼────╂────┼────┼────┨
５┃36 . . . . . .│ . . . . . . . .│ . . . . . . . .┃1359 . . . .│159 . . . . .│359 . . . . .┃ . . . . . . . .│56 . . . . . .│ . . . . . . . .┃
┠────┼────┼────╂────┼────┼────╂────┼────┼────┨
６┃46 . . . . . .│ . . . . . . . .│ . . . . . . . .┃45 . . . . . .│ . . . . . . . .│ . . . . . . . .┃ . . . . . . . .│56 . . . . . .│ . . . . . . . .┃
┣━━━━┿━━━━┿━━━━╋━━━━┿━━━━┿━━━━╋━━━━┿━━━━┿━━━━┫
７┃ . . . . . . . .│18 . . . . . .│39 . . . . . .┃139 . . . . .│ . . . . . . . .│ . . . . . . . .┃89 . . . . . .│ . . . . . . . .│ . . . . . . . .┃
┠────┼────┼────╂────┼────┼────╂────┼────┼────┨
８┃128 . . . . .│ . . . . . . . .│29 . . . . . .┃159 . . . . .│1589 . . . .│ . . . . . . . .┃89 . . . . . .│ . . . . . . . .│ . . . . . . . .┃
┠────┼────┼────╂────┼────┼────╂────┼────┼────┨
９┃38 . . . . . .│ . . . . . . . .│ . . . . . . . .┃ . . . . . . . .│89 . . . . . .│389 . . . . .┃ . . . . . . . .│ . . . . . . . .│ . . . . . . . .┃
┗━━━━┷━━━━┷━━━━┻━━━━┷━━━━┷━━━━┻━━━━┷━━━━┷━━━━┛
２国の場合はどんな方法でやっていますか？
まだ２国もプログラム化してないですが、
[12]の２国の場合[12][12]しかありませんが
[123]の３国の場合、[123][123][123],[123][123][12],[123][123][13],
[123][123][23],[123][12][123],[123][12][13]......と
膨大な数の組合せがありうるのである種のアルゴリズムを考えないと
見つけ出せないと思います。
1,2,3の数字で出来ている所が３つあれば３国という形ではだめですか？
それをアルゴリズム化するところが難しいのです。
┏━━━━┯━━━━┯━━━━┳━━━━┯━━━━┯━━━━┳━━━━┯━━━━┯━━━━┓
１┃248 . . . . .│78 . . . . . .│ . . . . . . . .┃49 . . . . . .│249 . . . . .│ . . . . . . . .┃27 . . . . . .│ . . . . . . . .│ . . . . . . . .┃
┠────┼────┼────╂────┼────┼────╂────┼────┼────┨
上の例で１行目を取り出せばこのようになり、９つのますから３つを取り出すパターンを網羅するアルゴリズムを
作るということになります。
for i=1 to 7
for j=2 to 8
for k=3 to 9
判定処理
next
next
next
これでいきそうな気もする
for j=i+1 to 8
for k=j+1 to 9
debug.print i,j,k
next
next
next
で試してみます
それだと、同じパターンが何度か出てくるのでは？
a1～a3:選んだマス
b1～b6:制約範囲(行列囲み)の他のマス
f:立っているビット数を返す関数
陽的3国同盟(同じ制約範囲の候補が消える)の判定
f(a1 | a2 | a3) == 3
陰的3国同盟(該当マスの他の候補が消える)の判定
(a1 | a2 | a3) & (b1 | ... | b6) == 0
伝統的な再帰ソルバしか書いたことがないから間違ってるかも。
陰的３国同盟の意味について考えていました。
２個表出、７個未確定の場合なら陰的３国同盟は陽的４国同盟に等しいのではと
思うのですが
[abcd][abc][acd][bcd][abcxyz][bcxz][abxy][8][9]
０個表出、９個未確定の場合、陽的６国同盟なんてちょっとしんどいから
陰的３国同盟を探したほうがいい、という考え方であってるのかなー
たとえば、1,2,3,5のどれかが入るなら、p=000010111
制約範囲（行列囲み）の全てのマスに対してp1～p9を求める。
[123]の３国同盟を調べたいなら、
f(123)=000000111というフラグを用意しておき、
(pn|f)=fとなるpの個数が3なら、３国同盟成立。
f(123)～f(789)の全てを調べれば、全ての３国同盟が調べられるし、
４国でも５国でも同じやり方でできる。
縦列にマスの番号、横列に１～９の各数字をとって、
その交点に「マスに数字が入るか否か」を書き込むと
Boolean を成分にもつ９×９行列になるよね
その行列に、行の入れ替えと列の入れ替えを施して
Ａ Ｂ
０ Ｃ
の形に変形できるか？ ということなんだと思う
（そのとき、Ｂの部分が０になる、ということ）
なんか相関関係の分析とかでこういうのあった気がするし
こういう見方からだと色々あるんじゃないか
夏、彼氏が出会い系にはまってることがわかりすぐに別れました。
怖くなったので念のためHIV検査を受けると陽性でした。まだ症状は出てません。
そのあと、彼は秋にまた出会い系で三重の21歳ぐらいの女を拾ったと自慢して連絡してきました。
すぐに彼にも検査を受けるようにすすめました。彼は、受けなくてもわかってる。と答えました。
彼は自分がHIV感染者だと理解した上でセックスしていました。
私だけではありません。出会い系で知り合った人たちとしているそうです。
感染させるために。 今も続けています。
私は今後いつ発症するかわかりません。
好きな人ができても結ばれることはありません。子供も産めません。
私だけではありません。
彼から感染した女性はたくさんいるはずです。 彼の行為は殺人罪に値しないのでしょうか。
彼は三重の近辺らしいです。三重県の女性の方気をつけてください。
出会い系で知り合った男とは別れなさい！
もう一度アップお願いします。
本当にお願いします
独り言(四角の対角線や浜田ロジックに対応してくれうると嬉しいな……)
一方が駄目ならもう一方が正解、っていうのはパズルの場合、一方が正解なら
他方の解が非解であるかどうか確かめる物好きって滅多におりませんし
ttp://www5e.biglobe.ne.jp/~hosiza/skenew.html ツールは確か他にもあった気がするけど・・・
ttp://hobby10.2ch.net/test/read.cgi/puzzle/1180026462/253-256 低いレベルの手筋だけ使って探索して、
解けない時に手筋のレベルを上げる
という方法で解くソフト
ttp://http://www5e.biglobe.ne.jp/~jyokun/numlin/ 自分で書くのもなんですがかなり速いです
ほとんどの15x15で1秒以内
25x25でもほぼ数十秒から数時間以内に終了します
このスレや進可さんのページが大変参考になりました
ありがとうございます
それともDELPHIが遅いのかな？
そのあと、各ステップごとに自動で決まる線はどんどん引く、
二種類の数字が必ず交差するようなら戻る、
などの手法が入ってます。
DelphiとVC++って速度は、
精々二倍ぐらいしか変わらなかったような（良く知らない）。
間違っても気にしない
>二種類の数字が必ず交差するようなら戻る
これ、取り入れようとしてあきらめたんだよなー
うまい方法でもあるんですか？
>405
気にしろよw
基本的には、
外枠と確定マスをまとめて「壁」とみなし、
壁沿いに数字を拾っていって、
ABA'B'って順に現れたらダメ、
って考え方で実装してます。
いっぱい解きたいです。
しばらくは気力のガソリンの補充だ。
ttp://http://www.amazon.co.jp/exec/obidos/ASIN/4797340207/zapanet-22/ref=nosim/ でも専門書なみのお値段だなあ
スペック的に可能な範囲なんでしょうか？
電車の中や日常で思い付いたのをささっと手軽にチェック出来たらいいなあ。
紙と鉛筆で記録するのってめんどいから携帯にメモをしてるんだけどね。
P501iのＣＰＵクロックは9.2MHz
P900iのＣＰＵクロックは192MHｚ
一般のパソのCPUが2GHz程度として考えると
約10倍の解答時間がかかると予想。
10*10は可能かな？15*15は厳しいと思う。
倍以上になってる気がするんだが
参考になりますた
ありが㌧
ソフバンの携帯にはWindowsが入ってるのもあるし、進化してるんだねえ
プログラムほしいですお願いします
数独ソルバー
ttp://http://www.geocities.jp/katayama_hirofumi_mz/sudoku/ ﾊﾟｼｬｯ ﾊﾟｼｬｯ
ﾊﾟｼｬｯ
∧_∧ ﾊﾟｼｬｯ
ﾊﾟｼｬｯ ( )】Σ
. / /┘ ﾊﾟｼｬｯ
ノ￣ゝ
数独ソルバー ver.1.1
ttp://http://www.geocities.jp/katayama_hirofumi_mz/sudoku/ 買わなくても
富山DQN男の家族消えろ 富山DQN男の親消えろ 富山DQN男の子供消えろ 富山DQN男の親戚消えろ
富山DQN男の家族消えろ 富山DQN男の親消えろ 富山DQN男の子供消えろ 富山DQN男の親戚消えろ
富山DQN男の家族消えろ 富山DQN男の親消えろ 富山DQN男の子供消えろ 富山DQN男の親戚消えろ
ニヤニヤ(・∀・) ニヤニヤ(・∀・) ニヤニヤ(・∀・) ニヤニヤ(・∀・)
死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね
死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね
死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね
死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね死ね
苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね
苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね
苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね
苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね 苦しんで死ね
死ぬとき このレスの事思い出してから地獄へ行けよ
ニヤ(・∀・)ニヤ(・∀・)
ttp://http://www.geocities.jp/katayama_hirofumi_mz/logic/ ピクロス で検索した結果 1～10件目 / 約363,000件 - 0.33秒
イラストロジック で検索した結果 1～10件目 / 約534,000件 - 0.03秒
お絵かきロジック で検索した結果 1～10件目 / 約874,000件 - 0.05秒
ピクチャーロジック で検索した結果 1～10件目 / 約32,500件 - 0.16秒
遅い速い以前に、誰もリンク踏もうなんて思わないぞ。
どうやって高速化したとか、賢くしたとか、そういう話題を振るなら
その成果を確認するために他の人も覗いてみる気が起きるだろ？
ロジックが得意なら、そういうロジックも考えた方がいいぞ。
無料のソフトでも、0.1秒以下で解けますよ。
ロジックアーティストで試してみたら、サイズ35ｘ35で、6秒以上かかるみたいですよ。
数独のことを言っているのか。イラロジと間違えた。
とても価値のあるソフトと思います。
使ってみましたが、とても便利でした。
他の新しいソフトも期待しています。
たいていの数独ソフトは、世の中の数独を全部解けるでしょ。
あれ？
おまえはふだんは俺のIDを書くのに。
まちがえた？
多数解の問題には対応してないみたいだな
単純な例では５マス四方の問題で縦横ともに(1,1)(1,1)(0)(0)(0)
の問題だと２通りの答えがあることは明らかだがどちらか一方の解しか表示されない
世の中にあるこの手の問題がすべて1通りだと思うなよ
数独ソルバーは難しい問題だと解いてくれないし
ついでに言うと数独はニコリ社の商標登録だ
その名前を勝手に使って商売してるということは・・・どうなるかはわかるよな？
パズルで小遣い稼ぎするんならもっとパズルのことを調べろ、勉強不足だ
ナンプレソルバー
ttp://http://www.geocities.jp/katayama_hirofumi_mz/numplace/ 大きなナンプレソルバー
ttp://http://www.geocities.jp/katayama_hirofumi_mz/numpla2/ イラストロジックソルバー
ttp://http://www.geocities.jp/katayama_hirofumi_mz/ilogic/ まあ、「ナンプレ」は雑誌だけかもしれんが、
「イラストロジック」のプログラム関連はハドソンが持ってるんじゃなかった？
ttp://search.vector.co.jp/search?query=%83i%83%93%83v%83%8C ttp://search.vector.co.jp/search?query=%82%A8%8AG%82%A9%82%AB%83%8D%83W%83b%83N Killer Su Doku(サムナンプレ)の
新作問題自動作成ソフトを作ってくれたら神
ハドソン持ってるね。お金が絡んでるからきちんと対応しとかないと後でまずいかも。
有料なら、かなり高い率で刑務所行きかもね。
いい加減すれ違いだと思うのだがみんな寛容だな。
速さは雑誌掲載の最大サイズのもので20秒前後。早いのか遅いのかは分からない。
仮定法込みだと1.5倍くらい？
それは解くためのソフト？
解く為のソフトだけど、自分で解けるようにもしてある。
問題点は入力にものごっつい時間が掛かること。
巨大サイズの場合、１ライン平均５個として、×200×100=100000。この個数を打ち込まないといけないｗ
行ってる意味が良く分からない。5*(100+200) ではないのか。
要は人間が脳を使ってパズルを解くのを紙の代わりにPCでやれて、
必要ならいろんなヒントも出せる的なソフトだと仮定して
そういうのの数独用でいいのない?
うん、それで合ってる。自分がバカでした。大体１～２時間位掛かる。
掲載されているイラロジを入力して、紙の代わりにPCでもやれるし、コンピューターに解かせる事もできるだけです。
数独って自分は殆んどやらないから詳しくないです。
自分で組むんじゃ総当りにしてしまいそう。コツが分からないし。
有料でもいいです。よろしく。
同じ数字だけ色を付ける、とかの軽いヒント情報から、
初歩的な手筋から入ることが確定する数字を表示するとか、
手筋に順位を付けて、最も簡単な手筋で解ける部分を示すとか、
それでも判らない場合は、手筋の種類や、関連するマス等を
小出しにヒントを表示する、チュートリアル的な機能もあるソフトｷﾎﾞﾝ
手で作る場合、どうやってんの？
作りたいけど作れないの。
予想してみると、こんな感じかな？
削岩タイプ
全部埋まっている答えの状態を作っておいて、答えが出るように削っていく。
盛り土タイプ
数字を置いて手解きしながら隣のマスが判明するように、初期位置数字を置いていく。
は欲しい人で作りたい人じゃないんじゃない？
ぱっと思いつくのは、適当なマスを選んで再帰掛けて決まった個数分だけ埋め込んでいくやり方。
これだけだと重そうなんで、最初に少しだけ↑の方法で埋め込んでから、全マスを端から調べて埋めていく。
Eternity II Puzzle解き始めたからここで何かないかなーって思ってたとこ
ペンシルパズルのも興味あるから自分もブクマしておこっと
ttp://www.conceptispuzzles.com/ ここのFill-a-Pixの支援(解答)ソフトってないかな？
ルールが同じで違う名前ってのが探し辛いから…
あればうれしいのですがなければ自力で解答なのかな～
サンプルパターンを入手したので、気長に挑戦しようと思う
この辺のパズルを思う存分遊びたいので、自動で問題作成してくれるソフト
お願いします。
って書くと「自分で作れ」って返されると思うので、違うことを言います。
各マス（10×10、20×20）で一意の解答が得られる組み合わせって言うのは有限ですよね？
それを効率的に抽出するにはどうしたらいいと思いますか？
一番興味を持っている人が考えるのが良いと思う。
っていうか自動的な問題作成だと味が無いという話を聞くが
それほどまでに違うのだろうか？
求めているものはひとつくらいここにありそうだが英名わからん
ttp://www.chiark.greenend.org.uk/~sgtatham/puzzles/ ありがとう。「Light Up」が美術館でした。他のは知っている奴やルールの分からないパズル……
面白そうです。
プログラミング能力がほぼゼロなので作れませんｗ
が、やってみたいことは……
有限のパズル面を全部抽出、すべてにIDを付与、難易度別に一覧表示などなど
夢は尽きませんねｗ
ちょっと調べると、「ぬりかべ」は難易度評価が出来るようです。他は不明
ドイツあたりに自動生成ソフトがあるようですが、例によってドイツ語わからんｗ
しかも日本名以外パズルの名前も分からんｗｗｗ
パズルを作れるならプログラムも作れる。
法則がわかれば意外とできるもんだぞ。
０１２の100桁の重複順列とする事が出来る。
なんか色々考えてみたけど、処理速度がすごいことになる（超遅いｗ）
角に１は無い。辺に3個０は並ばない……とか条件付けても
条件付けただけ遅くなるｗ
うまく10桁づつに分割して計算したり、気の利いた方法は無いのだろうか。
5×5で25桁の重複順列を出力するだけでもきびしいｗ
ファイルサイズが４Gを超えた時点で諦めたｗｗｗ
考えていることは判るけど，5x5でも3**25になる。
3**25は8472億って膨大な数。
ましてや10x10だと3**100になります。
全部虱潰すのは無理ではないですか。
現実的に出来ることは，作った問題をDB化することぐらいでしょうか。
ましゅの場合，自動生成は以下のようにしてはどう?
1.内部に輪(解答)を生成する。
2.それに合わせて○●を配置する。
3.解いてみる。唯一解ならば問題として成立。
4.1へ戻る。
解けないとき1へ戻るのでなく，輪の一部を修正していくっていうのも一つの考え方。
3で解けたとして，○●の配置を変えたり，数を減らしたりしても問題として成立してしまうのが悩みの種か。
10x10だとそこそこの確率(100回に1回くらい?)で作成できると思う(今やってみたら75回で唯一解の問題が出来た。
複数解が出るのはもっと多い)。
5x5で自動生成した問題。
●＿＿＿＿
＿＿＿○○
＿○＿＿○
＿＿＿＿＿
●＿○＿＿
右の○4つはどれか一つを除いても問題として成立。
左上の●は代わりに右と下に○を置いても問題として成立。
左下の●は代わりに上に○を置いても問題として成立。
問題として面白いのはどれだろう?
ちょっと違うんじゃないかな．
にあるような置き方制限があるから
端から順に置いていくとそれなりに枝狩りはできる．
あとは回転対称は省略するとか，●●●が禁止とか，
○だけの3xA（A≧3）の長方形が無いとかの制限も考えられる．
とはいえ5x5で3**15～3**20程度までしか抑えられないと思うけど．
（ちなみに3**20≒3.5Gパターンなので予想が正しければDB化もギリ可能）
でも結局キチンと解答できるプログラム作らないと
最終的な唯一解判定ができないな．
とりあえず，5x5(10x10)のフィールドで唯一解になるましゅの
全パターン出力だと思われ．
ttp://cl-informatik.uibk.ac.at/software/puzzles/ ここにあるソフトが問題の自動作成と自動解答を備えている・・・
自動解答は、ベーシックソルバーとトライアンドエラーソルバー
確定探索と背理法探索？
自動作成は５段階のレベル設定付き
JAVAのソース見ても意味わからんけどね。しかも変数名がドイツ語ｗ
自分の都合の良いようにソースの編集とかできる能力が欲しいね。
答え解析に向いてなさそうだ。ちょっと失敗だったかなぁ。
遅くなるだろうねー…
まあ中間コードに変換するからいくらなんでもBASICよりは速かろう･･･
いやコンパイルするBASICもあるか
ttp://www.oct.zaq.ne.jp/woodside/mash/ MashPlayer すごいね・・・。
MashPlayer.jarファイルが見つからないんだけど・・・
ttp://www.oct.zaq.ne.jp/woodside/mash/MashPlayer.jar 画面中央に
ダウンロード
本体(MashPlayer.jar ver 0.57 : 実行jarファイル 182kbyte)
って出てるけど・・・。
それの中身に入ってないみたいなんだよ
せっかく面白そうなのに・・・
.jarにリネームしたら動いたよ
そりゃjarってzipで固めたものですしおすし
ttps://twitter.com/#!/imos/status/135172910125039616 @imos Imo / Kentaro Imajo
ナンバーリンクソルバーをアップしてみた bit.ly/tprX41 [要出典] [Espeon]
→
ttps://github.com/imos/Puzzle/tree/master/NumberLink かなり時間掛かってる。一問解くのに1日くらいは余裕で掛かりそうな感じ。
高速なソルバーだとどれくらいで解けるもんなんだろう。
ttp://http://www.geocities.jp/takeiteasy_idontthinkso/puzzle/numple/index.html 数独解くのなんだけど
このアルゴリズムどう？
残念ながらシェアウエアみたいですが
ttp://cl-informatik.uibk.ac.at/software/puzzles/ ここのmasyu.jarに外部プログラムから問題データを流し込んで解答ソルバーを自動実行させて、問題が解けるかどうかの返り値を得る。
そんなプログラムって作れる物ですかね？
問題の自動生成については、質ははっきり言ってしょぼい。
ソルバーも使いにくいし。
まあ、アプリのメニュー等の日本語翻訳に協力すれば、
謝礼としてライセンス無料でもらえるみたいだし。
（翻訳すべきところはすべて１つのファイルに納められてる）
ttp://http://katahiromz.web.fc2.com/xword/ 無料でクロスワード自動作成。二重マス対応。高速化。
7x7があっという間に作成できる！？
ttp://http://katahiromz.web.fc2.com/xword/guide.html それと仲良く会話したいならTwitterでもしなよ
お願いします。
少なくともループコースパズルは解く気になれない
ver1.0にしてから来い
あとソースコード読みにくい
ttp://http://xword.squares.net/ ttp://http://katahiromz.web.fc2.com/xword/ 英和単語データ追加。二重マス単語がタイトルバーに表示されるようになりました。
パズルに限った話ではない
何でもかんでも辞書から持ってこればいいってもんじゃない
クロスワード雑誌買って使われている言葉を見てみなよ
マスコミで書き換え対象になっている言葉を
わざわざ出さなくてもいいんじゃないかな。
そのソフトでいくつでも盤面は作れるのだろうから
きれいな言葉が並んだものを選んで載せておいた方がいい。
うまくない例えだけれど、食品のパッケージに虫の絵を使っているような感じ。
気にしない人は気にしない、だけど絶対に手に取らない人も出てくる。
ユーザを増やしたいならそういうところに気を遣っても損じゃない。
お前なんか勘違いしてるけど、
ギバー同梱の単語リストには日本語・英語毎に二種類(「ドカタ」等もアリな自由Verと謹慎Ver)あるからな？
実験用と実践用に分けて用意してくれるだけ良心的だろ
そもそも10x10の時点でかなり重い(＝ミニサイズ用途にしか使えない)から、投稿用の単語フィルタとか考慮する意味は薄いけどね
印象がいいんじゃないかという話なんですけれど…
どうやら関わらないほうがいいようですね。
のソフト
TOPページの画像に放送禁止用語
そんなソフトなら何も言わないか嘘のレビューして淘汰されるのを待てよ
冷静に考えると些細な問題だよな……
そんなにいいソフトなのか
>10x10の時点でかなり重い(＝ミニサイズ用途にしか使えない)
別に俺の美術館ソルバーを事細かく紹介してもいいけど、
この状況でそこまで暇なことはできないよね……
ttp://http://katahiromz.web.fc2.com/xword/ 線対称や点対称の凝った黒マス配置もできますよ。詳しくは
付属の技術文書をご覧ください。
黒マス配置してからだと10x10でもすぐ作成できることがありますよ。
単に他の話題がないだけ
黒マスだけでなく、文字についても初期配置できるようにしてほしいです(特定ワードを埋め込みたい時に)
このソフト使う気？
個人で楽しむ分には良いだろうが、これで投稿しようと思わない方が良いぞ
今作成中です。１週間ほどお待ちください。
を大型体重計に一人ずつ乗せていってその都度重さを確認しながら総重量500kg±1kgにできる確率が一番高い手順を求めたいのですが
どうすればよいでしょうか？なお上限を40人とし、体重のキログラム未満は考えないものとし誤差分布は平等としています。
無駄が出ない組み合わせを計算させたりしてたな
普通にナップサック問題だけど、数が少なければ力業で解ける
ちょっと数が増えるとすぐに解けなくなるけど、
厳密解である必要も無いので、適当に数を絞れば簡単に解ける
それって最小二乗法的な解答を求めてるんかね？
±を無視してナップサック問題を解くと「14＋9×54」(皆の価値が均等)か「23×21＋17」(価値が体重比例)
になっちまうから難しい……
あればその中で誤差最小
無い場合の評価が難しいな
まあ、あるんだけど
人力で考えれば、大きい子供で選択肢を温存しながら総重量を増やしていって、500kgか40人に近付いてきたら誤差の少ない小さい子供に切り替えていく方法が一番良さそうですがちから任せ探索かバックトラックでも大丈夫です。
その場合上の例ではどのようなプログラムになるのでしょうか？誤差を評価しながら枝刈りしようとしてつまずいてしまいました
この程度の数なら一瞬で解ける
14*28+9*12が最小
計算は2秒かからない
ぴったり40人で計算してた
17*2+14*32+9*2 かな
ちなみに500±1kgに収まる確率はどう出たでしょうか？
よろしければプログラム拝見して参考にさせて頂きたい
$min = 100;
for ($n1 = 0; $n1 <= 40; $n1++) {
for ($n2 = 0; $n2 <= 40; $n2++) {
for ($n3 = 0; $n3 <= 40; $n3++) {
for ($n4 = 0; $n4 <= 40; $n4++) {
next if $n1 + $n2 + $n3 + $n4 > 40;
next if $n1 * 23 + $n2 * 17 + $n3 * 14 + $n4 * 9 != 500;
$score = $n1 * 6 + $n2 * 4 + $n3 * 2 + $n4 * 1;
if ($score < $min) {
print "$n1 $n2 $n3 $n4 $score\n";
$min = $score;
}
}
}
}
}
例えばで14±2kgを25人乗せた時点で最大値である400kgだったら次から9±1kgを乗せたほうがいいんじゃないかとか
バックトラックでも厳しい計算量でしょうか？
チェスの対戦プログラムみたいな感じで、その場で入力しながら、
最善手を探すような実装になるのでは
ver.1.2で未登録単語の処理を追加しました。
未登録単語を使うときは、きちんと端を黒マスで閉じてください。
乙でした！
ttp://up3.viploader.net/pc/src/vlpc014174.png 「フケ」はまずかったかな？
ヨウケン
ウレツコ
カイケン
キンユウ
メリツト
シンケン
キユウジツ
ヨウキユウ
ウシ■ウチ
チヨウシヨ
ヨクジヨウ
右下が「ん」の4×4のフィールドに同じ文字を使わずに4文字の言葉8個作れとか
(あれ、これって数え切り問題にならね？)
あなたは逆コンパイラを作る作業に戻って下さい
6
aaaabb
cccdbb
ccceef
gggeef
hhhiii
hhhiii
2
0
1
-1
0
-1
2
2
2
こういう形式の、へやわけの問題ファイルを拾ってきたけどペンシルボックスで動くように書き換えるスクリプトってありますか？ 3000問あるんですが・・・。
ttp://http://www.dotup.org/uploda/www.dotup.org4829887.zip.html 「クロスワード ギバー ver.1.4」Windows用
ttp://http://katahiromz.web.fc2.com/xword/ 簡単そうなら作るけど
ペンシルボックス形式ってどんな形式だっけ？
すぐ修正する。
今日はもう夜遅いけど数日待ってくれるなら作るよ
出来た
ttp://www1.axfc.net/u/3156448.zip?key=sage 使い方は中に説明書があるけどわからなかったら聞いて
ありがとうございます。変換できました。
また何かありましたら、よろしくお願いします。
「クロスワード ギバー ver.1.5」Windows用
ttp://http://katahiromz.web.fc2.com/xword/ ttp://http://www.menneske.no/hashi/eng/ 「橋をかけろ」 366474問って何だよｗｗ
お絵かきロジック・ソルバーを作っていますnekoppy3と申します
僕のレベルはどれくらいか腕試しにきました
OSはウブンツですが
twitter : @nekoppy3000
mail: nekoppy@gmail.com
HP:
ttp://logic777.web.fc2.com/ よろしくお願いします
PCのスペックの問題なのか解くの遅いような気がする
loginekoとロジック・アーティストを試したことあります
彼らにはかないませんでした
ttp://www.puzzle-bridges.com/task.php?id=1&size=11 「橋をかけろ」の問題画像データ（PNG）からテキストデータに変換する。
ピクセル単位の色情報を取得して型にハマったら「１」とか変換すればいいのかな？
幸い画像上の数字の大きさとか形状は同一のようなので融通は利きそう。
HSPで「美術館」画像のOCRなんてのもあるみたいですね。
loginekoって謎の速さだよね……
データインポート辺りが割りと糞だけど
苛ついた挙句、仕様書ひっくり返してこんなものを作ってしまったレベル
ttp://http://www.vector.co.jp/soft/win95/game/se497399.html ちな、そのOCR作ったの俺。最近じゃソルバの方もうｐしたから試してみてちょ
ttp://http://www.vector.co.jp/soft/win95/game/se503886.html サイトからデータを抜く話をしてると本人がいる可能性もあるのかぁ。
おっぱい研究お疲れ様です！。
それは音伎さんに言ってやれよ。まあどうやって労えばいいか分からないのが残念だが
あれの元ネタは御存知の通りWebアプリだが、ソースが酷すぎたのにキレて書き直した記憶がある……
ttp://http://ysrken.blog.fc2.com/blog-entry-43.html(注：サイト更新してなくてスマン) ttp://http://ysrken.blog.fc2.com/blog-entry-44.html(同上) ちなみに、このアプリ(と元ネタ)に言えることだが、パラメータの根拠に疑義があるようだ。
詳しくは以下のレスを参照。祇条さんかわいいよ祇条さん(ID:qR2KRckzが俺)
ttp://toro.2ch.net/test/read.cgi/gal/1369674241/637-644 「クロスワード ギバー ver.1.6」Windows用
ttp://http://katahiromz.web.fc2.com/xword/ イラストロジックの問題に変換出来るようにして、出版社にイラロジ問題の
アマチュア投稿作品として連投すればいいのでは？というアイデアが浮かんだ
おっとドット絵（白黒）→イラロジ変換は俺が既に作ったのがあるぞ
ttp://http://www.vector.co.jp/soft/win95/game/se497399.html とは言え、LogiNeko等の編集ソフトを使って調整しないとマトモな問題にならないがな……
せめて、「唯一解が出る」「人類が解ける程度の難易度」であることは確認しようぜ
WINじゃなくてLINUXなのがネックですけど
ttp://logic777.web.fc2.com/ ＞＞「唯一解が出る」「人類が解ける程度の難易度」であることは
このへんはクリアできると思います
なんだ、既に出来たドット絵を変換したいんじゃないのかよ……
と言うか試しにDLしてみたがファイル数多すぎワロタｗ
ソースも67ファイルある＆中身がマジックナンバーだらけだから解析するのが大変でござるorz
メインのプログラムは、白黒解析がm246j.c
白黒データファイルがmno（解析はそんなに難しくないはず）
bmm.cがランチャーです
Wineとか多分無理＆マシンが非力と思います
ところでソッチの環境ってC++もコンパイルできる？
ちょっとC++で*.mnoを解析するプログラム書いてみようかと思うんだが
m246j.cのなかにvoid mno_open1()見たら解析できると思います
そろそろ帰らなくちゃ。家ではネット環境がないもので・・・
遅くなったがとりあえず完成。標準入力からファイル名を読ませるだけの簡単仕様だよ！
まあ最適化はまだしてないから遅いけど、全部C++だから覚悟してね！
ttp://http://codepad.org/aOQa0tXh ちなみに開発環境はVS2013、64ビットコンパイルして実行。i5-3210M・シングルスレッドで121118C.mnoを
29.001ミリ秒で解く程度の能力がある感じ。これってやっぱり遅いのかな？
……ところで、なんでコメントでの説明では数字区切りがカンマなのに実際のファイルはピリオド区切りなんですかね（憤慨）
入れられないです。
１６年前PC-9821で作ってころはカンマでやってて、ここ３年間で
再開したときに外付けテンキーボードがピリオドだったため
if(ch==','||ch=='.')とすれば回避できます。スマソ
昨晩、親父のネットブック借りてx86のatom1.6Ghzで前もって作って
おいたmno->lgdコンバーターでloginekoさんとの比較してみた
131313A.mno～131313G.mnoまで70x180のサイズが僕のやつは３０～５０秒
loginekoさんは0.3～0.8秒違いすぎる
mno->lgdコンバーター(log2.cの方がloginekoさん
;log1.cはロジック・アーティストさん）
ttp://logic777.web.fc2.com/logineko_conv.zip でうまくいくかな?
家帰ってbcc5.5で試してみます
Visual C++ 6.0 もう捨てたかも知れんね３万円も、したのに
最近のVS環境はネットひいてないとインストールできなかったと思う
・今時ネット環境はあった方が便利だと思われ(やっぱり無いと不便)
・今時Borland C++ Compiler 5.5は「古い」(規格準拠的な意味で)
ttp://http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q10119943595 ・いまどきのVSは無料(ネットからDLする形)。iso形式ならネットワーク無しなPCでも
インストールできる(isoファイルを別途ダウンロード→CDかDVDに焼く→インストール)
から、そちらを使ってみては？
参考：
ttp://http://homepage2.nifty.com/nonnon/Chinamini/20110001/20110308.html ttp://http://www.microsoft.com/ja-jp/download/details.aspx?id=40787 ・ただしVSは世代によって使えるVerが違うから注意。そちらの開発OS(Windowsの)は
知らないが、VS2012以降はWin2008ServerR2・Win7以降でしか使えない。
要するに古いOSならVS2010が限界なはず。
(ちなみにVC++6.0はVista以降では使えない)
参考：
ttp://https://www.microsoft.com/ja-jp/dev/support/tools.aspx ・そもそもgcc使えるんならg++でC++のコードをコンパイルできるんじゃね？
しかも今は規格準拠度が高いClangがあるじゃん……
参考：
ttp://http://kaworu.jpn.org/cpp/g++ ttp://http://ja.wikipedia.org/wiki/Clang ttp://http://katze.hatenablog.jp/entry/2014/01/07/180330 の改良版はもうちょっと待っててね
ネットブックのOSはXPです
そうですよね。g++使ったことないけど試してみます。manとかしたり
ここのネット環境でいろいろ調べてみます
参考URLありがとうございます！
ふと思ったんだけど大学とかでネットしてんの？それともネットカフェ？
はうまくいかない
while(getline(csvin, BoardNumberString, '.')){
で。mno問題のほとんどがピリオドでカンマはめったにないです
getline関数はcsvinを一度読みこむと次の読み込み位置に移動するみたい
Linux mint 14, atom1.6GHz NECのネットブック((デュアルブートでwin XP))
$ g++ -o solver solver.cpp -std=c++11 -O2 -lGL
でいけました
121118B.mno 30x30 クリリン 1145674ms
121118C.mno 30x30 ロイ・マスタング 147112ms
121118D.mno 30x30 スニフ 193859ms
121118E.mno 30x30 ねずみ男 965241ms
go46.mno 25x25 マジンガーZ ,を.に置き換えが必要 464685ms
120718A.mno 40x35 トトロ ３分間放置
110814A.mno 70x80 屋台 ３分間放置
110818H.mno 50x50 犬はりこ ３分間放置
110529b.mno 40x45 オフロードバイク ３分間放置
110614a.mno 20x20 イチゴのショートケーキ 37792ms
40x40のあたりが壁のようですね。僕も最初のころはこのへんが壁でした
micro second(マイクロ秒)をms(ミリ秒)と間違えてないですかねそれ……？
確かに大きな問題になるとキツいので改良は必須でしょう。頑張ってみます
ttp://www.pro.or.jp/~fuji/puzzlestudy/HashioKakero.C このコードをJAVAに移植しようと考えている。
C言語もJAVA言語も全くのド素人初心者なのですが、
特に、private void LinkBridge( void ) で何を行っているのか意味不明です。
元もｇ++でコンパイルできないしｗ
>C言語もJAVA言語も全くのド素人
じゃあなんで移植しようとしたんだよ……
>ｇ++でコンパイルできない
なにそれｋｗｓｋ
と言うかコメントに偽りありじゃん……ありじゃん……
何だろう C/C++ が出来る気がしない。次に早そうなのがJAVAだからｗ
拾ってきたコードの C/C++ エラー率が高い。意味が分からないから直せない。の悪循環
時代はＪＡＶＡですよね。
それは流石に甘えというもの
と言うか本気で動かしたいならエラーでググるぐらいするだろと
いろいろやってみたけど、ＪＡＶＡ、Ruby、Python、Perl、D、とかは何となく動いたｗ
まあリンク先のは拡張子が.cなクセに思いっきりC++の文法で書いてるしね……
（しかもC++なのに「iostream.h」等と書いている。これは時代のせい？）
void HashioKakero::LinkBridge( void )は日本語にすると
「HashioKakeroクラスの、外部からアクセスできない引数・返り値なしの関数」
なんだが、JavaもC++も分からんかったらちんぷんかんぷんだろうなｗ
その状態じゃ、移植どころか読み解くことすら無理だから、
先に入門書買うか入門サイト読むとかして勉強するべきかと
ちなみにHashioKakero.Cだけじゃ当然動かないよ。書いてあるとおりHashioKakero.hも必要
(そもそも#includeすら分からないって、本気でC言語も勉強してないんだな……)
ポインタが怪しいのにポインタのポインタは・・・・。
どっちが行でどっちが列なのかが。
iostream.h iostream ＜＞ ”” は、確かに違いがわからない。
そこで移植ですよ。ネットで構文検索しながらJAVAに移していく。
動かなくても移し終わる頃にはパズルの考え方が理解できて他にも応用が利くはず！
動かないけどｗ
言語に関する知識が足りないのに移植とかﾃﾗﾜﾛｽｗｗｗｗ
大文字の.CはC++だし.hは時代のせい
ところでそのコード使っていいの?
著作権表示だけがある状態だから原則上は使えない
その人の会社はパズルのアルゴリズムに関して特許取ったらしいし
この分野に関わる人は見てはいけないものかもしれない
ttp://http://puzzle.gr.jp/show/Japanese/Event/2007AkibaPress 1から作れば移植する必要はないよ！やったね！
tableとonClickでやるどこかに似たようなGUIのやつあったべ。
あえてJava使ってそのうちAndroidアプリにしたいとかならあえて止めないけど
暫定的な修正版。別のページを参考にしたらあっさりできた（もちろん改良予定)。背理法最強伝説
ttp://http://codepad.org/RYBb423Y 参考：
ttp://http://infosys.sys.i.kyoto-u.ac.jp/~ken3/IL/index.html 病院来るときは、DynabookAZです
Dynabook AZ (ARM Tegra250 1.0Ghz, Lubuntu13.04)
マイクロ秒は「us」と表記していいみたい
24,689,813usと書いていれば２４秒と見えるようわかりやすく書きます
Ver.1(), Ver.2()
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（４分）
のソース見て、今までc++書いたことないけど、見よう見まねで
いじくってみようと思う
ttp://http://www2.ocn.ne.jp/~minui/illulogi/index.htmlを書いた apostata氏（？）に差し入れしたいレベル。
ttp://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
問題の絵の名前か・・・と思い至ったときホッっとした。
今からソース貰って試してみますわ。ありがとう！
38,949,227[us]で解いたぞ……メモ化の威力が凄すぎる
70x180サイズに挑戦
さんの 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++って速いんだな～驚愕する
ttp://www.ic-net.or.jp/home/takaken/nt/logic/index.html ここのは古い感じなの？
>C++
まあC++使うのは趣味も半分ですけどねｗ
カプセル化とかに慣れれば（C言語よりは）良い言語ですよ……
そうでもないと思いますよ。ぶっちゃけググって上の方に出ていたページを
参考にしただけですからｗ
私が使ったアルゴリズムは普通に背理法で、
「列または行毎に、『あるマスが■だとして矛盾が出れば×。あるマスが×だとして
矛盾が出れば■。そうでない時は放置』として確定させる」というものです。
矛盾の判定は、「ヒント数字の置き方が1通りでも存在すればOK」といった感じなので、
そこだけより良いアルゴリズムに差し替えても構わない仕様になっています。
ttp://http://www2.ocn.ne.jp/~minui/illulogi/index.htmlの場合、その判定を キャッシュ（メモ化）によって大幅に高速化しています。これがカラーイラストロジックに
使えるかまでは分かりませんが、スマートな発想だと言えます。
（そうしないと超難問に対応できないと思われる）
＞＞更に人間が解くみたいに「更新があったマスを含む行列を優先的に見る」
それ必須と（出来れば、過去の行列の時間測定から速い順で行列を行う）
ある行が１０こヒントデータがあるとして
１～３番目と８～１０番目が既に確定している場合
４～７番目のみ調べるようにする
僕のは実装してますけど６０８さんのは、まだまだ速くなりますよ
ってのは無駄な計算かな？
手作業で解くときはよく使うけど。
＠：黒
ｘ：白
＿：未確定で
１２３４５６７８９０１２３４５６７８９０
ｘｘ＿＿＠＿＿ｘｘｘｘｘｘ
のときに３～７まで４つ入るって分かってたら
１２３４５６７８９０１２３４５６７８９０
ｘｘ＿＠＠＠＿ｘｘｘｘｘｘ
なんてのを実装すれば速くなりますよ
トップに出てくるサイトの
「Section 4 存在仮定法」っていうの僕のには実装していないから遅いのかも。
演繹法は、やっています。
皆さんの意見も参考にして、とりあえず組み直してみますね。
ちなみに私、イラストロジックの問題ファイルを相互変換する
ソフトを作ったことがあったりしますｗ
ttp://http://www.vector.co.jp/soft/win95/game/se497399.html :::::::: :.: . . /彡ミ゛ヽ;)ヽ、. ::: : :: で既に書いてあるのに宣伝がましくてごめんなさい
::::::: :.: . . / :::/:: ヽ、ヽ、i . .:: :.: ::: 言い訳ついでに書くと、アレを作った時はパズルを解く方がメイン
￣￣￣（_,ノ ￣￣ヽ､_ノ￣ でして、幾つかソフトがあるのに互換が効かないのに戸惑った
から作ったという経緯があります。一番面倒だったのはLogiNeko形式で、
目一杯容量を削った代償にチョー複雑なファイルフォーマットに四苦八苦しながら開発しました。
そのかいあって、画像インポート機能がないLogiNeko相手にも、こいつを噛ますことで擬似的に
画像インポートさせることができるんですよｴｯﾍﾝ、というのがささやかな自慢です。
まあ勝手に作ったソフトなので各ソフト作者からは連絡も何もありませんが、ちょっと寂しい気もしますね。
ttp://http://codepad.org/ZC3MxCc9 (注：mno形式) 注：元データは、昔某所に貼られていた問題をテキスト化したものです。
--------------------------------------------------------------------------------
【けいおん！】田井中律は目指せﾊｯﾋﾟｰ100％【ﾄﾞﾗﾑ】
ttp://changi.5ch.net/test/read.cgi/anichara2/1254827509/">
ttp://changi.2ch.net/test/read.cgi/anichara2/1254827509/ 38 ：名無しさん＠お腹いっぱい。：2009/10/06(火) 20:31:45 ID:2Pg/phyn
ttp://nagamochi.info/src/up39860.jpg 解答
ttp://nagamochi.info/src/up39861.jpg 49 ：名無しさん＠お腹いっぱい。：2009/10/06(火) 20:37:07 ID:2Pg/phyn
プログラム作って唯一解であることを確認済みです
難易度は上級です（いわゆる上級テクニックが必要）
--------------------------------------------------------------------------------
ttp://http://www.syu-ta.com/blog/2009/10/07/015131.shtml (
ttp://http://web.archive.org/web/20130426174102/http://www.syu-ta.com/blog/2009/10/07/015131.shtml) 問題画像：
ttp://i.imgur.com/KepEOB8.jpg 正解画像：
ttp://i.imgur.com/IEIA0RH.jpg ttp://http://plaza.rakuten.co.jp/nekoppy3/diary/201208100000/ 中学生がスパコンで魔方陣を解いたアルゴリズム。とか
中身を見ても居ないし想像もつかないけどワクワクするね。
>中身を見ても居ないし想像もつかない
いや見ろよ
前者のJavaコード付き解説：
ttp://http://d.hatena.ne.jp/nowokay/20120911 ttp://http://d.hatena.ne.jp/nowokay/20121015#1350267331 ttp://http://d.hatena.ne.jp/nowokay/20121016#1350351212 ttp://http://d.hatena.ne.jp/nowokay/20121017#1350435805 ttp://http://d.hatena.ne.jp/nowokay/20121018#1350528607 ttp://http://d.hatena.ne.jp/nowokay/20121019#1350607290 後者の解説：
ttp://http://pc.watch.impress.co.jp/docs/news/yajiuma/20140303_637771.html ttp://http://www.ccs.tsukuba.ac.jp/pr/media/140228_press それ作った本人参上
大まかに説明すると、解き方は大きく3段階に分けられて
まずは1段階だけで解き、完成しなかったら次の段階へ行く
3段階で解けなければ不成立か重解
どの段階まで使ったかを見れば難易度も分かる
GUIの部分が今の自分の環境では動かないから試せないけど、10秒程度で解けてた
あとカラーロジックにも対応している
>それ作った本人
＿人人人人人人人人人人人人人人＿
＞ な なんだってー！！ ＜
￣^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^￣
_,,.-‐-..,,_ _,,..--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：
ttp://i.imgur.com/11pOciw.jpg（元絵） 
ttp://i.imgur.com/fhWpz5E.png（問題） 
ttp://i.imgur.com/F71MutP.png（解答） 最近作ったもの2：
ttp://i.imgur.com/rMqisle.jpg（元絵) 
ttp://i.imgur.com/eQRDIWB.png（問題） 
ttp://i.imgur.com/vOp1hgq.png（解答） 理論をちゃんと理解してないのか
Dynabook AZ (ARM Tegra250 1.0Ghz, Lubuntu13.04)
田井中律 100x100 ()
僕の mx46j 14.99秒 だけどお腹のあたりが未確定で解けない
さんのVer.3 5.30秒 だけどお腹のあたりが未確定で解けない
けいおん 60x100 120819E.mno
僕の mx46j 11.11秒
さんの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秒 ドガのエトワール
さんの 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 は背理法を白から始めているせいか
白っぽい絵は解くのが早いけど
黒っぽい絵は遅い傾向があるんじゃないかと思う
ttp://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
ttp://http://codepad.org/95H0X1Cb (注：mno形式) 注：元データは、昔某所に貼られていた問題をテキスト化したものです。
--------------------------------------------------------------------------------
けいおん！紅茶715杯目
ttp://changi.5ch.net/test/read.cgi/anime2/1264864946/">
ttp://changi.2ch.net/test/read.cgi/anime2/1264864946/ 24 logic sage 2010/01/31(日) 00:39:52 ID:hFZ5c2QD
キャラスレが過疎ってるようなのでこっちにうｐ
イラストロジック
ttp://changi.5ch.net/test/read.cgi/anime2/1264935488/">
ttp://changi.2ch.net/test/read.cgi/anime2/1264935488/ 410 logic sage 2010/01/31(日) 23:55:52 ID:hFZ5c2QD
問題
ttp://nagamochi.info/src/up59052.jpg (cache) --------------------------------------------------------------------------------
ttp://http://www.syu-ta.com/blog/2010/02/01/004724.shtml (
ttp://http://web.archive.org/web/20130426200910/http://www.syu-ta.com/blog/2010/02/01/004724.shtml) 問題画像：
ttp://i.imgur.com/fd908c0.jpg 正解画像：
ttp://i.imgur.com/uK23uxW.jpg (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]
の言うバックトラックは、20091007k-on01.mno のような解けない問題に
Ver.4のソースの後にバックトラック・プログラムを追加すればいいと思う
高速化でよく聞くのは、１次元配列化・ビット演算。
何かすごい計算方法が眠って居るんだろうなぁ。
縦・横ときたらナナメ！ 上下に分割して！ 意味不明
ソースのコメントにも書いてますが、下手にCに近くすると(コードを最適化しすぎると)、
デバッグが大変になるので(まだ)やる気はありません。それにこのパズルの場合、
盤面をビット表現すると縦横が65マス以上になった際を考慮するのが面倒くさいということもあります。
また、アルゴリズムの良し悪し(オーダ)＞コードの最適化具合(係数)なので、
C++でバッチリ決めた後にボトルネックを最適化しようかと思います。
(あるパズルで)
ところで、ソルバーは1秒云々のソースはどこにあるのでしょうか？
平均して2割ぐらいは速くなる、はず
ttp://http://codepad.org/N2UwGvhq とりあえず「イラロジヘルパー」(
ttp://http://www6.ocn.ne.jp/~b-lab/txt_lib/)の「*.lgs」形式には対応させました。 パターン認識みたいなことをやってた
あるマスが決定すると他のマスも次々に決定する時、「影響度が高い」と言う
この「影響度」を未決定の各マス毎に計算し、高い順に仮決定していく
影響度の計算式がカギ
「*.lgc(LogicLand)」への対応を追加し、更にバックトラックを試験的に導入しました。
その影響でコマンドライン引数が微妙に仕様変更されましたのでご了承下さい。
(ファイル名のみだとバックトラック無し、ファイル名の後に正数を書くとその段階までバックトラック)
ttp://http://codepad.org/byX1WiQJ 影響度ですか……実装を検討してみます。
修正版を上げておきます。
ttp://http://codepad.org/3PzprA51 美しいソースじゃないからなのかな～？
それともC++には高速演算に向いているのか、僕にはわからない世界
でも今まで解けなかった問題が存在仮定法を使うと２問ほど解けた
（２つとも70x180位のサイズで)
その２問の問題。「先生たち」と「ポケモン、ジオリジン」
ttp://logic777.web.fc2.com/i/140408a.zip 相変わらず凄まじいコードだな……
書き方が違いすぎてまるで暗号だぜHAHAHA(別に悪い意味は無い)
さて、のおまけとして、ファイルコンバータを上げておきます。
具体的には、*.mno・*.txt・*.lgc・*.lgsを相互変換できます。お試しあれ
(まあヒント数字以外の盤面情報はlgc形式しか保存できないんですけどね……)
ttp://http://codepad.org/mCPTln3E ちなみに当方のプログラムはUnicodeを考慮していません……ご了承下さい
誤りがあることが発覚しました。謹んで訂正いたします。
修正版：
ttp://http://codepad.org/cyziWoZX 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
(訳：全然変換できないようわああん！)
画像から自動的にトレースして検算結果も出せるエディタできたよー！
ttp://i.imgur.com/l01KL4k.jpg ……手動編集機能はまだ付けてない。とりあえず試験的にうｐ
インターフェースが使いづらいだろうけど今は我慢してくだしあ
(エンターキーで出力画面を画像としてセーブ可能)
ttp://http://www1.axfc.net/u/3219410.zip 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}
だったと思う。間違えてたらごめん
普通の演繹法の内部で背理法が存在仮定法で
普通の演繹法の外部で背理法を行ったのが僕のやり方でなんとか解いた
（いきあたりばったりで滅茶苦茶だけど強引に解いた）
白マスも幅・高さ・ヒントからある程度の推定が出来ますよね
白マスの推定ってのは強力な枝狩りにはなりえない？
縦の可能性・横の可能性から接点の可能性を絞るってのは無駄？
X:白
@:黒
_:未確定で
３～１２の間に＠が３つ入るって分かっていたら
この場合わかりやすいよう３つの後は３０ことかで３０こは３～１２
に入らないものとする
123456789012345
XX___@______XXX
123456789012345
XXx__@__xxxxXXX
小文字のｘが新たに入る白マスってわかります
二番目以降は、CacheX={(1)Unkown,(2)BlackにWhiteの上塗り->Unknown,
(3)WhiteにBlackの上塗り->Unknown}
だったか。
演繹の終わりに、１回以上配置成功の場合
CellList=CacheX(ただし、Unknownはコピーせず、BlackとWhiteをコピー）
また間違ってたら、ここに書きこむわ
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のスイッチ付けてなかった
！！！？
gcc(g++)で-O2をつけるとSSE(x86),NEON(ARM)に最適化するらしい。
mx46j.c(ARM)は速くなったけどm246j.c(x86)は、さほど速くならなかったなあ
横から申し訳。猫 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ちょい)
え？リリースビルドって普通-O2にするもんじゃないの？
……まあ、コンパイラによってデフォでの最適化方向は違う()けどね
メインプログラムがm246j(mx46j)ね。リア友じゃん
やっぱバレたか
一応、irx86 と irarm とir の引数も変えてますがこれじゃ不味いすか？？
僕は猫さんに怒られながらrenice でプロセス優先度を-20にする時があります
邪道と言われますw
つか、猫さんのあずにゃんで動かしたさんのぷろぐらむ見せて貰ったけど爆速吹いたす
猫さんに書いちゃダメて言われてたけど、約束破って書いちゃったす
木曜日に１人じゃねえとプログラム書けねえつーから早退したす
猫さんが２ちゃんねる書いて楽しそうにしてるからROMるの楽しいす
アンパンマン嫌いです
それはともかく、の改良版が出来ました
ttp://i.imgur.com/tFXuP8b.jpg 
ttp://i.imgur.com/qobsjHo.jpg 動作原理としては、自動トレース→盤面データをdllに送って解析→
結果を元に手動で修正、といったところ
2枚目のように、未確定部分は黄色で表示されるので楽に書けるのが(・∀・)ｲｲﾈ!!
真面目にVectorに上げる予定なのでここにうｐするのは難しいかな……
おはようございます
サムネ見たら凄すぎふいたす
$ ./irx86
or
$ ./irarm
の初期でbmm or armbmm のlauncherを作り、
その後、ir から必要な.cを沢山引数をつけつつ、ずらーっとコンパイルする仕様なのです
バリバリ猫さんの俺様仕様す
猫さん、プログラムやめるて言ってたけどあずにゃんを無理矢理買わせ。汗
無理矢理開発させている
のはボクです(爆)
>>猫さん
ずっぱ●いわく、SSEはインラインアセンブラで書いた方が速いらしいす
今日は、 の70x180>一万ドット越えの問題
(biglogicに収録してあるのは６０～７０問、未収録は他に１０問くらい）
の時間計測したり、
の未解決問題をすんなり解く方法の模索をしようと思っています
中電さん、ウチワ受けする話が多すぎです
バッチファイルのirの中身いじるだけでいいんじゃね？
さんの (Ver.6)とmx46jl.c(ともにスイッチ-O2)
ttp://http://logic777.web.fc2.com/ にある、biglogic_j140330a.zip に収録してある、１万ドット越えの問題の演算比較
時間単位は[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 キャラ８匹
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 海外ドラマ
さんの (Ver.6)とmx46jl.c(ともにスイッチ-O2)
ttp://logic777.web.fc2.com/ にある、biglogic_j140330a.zip に収録してある、１万ドット越えの問題の演算比較
時間単位は[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 歌舞伎、５人か？
昔貼られてたヤツのソースを見つけました。
Simon Tatham's Puzzle Collection
ttp://code.ohloh.net/project?pid=6dCunV7fspU&cid=ZJt1JK_7eXs&fp=299756&mp=&projSelected=true js版もありましたがコードが２万行もある；； わけわかめ
流石にjsで2万行とか頭おかしいとしか……
別の言語から自動変換して難読化とかしてあるんですかねｗ
ニコリのパズルの自動生成・自動解答への夢は遠い・・・
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)とき、白優先で白から仮置き
(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,黒に決定
このあと全部解けた
今段取り悪くて１５００秒かかるんですけど
双方向リストにして各ノードに盤面コピーして高速化を図りたいと思います
つまりバックトラックは2段階で十分ということか……
ちょっとプログラム見直してくる
作ってみた
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秒
昔というのは>483かな
そのページに書いてあるけど元がCで他はコンバートみたいよ
jsは見たら
ttp://emscripten.org/ 使ってるみたい ４つかどの背理法でどっちつかず(n1=n2=0)のとき、黒優先で黒から仮置き
４つかど以外の背理法でどっちつかずの(n1=n2=0)とき、白優先で白から仮置き
訂正
４つかど以外の背理法でどっちつかずの(n1=n2=0)ときも、黒優先で黒から仮置き
田井中律９０度回転させて４つ作ったんだけど
全部解析パターンも違うし、解く時間も違う
オリジナル １１８秒
左９０度回転 ２６６秒
１８０度回転 ２６２秒
右９０度回転 途中で異常になって解けなかった
遅いのを速くするのは、またアイデア絞ってみます
解けない謎を解明したい
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 ガンジー
解けない理由（仮説）
誤った盤面（ノード）で(X,Y)=Unknownを見つけ出すから
仮置き背理法で、黒でも白でも大きな変化がない個所を
何回もつかまされると、リカバリーに苦労する
あらかじめ大きな変化があるところを探す
その場所とは、
（１）４つかど
（２）４つかど付近
（３）４つの辺
（４）２択・３択・４択
（５）その他
初心者がまず手を付けるべきパズルって何ですかね・・・。
いや、何が悪いのやら……(hissiで見ても他にレスが見当たらない)
>初心者がまず手を付けるべきパズル
自分が解きたいパズルを選べばいいと思うけど、
数独は9×9サイズならゴリ押し(バックトラックのみ)でも解けるから楽といえば楽かな？
動くという成功体験が大事ですよね。
ソルバーを作るならそのパズルが得意でないと手こずる
n国同盟とかX-wingとかが上級問題になると必要になってくる
いや、9x9なら普通に解けるよ。証拠にソースを上げておく(拙いものだが)↓
ttp://http://codepad.org/0sqgRLH3 それより大きくなると手筋必須。
ttp://http://www2.tokai.or.jp/deepgreen/shortnotes/numberplace/algorithm.htm に載ってたEnclosure関数を実装してみた結果がこちら↓
ttp://http://codepad.org/qThGei4K ttp://karetta.jp/book/cpuzzle-recursion ここのナンバープレースをＪＡＶＡに移植し始めました。
第二段階の問題ファイルの読み込みでつまずいてますｗ
順番に理解していけば何とかなる・・・何とかなる。
ぶっちゃけ知ってるならC言語流に読むよりC++風に読むほうが簡単でミスもない気が……
と言うか9ｘ9前提でコード書いてるなこの人ｗ
ナンバープレースを解くことが目的なら
・サイズが9×9以外
・ブロックの形が正方形でない
・1～9の数字が1つずつ入るマスの組が他にもある（対角線など）
がよくあるから、それに対応させないことにしても拡張しやすいように作る
>ブロックの形が正方形でない
これを実現するために、ナンプレ自動生成エンジンでは
「マスの集合」を定義して認識する実装だと知った時は感心したものだ……
(つまり普通の数独では縦横ブロック合計27通りの集合、対角線も加えると29通り、
変形ブロックやカラー付きの場合はそれぞれに応じて定義可能)
新しいバージョンをお使い下さい。
ttp://http://katahiromz.web.fc2.com/xword/ 知恵を貸してくれ
イラストロジックの話が興味深くて少し実験していましたが
行き詰まってきたので公開することにしました
ttps://gist.github.com/anonymous/11100710 もし難問・奇問があれば欲しいです。よろしければください
９０度回転させてもバックトラック（あれでも、っていうのかなあ？？）
して解けるようになりました
あとはバクが潜んでいるか徹底的に見つけたいところまできました
逆に勉強させてもらいます。
動かせたら、また感想なり述べさせていただきます
僕なんか下っ端ですね
聞き流すから！！！
面白い方法があります
各ヒントデータに可動領域があって可動領域の開始位置と終了位置を
常に計算させます
長さが１０でヒントデータが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___
盤面の真ん中で７こ確定されれば、可動領域の開始位置と終了位置は
狭められます
初期段階では可動領域の開始位置と終了位置は、たいてい
他のヒントデータの開始位置と終了位置はかぶっていますが
どこともかぶらなくなると開始位置と終了位置は一意になります
演繹をするルーチンに開始位置と終了位置を渡すだけでずっと速くなると思います
a_b_cd_e_f
1(a-d),1(b-e),1(c-f)が可動領域です
の間違いですね
m246j.cで唯一の７を探すルーチンはuniqueing()
開始位置sst[]と終了位置eet[]を計算するルーチンは、qcheckt()です
汚いソースですいません。人に見られる前提で書けばよかったな～
念の為、確認してみた
マス＝？？？？？？？？？？
有限で一意なら出来るんでしょうね。意味ないだろうけど
LISPとか良さそうな気がするんだが
いずれは公開するつもりだったのですが
テスト用に問題を回転させるアイデアに驚いて早めました
テスト問題ですがランダムなドット絵を使い始めました
安定的に1秒程度で判別できるのは50×50黒6割で
黒が減ったり問題が大きくなると極端に遅くなります
100×100を10秒以内はまだまだ先のようです
ところでとても速いものをみつけました
ttp://sourceforge.net/projects/jsolver/ ソースが読みづらく説明もなくてアルゴリズムがわからないのが残念です
さん
120818C.mno が確か一番時間の掛かる問題であったかと思います
しかし5年前の C2D で1秒切ってますよ
ARM(Nexus 7(2012)) だと3秒ほどで爆速過ぎます
僕もランダムな絵の問題作ってみます
100x100は僕の力では１００秒かかります。この辺が限界ですわ、C言語で
C言語よりC++の方が向いてると思います。こういうの
ランダムなドット絵、裁縫のパッチワークをイメージした
元絵（131313A.mno～131313N.mno,サイズ180x70)のイメージから
ランダムに20x20の布切れを切り取り、100x100のサイズに貼り合わせる
というもの。布切れはランダムに90度、180度回転している
昨晩、作っていた。問題がほぼ無限に作れます
ttp://logic777.web.fc2.com/i/paw_mno140424a.zip 00001.mnoは１０００秒かかりました
00002.mnoはまだ解けていません
n1=n2=0（黒と白の仮置き、どちらでもOKのとき増え方がどちらも
２００ドット以下の時、リスト構造を枝刈りしてもうまくいかないです
５００ドット以下の時、枝刈りにしてみます
データの受け渡しに便利ですよね。
理屈から言えば、長さがnある部分のヒント数字は
最大n/2個(nが奇数なら(n+1)/2個)必要なので、
100x100固定なら50×100×2＝10000個の数字枠が必要になります
charでも10KBは必要ですね
00001.mnoから00010.mnoをtxtにコンバートして動かしてみた
$ ./js1 00005 // mno->txt converting, original program
$ ./jsolver -n 2 00005.txt
どれも２秒もかからない
ttp://logic777.web.fc2.com/i/js1.zip No. (X, Y)
１ １ １ 両方OK黒から 黒８６３ドット白０ドットの増加分
２ １ １００ 両方OK黒から 黒１６６９白１５１４
３ ９８ ６３ 両方OK黒から 黒１６３４白１６２９
３は黒でこのまま続けるが、実際はここは白が正解
４ ８３ １００ 白のみ 黒６５白２
５ ８２ １００ 黒のみ 黒１２０白１６４
６ ７９ １００ 黒のみ 黒１６４白２
７ ７８ １００ 白のみ 黒６９白０
８ ７７ １００ 白のみ 黒４７白１
９ ７６ １００ 白のみ 黒４１白１
１０ ７５ １００ 白のみ 黒１２２０白０
１１ ７４ １００ 白のみ 黒３３白０
Noはこの後１１から１９まで進むんだけど、No１０で疑問に思わなければ
（プログラム的に）１万ドットのうち黒１２２０ドットも動いているのに
なんで白に決めるんかと。このへんを改良できれば速くなるような気がする
ちょっとゆっくりやってみます
ポインタの＋＋使われるときついわぁｗ
変換じゃなくて元から1次元配列のデータを持たせた方が楽かな。
動かんけどｗ
その中で一次元配列なりなんなり使って実装すればいいんじゃね
本当なら当該言語(今回はJava)に合わせたコードに
書き直せればいいんだけどなぁ……＞ポインタの移植云々
俺？Javaはまだ勉強中で……
ttp://logic777.web.fc2.com/i/paw_mnx140427.zip ファイルの中は、mnoファイルと拡張子が.1と.2のファイル
mnxファイル、そしてmnofix.cとmnoprint.cが入っていると思います
.1と.2はイメージファイルで、.1と.2が存在して.3のファイルが存在しない時
.2を読み込みます。このファイルの実装は解析時間が５７８秒だったとき
578/100+1=6で拡張子が「.6」100秒置きに１００秒目で「.1」、２００秒目で
「.2」、３００秒目で「.3」の拡張子の中断ファイルを作っていた経緯からです。
イメージファイルの書式は、盤面のデータが未確定のとき「_」、
黒は「Q」、白は「x」です。ファイルの中身はその３つと改行とEOFの５つしかありません
mnofix.cはmnoファイルとイメージファイルを読み込んで、
さん用の復元用の数値のファイル.mnxを出力します
mnoファイルで
*Y10
*y001 5
で、イメージファイルが
___QQQQQxx
(未確定が３つ、黒が５つ、白が２つのとき）
mnxファイルでは
*y001 _3,5,x2
というように、数値の前に「_」や「x」が、つきます
例外的に
mnoファイルで
*Y10
*y001 0
のとき、イメージファイルは
xxxxxxxxxx （白が１０こ）になりますが、
mnxファイルでは
*y001 0
となる（？こういう仕様にしたはず、ちょっと自信がない）
いずれにしても、mnxファイルからmnoに、いつでも戻せるように
したかったです
mnoprint.cはmnxを読み込んで、実際に絵が出るかCUIで表示
*yのデータは盤面data[]に
*tのデータは盤面data2[]に
data[]とdata2[]に異常がなければ、未確定は「_」黒は「Q」白は「x」
異常があれば「E」を表示します
なんぞそれｗ
再帰の引数にポインタ＋１しやがって・・・・・・。どうしろとｗ
今更だが自己解決
って2009年かよ！書いたのw
検索すれば出てくるんでリンクはしない…
考え方だけ参考にしてプログラムはJavaで書いてあるものを読んでみたら
例えば
ttp://oku.edu.mie-u.ac.jp/~okumura/java-algo/ の Tetromino.java わろたｗ
／| |
||. 彡⌒ミ|
||. (･ω･`| 誰かいる？
||oと. Ｕ|
|| |（__）Ｊ|
||／彡￣ ｶﾞﾁｬ
彡 ⌒ ミ ♪
(( (･ω･` )
♪ / ⊂ ) )) ♪
((( ヽつ 〈
(＿)^ヽ__）
♪ 彡⌒ ミ
(´･ω･彡⌒ ミ
彡⌒ ミつ(´･ω･`) )) ♪
(( (´･ω･`) ( つ )
( つ ヽ とノ ♪
〉 とノ ）^(＿)
（__ノ⌒(＿)
＿＿_
／| |
|| .彡⌒ ミ
||. ( )|
||oと. |
|| |（__）Ｊ|
||／彡￣ ｶﾞﾁｬ
（実際書きこめなかった）Jimのやつめ・・・
ミラー：
ttp://hello.2ch.net/test/read.cgi/puzzle/1092459010/l50 ここなら書きこめるかテスト
内容は、m246k.cで、biglogic_k140430a.zip と変わりませんが一応
ttps://gist.github.com/nekoppy3 
ttp://i.imgur.com/Wv1Fx2u.jpg 1～16までの数字を一個ずつ入れて
各線上の4つの合計が
いずれも34になるように
１ ２ ３ ４
12 ５
14 15
11 ６
10 ９ ８ ７
16
[1,3,14,16,2,7,9,4,8,13,5,15,6,10,12,11]
au予報言氷雨デモなぜ末端ディレクター戦争指名タイ米粉ステーキ万国ニューヨークブカ牛肉直輸出制限業者議論病院雇用市議しょうゆダシマクッロスさむらいエバコラア山雪光金ガンダム風ミックドラ社員あかうんとパズ豚骨のり野菜炒めラーメン
au予報言氷雨デモなぜ末端ディレクター戦争指名タイ米粉ステーキ万国ニューヨークブカ牛肉直輸出制限業者議論病院雇用市議しょうゆダシマクッロスさむらいエバコラア山雪光金ガンダム風ミックドラ社員あかうんとパズ豚骨のり野菜炒めラーメン
ニンニクヤーフォー低原価スマ金土地酒気帯びNHK公的私的支出トウデン教授嘘芸人横浜名古屋遅延電池切れ福岡損保新規駐車近代ゲームシェア回収フジ政権転職提案たれ巫女ラーメン
abk公式審判漏洩安保険王なにあげてんだよ？「わー！ふーう？」↓↓★★↓↓★↓★▼★宿題通調印鑑カウントダウンたまらんだけ労災募金額休日接待ゴルフ議員国会アイスブルームハンバーグ歌舞伎派大学生
ヒント直接編集機能が付いたよ！！！
ttp://http://katahiromz.web.fc2.com/xword/ ver.2.2にバージョンアップしたよ！！！
ttp://http://katahiromz.web.fc2.com/xword/ ver.2.4にバージョンアップしたよ！！！
漢字・英語クロスワードも作れるよ！！！
ttp://http://katahiromz.web.fc2.com/xword/ ／| |
|| .彡⌒ ミ
||. ( )|
||oと. |
|| |（__）Ｊ|
||／彡￣ ｶﾞﾁｬ
ＪＡＶＡアプレット・フラッシュ・html5・・・・
色々選択肢があるのだろうが、無難なのはどれなんだろう。
迷路作成アルゴリズムで迷路の直線長さを制限するとよいように思うがうまくゆかない。
逆走した軽乗用車が大型トラックと衝突。
計３人が死傷した。
認知症の過程は放射能汚染によって加速します。
注意欠陥障害（ADD）多動性障害（ADHD）、
若年性アルツハイマー病の原因となっており、
人々は肺炎やインフルエンザ、慢性疲労、癌、
ＨＩＶ/エイズなどに抵抗できなくなっています。
免疫システムの崩壊の結果がアレルギーです。
死者の数は、他のいかなる原因よりも多いです。
河川の汚染は犯罪と見られなければなりません。
問題は、日本政府が何も認めないことです。
多くの人々が放射能の影響で死んでいるのに、
彼らは幻想の中に生きています。
日本の近海の食料は安全ではありません。
健康上のリスクは福島に近づくほど高まります。
福島の子供達は癌をもたらす被爆をしています。
福島県民は廃炉後1、２年で戻れるでしょう。
マイト レーヤは原発の閉鎖を助言されます。
マイト レーヤによれば、飛行機など
原子のパターンが妨害されると墜落します。
彼はいかなる人間よりも危険をよくご存じです。
マイト レーヤの唇からますます厳しい
警告と重みが発せられることを覚悟しなさい。
