パズルプログラミング勉強会

第４課題：四角に切れ

by パソコン初心者

とりあえず、第４課題は、勝手に「四角に切れ」にすることにした。 とにかく決めないと、プログラミングが楽しめないではないか。

■問題データ： shikaku-samplevol.data 　 (遊びたい人は、問題集(サンプル)) へどうぞ

これは、私のページで公開している「四角に切れ」の例題の全データである。 もっと増やす予定だったのだが、いつのまにか止まってしまった。全ては仕事のせいである。
目標は、これを読み込みながら、ホイホイ解けることでしょうかね。(ちょっとレベルが低いかな) とにかく、パズルプログラムの検証用に使う分にはいくらでも利用してくだされ。

■解答データ：

問題集(サンプル) の中のデータ(???.data)には、一応役に立ちそうもない形式ですが、 解答も含まれています。 もしかして正解と思われる解答データです。保証はしませ〜ん。 好きに使ってください。

■プログラムソース：

Shikaku.C  Shikaku.h  (2001年12月作、2003年7月12日公開)

あまりにも長い間熟成させていたので、内容についてはさっぱり覚えていない。 解説にあるとおり、とんでもない手抜きのままなので、低速である。

■解説：

とりあえず、何かいい加減なプログラムでもと思って、月曜日(12/3)から作り始めた。 今日で、既に３日目になる。でも、何とかちゃんと動くレベルになったようだ。 まだ、出力とか綺麗に整形はしていない。

これだけの期間で作ったので、めちゃくちゃ手抜きである。調べていることといったら 極めて簡単である。数字を含む長方形の区域のことを、 以下では領域(プログラムではArea)と呼ぶ。

1. ある領域に対する可能な長方形の共通部分は必ずその領域に属す。
2. あるマスが所属する領域が１つだけならば、そのマスはその領域に属す。

これだけのプログラムを書き、あとは仮定をしながら再帰的に求めている。 あるマスが決まれば、その周辺を次に調べると高速になるのであるが、 初心者なのでそんな面倒なことはしていない。

$ Shikaku 015.data [return]
# 015.data
 .  .  4  .  .  .  5  .  .  .  .  .  .  6  .  .  .  3  .  . 
 3  4  .  .  .  2  .  .  .  3  4  .  .  .  4  .  .  .  3  2 
 .  .  .  .  6  .  .  .  4  .  .  3  .  .  .  3  .  .  .  . 
 .  .  3  3  .  .  .  3  .  .  .  .  4  .  .  .  4  3  .  . 
 3  2  .  .  .  .  5  .  .  4  3  .  .  3  .  .  .  .  2  3 
 .  .  .  .  4  2  .  .  2  .  .  3  .  .  4  4  .  .  .  . 
 .  .  3  4  .  .  .  2  .  .  .  .  4  .  .  .  2  3  .  . 
 3  3  .  .  .  2  2  .  .  4  3  .  .  3  3  .  .  .  3  2 
 .  .  2  4  .  .  .  3  .  .  .  .  4  .  .  .  2  4  .  . 
 .  .  .  .  2  2  .  .  3  .  .  3  .  .  3  2  .  .  .  . 
 2  3  .  .  .  .  4  .  .  3  2  .  .  2  .  .  .  .  3  4 
 .  .  3  3  .  .  .  4  .  .  .  .  6  .  .  .  3  4  .  . 
 .  .  .  .  3  .  .  .  3  .  .  3  .  .  .  3  .  .  .  . 
 3  4  .  .  .  4  .  .  .  3  2  .  .  .  2  .  .  .  2  2 
 .  .  4  .  .  .  5  .  .  .  .  .  .  4  .  .  .  4  .  . 


Answer 1
  4  5  0  0  0  0  1  1  1  1  1  2  2  2  2  2  2  3  3  3
  4  5 12 12 12  6 24  7  7  7  8  8  8  8  9  9  9  9 10 11
  4  5 12 12 12  6 24 13 13 13 13 14 14 14 34 15 15 15 10 11
 22  5 16 17 17 17 24 18 25 25 19 19 19 19 34 20 20 21 10 29
 22 23 16 30 30 31 24 18 25 25 26 26 26 27 34 20 20 21 28 29
 22 23 16 30 30 31 24 18 32 32 33 33 33 27 34 35 40 21 28 29
 36 36 36 37 37 37 37 38 38 39 39 39 39 27 49 35 40 41 41 41
 42 43 43 43 44 44 45 45 46 46 47 48 48 48 49 35 50 50 50 51
 42 52 52 53 53 53 53 54 46 46 47 61 55 55 49 35 56 57 57 51
 42 65 72 58 58 59 59 54 60 67 47 61 55 55 62 63 56 57 57 71
 64 65 72 66 66 66 66 54 60 67 68 61 69 69 62 63 70 70 70 71
 64 65 72 73 73 73 74 74 60 67 68 80 75 75 62 81 76 77 77 71
 82 83 83 78 78 78 74 74 79 79 79 80 75 75 87 81 76 77 77 71
 82 83 83 84 84 84 84 85 85 85 86 80 75 75 87 81 76 88 88 89
 82 90 90 90 90 91 91 91 91 91 86 92 92 92 92 93 93 93 93 89

$

とりあえず、例題の32問を解いて、約4秒(Kondara, g++, Celeron 700MHz)もかかる。 とくに、015.data が、何と３秒かかっているのである。一応、私が昔適当につけた レベルでも★が一番たくさん(一応、レベル８)ついている。

しかし、色々調べたら、これとて仮定は１レベルだけで解けてしまうようだった。 それなのに３秒もかかるということは、よほどプログラムが馬鹿ということだろう。

詳しいことは、日曜日の勉強会(2001/12/9)の時にでも。