パズルの問題をプログラムで解いたり
プログラムで面を作成したりする方法を話し合うスレ。
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++++++++
+++++++++++++++
