パズルは面白い

７ｘ７はわかりました。
１１ｘ１１も同様の方法で１つ見つけました。
それ以外はまだです。
極限は１／３のようですが、いかがでしょうか。

最後の問題は、黒ますと影響範囲をあわせると十字型（ペントミノのＸ）になることを利用して、
Ｘで領域を覆う問題(重なりと出っ張りを許す）にしてはいかがでしょうか。
深く考えてはいませんが。

1. 2008/03/18(火) 20:24:21 |
2. URL |
3. 数楽者 #1Qqcdk6s
4. [ 編集]

極限は1/3：さすが、するどいです。数楽者さん。
説明はできませんが、確かに1/3っぽいのです。
昔調べた最大個数と盤面数（鏡像・回転を別々として数えたもの）
N　最大個数　盤面数
2 1 4
3 4 1
4 5 36
5 9 1
6 12 104
7 17 1
8 21 8896
9 27 1952
10 33 168960
11 41 17
12 48 204768
13 57 64
で、N*N-3*最大個数は、N=2,3,4…に対して、
1,-3,1,-2,0,-2,1,0,1,-2,0,-2
となっています。周期性がありそうでずっとモヤモヤしてます。
パソコンが非力な時代に調べたものなので、今ならもう少し先まで求められるはずですね。

1. 2008/03/21(金) 02:03:46 |
2. URL |
3. タロタロ #-
4. [ 編集]

はじめまして　タロタロ様
確か昔のＣマガ電脳クラブの問題にもあったような？
　白マスが分断されているかを判定するアルゴリズム
はどのようなものになりましたか？
参考までにご教授下されば幸いです。

1. 2008/03/22(土) 02:52:17 |
2. URL |
3. パズルは難しい #-
4. [ 編集]

初めまして、パズルは難しいさん。
分断寸前、というタイトルでCマガ電脳クラブで出題されたのをご存知ですか！
うれしいです。実はあれは私が出題しました。
当時、照れくさくて適当なペンネームを使っていました。今ならタロタロで出題したと思いますが（＾＾；

私のアルゴリズムは、説明するのは難しいですけどやってみましょう。5x5を例にとりますね。
基本的に、1行の白黒のパターンを全部用意しておいて、行毎に順に置いていくものです。
黒によって1行の中でも白がいくつかの領域に分かれることになりますが、1行の中の白領域の数で分類すると、
1行の白黒の置き方は、
　白領域が1個：4通り（黒0個1通り、黒1個2通り、黒2個1通り）
　白領域が2個：8通り（黒1個3通り、黒2個4通り、黒3個1通り）
　白領域が3個：1通り（黒2個1通り）、の合計13通りあります。
さらに、1行の中の白領域が互いに繋がっているかいないか、領域ごとにラベルをつけて区別します。例えば、
□□□■□という行には、１１１■１と、１１１■２の２通りがあります。
□■□■□という行には、１■１■１、１■１■２、１■２■２、１■２■１、１■２■３の５通りがあります。（同じ数字は既に繋がっていることを表します。）
こうやって、白の繋がり具合（ラベルを振った行）まで考えると、
1行の白黒の置き方は、
　白領域が1個：4x1=4通り
　白領域が2個：8x2=16通り
　白領域が3個：1x5=5通り、の合計25通りになります。
この25通りのラベル付き行の下に、13通りのラベル無し行を置くと、
　黒が隣接するので置けないか、
　あるラベルが消滅（分断）するので置けないか、
　置けるか、
のどれかになります。置ける場合は、当然25通りのどれかのラベル付き行になっています。
25x13の結果の表を用意しておくと、表を引くだけで行を置いていけるので単純になります。
あとは、途中の黒の数をカウントしておいて、途中の25通りのラベル付き行毎に黒の最大数と何通りかを覚えておきます。

ざっとこんな感じです。

実は、Cマガで出題したときは、応募プログラムに速いものが無かったので、自分のプログラムを模範解答として紹介しました。

1. 2008/03/22(土) 23:06:59 |
2. URL |
3. タロタロ #-
4. [ 編集]

タロタロ様
詳しい解説ありがとうございました。
出題者（三木さん）とは恐縮です。自分がＣマガを見始めました
のが９７年からでその頃は吉柄さんのみになっていました。
分断寸前の問題を知ったのは高橋さんのページからです。
http://www2.ic-net.or.jp/~takaken/auto/guest/bbs13.html
それ以来、頭の隅にこの問題があっていつか解こうと考えていました。
なるほど１行をあらかじめパーターンを決めて組み合わせて
いくんですね。効率も良さそうで速度もでそうな気がします。
自分が考えていましたのは２５個から隣り合わないように黒の個数分の組み合わせを作成しその各々についてスタート地点を決め一筆書きのように塗りつぶし塗りつぶした個数が２５－黒の個数であれば分断していないと判定し黒の個数を増やし又検索するというものです。
　教えられたアルゴリズムで作成してみたいと思います。

1. 2008/03/23(日) 13:07:56 |
2. URL |
3. パズルは難しい #-
4. [ 編集]

パズルは難しいさん、
当時使っていた開発環境の制約があって、私が求めたのは13x13までです。そこから先は多分まだ誰も求めていないと思われます。どうぞ、チャレンジしてください。先の結果が出たら是非教えてください。

1. 2008/03/24(月) 23:26:03 |
2. URL |
3. タロタロ #-
4. [ 編集]

ごぶさだしています。暇ができたので調べてみました。
盤面 　　　行 　　　行ラベル 最大黒数 パターン数
パターン パターン
---------------------------------------------
14x14 987 50814 65 　273209536
15x15 1597 130632 75 　42462180
盤面を表示する処理を追加しました。ところが10,11,12,13に関してうまくいきません。ソースは以下にアップしました。
http://www.dotup.org/uploda/www.dotup.org2236650.txt.html パスtarotaro

1. 2011/11/08(火) 13:28:28 |
2. URL |
3. パズルは難しい #-
4. [ 編集]

度々すみません。どうやら同一関数で動的確保・開放を繰り返すのは良くないようなので
2回目の呼び出しではblack_num1のアドレスをblack_num0に引き渡すのをやめて
実体をコピーするやり方に変更しました。今度はうまくいくようです。13×13の結果を掲載しました。
http://www1.axfc.net/uploader/Sc/so/291027
パスtarotaro

1. 2011/11/10(木) 18:59:17 |
2. URL |
3. パズルは難しい #-
4. [ 編集]

パズルは難しい、さん。

分断寸前、の解析を進めてくださってありがとうございます。
15x15まで判明しましたか！
やはり1/3仮説は成り立っていますね。う～ん、不思議だ。

また、13x13の盤面に黒マスを57個配置する全8解を見ることができて感激しました。
何度となく手でやってみたけれど8種類全部は見つけられなかったのです。

返信が遅くなって済みませんでした。m(_ _)m

1. 2011/11/26(土) 03:25:26 |
2. URL |
3. タロタロ #-
4. [ 編集]

いえいえ楽しませて頂きました。盤面を見てみるとまず外周を囲って中で調整するといった感じですかね。妄想ですがこの事象を世の中に当てはめてみると困難度（負荷）が散らばっている状況である仕事を完成させるとすると困難度合いが仕事の大きさに対して1/３までだったら成し遂げることができるみたいな感じになるのでしょうか。超々難問推理パズル（芦ヶ原著）をやっていますが電脳クラブのネタになっていたんだなぁと驚きです。うっかりソロモンをコンピュータに解かせたいと思っています。

1. 2011/11/26(土) 12:39:30 |
2. URL |
3. パズルは難しい #-
4. [ 編集]