パズルは面白い

パズルが好きで毎日やっているわけですが、自分の軌跡を残しておきたいと、ふと思いました。

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
  1. --/--/--(--) --:--:--|
  2. スポンサー広告

分断寸前

盤面のいくつかのマスを黒く塗り、
黒マス同士は辺で接しない、
黒マスによって盤面が分断されない(白マスは一繋がりになる)

という条件は、いろいろなパズルに出てきます。
クロスワードパズルも大抵はこの条件になっています。

この条件で、黒マスを最大何個配置できるか、について10年以上前にコンピュータで調べたことがあります。これを高速に調べるうまいアルゴリズムを思いついて、13x13までの正方格子について最大数を求めてあります。
ろくに調べていませんが、ほかに取り組んだ人はいないんじゃないかないか、と思っています。

結構面白いパズルだと思うのでここで紹介しておきます。
へやわけ、の問題にもできるかな?

問題1.7x7の盤面に黒マスを17個(全1解)
問題2.11x11の盤面に黒マスを41個(回転鏡像を同一解として、全3解)
問題3.13x13の盤面に黒マスを57個(回転鏡像を同一解として、全8解)

ちなみに、問題3は自分でも全解はわかっていません。
(当時作ったプログラムが、最大個数と、全部で何通りの配置があるかだけを求めるものだったので、具体的な盤面は知らないのです。)
ここ数日久しぶりに手で取り組んでみたけど、やはり問題3は全部はわかっていません。

これ以上の黒マスは配置できない時の最小個数、を求めるのも面白そうだけど、取っ掛かりが無くて調べていません。こっちのほうも奥は深そうです。
スポンサーサイト
  1. 2008/03/12(水) 01:51:12|
  2. パズル
  3. | トラックバック:0
  4. | コメント:10

コメント

7x7はわかりました。
11x11も同様の方法で1つ見つけました。
それ以外はまだです。
極限は1/3のようですが、いかがでしょうか。

最後の問題は、黒ますと影響範囲をあわせると十字型(ペントミノのX)になることを利用して、
Xで領域を覆う問題(重なりと出っ張りを許す)にしてはいかがでしょうか。
深く考えてはいませんが。
  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. [ 編集]

はじめまして タロタロ様
確か昔のCマガ電脳クラブの問題にもあったような?
 白マスが分断されているかを判定するアルゴリズム
はどのようなものになりましたか?
参考までにご教授下されば幸いです。
  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行の中の白領域が互いに繋がっているかいないか、領域ごとにラベルをつけて区別します。例えば、
□□□■□という行には、111■1と、111■2の2通りがあります。
□■□■□という行には、1■1■1、1■1■2、1■2■2、1■2■1、1■2■3の5通りがあります。(同じ数字は既に繋がっていることを表します。)
こうやって、白の繋がり具合(ラベルを振った行)まで考えると、
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. [ 編集]

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


  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/3までだったら成し遂げることができるみたいな感じになるのでしょうか。超々難問推理パズル(芦ヶ原著)をやっていますが電脳クラブのネタになっていたんだなぁと驚きです。うっかりソロモンをコンピュータに解かせたいと思っています。
  1. 2011/11/26(土) 12:39:30 |
  2. URL |
  3. パズルは難しい #-
  4. [ 編集]

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://puzzleelzzup.blog33.fc2.com/tb.php/328-2887ea6c
この記事にトラックバックする(FC2ブログユーザー)

FC2Ad

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。